比较单词的算法(不按字母顺序)

Question

我需要为特定需求编写解决方案，我想知道是否有人熟悉可以实现它的现成库，或者可以指导我进行最佳实践。说明:

用户输入的单词应该是几个固定选项之一(我将选项保存在列表中)。我知道输入必须在列表中的成员中，但由于是用户输入，他/她可能犯了错误。我正在寻找一种算法来告诉我用户最可能的意思是什么。我没有任何上下文，我不能强制用户从列表中进行选择(即他必须能够自由地手动输入单词)。

例如，假设列表包含单词“water”、“quarter”、“beer”、“beet”、“hell”、“hello”和“aardvark”。

解决方案必须考虑到不同类型的“正常”错误:

• 速度拼写错误(例如，重复字符、省略字符等)
• 键盘相邻字符拼写错误(例如“qater”代表“water”)
• 非母语英语拼写错误(例如，“quarter”是“quarter”)
• 等等...

显而易见的解决方案是逐个字母地进行比较，并对每个不同的字母、多余的字母和缺失的字母给予“惩罚权重”。但是这个解决方案忽略了我确定在某处列出的数千个“标准”错误。我确信有一些启发式方法可以处理所有情况，包括特定的和一般的，可能使用一个包含标准不匹配的大型数据库(我对数据密集型解决方案持开放态度)。

我正在用 Python 编写代码，但我认为这个问题与语言无关。

有什么建议/想法吗？

Answer 1

您想了解 google 如何做到这一点:http://norvig.com/spell-correct.html

编辑:有些人提到了定义用户给定词和候选词之间的度量的算法(levenshtein、soundex)。然而，这并不是问题的完整解决方案，因为还需要一种数据结构来有效地执行非欧几里德最近邻搜索。这可以做到，例如与封面树:http://hunch.net/~jl/projects/cover_tree/cover_tree.html