Abstract
We present an index to search a two-dimensional pattern of size m × m in a two-dimensional text of size n × n, even when the pattern appears rotated in the text. The index is based on (path compressed) tries. By using O(n 2) (i.e. linear) space the index can search the pattern in O((logσ n)5/2) time on average, where σ is the alphabet size. We also consider various schemes for approximate matching, for which we obtain either O(polylogσn) or O(n 2λ) search time, where λ < 1 in most useful cases. A larger index of size O(n 2(logσ n)3/2) yields an average time of O(logσ n) for the simplest matching model. The algorithms have applications e.g. in content based information retrieval from image databases.
Work supported by ComBi.
Work developed while the author was in a postdoctoral stay at the Dept. of Computer Science, Univ. of Helsinki. Partially supported by the Academy of Finland and Fundación Andes.
Work supported by the Academy of Finland.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
A. Amir, G. Benson, and M. Farach. Alphabet independent two dimensional matching. In N. Alon, editor, Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, pages 59–68, Victoria, B.C., Canada, May1992. ACM Press.
A. Amir. Multidimensional pattern matching: A survey. Technical Report GIT-CC-92/29, Georgia Institute of Technology, College of Computing, 1992.
K. Fredriksson and E. Ukkonen. A rotation invariant filter for two-dimensional string matching. In Proceedings of the 9th Annual Symposium on Combinatorial Pattern Matching (CPM’98), LNCS 1448, pages 118–125, 1998.
K. Fredriksson and E. Ukkonen. Algorithms for 2-d hamming distance under rotations. Manuscript, 1999.
K. Fredriksson and E. Ukkonen. Combinatorial methods for approximate image matching under translations and rotations. Pattern Recognition Letters, 20(11–13):1249–1258, 1999.
K. Fredriksson and E. Ukkonen. Combinatorial methods for approximate pattern matching under rotations and translations in 3D arrays. Submitted, 2000.
Z. Galil and K. Park. Truly alphabet-independent two-dimensional pattern matching. In IEEE, editor, Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 247–257, Pittsburgh, PN, October1992. IEEE Computer Society Press.
R. Giancarlo. A generalization of suffix trees to square matrices, with applications. SIAM J. on Computing, 24:520–562, 1995.
R. Giancarlo and R. Grossi. On the construction of classes of suffix trees for square matrices: Algorithms and applications. Information and Computation, 130:151–182, 1996.
G. H. Gonnet. Efficient searching of text and pictures. Report OED-88-02, University of Waterloo, 1988.
J. Kärkkäinen and E. Ukkonen. Two and higher dimensional pattern matching in optimal expected time. In Daniel D. Sleator, editor, Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 715–723, Arlington, VA, January 1994. ACM Press.
G. M. Landau and U. Vishkin. Pattern matching in a digitized image. Algorithmica, 12(4/5):375–408, October 1994.
G. Navarro and R. Baeza-Yates. Fast multi-dimensional approximate string matching. In Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching (CPM’99), LNCS, pages 243–257, 1999.
T. Takaoka. Approximate pattern matching with grey scale values. In Michael E. Houle and Peter Eades, editors, Proceedings of Conference on Computing: The Australian Theory Symposium, pages 196–203, Townsville, January 29-30 1996. Australian Computer Science Communications.
J. Tarhio. A sublinear algorithm for two-dimensional string matching. PRL: Pattern Recognition Letters, 17, 1996.
J. Wood. Invariant pattern recognition: a review. Pattern Recognition, 29(1):1–17, 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fredriksson, K., Navarro, G., Ukkonen, E. (2000). An Index for Two Dimensional String Matching Allowing Rotations. In: van Leeuwen, J., Watanabe, O., Hagiya, M., Mosses, P.D., Ito, T. (eds) Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics. TCS 2000. Lecture Notes in Computer Science, vol 1872. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44929-9_5
Download citation
DOI: https://doi.org/10.1007/3-540-44929-9_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67823-6
Online ISBN: 978-3-540-44929-4
eBook Packages: Springer Book Archive