| liulin188 |
2020-01-15 14:56 |
Qt之字符串编辑距离(Levenshtein Distance)算法实现
分享一片干货
最近需要找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];
}
|
|
