5

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

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

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

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

  • 速度拼写错误（例如双字符、删除字符等）
  • 键盘相邻字符拼写错误（例如“水”的“qater”）
  • 非母语英语拼写错误（例如，“quater”代表“季度”）
  • 等等...

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

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

有什么建议/想法吗？

4

7 回答 7

10

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

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

于 2009-05-19T16:49:41.367 回答
6

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

于 2009-05-19T16:51:18.820 回答
2

您是否考虑过通过语音进行比较的算法，例如soundex？生成单词列表的 soundex 表示，存储它们，然后获取用户输入的 soundex 并在那里找到最接近的匹配项应该不会太难。

于 2009-05-19T16:49:57.887 回答
1

如果您的数据集真的很小，那么简单地比较所有项目的 Levenshtein 距离就足够了。但是，如果它更大，则需要使用BK-Tree或类似的索引系统。我链接到的文章描述了如何在给定的 Levenshtein 距离内查找匹配项，但适应最近邻搜索相当简单（留给读者作为练习；）。

于 2009-05-20T09:04:27.287 回答
1

寻找Bitap算法。它非常适合您想要做的事情，甚至还附带了维基百科中的源代码示例。

于 2009-05-19T16:56:43.540 回答
0

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

于 2009-05-19T16:54:49.470 回答
0

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

于 2009-05-19T16:55:22.123 回答