字符串的相似度

Levenshtein Distance算法

Levenshtein Distance 算法,又叫编辑距离算法,是指两个字符串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括:

  • 替换一个字符

  • 插入一个字符

  • 删除一个字符

一般来说,编辑距离越小,两个串的相似度越大。相似度计算方式为:1 - (distance / maxLen)

注:distance 是所需的最少操作次数,maxLen是两个字符串长度的最大值。


算法实现原理图解

  1. 首先是有两个字符串,这里写一个简单的 abcabe
  2. 将字符串想象成下面的结构

A处是一个标记,为了方便讲解

abc a b c
abe 0 1 2 3
a 1 A处
b 2
e 3
  1. 来计算A处出得值,它的值取决于:左边的值、上边的值、左上角的值

按照Levenshtein distance的意思:

  • 上面的值加 1 ,得到 1+1=2 插入或删除
  • 左面的值加 1 ,得到 1+1=2 插入或删除
  • 左上角的值根据字符是否相同,相同加 0不同加 1替换

A处由于是两个 a 相同,左上角的值加 0 ,得到 0+0=0 ,然后从我们上面计算出来的 2,2,0 三个值中选取最小值,所以 A 处的值为 0 。

  1. 于是表成为下面的样子
abc a b c
abe 0 1 2 3
a 1 0
b 2 B处
e 3

B处会同样得到三个值,左边计算后为 3 ,上边计算后为 1 ,在B处由于对应的字符为 a、b,不相等,所以左上角应该在当前值的基础上加 1 ,这样得到 1+1=2 ,在(3,1,2)中选出最小的为 B 处的值。

5.于是表就更新了
abc a b c
abe 0 1 2 3
a 1 0
b 2 1
e 3 C处

C处计算后:上面的值为 2 ,左边的值为 4 ,左上角的:a 和 e 不相同,所以加 1 ,即 2+1 ,左上角的为 3 。

(2,4,3)中取最小的为 C 处的值。

6.于是依次推得到
a b c
0 1 2 3
a 1 A处 0 D处 1 G处 2
b 2 B处 1 E处 0 H处 1
e 3 C处 2 F处 1 I处 1

I处: 表示 abcabe 有1个需要编辑的操作

I处的值需要通过动态规划方法来计算,因此需要获取一些额外的信息:

  • A处: 表示aa需要有0个操作
  • B处: 表示aba需要有1个操作
  • C处: 表示abea需要有2个操作
  • D处: 表示aab需要有1个操作
  • E处: 表示abab需要有0个操作
  • F处: 表示abeab需要有1个操作
  • G处: 表示aabc需要有2个操作
  • H处: 表示ababc需要有1个操作
  • I处: 表示abeabc需要有1个操作


主要应用

  • Spell checking 检查拼写
  • Speech recognition 语音识别
  • DNA analysis DNA分析
  • Plagiarism detection 检测抄袭


JS实现

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
const LevenshteinDistance = {
_str1: null,
_str3: null,
_matrix: null,

_isString: function(s) {
return Object.prototype.toString.call(s) === '[object String]';
},

_isNumber: function(s) {
return Object.prototype.toString.call(s) === '[object Number]';
},

init: function(str1, str2) {
if (!this._isString(str1) || !this._isString(str2)) return;
this._str1 = str1;
this._str2 = str2;
str1.length && str2.length && this._createMatrix(str1.length + 1, str2.length + 1);
this._matrix && this._initMatrix();
return this;
},

get: function() {
return 1 - this._getDistance() / Math.max(this._str1.length, this._str2.length);
},

//计算编辑距离
_getDistance: function() {
var len1 = this._str1.length,
len2 = this._str2.length;
if (!len1 || !len2) return Math.max(len1, len2);
var str1 = this._str1.split(''),
str2 = this._str2.split('');
var i = 0,
j = 0,
temp = 0;
while (i++ < len1) {
j = 0;
while (j++ < len2) {
temp = str1[i - 1] === str2[j - 1] ? 0 : 1;
this._matrix[i][j] = Math.min(
this._matrix[i - 1][j] + 1,
this._matrix[i][j - 1] + 1,
this._matrix[i - 1][j - 1] + temp
);
}
}
return this._matrix[i - 1][j - 1];
},

/*
* 初始化矩阵
* 为第一行、第一列赋值
*/
_initMatrix: function() {
var cols = this._matrix[0].length,
rows = this._matrix.length;
var l = Math.max(cols, rows);
while (l--) {
cols - 1 >= l && (this._matrix[0][l] = l);
rows - 1 >= l && (this._matrix[l][0] = l);
}
},

/*
* 创建矩阵
* n:行
* m:列
*/
_createMatrix: function(n, m) {
if (!this._isNumber(n) || !this._isNumber(m) || n < 1 || m < 1) return;
this._matrix = new Array(n), i = 0;
while (i < n) this._matrix[i++] = new Array(m);
}
}
1
LevenshteinDistance.init('omiga.org','omiga').get();