计算机应用研究
計算機應用研究
계산궤응용연구
Application Research of Computers
2015年
10期
2973-2977
,共5页
模式匹配%通配符%One-Off条件
模式匹配%通配符%One-Off條件
모식필배%통배부%One-Off조건
pattern matching%wildcards%One-Off condition
带有灵活通配符和One-Off条件的模式匹配问题(pattern matching with flexible wildcards and One-Off condition,PMWOC)具有重要的理论意义和实际应用价值.给定带灵活通配符的模式和文本,目标是在线的计算模式在文本中的出现次数和匹配位置,这里要求任何两次出现不能共享文本同一位置,即One-Off条件.提出了一个基于位并行的搜索算法,采用了非确定有限自动机(nondeterministic finite automatons,NFA)对文本进行扫描.通过理论和实验证明,与其他解决相同问题的算法对比,该算法取得更好的时间性能和空间性能,而且不受模式长度变化和通配符间距变化影响.
帶有靈活通配符和One-Off條件的模式匹配問題(pattern matching with flexible wildcards and One-Off condition,PMWOC)具有重要的理論意義和實際應用價值.給定帶靈活通配符的模式和文本,目標是在線的計算模式在文本中的齣現次數和匹配位置,這裏要求任何兩次齣現不能共享文本同一位置,即One-Off條件.提齣瞭一箇基于位併行的搜索算法,採用瞭非確定有限自動機(nondeterministic finite automatons,NFA)對文本進行掃描.通過理論和實驗證明,與其他解決相同問題的算法對比,該算法取得更好的時間性能和空間性能,而且不受模式長度變化和通配符間距變化影響.
대유령활통배부화One-Off조건적모식필배문제(pattern matching with flexible wildcards and One-Off condition,PMWOC)구유중요적이론의의화실제응용개치.급정대령활통배부적모식화문본,목표시재선적계산모식재문본중적출현차수화필배위치,저리요구임하량차출현불능공향문본동일위치,즉One-Off조건.제출료일개기우위병행적수색산법,채용료비학정유한자동궤(nondeterministic finite automatons,NFA)대문본진행소묘.통과이론화실험증명,여기타해결상동문제적산법대비,해산법취득경호적시간성능화공간성능,이차불수모식장도변화화통배부간거변화영향.
