c++ - 简单的拼写检查算法

Question

我的任务是为作业创建一个简单的拼写检查器，但几乎没有给出任何指导，所以想知道是否有人可以帮助我。我不是在找人为我做作业，但任何关于算法的方向或帮助都会很棒!如果我要问的不在网站的公会范围内，那么我很抱歉，我会去别处看看。 :)

该项目加载正确拼写的小写单词，然后需要根据两个标准提出拼写建议:

一个字母差异(添加或减去以使单词与字典中的单词相同)。例如，'stack' 是对 'staick' 的建议，而 'cool' 是对 'coo' 的建议。

一个字母替换。例如，'bad' 将是对 'bod' 的建议。

所以，只是为了确保我已经正确解释了......我可能会加载[你好，再见，梦幻般的，好，上帝]，然后对(拼写错误)单词'godd'的建议将是[好，上帝]。

速度是我在这里的主要考虑因素，所以虽然我认为我知道一种方法来完成这项工作，但我真的不太确定它的效率如何。我想这样做的方式是创建一个 map<string, vector<string>>然后对于加载的每个拼写正确的单词，将拼写正确的作品添加为 map 中的键，并将 vector 填充为该单词的所有可能的“错误”排列。

然后，当我想查找一个单词时，我会查看 map 中的每个 vector ，看看该单词是否是拼写正确的单词之一的排列。如果是，我将添加该键作为拼写建议。

这似乎会占用大量内存，因为每个单词肯定会有数千个排列？如果我最初的正确拼写单词字典很大，它似乎也会非常非常慢？

我在想，也许我可以通过只查看与我正在查看的单词相似的键来减少时间。但话又说回来，如果它们在某些方面相似，那么这可能意味着关键将是一个建议，这意味着我不需要所有这些排列!

所以，是的，我对我应该朝哪个方向看有些困惑。我真的很感激任何帮助，因为我真的不知道如何估计不同做事方式的速度(我们还没有被教过这个在类里面)。

Answer 1

解决问题的更简单的方法确实是预先计算的映射[坏词] -> [建议]。

问题是，虽然删除一个字母会产生很少的“坏词”，但对于添加或替换，您有很多候选词。

所以我建议另一种解决方案;)

注意:您所描述的编辑距离称为 Levenshtein Distance

解决方案是以增量步骤描述​​的，通常搜索速度应该在每个想法上不断提高，我试图首先用更简单的想法(在实现方面)来组织它们。当您对结果感到满意时，请随时停止。

0. 初赛

实现 Levenshtein 距离算法

将字典存储在排序的序列中(例如 std::set，尽管排序的 std::deque 或 std::vector 会在性能方面更好)

要点:

Levenshtein 距离计算使用一个数组，在每一步中，下一行仅与前一行一起计算

一行中的最小距离始终优于(或等于)前一行中的最小值

后一个属性允许短路实现:如果您想将自己限制为 2 个错误(阈值)，那么只要当前行的最小值大于 2，您就可以放弃计算。一个简单的策略是返回阈值 + 1 作为距离。

1.第一个暂定

让我们从简单的开始。

我们将实现线性扫描:对于每个单词，我们计算距离(短路)，并列出到目前为止实现较小距离的那些单词。

它在小型词典上效果很好。

2. 改进数据结构

编辑距离至少等于长度差。

通过使用夫妇 (length, word) 而不仅仅是单词作为关键字，您可以将搜索限制在长度范围 [length - edit, length + edit]并大大减少搜索空间。

3. 前缀和修剪

为了改进这一点，我们可以注意到，当我们逐行构建距离矩阵时，一个世界(我们寻找的词)被完全扫描，而另一个(所指对象)不是:我们只对每一行使用一个字母.

这个非常重要的属性意味着对于共享相同初始序列(前缀)的两个所指对象，则矩阵的第一行将是相同的。

还记得我要求您存储已排序的字典吗？这意味着共享相同前缀的单词是相邻的。

假设您正在对照 cartoon 核对您的话。并在 car你意识到它不起作用(距离已经太长了)，那么任何以 car 开头的词也不行，你可以跳过单词，只要它们以 car 开头.

跳过本身可以线性完成，也可以通过搜索完成(找到前缀高于 car 的第一个单词):

如果前缀很长，线性效果最好(跳过几个词)

二分搜索最适合短前缀(要跳过许多单词)

“长”有多长取决于你的字典，你必须测量。我会从二进制搜索开始。

注意:长度分区与前缀分区相反，但它修剪了更多的搜索空间

4. 前缀和重用

现在，我们还将尝试尽可能多地重用计算(而不仅仅是“它不起作用”的结果)

假设你有两个词:

卡通

洗车

您首先逐行计算 cartoon 的矩阵.然后在阅读时carwash您需要确定公共(public)前缀的长度(此处为 car )，并且可以保留矩阵的前 4 行(对应于 void、 c 、 a 、 r )。

因此，当开始计算时carwash ，您实际上从 w 开始迭代.

为此，只需使用在搜索开始时直接分配的数组，并使其足够大以容纳更大的引用(您应该知道字典中的最大长度是多少)。

5. 使用“更好”的数据结构

为了更轻松地使用前缀，您可以使用 Trie或 Patricia Tree 来存储字典。但是，它不是 STL 数据结构，您需要对其进行扩充以在每个子树中存储存储的单词长度范围，因此您必须进行自己的实现。这并不像看起来那么容易，因为内存爆炸问题可以杀死局部性。

这是最后的选择。实现成本很高。