Levenshtein算法：如何满足文本编辑要求？

Question

我正在使用Levenshtein算法来满足以下要求：

当查找一个N个字符的单词时，我的字典数据库中建议的更正单词是：

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

与找到的单词的N个字符相等且长度为N+1的每个字典单词。 例如： 找到的单词：bear，字典单词：bears

与找到的单词的N-1个字符相等且长度为N-1的每个字典单词。 例如： 找到的单词：bears，字典单词：bear

我正在使用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];
}

- Melkhiah66

Answer 1

您可能还想阅读Norvig关于拼写纠正的优秀文章。

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

- Triptych

---

这篇文章可能是关于Python的，但并不是关于Python的。 - blank

即使您不了解Python代码，您也可能能够理解本文。我在那段代码中唯一看到的不明显的东西是“列表推导式”，您可以通过谷歌搜索来了解它。 - Kenan Banks

Answer 2

正如我在其他地方所说的，Boyer-Moore算法并不适合这种情况。由于您想同时搜索多个字符串，因此Wu和Manber算法应更符合您的口味。

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

- Konrad Rudolph

Answer 3

为什么要限制建议只有一个单词，而不是一组单词？如果只能使用一个单词，可以通过某些预先计算的使用频率或其他方式对结果进行排序。这个频率可以根据用户从建议中选择的内容进行更新。

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

此外，您不需要了解Python就可以理解Norvig文章中描述的算法。

- codelogic

Answer 4

如果我理解正确的话，那么你的问题没有正确答案。使用Levenshtein识别给定单词的最多三个建议 - 由你决定采用哪一个规则来决定使用哪个建议和过滤掉哪些建议。或者也许你应该全部使用？

仅作为一个趣味问题，Damerau扩展到Levenshtein可能会对你有兴趣，其中两个交换字符也被认为得分1，而不是vanilla Levenshtein返回的2。

- Epidemus