CAJ | 학술논문

针对目前已有的算法在计算带有可变长度通配符的模式在文本中的出现次数问题时，需要的时间是多项式级别，而且受文本长度、模式长度和通配符间距的影响比较大。提出了一种基于Aho-Corasick自动机的AAI（pAttern mAtching with wIldcards）算法，计算中采用了动态规划思想和有效的修剪技术。AAI算法的时间复杂度和空间复杂度分别为O(n+m+α)和O(m+B)，其中n和m分别表示文本和模式的长度，α是所有子模式在文本中出现的数目，B是模式中通配符间距下限的总和。通过真实数据和人工数据的实验结果表明，AAI算法与同类算法相比具备显著的优势。
침대목전이유적산법재계산대유가변장도통배부적모식재문본중적출현차수문제시，수요적시간시다항식급별，이차수문본장도、모식장도화통배부간거적영향비교대。제출료일충기우Aho-Corasick자동궤적AAI（pAttern mAtching with wIldcards）산법，계산중채용료동태규화사상화유효적수전기술。AAI산법적시간복잡도화공간복잡도분별위O(n+m+α)화O(m+B)，기중n화m분별표시문본화모식적장도，α시소유자모식재문본중출현적수목，B시모식중통배부간거하한적총화。통과진실수거화인공수거적실험결과표명，AAI산법여동류산법상비구비현저적우세。
Current works on computing the number of all matches of pattern with variable length wildcards in text need polynomial time, and have been greatly influenced by the length of the text, pattern, and wildcards interval. This paper proposes an algorithm AAI(pAttern mAtching with wIldcards)based on Aho-corasick automaton which adopts dynamic programming and effective pruning strategies. Let n and m be the length of P and T, respectively. The algorithm AAI need time O(n+m+α) and space O(m+B) , whereαis the total number of occurrences of the subpatterns in P within S, B is the sum of the lower bonds of the wildcards. Experimental results from different aspects validate that AAI is more stable and effective than other peers on both artificial and real-world data.