解决问题的更简单方法确实是预先计算的地图[坏词] -> [建议]。
问题是，虽然删除一个字母会产生很少的“坏词”，但对于添加或替换你有many候选人。
所以我建议另一种解决方案；）
注意：您所描述的编辑距离称为编辑距离 http://en.wikipedia.org/wiki/Levenshtein_distance
该解决方案以增量步骤进行描述，通常每个想法的搜索速度应该不断提高，我尝试首先用更简单的想法（在实现方面）来组织它们。只要您对结果感到满意，就可以随时停止。
0. 初步
- 实现编辑距离算法
- 将字典存储在排序序列中（
std::set例如，虽然已排序std::deque or std::vector性能会更好）
要点：
- Levenshtein 距离计算使用数组，在每一步中，下一行仅与前一行计算
- 一行中的最小距离始终优于（或等于）前一行中的最小值
后一个属性允许短路实现：如果您想将自己限制为 2 个错误（阈值），那么只要当前行的最小值大于 2，您就可以放弃计算。一个简单的策略是返回阈值 + 1 作为距离。
1. 第一个暂定
让我们从简单开始吧。
我们将实现线性扫描：对于每个单词，我们计算距离（短路），并列出迄今为止实现较小距离的单词。
它在小型词典上效果很好。
2. 完善数据结构
编辑距离为at least等于长度差。
通过使用一对（长度，单词）而不是单词作为键，您可以将搜索限制在长度范围内[length - edit, length + edit]并大大减少搜索空间。
3. 前缀和修剪
为了改进这一点，我们可以指出，当我们逐行构建距离矩阵时，一个世界被完全扫描（我们寻找的单词），但另一个世界（所指对象）却没有：我们每行只使用一个字母。
这个非常重要的属性意味着对于共享相同初始序列（前缀）的两个指示对象，矩阵的第一行将是相同的。
还记得我要求你存储排序后的字典吗？这意味着共享相同前缀的单词是相邻的。
假设你正在检查你的话cartoon and at car你意识到它不起作用（距离已经太长），那么任何以car也不起作用，你可以跳过以以下开头的单词car.
跳过本身可以线性完成，也可以通过搜索完成（找到第一个具有比car):
- 如果前缀很长（要跳过的单词很少），则线性效果最好
- 二分搜索最适合短前缀（要跳过许多单词）
“长”有多长取决于你的字典，你必须测量。我会从二分搜索开始。
注意：长度分区与前缀分区相反，但它会修剪更多的搜索空间
4. 前缀和重用
现在，我们还将尝试尽可能地重复使用计算（而不仅仅是“它不起作用”的结果）
假设你有两个单词：
您首先逐行计算矩阵，cartoon。然后读书的时候carwash您需要确定公共前缀的长度（此处car）并且您可以保留矩阵的前 4 行（对应于 void，c, a, r).
因此，当开始计算时carwash，您实际上开始迭代w.
为此，只需使用在搜索开始时直接分配的数组，并使其足够大以容纳更大的引用（您应该知道字典中的最大长度是多少）。
5.使用“更好”的数据结构
为了更轻松地使用前缀，您可以使用Trie http://en.wikipedia.org/wiki/Trie或帕特里夏树来存储字典。然而，它不是 STL 数据结构，您需要对其进行扩充，以在每个子树中存储所存储的单词长度范围，因此您必须自己实现。这并不像看起来那么容易，因为存在内存爆炸问题，可能会杀死局部性。
这是最后的选择。实施起来成本很高。
