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