编辑距离应用.pptVIP

编辑距离 林彦彦 04-11-19 1. 概念 编辑距离（edit distance） 两个字符串通过插入字符、删除字符、改写字符而变为相同字符串所需要的操作数 。 eg. d(“abc”,”abd”) = 1 d(“abc”,”ab”) = 1 d(“abc”, “abcdf”) = 2 d(“serverU”,” ser-u”)=4 规则定义 对字符串s1和s2的编辑距离d(s1,s2) 定义： d(, ) = 0 d(s, ) = d(, s) = |s| d(s1+ch1, s2+ch2) = min( d(s1, s2) + if ch1=ch2 then 0 else 1 fi, d(s1+ch1, s2) + 1, d(s1, s2+ch2) + 1 ) 2.DPA实现 设二维矩阵 m[0..|s1|,0..|s2|] 其中， i=1..|s1|, j=1..|s2| m[0, 0] = 0 m[i, 0] = i, i=1..|s1| m[0, j] = j, j=1..|s2| m[i,j] = min( m[i-1,j-1] + if s1[i]=s2[j] then 0 else 1 fi, m[i-1, j] + 1, m[i, j-1] + 1） 复杂度分析 时间复杂性：O(|s1|*|s2|) 设|s1|和|s2|与n相当，则复杂性为O(n2) 空间复杂性： O(n2) 改进： O(|s1|)也就是O(n) 3.路径方法 现有字符串X=abbab, Y=bbaba 横边——插入 斜边——替换 竖边——删除 从start到goal 的最短路径为 d(X,Y) ; 加速机制： 相同替换操作优先 最小变换里头，删除和插入不可能成为连续操作 4.模糊统一问题 三个需求 编辑距离要拓展成能处理树结构的比较； 与传统一致化问题的兼容性 字符串比较与长度无关； [i] 解决方法 消除字符串长度对编辑距离值的影响 编辑距离标准化： 对两个字符串X、Y，计算 ne的值介于0与1之间 d(address,adresse)=2 d(007,oo7)=2 ne(address,adresse)=2/7 ne(007,oo7)=2/3 [ii] 解决方法 对树结构的比较 定义（一）： V为变量集 F为函数集 P为公式集 对 都可视x为一个项； 对 ，t1,t2,…,tn为项 f(t1,…tn)都为一个项； p(t1,…,tn)为一个原子式 定义（二） 设t=f(t1,..tn)和t’=ft(t1’,…tm’)为两个项或公式，x、y为变量，那么有 size(x)=size(ε)εεεε size(f)=|f| size(f(t1,…,tn))=|f|+∑i=1…nsize(ti) 定义（三） 树编辑距离et，它返回三个参数： 1st：错配数目；2nd：可置换的表示