计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2008年
7期
91-95
,共5页
吴玲%秦志光%石竑松%陈兆冲
吳玲%秦誌光%石竑鬆%陳兆遲
오령%진지광%석횡송%진조충
概率字符串匹配%动态规划%分段策略%回溯策略
概率字符串匹配%動態規劃%分段策略%迴溯策略
개솔자부천필배%동태규화%분단책략%회소책략
现有的概率字符串匹配算法通过计算字符串之间的最小失配字符数(编辑距离),可求出字符串之间的相似度.这些算法平等地看待模式串和文本串,虽然可求出二者之间完整的编辑距离,但并不能解决以下问题:即判断是否模式串中至少有1/p的字符顺序地出现在文本串中.基于动态规划字符串匹配算法,提出了一个改进算法.该算法通过将字符串分段,在段内执行改进的概率匹配算法可求出段内的编辑距离,再结合回溯策略可以很好地解决上述问题.该算法的复杂性要低于基本动态规划匹配算法,且在某些情况下效率更高.就问题的一般性而言,该算法可广泛地应用于计算生物学、信息安全和信号处理等诸多领域.
現有的概率字符串匹配算法通過計算字符串之間的最小失配字符數(編輯距離),可求齣字符串之間的相似度.這些算法平等地看待模式串和文本串,雖然可求齣二者之間完整的編輯距離,但併不能解決以下問題:即判斷是否模式串中至少有1/p的字符順序地齣現在文本串中.基于動態規劃字符串匹配算法,提齣瞭一箇改進算法.該算法通過將字符串分段,在段內執行改進的概率匹配算法可求齣段內的編輯距離,再結閤迴溯策略可以很好地解決上述問題.該算法的複雜性要低于基本動態規劃匹配算法,且在某些情況下效率更高.就問題的一般性而言,該算法可廣汎地應用于計算生物學、信息安全和信號處理等諸多領域.
현유적개솔자부천필배산법통과계산자부천지간적최소실배자부수(편집거리),가구출자부천지간적상사도.저사산법평등지간대모식천화문본천,수연가구출이자지간완정적편집거리,단병불능해결이하문제:즉판단시부모식천중지소유1/p적자부순서지출현재문본천중.기우동태규화자부천필배산법,제출료일개개진산법.해산법통과장자부천분단,재단내집행개진적개솔필배산법가구출단내적편집거리,재결합회소책략가이흔호지해결상술문제.해산법적복잡성요저우기본동태규화필배산법,차재모사정황하효솔경고.취문제적일반성이언,해산법가엄범지응용우계산생물학、신식안전화신호처리등제다영역.
