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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了c – Levenshtein算法：如何满足此文本编辑要求？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1180字，纯文字阅读大概需要2分钟。

内容图文

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

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

N个字符的每个字典单词,与找到的单词有1个字符差异.
例：
发现词：bearn,词典词：熊

N 1个字符的每个字典单词,其N个字符等于找到的单词.
例：
发现词：熊,字典词：熊

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];
}

解决方法:

您可能还想在阅读中添加Norvig’s excellent article on spelling correction.

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

内容总结

以上是互联网集市为您收集整理的c – Levenshtein算法：如何满足此文本编辑要求？全部内容，希望文章能够帮你解决c – Levenshtein算法：如何满足此文本编辑要求？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---