Damerau-Levenshtein距离实现
我正在尝试在JS中创建damerau-levenshtein距离函数。
我在WIkipedia上找到了关于该算法的描述，但是他们没有实现它。它说：
要设计适当的算法来计算不受限制的Damerau–Levenshtein距离，请注意，始终存在最佳的编辑操作序列，在此之后，一旦转置的字母就永远不会被修改。因此，我们只需要考虑两种以上修改子串的对称方式：（1）转置字母并在它们之间插入任意数量的字符，或者（2）删除一系列字符并转置在删除后变为相邻的字母。这个想法的直接实现给出了三次复杂度的算法：O
\ left（M \ cdot N \ cdot \ max（M，N）\
right），其中M和N是字符串长度。利用Lowrance和Wagner的思想，[7]在最坏的情况下，可以将这种幼稚算法改进为O \ left（M \
cdot N \ right）。有趣的是，可以修改bitap算法以处理换位。有关此类修改的示例，请参见[1]的信息检索部分。
https://zh.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
[1]部分指向http://acl.ldc.upenn.edu/P/P00/P00-1037.pdf，这对我来说更加复杂。
如果我正确理解了这一点，那么创建一个实现就不那么容易了。
这是我当前使用的levenshtein实现：
levenshtein=function (s1, s2) { // discuss at: http://phpjs.org/functions/levenshtein/
// original by: Carlos R. L. Rodrigues (http://www.jsfromhell.com)
// bugfixed by: Onno Marsman
// revised by: Andrea Giammarchi (http://webreflection.blogspot.com)
// reimplemented by: Brett Zamir (http://brett-zamir.me)
// reimplemented by: Alexander M Beedie
// example 1: levenshtein('Kevin van Zonneveld', 'Kevin van Sommeveld');
// returns 1: 3
if (s1 == s2) {
return 0;
}
var s1_len = s1.length;
var s2_len = s2.length;
if (s1_len === 0) {
return s2_len;
}
if (s2_len === 0) {
return s1_len;
}
// BEGIN STATIC
var split = false;
try {
split = !('0')[0];
} catch (e) {
// Earlier IE may not support access by string index
split = true;
}
// END STATIC
if (split) {
s1 = s1.split('');
s2 = s2.split('');
}
var v0 = new Array(s1_len + 1);
var v1 = new Array(s1_len + 1);
var s1_idx = 0,
s2_idx = 0,
cost = 0;
for (s1_idx = 0; s1_idx < s1_len + 1; s1_idx++) {
v0[s1_idx] = s1_idx;
}
var char_s1 = '',
char_s2 = '';
for (s2_idx = 1; s2_idx <= s2_len; s2_idx++) {
v1[0] = s2_idx;
char_s2 = s2[s2_idx - 1];
for (s1_idx = 0; s1_idx < s1_len; s1_idx++) {
char_s1 = s1[s1_idx];
cost = (char_s1 == char_s2) ? 0 : 1;
var m_min = v0[s1_idx + 1] + 1;
var b = v1[s1_idx] + 1;
var c = v0[s1_idx] + cost;
if (b < m_min) {
m_min = b;
}
if (c < m_min) {
m_min = c;
}
v1[s1_idx + 1] = m_min;
}
var v_tmp = v0;
v0 = v1;
v1 = v_tmp;
}
return v0[s1_len];
}
构建这种算法的想法是什么，如果您认为它太复杂了，那么我该怎么做才能使“ l”（L小写）和“ I”（i大写）之间没有区别。
回答：
要点@doukremt给出了：https
://gist.github.com/doukremt/9473228
在Javascript中提供以下内容。
您可以在加权对象中更改操作的权重。
var levenshteinWeighted= function(seq1,seq2){
var len1=seq1.length;
var len2=seq2.length;
var i, j;
var dist;
var ic, dc, rc;
var last, old, column;
var weighter={
insert:function(c) { return 1.; },
delete:function(c) { return 0.5; },
replace:function(c, d) { return 0.3; }
};
/* don't swap the sequences, or this is gonna be painful */
if (len1 == 0 || len2 == 0) {
dist = 0;
while (len1)
dist += weighter.delete(seq1[--len1]);
while (len2)
dist += weighter.insert(seq2[--len2]);
return dist;
}
column = []; // malloc((len2 + 1) * sizeof(double));
//if (!column) return -1;
column[0] = 0;
for (j = 1; j <= len2; ++j)
column[j] = column[j - 1] + weighter.insert(seq2[j - 1]);
for (i = 1; i <= len1; ++i) {
last = column[0]; /* m[i-1][0] */
column[0] += weighter.delete(seq1[i - 1]); /* m[i][0] */
for (j = 1; j <= len2; ++j) {
old = column[j];
if (seq1[i - 1] == seq2[j - 1]) {
column[j] = last; /* m[i-1][j-1] */
} else {
ic = column[j - 1] + weighter.insert(seq2[j - 1]); /* m[i][j-1] */
dc = column[j] + weighter.delete(seq1[i - 1]); /* m[i-1][j] */
rc = last + weighter.replace(seq1[i - 1], seq2[j - 1]); /* m[i-1][j-1] */
column[j] = ic < dc ? ic : (dc < rc ? dc : rc);
}
last = old;
}
}
dist = column[len2];
return dist;
}
以上是 Damerau-Levenshtein距离实现 的全部内容， 来源链接： utcz.com/qa/413162.html
