Levenshtein distance 编辑距离算法
2020-12-13 04:47
标签：初始 ati == turn 不同的 改进 地址 func uil 这几天再看 virtrual-dom，关于两个列表的对比，讲到了 Levenshtein distance 距离，周末抽空做一下总结。 在信息理论和计算机科学中，Levenshtein 距离是用于测量两个序列之间的差异量（即编辑距离）的度量。两个字符串之间的 Levenshtein 距离定义为将一个字符串转换为另一个字符串所需的最小编辑数，允许的编辑操作是单个字符的插入，删除或替换。 ‘kitten’和’sitten’之间的 Levenshtein 距离是 3，因为一下三个编辑将一个更改为另一个，并且没有办法用少于三个编辑来执行操作。 为了得到编辑距离，我们用 beauty 和 batyu 为例： 图示如 ① 单元位置是两个单词的第一个字符 [b] 比较得到的值，其的值有它的上方的值 (1)、它左方的值 (1) 和它左上角的值 (0) 来决定。当单元格所在的行和列所对应的字符相等时，单元格的值为左上方的值。 否则，单元格左上角的值与其上方和左方的值进行比较，它们之间的最小值 + 1 即是单元格的值。 图中 ① 的值由于单元格行和列相等，所以取左上角值 0。 图中 ② 的值由于单元格行列不相等，(1, 2, 0) 取最小为 0， 结果 + 1， 所以 ② 值为 1。 图示 ③ 的值由于单元格行列不相等，(1, 0, 2) 取最小 0， 结果 + 1， 所以 ③ 值为 1。 这个算法计算的是将 s [1…i] 转换为 t [1…j]（例如将 beauty 转换为 batyu）所需最少的操作数（也就是所谓的编辑距离），这个操作数被保存在 d [i,j]（d 代表的就是上图所示的二维数组）中。 这一部分的代码，参考了 https://rosettacode.org/wiki/Levenshtein_distance#ES5 上面总结了传统的计算字符串之间的差距，那么当我们怎么能在计算的过程中，记录需要转换的步骤，并且进行还原呢。 这里我们需要对比较的每一位的步骤有一个了解。 为了得到编辑距离，我们用 beauty 和 batyu 为例： 那么对角线也显而易见就是先相对于替换操作。那么我们现在需要做的就是，记录下相对应的索引和元素以及需要进行的操作，并将其保存为一个对象，每次新增的对象用数组来保存就可以了。 下面是 compare 方法： 上面需要注意的是，我们一组保存了多个数组对象，不要对原数组进行操作，每一次操作我们都需要拷贝一个新的数组对象。 具体的的 diff 代码参考 diff 代码 得到了，patches 对象，剩下的我们就需要 patch 了 具体代码参考代码地址 Levenshtein distance 编辑距离算法 标签：初始 ati == turn 不同的 改进 地址 func uil 原文地址：https://www.cnblogs.com/jfdwd/p/11122372.htmlLevenshtein Distance 介绍
例子
k itten sitten => 用’s’代替’k’e n sitt i => 用’i’代替’e’g 在结尾插入’g’Levenshtein Distance (编辑距离) 算法详解
算法证明
可能的改进
字符串比较代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const ld = (a, b) => {
let t = [], u, i, j, m = a.length, n = b.length;
if (!m) return b;
if (!n) return a;
for (j = 0; j t[j] = j;
}
console.log(t);
for (i = 1; i for (u = [i], j = 1; j u[j] = a[j - 1] === b[i - 1] ? t[j - 1] : Math.min(t[j - 1], t[j], u[j - 1]) + 1 // Levenshtein Distance 算法核心比较部分。
}
t = u;
console.log(t);
}
return u[m];
}
[[‘beauty‘, ‘batyu‘, 3],
].forEach(function (v) {
var a = v[0], b = v[1], t = v[2], d = ld(a, b);
if (d !== t) {
console.log(‘levenstein("‘ + a + ‘","‘ + b + ‘") was ‘ + d + ‘ should be ‘ + t);
}
});
// 打印出来
[ 0, 1, 2, 3, 4, 5, 6 ]
[ 1, 0, 1, 2, 3, 4, 5 ]
[ 2, 1, 1, 1, 2, 3, 4 ]
[ 3, 2, 2, 2, 2, 2, 3 ]
[ 4, 3, 3, 3, 3, 3, 2 ]
[ 5, 4, 4, 4, 3, 4, 3 ]还原字符串
从上面一节的图中可以看到，‘beauty‘ 转换为 ‘‘ ，对一个的第一行的 [1，2，3，4，5，6]，每一个步骤都相对与上一个元素新建一个元素，同理 ‘‘ 转换为 ‘batyu‘，每一个值都是相对一上一个元素的删除步骤。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
const actionType = {
TYPE_REPLACE: ‘TYPE_REPLACE‘,
TYPE_NEW: ‘TYPE_NEW‘,
TYPE_DELETE: ‘TYPE_DELETE‘
}
// 生成对象的方法
const patchObj = (index, type, item = ‘‘) => {
return {
index,
type,
item
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
*
* @param { array } r 替换操作 replace
* @param { array } n 新建操作 new
* @param { array } d 删除操作 delete
* @param { number } i 需要转换元素的 index
* @param { number } j 需要删除元素的 index
* @param { string } b 比较字符串
*/
const compare = (r, n, d, i, j, b) => {
const min = Math.min(r.length, n.length, d.length);
switch (min) {
case r.length:
return [...r, patchObj(i, actionType.TYPE_REPLACE, b[i])];
case n.length:
return [...n, patchObj(i, actionType.TYPE_NEW, b[i])];
case d.length:
return [...d, patchObj(j, actionType.TYPE_DELETE)];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const patch = (a, diffs) => {
let aList = a.split(‘‘);
let delCount = 0; // 删除之后，后续的index计算需要加上之前删除的数量
diffs.forEach((diff) => {
switch (diff.type) {
case actionType.TYPE_DELETE:
aList.splice(diff.index - delCount, 1);
delCount++
break;
case actionType.TYPE_NEW:
aList.splice(diff.index, 0, diff.item);
break;
case actionType.TYPE_REPLACE:
aList.splice(diff.index, 1, diff.item);
break;
default:
break;
}
})
// console.log(aList.join(‘‘))
return aList.join(‘‘)
}参考资料