比较字的算法（不按字母顺序）

Question

我需要为特定需求编写一个解决方案，并且我想知道是否有人熟悉可以实现它的现成库，或者可以指导我最佳做法。描述：

用户输入应该是几个固定选项之一（我拥有列表中的选项）的单词。我知道输入必须在列表中的成员中，但由于是用户输入，他/她可能犯了错误。我正在寻找一种能够告诉我用户意思最可能的单词的算法。我没有任何上下文，我不能强迫用户从列表中选择（即他必须能够自由地和手动地输入单词）。例如，假设列表中包含“水”，“季度”，“啤酒”，“甜菜”，“地狱”，“你好”以及“土豚”等词组。

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

• 速度错别字（例如加倍字符，滴字符等）
• 键盘相邻字符的拼写错误（例如，“qater”为“水“）
• 母语非英语的拼写错误（如 “四” 为‘季度’）
• 等等...

显而易见的解决方案是逐字比较，并给每个不同的字母，额外的字母和丢失的字母赋予“惩罚权重”。但是这个解决方案忽略了数千个我确定列在某处的“标准”错误。我确信有那些处理所有案例的启发式方法，无论是特定的还是一般的，都可能使用标准不匹配的大型数据库（我愿意接受数据量大的解决方案）。

我在Python中编码，但我认为这个问题是语言不可知的。

任何建议/想法？

Answer 1

你想读谷歌如何做的：http://norvig.com/spell-correct.html

编辑：有人指出，定义一个用户给定词和候选词（莱文斯坦，同音）之间的度量算法。然而，这不是一个完整的解决方案，因为人们还需要一个数据结构来高效地执行非欧几里得最近邻搜索。这可以通过例如与覆盖树：http://hunch.net/~jl/projects/cover_tree/cover_tree.html

Answer 2

你有没有考虑通过拼音比较算法，如soundex？生成单词列表的soundex表示，存储它们，然后获取用户输入的soundex并找到最接近的匹配不应太难。

Answer 3

一个常见的解决方案是计算输入和固定文本之间的Levenshtein distance。两个字符串的Levenshtein距离只是简单操作的数量 - 插入，删除和单个字符的替换 - 将字符串中的一个转换为另一个字符所需的操作数。

Answer 4

虽然它可能无法解决整个问题，但您可能需要考虑使用soundex算法作为解决方案的一部分。对“soundex”和“python”的快速搜索显示了该算法的一些python实现。

Answer 5

尝试搜索“Levenshtein距离”或“编辑距离”。它计算您需要将一个单词转换为另一个单词的编辑操作的数量（删除，插入，更改字母）。这是一种常见算法，但根据问题的不同，您可能需要针对不同类型的拼写错误使用不同的权重。

Answer 6

寻找Bitap算法。它很适合你想要做的事情，甚至在维基百科中有一个源代码示例。

Answer 7

如果您的数据集非常小，只需比较所有项目上的Levenshtein距离就足够了。但是，如果它更大，则需要使用BK-Tree或类似的索引系统。我链接的文章描述了如何在给定的Levenshtein距离内找到匹配，但适应做最近邻居搜索是相当直接的（并且作为练习读者;）。