Multidimensional Pattern Matching

字符串匹配是计算机科学中的一个基本问题，也是研究最多的问题。 相比之下，多维匹配证明更难处理。 然而，多维模式匹配是许多重要应用的核心，从多媒体到计算分子生物学。 本研究开发了多维匹配理论，涉及到多维匹配的性质，和结果，如以下：更好的串行和并行算法的准确多维匹配;高效的算法旋转和近似匹配;和高效的算法近似字典匹配的新见解。 部分算法已在实际应用系统中实现。

String Matching is one of the fundamental and most studied problems in computer science. In contrast, multidimensional matching proved more difficult to tackle. However, multidimensional pattern matching is central to many important applications, from multimedia to computational molecular biology. This research develops a theory of multidimensional matching, involving new insights into the nature of multidimensional matching, and results such as the following: better serial and parallel algorithms for exact multidimensional matching; efficient algorithms for rotations and approximate matching; and efficient algorithms for approximate dictionary matching. Several of the algorithms have been implemented in some practical application systems.