使用莱文斯坦距离(Levenshtein distance)计算两数组的差异

前言

莱文斯坦距离(Levenshtein distance以下简称ld)是一种常见的算法或可以称之为一种度量单位(前提是操作权重确定),它用于表示从字串序列A到字串序列B所需要进行操作(增加、删除、更新)的综合。

鉴于数组与字符的相似性,这个算法当然同样适合与数组

问题是作为一个前端开发,你不好好切图,用这个算法做啥?

事实上Regularjs内部就使用到了这种算法,它用于检测数组的变动差异,并将差异反映到View中(即Dom)。

ld算法的另一个好处是,可以容易的将计算结果映射到未来将会到来的JS ES6Array.observe的返回值形式,方便未来的无缝迁移。

原理描述

ld算法

上图从Wiki上引用,它表示了LD距离的计算的基本原理,事实上我们需要提取编辑路径,这样我们才可以映射到具体的路径操作(比如更新dom).

在执行ld算法后,我们可以得到这样的二维矩阵

ld table

生成的矩阵的最后一个单元格, 即代表LS计算距离,这里从最后一个单元格回溯,我们就可以获得到从字符串A到字符串B的操作步骤,其中各个方向代表的含义是:

  1. 左上角: 不变或者替换(根据ld距离是否改变)
  2. 直左:代表删除一个字符
  3. 直右: 代表增加一个字符

具体路径选择根据特定环境而定 比如我们由于后续要用于dom更新的特点,我们需要保留的原对象越多越好。

【一知半解?戳这个demo】

See the Pen GnkAC by leeluolee (@leeluolee) on CodePen.

你可以手动输入字符串1和字符串2,由于使用了Regularjs,结果会实时响应。

javascript实现源代码

说明

  1. diff用来生成首次路径matrix
  2. whole函数用来回溯路径matrix,选择最合适路径
  3. 这里除了算法本身,还引入了转换数据格式的逻辑,方便后续操作
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
var ld = (function(){
// 代表判定两者是否相等依据,这里我们认为 ===
function equals(a,b){
return a === b;
}
// 计算
function diff(array1, array2){
var n = array1.length;
var m = array2.length;
var matrix = [];
for(var i = 0; i <= n; i++){
matrix.push([i]);
}
for(var j=1;j<=m;j++){
matrix[0][j]=j;
}
for(var i = 1; i <= n; i++){
for(var j = 1; j <= m; j++){
if(equals(array1[i-1], array2[j-1])){
matrix[i][j] = matrix[i-1][j-1];
}else{
matrix[i][j] = Math.min(
matrix[i-1][j]+1, //delete
matrix[i][j-1]+1//add
)
}
}
}
return matrix;
}
// 根据diff算法,回溯matrix,得到最后结果
function whole(arr2, arr1) {
var matrix = ld(arr1, arr2)
var n = arr1.length;
var i = n;
var m = arr2.length;
var j = m;
var edits = [];
var current = matrix[i][j];
while(i>0 || j>0){
// the last line
if (i === 0) {
edits.unshift(3);
j--;
continue;
}
// the last col
if (j === 0) {
edits.unshift(2);
i--;
continue;
}
var northWest = matrix[i - 1][j - 1];
var west = matrix[i - 1][j];
var north = matrix[i][j - 1];
var min = Math.min(north, west, northWest);
if (min === west) {
edits.unshift(2); //delete
i--;
current = west;
} else if (min === northWest ) {
if (northWest === current) {
edits.unshift(0); //no change
} else {
edits.unshift(1); //update
current = northWest;
}
i--;
j--;
} else {
edits.unshift(3); //add
j--;
current = north;
}
}
var LEAVE = 0;
var ADD = 3;
var DELELE = 2;
var UPDATE = 1;
var n = 0;m=0;
var steps = [];
var step = {index: null, add:0, removed:[]};
for(var i=0;i 0 ){ // NOT LEAVE
if(step.index === null){
step.index = m;
}
} else { //LEAVE
if(step.index != null){
steps.push(step)
step = {index: null, add:0, removed:[]};
}
}
switch(edits[i]){
case LEAVE:
n++;
m++;
break;
case ADD:
step.add++;
m++;
break;
case DELELE:
step.removed.push(arr1[n])
n++;
break;
case UPDATE:
step.add++;
step.removed.push(arr1[n])
n++;
m++;
break;
}
}
if(step.index != null){
steps.push(step)
}
return steps
}
return whole;
})();

结尾

对一个正常人来讲,这种程度的算法都花不了你几个小时用来学习(更别说一些更常见的算法),关键是要有这个意识它能用来解决什么实际问题,否则对数据结构与算法倒背如流都毫无意义。