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