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