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

Question

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

当找到N个字符的单词时,在我的字典数据库中建议更正的单词是:

N个字符的每个字典单词,与找到的单词有1个字符差异.示例:找到单词:bearn,dictionary word:bears

N + 1个字符的每个字典单词,其N个字符等于找到的单词.示例:找到的单词:bear,dictionary word:bears

N-1个字符的每个字典单词,其N-1个字符等于找到的单词.示例:找到单词:bears,dictionary word: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];
}

Answer 1

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

我读过它已经有一段时间,但我记得它与你的写作非常相似.