字符串近似匹配算法.ppt

《字符串近似匹配算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、应用背景1、字处理程序中的拼写检查2、语音或文字识别3、去传输噪声一、问题与思路“Difference”Thedifferencescanbeanyofthefollowingthreetypes.ThenameofthedifferenceistheoperationneededonTtobringitclosertoP.revise:ThecorrespondingcharactersinPandTaredifferent.delete:TcontainsacharacterthatismissingfromPinsert:Tismissingacharacterthatappear

2、inP.Example11.9P505二、解决方案----动态规划1、采用从右向左的比较方案。2、子问题图中(i,j)表示模板p1,…,pi在以tj为结尾的正文T中的minimum-differencematch.DifferenceTableD[i][j]=theminimumnumberofdifferencebetweenp1,…,piandasegmentofTendingattj.D[i][j]之间的关系matchCost=D[i-1][j-1]ifpi=tjrevisedCost=D[i-1][j-1]+1ifpitjinsertCost=D[i-1][j]+1在tj后面插

3、入pideleteCost=D[i][j-1]+1删除tjifpi=tjD[i][j]=D[i-1][j-1]Otherwise,D[i][j]=min(D[i-1][j-1]+1,D[i-1][j]+1,D[i][j-1]+1)三、例P508例11.11四、练习在“TheBMagorithmisanalgorismwhichdoesmatchingfromrighttoleft”中寻找algorithm的2-difference匹配，并说明理由