In this paper, we study a complex pattern matching problem over a single continuous stream of numerical values. Based on bit-parallel technique for string matching, we propose an efficient algorithm called BPS (Bit-Parallel matching on Streams) that finds the set of all occurrences of a given pattern of length m in an input stream of length n in O(1/w mn) time for ordered values and in O(1/w mn log m) time for real values over a fixed data range, where w is the bit-width of registers. This time complex properly improves the time complexity O(mn) of the previous algorithms. The keys of the algorithm are fast NFA simulation based on bit-parallel operation and hit predicate table lookup technique. We also present empirical analysis to evaluate the performance of the algorithm showing that the proposed algorithm is twice as fast as and more stable than the previous algorithms.
展开▼
机译：在本文中，我们在单个连续的数值流中研究复杂的模式匹配问题。基于对串匹配的比特并行技术，我们提出了一种称为BPS（流匹配的比特平行匹配）的有效算法，其在O（1的输入流中的输入流中的给定图案的给定模式的所有出现集合/ w mn）有序值的时间和在固定数据范围内的实际值的O（1 / W Mn log m）时间，其中w是寄存器的比特宽度。这次复杂地适当地改善了先前算法的时间复杂度O（MN）。算法的键是基于比特并行操作的快速NFA仿真，并点击谓词表查找技术。我们还提出了实证分析来评估算法的性能，表明所提出的算法是比以前的算法更快速且更稳定的算法。
展开▼
