计算机与数字工程
計算機與數字工程
계산궤여수자공정
COMPUTER & DIGITAL ENGINEERING
2012年
3期
14-17
,共4页
字符串相似度%编辑距离%最长公共子串%贪心字符串匹配%RKR-GST
字符串相似度%編輯距離%最長公共子串%貪心字符串匹配%RKR-GST
자부천상사도%편집거리%최장공공자천%탐심자부천필배%RKR-GST
对计算字符串相似度的编辑距离算法、最长公共子串算法、贪心字符串匹配算法、RKR-GST等多种算法,根据匹配过程是否有序,对这些算法进行了分类.然后对每种算法的实现原理进行了描述,并给出每个算法的运行步骤,结合一个实际的例子列出了算法运行的结果,最后给出每种算法计算相似度的计算公式和算法时间复杂度及应用领域.由于字符串相似度具有广泛的应用领域,对其中经典的几种算法进行总结对比是一件十分有意义的研究工作.
對計算字符串相似度的編輯距離算法、最長公共子串算法、貪心字符串匹配算法、RKR-GST等多種算法,根據匹配過程是否有序,對這些算法進行瞭分類.然後對每種算法的實現原理進行瞭描述,併給齣每箇算法的運行步驟,結閤一箇實際的例子列齣瞭算法運行的結果,最後給齣每種算法計算相似度的計算公式和算法時間複雜度及應用領域.由于字符串相似度具有廣汎的應用領域,對其中經典的幾種算法進行總結對比是一件十分有意義的研究工作.
대계산자부천상사도적편집거리산법、최장공공자천산법、탐심자부천필배산법、RKR-GST등다충산법,근거필배과정시부유서,대저사산법진행료분류.연후대매충산법적실현원리진행료묘술,병급출매개산법적운행보취,결합일개실제적례자렬출료산법운행적결과,최후급출매충산법계산상사도적계산공식화산법시간복잡도급응용영역.유우자부천상사도구유엄범적응용영역,대기중경전적궤충산법진행총결대비시일건십분유의의적연구공작.