Levenshtein算法：我如何认识这个文本编辑要求？

Question

我使用Levenshtein算法来满足这些要求：

当找到的N个字符的单词，单词建议如在我的字典数据库校正是：

的具有与所找到的字差的1个字符的N个字符的每个字典字。 例： 发现字：贝亚恩，字典字：熊

的N + 1个字符的每个字典字具有N个字符等于所找到的字。 例： 发现字：熊，字典字：熊

的N-1个字符的每个字典字具有N-1个字符等于所找到的字。 例： 发现字：熊，字典字：熊

我用这个实现Levenshtein算法C ++中找到当一个字有1莱文斯坦数量（这是所有三种情况下，莱文斯坦号），但后来我该如何选择的话建议？我读到博耶 - 穆尔 - Horspool和克努特莫里斯普拉特，但我不知道如何要么他们会有所帮助。

#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

您可能还需要添加弱势族群的拼写校正优秀文章您阅读。

这已经有一段时间，因为我读过，但我记得它非常类似于你什么写作。

Answer 2

正如我在别处说，博耶 - 摩尔是不是这真的贴切。既然你要搜索的多刺simultanously，吴和曼伯的算法应该是根据自己的喜好。

我已经张贴的概念C ++中的回答代码证明另一个问题。听从警告有提及。

Answer 3

为什么限制的建议，一个字，为什么不包括一组字？如果仅限于单个单词，你可以使用什么的一些预先计算的频率排序结果。该频率可以基于什么用户建议选择进行更新。

此外，在那里是不是在原来的单词拼写错误的情况下，你可能希望将N + 1的情况下，这将是更喜欢自动完成的优先次序。无论如何，我不认为有这样做，也许如果你的要求更加具体，它会更容易缩小一个正确的方式。

此外，你不需要知道Python来了解弱势族群的文章中描述的算法。

Answer 4

如果我理解正确的话，那么有没有正确回答你的问题。您识别最多使用的Levenshtein给定单词三点建议 - 这是给你拿出一个规则来决定使用哪一个，并筛选哪些出来。或许你应该使用它们呢？

正如感兴趣的事，Damerau扩展莱文斯坦可能是你的兴趣，其中两个交换字符也算给1分，而不是2，而这正是香草莱文斯坦的回报。