Levenshtein Distance算法
Levenshtein Distance
算法,又叫编辑距离算法,是指两个字符串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括:
替换一个字符
插入一个字符
删除一个字符
一般来说,编辑距离越小,两个串的相似度越大。相似度计算方式为:1 - (distance / maxLen)
注:distance
是所需的最少操作次数,maxLen
是两个字符串长度的最大值。
算法实现原理图解
A处
是一个标记,为了方便讲解
abc | a | b | c | |
---|---|---|---|---|
abe | 0 | 1 | 2 | 3 |
a | 1 | A处 | ||
b | 2 | |||
e | 3 |
按照Levenshtein distance
的意思:
- 上面的值加 1 ,得到
1+1=2
插入或删除 - 左面的值加 1 ,得到
1+1=2
插入或删除 - 左上角的值根据字符是否相同,
相同加 0
,不同加 1
。替换
A处
由于是两个 a 相同,左上角的值加 0 ,得到 0+0=0
,然后从我们上面计算出来的 2,2,0
三个值中选取最小值,所以 A 处的值为 0 。
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处
: 表示 abc
和 abe
有1个需要编辑的操作
I处
的值需要通过动态规划方法来计算,因此需要获取一些额外的信息:
A处
: 表示a
和a
需要有0个操作B处
: 表示ab
和a
需要有1个操作C处
: 表示abe
和a
需要有2个操作D处
: 表示a
和ab
需要有1个操作E处
: 表示ab
和ab
需要有0个操作F处
: 表示abe
和ab
需要有1个操作G处
: 表示a
和abc
需要有2个操作H处
: 表示ab
和abc
需要有1个操作I处
: 表示abe
和abc
需要有1个操作
主要应用
- Spell checking 检查拼写
- Speech recognition 语音识别
- DNA analysis DNA分析
- Plagiarism detection 检测抄袭
JS实现
1 | const LevenshteinDistance = { |
1 | LevenshteinDistance.init('omiga.org','omiga').get(); |