简单的拼写检查算法

Question

我的任务是为一个作业创建一个简单的拼写检查器,但是旁边没有任何指导,所以想知道是否有人可以帮助我.我不是在跟别人为我做任务,但算法的任何方向或帮助都会很棒!如果我要求的不在网站的guildlines内,那么我很抱歉,我会在其他地方看看.:)

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

• 一个字母的差异(加上或减去以使单词与字典中的单词相同).例如,'stack'将是'staick'的建议,'cool'将是'coo'的建议.

• 一个字母替换.因此,例如,'坏'将是'bod'的建议.

所以,只是为了确保我已经正确解释了......我可能会加载[你好,再见,太棒了,好,上帝]的话,然后对(错误拼写的)'godd'这个词的建议就是[好,上帝] ].

速度是我在这里的主要考虑因素,所以当我认为我知道一种方法来完成这项工作时,我真的不太确定它的效率.我正在考虑这样做的方法是创建一个map<string, vector<string>>然后为每个正确拼写的单词加载,将正确拼写的作品添加为地图中的键,并将向量填充为所有可能的"错误"排列那个词.

然后,当我想查找一个单词时,我会查看地图中的每个向量,看看该单词是否是正确拼写单词之一的排列.如果是,我将添加密钥作为拼写建议.

这似乎会占用内存的HEAPS,因为每个单词肯定会有成千上万的排列？如果我的正确拼写单词的初始字典很大,它似乎也会非常慢？

我在想,也许我可以通过查看与我正在看的单词类似的键来缩短时间.但话说回来,如果它们在某种程度上相似,那么它可能意味着关键将是一个建议意味着我不需要所有这些排列!

所以,是的,我有点难过我应该看哪个方向.我真的很感激任何帮助,因为我真的不知道如何估计不同做事方式的速度(我们还没有教过这个在课堂上).

Answer 1

解决问题的简单方法确实是预先计算好的地图[坏词] - > [建议].

问题在于,虽然删除一个字母会产生很少的"坏词",但对于添加或替换,你有很多候选人.

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

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

解决方案以增量步骤描述​​,通常搜索速度应该在每个想法中不断改进,并且我尝试首先使用更简单的想法(在实现方面)来组织它们.每当您对结果感到满意时,请随时停下来.

0.初步

• 实现Levenshtein距离算法
• 将字典存储在排序的序列中(std::set例如,虽然排序std::deque或std::vector更好的性能)

关键点:

• Levenshtein距离计算使用数组,在每一步中,下一行仅使用前一行计算
• 一行中的最小距离始终优于(或等于)前一行中的最小距离

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

1.第一个暂定

让我们开始吧.

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

它对小词典非常有效.

2.改进数据结构

levenshtein距离至少等于长度的差异.

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

3.前缀和修剪

为了改进这一点,我们可以说,当我们逐行构建距离矩阵时,一个世界被完全扫描(我们寻找的那个)但另一个(指示物)不是:我们每行只使用一个字母.

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

请记住,我要求您存储字典排序？这意味着共享相同前缀的单词是相邻的.

假设您正在检查您的单词cartoon并且car您发现它不起作用(距离已经太长),那么任何开头的单词car也都不起作用,只要它们开始就可以跳过单词car.

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

• 如果前缀很长(几个要跳过的单词),线性效果最佳
• 二进制搜索最适合短前缀(许多单词要跳过)

多长时间取决于你的字典,你必须衡量.我会继续二进制搜索.

注意:长度分区对前缀分区起作用,但它会修剪更多的搜索空间

4.前缀和重复使用

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

假设你有两个词:

• 动画片
• 洗车

您首先逐行计算矩阵cartoon.然后,阅读时carwash,你需要确定共同的前缀(这里的长度car),你可以保持前4行矩阵(相当于作废,c,a,r).

因此,当开始计算时carwash,你实际上开始迭代w.

要做到这一点,只需使用在搜索开始时直接分配的数组,并使其足够大以容纳更大的引用(您应该知道字典中最大的长度).

5.使用"更好"的数据结构

为了更轻松地使用前缀,您可以使用Trie或Patricia Tree来存储字典.然而,它不是STL数据结构,您需要对其进行扩充以在每个子树中存储存储的字长度范围,因此您必须自己实现.它并不像看起来那么容易,因为存在可能会破坏地方的内存爆炸问题.

这是最后的选择.实施成本很高.