求解PMWOC问题的位并行算法

Bit-parallelism algorithm for PMWOC

带有灵活通配符和One-Off条件的模式匹配问题(pattern matching with flexible wildcards and One-Off condition,PMWOC)具有重要的理论意义和实际应用价值。给定带灵活通配符的模式和文本,目标是在线的计算模式在文本中的出现次数和匹配位置,这里要求任何两次出现不能共享文本同一位置,即One-Off条件。提出了一个基于位并行的搜索算法,采用了非确定有限自动机(nondeterministic finite automatons,NFA)对文本进行扫描。通过理论和实验证明,与其他解决相同问题的算法对比,该算法取得更好的时间性能和空间性能,而且不受模式长度变化和通配符间距变化影响。

The problem of pattern matching with flexible wildcards and One-Off condition（ PMWOC） is of great importance for both theory and practice. Giving a pattern with flexible wildcards and a text,it focused on finding the number of occurrences of a pattern in a text and each occurrence＇s position online. Here,any two occurrences cannot share the same position of the text,namely the One-Off condition. This paper proposed a search algorithm based on bit-parallelism,which adopted nondeterministic finite automatons（ NFA） to stimulate the search process. Compared to the previous peers,theoretical analysis and experimental results show that it can get better performances on both time and space. Moreover,it also has better stability with the increasing of the pattern length or the maximum wildcard constraints.