×

Parameterized matching on non-linear structures. (English) Zbl 1209.68167

Summary: The classical pattern matching paradigm is that of seeking occurrences of one string in another, where both strings are drawn from an alphabet set \(\Sigma \). In the parameterized pattern matching model, a consistent renaming of symbols from \(\Sigma \) is allowed in a match. The parameterized matching paradigm has proven useful in problems in software engineering, computer vision, and other applications. In classical pattern matching, both the text and pattern are strings. Applications such as searching in xml or searching in hypertext require searching strings in non-linear structures such as trees or graphs. There has been work in the literature on exact and approximate parameterized matching, as well as work on exact and approximate string matching on non-linear structures. In this paper we explore parameterized matching in non-linear structures. We prove that exact parameterized matching on trees can be computed in linear time for alphabets in an \(O(n)\)-size integer range, and in time \(O(n\log m)\) in general, where \(n\) is the tree size and \(m\) the pattern length. These bounds are optimal in the comparison model. We also show that exact parameterized matching on directed acyclic graphs (DAGs) is \(\mathcal {NP}\)-complete.

MSC:

68P10 Searching and sorting
68T10 Pattern recognition, speech recognition
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] T. Akutsu, A linear time pattern matching algorithm between a string and a tree, in: Proc. 4th Symp. on Combinatorial Pattern Matching (CPM), Padova, Italy, 1993, pp. 1-10; T. Akutsu, A linear time pattern matching algorithm between a string and a tree, in: Proc. 4th Symp. on Combinatorial Pattern Matching (CPM), Padova, Italy, 1993, pp. 1-10
[2] Amir, A.; Aumann, A.; Lewenstein, M.; Porat, E., Function matching, SIAM Journal on Computing, 35, 5, 1007-1022 (2006) · Zbl 1100.68123
[3] Amir, A.; Benson, G.; Farach, M., An alphabet independent approach to two dimensional pattern matching, SIAM Journal on Computing, 23, 2, 313-323 (1994) · Zbl 0804.68056
[4] A. Amir, K.W. Church, E. Dar, Separable attributes: A technique for solving the submatrices character count problem, in: Proc. 13th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2002, pp. 400-401; A. Amir, K.W. Church, E. Dar, Separable attributes: A technique for solving the submatrices character count problem, in: Proc. 13th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2002, pp. 400-401 · Zbl 1092.68714
[5] Amir, A.; Farach, M.; Muthukrishnan, S., Alphabet dependence in parameterized matching, Information Processing Letters, 49, 111-115 (1994) · Zbl 0795.68077
[6] Amir, A.; Lewenstein, N.; Lewenstein, M., Pattern matching in hypertext, Journal of Algorithms, 35, 82-99 (2000) · Zbl 0956.68043
[7] (Apostolico, A.; Galil, Z., Pattern Matching Algorithms (1997), Oxford University Press) · Zbl 0874.68006
[8] Apostolico, A.; Lewenstein, M.; Erdös, P., Parameterized matching with mismatches, Journal of Discrete Algorithms, 5, 1, 135-140 (2007) · Zbl 1139.68055
[9] Babu, G. P.; Mehtre, B. M.; Kankanhalli, M. S., Color indexing for efficient image retrieval, Multimedia Tools and Applications, 1, 4, 327-348 (1995)
[10] Baker, B. S., Parameterized pattern matching: Algorithms and applications, Journal of Computer and System Sciences, 52, 1, 28-42 (1996) · Zbl 0849.68019
[11] Baker, B. S., Parameterized duplication in strings: Algorithms and an application to software maintenance, SIAM Journal on Computing, 26, 5, 1343-1362 (1997) · Zbl 0885.68085
[12] Crochemore, M.; Rytter, W., Text Algorithms (1994), Oxford University Press · Zbl 0844.68101
[13] Fischer, M. J.; Paterson, M. S.; Karp, R. M., String matching and other products, Complexity of Computation. Complexity of Computation, SIAM-AMS Proceedings, 7, 113-125 (1974)
[14] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Co.: W.H. Freeman and Co. New York · Zbl 0411.68039
[15] C. Hazay, M. Lewenstein, D. Sokol, Approximate parameterized matching, in: Proc. 12th Annual European Symposium on Algorithms (ESA 2004), 2004, pp. 414-425; C. Hazay, M. Lewenstein, D. Sokol, Approximate parameterized matching, in: Proc. 12th Annual European Symposium on Algorithms (ESA 2004), 2004, pp. 414-425 · Zbl 1111.68795
[16] Idury, R. M.; Schäffer, A. A., Multiple matching of parameterized patterns, (Proc. 5th Combinatorial Pattern Matching (CPM). Proc. 5th Combinatorial Pattern Matching (CPM), LNCS, vol. 807 (1994), Springer-Verlag), 226-239 · Zbl 0873.68074
[17] D.K. Kim, K. Park, String matching in hypertext, in: Proc. 6th Symposium on Combinatorial Pattern Matching (CPM 95), 1995; D.K. Kim, K. Park, String matching in hypertext, in: Proc. 6th Symposium on Combinatorial Pattern Matching (CPM 95), 1995
[18] Knuth, D. E.; Morris, J. H.; Pratt, V. R., Fast pattern matching in strings, SIAM Journal on Computing, 6, 323-350 (1977) · Zbl 0372.68005
[19] U. Manber, S. Wu, Approximate string matching with arbitrary cost for text and hypertext, in: Proc. Internat. Workshop on Structural and Syntactic Pattern Recognition, 1992, pp. 22-33; U. Manber, S. Wu, Approximate string matching with arbitrary cost for text and hypertext, in: Proc. Internat. Workshop on Structural and Syntactic Pattern Recognition, 1992, pp. 22-33
[20] Navarro, G., Improved approximate pattern matching on hypertext, Theoretical Computer Science, 237, 455-463 (2000) · Zbl 0943.68181
[21] Swain, M.; Ballard, D., Color indexing, International Journal of Computer Vision, 7, 1, 11-32 (1991)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.