• 523阅读
  • 1回复

Qt之字符串编辑距离(Levenshtein Distance)算法实现 [复制链接]

上一主题 下一主题
在线liulin188
 

只看楼主 倒序阅读 楼主  发表于: 01-15
— 本帖被 20091001753 从 Qt 作品展 移动到本区(2020-01-16) —

分享一片干货
最近需要找2个字符串的相似度,找来找去还是这个算法最靠谱:Levenshtein距离是一种计算两个字符串间的差异程度的字符串度量(string metric)。我们可以认为Levenshtein距离就是从一个字符串修改到另一个字符串时,其中编辑单个字符(比如修改、插入、删除)所需要的最少次数。俄罗斯科学家Vladimir Levenshtein于1965年提出了这一概念。
参考别人的算法,写了个Qt的
  1. int calcDistance(const QString source, const QString target)
  2. {
  3.     int n = source.length();
  4.     int m = target.length();
  5.     if (m == 0) return n;
  6.     if (n == 0) return m;
  7.     QVector <QVector <int>> matrix(n + 1);
  8.     for (int i = 0; i <= n; i++) matrix[i].resize(m + 1);
  9.     for (int i = 1; i <= n; i++) matrix[i][0] = i;
  10.     for (int i = 1; i <= m; i++) matrix[0][i] = i;
  11.     for (int i = 1; i <= n; i++)
  12.     {
  13.         const QChar si = source.at(i - 1);
  14.         for (int j = 1; j <= m; j++)
  15.         {
  16.             const QChar dj = target.at(j - 1);
  17.             int cost;
  18.             if (si == dj)
  19.                 cost = 0;
  20.             else
  21.                 cost = 1;
  22.             const int above = matrix[i - 1][j] + 1;
  23.             const int left = matrix[i][j - 1] + 1;
  24.             const int diag = matrix[i - 1][j - 1] + cost;
  25.             matrix[i][j] = min(above, min(left, diag));
  26.         }
  27.     }
  28.     return matrix[n][m];
  29. }
min函数是win32自带的在<minwindef.h>里


4条评分好评度+1贡献值+1金钱+10威望+1
20091001753 好评度 +1 - 01-16
20091001753 贡献值 +1 - 01-16
20091001753 威望 +1 - 01-16
20091001753 金钱 +10 - 01-16
https://wiki.qt.io/Qt_5.12_Release
https://www.qt.io/blog/qt-5.13.2-released
https://www.qt.io/blog/qt-creator-4.10.2-released
离线toby520

只看该作者 1楼 发表于: 01-16
    
QtQML多多指教开发社区 http://qtclub.heilqt.com
将QtCoding进行到底
关注移动互联网,关注金融
开发跨平台客户端,服务于金融行业
专业定制界面
群号:312125701   373955953(qml控件定做)
快速回复
限100 字节
 
上一个 下一个