IEEE Trans Pattern Anal Mach Intell. 2012 Jan;34(1):127-43. doi: 10.1109/TPAMI.2011.106. Epub 2011 May 19.
Pattern matching is widely used in signal processing, computer vision, and image and video processing. Full search equivalent algorithms accelerate the pattern matching process and, in the meantime, yield exactly the same result as the full search. This paper proposes an analysis and comparison of state-of-the-art algorithms for full search equivalent pattern matching. Our intention is that the data sets and tests used in our evaluation will be a benchmark for testing future pattern matching algorithms, and that the analysis concerning state-of-the-art algorithms could inspire new fast algorithms. We also propose extensions of the evaluated algorithms and show that they outperform the original formulations.
模式匹配在信号处理、计算机视觉以及图像和视频处理中得到了广泛的应用。全搜索等效算法加速了模式匹配过程，同时产生与全搜索完全相同的结果。本文对全搜索等效模式匹配的最新算法进行了分析和比较。我们的目的是，我们在评估中使用的数据集和测试将成为未来模式匹配算法的测试基准，并且对现有算法的分析可以启发新的快速算法。我们还提出了评估算法的扩展，并表明它们优于原始公式。
