20210424 Levenshtein距离解析

0.前言

距离上一次分析算法已经过去好几年了- -以我的算法水平其实是很讨厌分析算法的,一个是想写明白耗时很长,一个是说人话很啰嗦。但是写代码或公式又大部分人很难理解。今天要分析的算法是字符串相似度,Levenshtein距离

形式化描述:给定字符串strA,strB,求解dist(strA,strB)的值,dist为Levenshtein距离

说人话:两个字符串,编辑几次能变得完全一样,编辑允许的操作(插入,删除,替换字符)

0.定理/公理,人人都能看懂的情况

字符串基本操作:

连接 下文用+代表

删除字符 下文用 删除strA[0]表示

增加字符 下文用 str[x]=’a’表示 x从0开始

替换字符 下文用 str[x]=’a’表示 x从0开始

(这里一切的基础,类似于公理无需证明、显而易见、或可以轻易穷举证明的规律或法则)

0.1 (多嘴说两句,空串””可以理解为代数系统幺元的概念)

初始状态strA=”” strB=”abcdefgxxxxxx”

显然dist(strA,strB)=len(strB) len代表strB的长度

0.2 交换律

显然交换律成立

strA+strB == strB + strA

dist(strA,strB) == dist(strB,strA)

0.3 结合律(瞎起的名,可能不够严谨)

dist(strA,strB) == dist(strA+strC,strB+strC) == dist(strC+strA, strC+strB)

初始状态strA=”xxxxa…” strB=”xxxxb…”

显然,如果前缀x的部分相等,不论x多长,都可以等价于直接去掉,变成strA=”a” strB=”b”

初始状态strA=”axxxx” strB=”bxxxx”

显然,如果后缀x的部分相等,不论x多长,都可以等价于直接去掉,变成strA=”a” strB=”b”

特殊情况:初始状态strA=”a” strB=”a”

显然,当strA和strB完全相等时:dist(strA,strB)==dist(“”,””)==dist(“”,len(“”))==0

1.下面从最简单的情况开始分析

从最简单的情况开始分析,只有一个字母的时候,有这么几种情况

1.1.case1

初始状态strA=”a” strB=””,显然有这么几种情况

1.1步=删除1次

1.1.删除strA[0]->””,””

2.1步=插入1次

2.1.插入strB[0]=’a’,->”a”,”a”

1.2.case2

初始状态strA=”” strB=”b”,显然有这么几种情况

1.1步=删除1次

1.1.删除strB[0]->””,””

2.1步=插入1次

2.1.插入strA[0]=’b’,->”b”,”b”

2.稍微复杂一点,两个不等字符跟别构成的字符串

初始状态strA=”a” strB=”b”

以下表示格式为strA,strB

1.

“a”,”b”

1.1.替换strB[0]=’a’->”a”,”a”

共1步=替换1次 => dist(“”, “”) + 1

如何理解dist(“”,””)是这个地方的关键,在替换的策略下,总次数实际是是替换位置前面所有的部分的编辑次数,加上替换的这1次即是整个字符串的总次数,这个case下位置0前面没东西了,所以是空串””

2.

“a”,”b”

2.1.替换strA[0]=’b’->”b”,”b”

共1步=替换1次 => dist(“”, “”) + 1

同上:如何理解dist(“”,””)是这个地方的关键,在替换的策略下,总次数实际是是替换位置前面所有的部分的编辑次数(不包括替换的位置自己),加上替换的这1次即是整个字符串的总编辑次数,这个case下位置0前面没东西了,所以是空串””

3

“a”,”b”

3.1.插入strA[0]=’b’->”ba”,”b”

3.2.插入strB[1]=’a’->”ba”,”ba”

共2步=插入1次+ dist(“ba”,”b”)== 插入1次 + dist(“a”,””)  =>  dist(“a”,””) + 1

如何理解 dist(“a”,””)是这个地方的关键:

实际上原本是dist(“ba”,”b”),因为前缀相同,所以变成了dist(“a”,””)

在这种插入策略下,插入位置之前的部分总是一样的(包括插入位置自己),所以总次数实际是是插入位置后面所有的部分的编辑次数(不包括插入的位置自己),加上插入的这1次即是整个字符串的总次数

这个case下strA[0]位置后面是”a”,strB后面是””

4

“a”,”b”

4.1.插入strB[0]=’a’->”a”,”ab”

4.2.插入strA[1]=’b’->”ab”,”ab”

共2步=插入1次+ dist(“a”,”ab”)== 插入1次 + dist(“”,”b”)  =>  dist(“”,”b”) + 1

如何理解 dist(“”,”b”) 是这个地方的关键:

实际上原本是dist(“a”,”ab”),因为前缀相同,所以变成了dist(“”,”b”)

在这种插入策略下,插入位置之前的部分总是一样的(包括插入位置自己),所以总次数实际是是插入位置后面所有的部分的编辑次数(不包括插入的位置自己),加上插入的这1次即是整个字符串的总次数

这个case下strA[0]位置后面是””,strB后面是”b”

5

“a”,”b”

共2步 显然等价于1

5.1.删除strB[0]->”a”,””

5.2.插入strB[0]=’a’->”a”,”a”

6

“a”,”b”

共2步 显然等价于2

6.1.删除strA[0]->””,”b”

6.2.插入strA[0]=’b’->”b”,”b”

7

“a”,”b”

7.1.插入strB[1]=’a’->”a”,”ba”

7.2.插入strA[0]=’b’->”ba”,”ba”

共2步=插入1次+ dist(“a”,”ba”)== 插入1次 + dist(“”,”b”)  =>  dist(“”,”b”) + 1  同4

如何理解 dist(“”,”b”)是这个地方的关键:

实际上原本是dist(“a”,”ba”),因为后缀相同,所以变成了dist(“”,”b”)

在这种插入策略下,插入位置之后的部分总是一样的(包括插入位置自己),所以总次数实际是是插入位置前面所有的部分的编辑次数(不包括插入的位置自己),加上插入的这1次即是整个字符串的总次数

这个case下strA[0]位置前面是””,strB[1]前面是”b”

8.

“a”,”b”

8.1.插入strA[1]=’b’->”ab”,”b”

8.2.插入strB[0]=’a’->”ab”,”ab”

共2步=插入1次+ dist(“ab”,”b”)== 插入1次 + dist(“a”,””)  =>  dist(“a”,””) + 1  同3

如何理解 dist(“a”,””) 是这个地方的关键:

实际上原本是dist(“ab”,”b”),因为后缀相同,所以变成了dist(“a”,””)

在这种插入策略下,插入位置之后的部分总是一样的(包括插入位置自己),所以总次数实际是是插入位置前面所有的部分的编辑次数(不包括插入的位置自己),加上插入的这1次即是整个字符串的总次数

这个case下strA[1]位置前面是”a”,strB[0]前面是””

 

综上1278,不难发现,最小的次数是1278中的最小值(选1234就是倒着了,一样的,两个方向都可以的)

dist(“a”,”b”) == min(dist(“”, “”) + 1, dist(“a”, “”) + 1, dist(“”, “b”) + 1)

或写做min(dist(“”, “”) , dist(“a”, “”) , dist(“”, “b”) ) + 1

认真思考下,替换策略计算的结果为替换位置之前的部分,插入策略因位置不同但相互对称,所以刚好是去掉插入位置的字符前面的部分

所以dist(“a”,”b”) == 1

3.再复杂一些

根据2的结论,能否扩充到长度为n的情况呢?

dist(“abcdef”,”agchef”)

根据定理3 ==> dist(“abcd”, “agch”)

根据定理3 ==> dist(“bcd”, “gch”)

根据规律 ==> min(    dist(“bc”, “gc”),    dist(“bcd”, “gc”),    dist(“bc”, “gch”) ) + 1

根据规律 ==>min(

dist(“b”, “g”),

min(  dist(“bc”, “g”),     dist(“bcd”, “g”),      dist(“bc”, “gc”)     ) + 1 ,

min( dist(“b”, “gc”),     dist(“bc”, “gc”),       dist(“b”, “gch”)   )  + 1

) + 1

根据规律 ==>min(

dist(“b”, “g”),

min(

min(dist(“b”, “”),dist(“bc”, “”),dist(“b”, “g”))+1,

min(dist(“bc”,””), dist(“bcd”,””), dist(“bc”,”g”))+ 1

dist(“b”,”g”)

) + 1,

min(dist(“b”, “gc”),  dist(“bc”, “gc”),  dist(“b”, “gch”)) + 1

) + 1

根据规律 ==>min(

dist(“b”, “g”),

min(

min(dist(“b”, “”),dist(“bc”, “”),dist(“b”, “g”))+1,

min(dist(“bc”,””), dist(“bcd”,””), min(dist(“b”,””), dist(“bc”,”g”), dist(“b”,”g”)) + 1) +  1

dist(“b”,”g”)

) + 1,

min(dist(“b”, “gc”),  dist(“bc”, “gc”),  min(dist(“”, “gc”), dist(“b”, “gc”), dist(“”, “gch”)) + 1) + 1

) + 1

根据规律 ==>min(

1,

min(

min(1,2,1)+1,

min(2,3, min(1,2,1) + 1) +  1

1

) + 1,

min(2, 1,  min(2, 2, 3) + 1) + 1

) + 1

根据规律 ==>2

4.程序实现

次数统计后如下,显然部分内容被重复计算了

dist(“”,”g”)
dist(“”,”gc”) * 2
dist(“”,”gch”)
dist(“b”,””) * 3
dist(“b”,”g”) * 5
dist(“b”,”gc”)
dist(“bc”,””) * 3
dist(“bc”,”gc”)
dist(“bcd”,””)

直接加缓存,或按状态转移方程填表即可

参考资料

https://zhuanlan.zhihu.com/p/91645988

0 Comments
Leave a Reply