分段处理的1／p概率字符串匹配

计算机科学 ›› 2008, Vol. 35 ›› Issue (7): 91-95.

分段处理的1／p概率字符串匹配

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
国家自然科学基金（N0.60673075）,国家高技术研究发展计划（863）（No.2006AA01ZA28）资助.

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 现有的概率字符串匹配算法通过计算字符串之间的最小失配字符数（编辑距离），可求出字符串之间的相似度。这些算法平等地看待模式串和文本串，虽然可求出二者之间完整的编辑距离，但并不能解决以下问题：即判断是否模式串中至少有1／p的字符顺序地出现在文本串中。基于动态规划字符串匹配算法，提出了一个改进算法。该算法通过将字符串分段，在段内执行改进的概率匹配算法可求出段内的编辑距离，再结合回溯策略可以很好地解决上述问题。该算法的复杂性要低于基本动态规划匹配算法，且在某些情况下效率更高。就问题的一般性而言，该算法可广泛地应用

关键词: 概率字符串匹配动态规划分段策略回溯策略

Abstract: Abstract Most of the existing Approximate String Matching （ASM） algorithms can determine the similarity of strings by computing the minimal number of mismatching characters （edition distance） between them, while the problem that deciding whether at least

Key words: Approximate string matching, Dynamic programming, Section policy, Trace back policy

. 分段处理的1／p概率字符串匹配[J]. 计算机科学, 2008, 35(7): 91-95. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed