想要的算法:查找字典中与自由文本中的单词类似的所有单词

Question

我们有一个大约150,000个单词的列表,当用户输入自由文本时,系统应该显示字典中的单词列表,这些单词与自由文本中的单词非常接近.

例如,用户输入:"我想在沃尔玛购买legoe玩具".如果字典包含"乐高","汽车"和"沃尔玛",系统应在列表中显示"乐高"和"沃尔玛"."沃尔玛"是显而易见的,因为它与句子中的单词相同,但"乐高"与"乐高"相似,也被提及.但是,没有什么与"Car"相似,所以没有显示单词.

显示列表应该是实时的,这意味着当用户输入句子时,屏幕上必须出现单词列表.有人知道一个很好的算法吗？

字典实际上包含可能包含空格的概念.例如,"乐高太空飞船".完美的解决方案也能识别这些多字概念.

任何建议表示赞赏.

Answer 1

请查看http://norvig.com/spell-correct.html以获取一个简单的算法.本文使用Python,但最后还有其他语言实现的链接.

Answer 2

您将针对固定字典进行相当多的单词查找.因此,您需要准备字典.从逻辑上讲,您可以快速消除"太不同"的候选人.

例如,单词car和dissimilar可能共享一个后缀,但它们显然不是彼此的拼写错误.现在为什么对我们人类如此明显？对于初学者来说,长度完全不同.这是一次立即取消资格(但有一个例外 - 下面).因此,您的字典应按字长排序.将输入单词与类似长度的单词匹配.对于简短的单词,这意味着+/- 1个字符; 更长的单词应该有更高的余量(你的人口统计拼写的确切程度如何？)

一旦你将自己局限于相似长度的候选词,你就会想要删除完全不同的词.有了这个,我的意思是他们使用完全不同的字母.如果按字母顺序对单词中的字母进行排序,这是最容易比较的.例如car变成"acr"; rack成为"ackr".您将在预处理字典和每个输入字时执行此操作.原因是确定两个有序集的差异(大小)很便宜.(如果需要解释,请添加评论).car并rack具有尺寸1的差异,car并hat有大小2的差异这缩小了你的候选集更进一步.请注意,对于较长的单词,当您发现太多差异时,可以提前纾困.例如dissimilar,biography总差异为13,但考虑到长度(8/9),一旦找到5个差异,你可能会纾困.

这将为您留下一组使用几乎相同字母的候选词,并且长度几乎相同.此时,您可以开始使用更精确的算法; 你不需要再为每个输入单词运行150,000次比较.

现在,对于前面提到的长度异常:问题在于"单词"之类的greencar.它与长度为8的单词并不完全匹配,但对于人类而言,它的意义非常明显.在这种情况下,你不能真正打破任何随机边界的输入词,并对两半运行额外的N-1不精确匹配.但是,检查缺少的空间是可行的.只需查找所有可能的前缀即可.这是有效的,因为你将要使用的字典的相同部分遍地,例如g gr,gre,gree等对于每一个你发现前缀,检查剩余suffixis也在dictionery,例如reencar,eencar.如果输入单词的两半都在字典中,但单词本身不是,则可以假设缺少空格.

Answer 3

您可能想要使用计算Levenshtein距离的算法.

但是,由于您的数据集非常大,并且您将比较大量的单词,因此直接实现执行此操作的典型算法将不切实际.

为了在合理的时间内找到单词,您必须以某种方式索引您的单词集,以便于模糊字符串匹配.

其中一种索引方法是使用后缀树.另一种方法是使用n-gram.

我倾向于使用后缀树,因为我发现它更容易缠绕它并且我发现它更适合这个问题.