3

我正在使用 levenshtein 算法来满足这些要求：

当找到一个包含 N 个字符的单词时，在我的字典数据库中建议作为更正的单词是：

与找到的单词有1个字符差异的每个N个字符的字典单词。示例：找到的单词：bearn，字典单词：bears

每个 N+1 个字符的字典单词，其中 N 个字符等于找到的单词。示例：找到的单词：bear，字典单词：bears

每个包含 N-1 个字符的字典单词，其中 N-1 个字符等于找到的单词。示例：找到的词：熊，字典词：熊

我在 C++ 中使用这个 Levenshtein 算法的实现来查找单词的 Levenshtein 编号何时为 1（这是所有三种情况的 Levenshtein 编号），但是我该如何选择要建议的单词呢？我读过有关 Boyer-Moore-Horspool 和 Knuth-Morris-Pratt 的文章，但我不确定它们中的任何一个有什么帮助。

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int levenshtein(const string &s1, const string &s2)
{
   string::size_type N1 = s1.length();
   string::size_type N2 = s2.length();
   string::size_type i, j;
   vector<int> T(N2+1);

   for ( i = 0; i <= N2; i++ )
      T[i] = i;

   for ( i = 0; i < N1; i++ ) {
      T[0] = i+1;
      int corner = i;
      for ( j = 0; j < N2; j++ ) {
         int upper = T[j+1];
         if ( s1[i] == s2[j] )
            T[j+1] = corner;
         else
            T[j+1] = min(T[j], min(upper, corner)) + 1;
         corner = upper;
      }
   }
   return T[N2];
}
4

4 回答 4

6

您可能还想将Norvig 关于拼写更正的优秀文章添加到您的阅读中。

我已经有一段时间没有阅读它了，但我记得它与您所写的非常相似。

于 2009-01-27T19:30:21.647 回答
2

正如我在其他地方所说，Boyer-Moore 并不真正适合这个。既然你想同时搜索多个stings，那么Wu和Manber的算法应该更符合你的喜好。

我已经发布了一个概念证明 C++ 代码来回答另一个问题。注意那里提到的警告。

于 2009-01-27T20:00:03.787 回答
0

为什么将建议限制在一个单词，为什么不包括一组单词？如果您仅限于一个单词，您可以通过一些预先计算的使用频率或其他东西对结果进行排序。该频率可以根据用户从建议中选择的内容进行更新。

此外，在原始单词中没有拼写错误的情况下，您可能希望优先处理 N+1 个案例，这更像是自动完成。无论如何，我认为没有一种正确的方法可以做到这一点，也许如果您的要求更具体，缩小范围会更容易。

此外，您无需了解 Python 即可理解 Norvig 文章中描述的算法。

于 2009-01-27T19:58:03.713 回答
0

如果我对您的理解正确，那么您的问题没有正确答案。您正在使用 Levenshtein 为给定单词识别多达三个建议 - 由您提出一个规则来决定使用哪个以及过滤掉哪些。或者也许你应该全部使用它们？

有趣的是，您可能会对 Levenshtein 的 Damerau 扩展感兴趣，其中两个交换的字符也被认为给出 1 分，而不是 2，这是原版 Levenshtein 所返回的。

于 2009-01-27T20:11:45.027 回答