Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper considers various flavors of the following online problem: preprocess a text or collection of strings, so that given a query string p, all matches of p with the text can be reported quickly. In this paper we consider matches in which a bounded number of mismatches are allowed, or in which a bounded number of "don't care" characters are allowed. The specific problems we look at are: indexing, in which there is a single text t, and we seek locations where p matches a substring of t; dictionary queries, in which a collection of strings is given upfront, and we seek those strings which match p in their entirety; and dictionary matching, in which a collection of strings is given upfront, and we seek those substrings of a (long) p which match an original string in its entirety. These are all instances of an all-to-all matching problem, for which we provide a single solution.The performance bounds all have a similar character. For example, for the indexing problem with n=|t| and m=|p|, the query time for k substitutions is O(m + (c1 log n)^k⁄k! + # matches), with a data structure of size O(n (c2 log n)^k⁄k!) and a preprocessing time of O(n (c2 log n)^k⁄k!), where c1,c2 > 1 are constants. The deterministic preprocessing assumes a weakly nonuniform RAM model; this assumption is not needed if randomization is used in the preprocessing.

REFERENCES

• 1: Karl Abrahamson, Generalized string matching, SIAM Journal on Computing, v.16 n.6, p.1039-1051, December 1, 1987 [doi>10.1137/0216067]
• 2: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 3: Tatsuya Akutsu, Approximate string matching with don't care characters, Information Processing Letters, v.55 n.5, p.235-239, Sept. 15, 1995 [doi>10.1016/0020-0190(95)00111-O]
• 4: T. Akutsu. Approximate string matching with variable length don't care characters. IEICE Trans. Information and Systems, E79-D:1353--1354, 1996.
• 5: Amihood Amir , Martin Farach, Adaptive dictionary matching, Proceedings of the 32nd annual symposium on Foundations of computer science, p.760-766, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185445]
• 6: Amihood Amir , Martin Farach , Zvi Galil , Raffaele Giancarlo , Kunsoo Park, Dynamic dictionary matching, Journal of Computer and System Sciences, v.49 n.2, p.208-222, Oct. 1994 [doi>10.1016/S0022-0000(05)80047-9]
• 7: Amihood Amir , Martin Farach , Ramana M. Idury , Johannes A. La Poutré , Alejandro A. Schäffer, Improved dynamic dictionary matching, Information and Computation, v.119 n.2, p.258-282, June 1995 [doi>10.1006/inco.1995.1090]
• 8: Amihood Amir , Dmitry Keselman , Gad M. Landau , Moshe Lewenstein , Noa Lewenstein , Michael Rodeh, Text indexing and dictionary matching with one error, Journal of Algorithms, v.37 n.2, p.309-325, Nov. 2000 [doi>10.1006/jagm.2000.1104]
• 9: A. Amir, G. Landau, M. Lewenstein and D. Sokol. Dynamic pattern, static text matching. Submitted for journal publication; preliminary version, Proc. of Workshop on Algorithms and Data Structures, 2003, 340--352.
• 10: Amihood Amir , Moshe Lewenstein , Ely Porat, Faster algorithms for string matching with k mismatches, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.794-803, January 09-11, 2000, San Francisco, California, United States
• 11: Amihood Amir , Ely Porat , Moshe Lewenstein, Approximate subset matching with Don't Cares, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.305-306, January 07-09, 2001, Washington, D.C., United States
• 12: Gerth Stølting Brodal , Leszek Gasieniec, Approximate Dictionary Queries, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.65-74, June 10-12, 1996
• 13: Gerth Stølting Brodal , S. Venkatesh, Improved bounds for dictionary look-up with one error, Information Processing Letters, v.75 n.1-2, p.57-59, July 2000 [doi>10.1016/S0020-0190(00)00079-X]
• 14: Adam L. Buchsbaum , Michael T. Goodrich , Jeffery Westbrook, Range Searching Over Tree Cross Products, Proceedings of the 8th Annual European Symposium on Algorithms, p.120-131, September 05-08, 2000
• 15: Richard Cole , Ramesh Hariharan, Approximate string matching: a simpler faster algorithm, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.463-472, January 25-27, 1998, San Francisco, California, United States
• 16: Richard Cole , Ramesh Hariharan, Verifying candidate matches in sparse and wildcard matching, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509992]
• 17: M. Farach, Optimal suffix tree construction with large alphabets, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.137, October 19-22, 1997
• 18: Paolo Ferragina , S. Muthukrishnan , Mark de Berg, Multi-method dispatching: a geometric approach with applications to string matching problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.483-491, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301378]
• 19: M. J. Fischer and M. S. Paterson. String matching and other products. Complexity of Computation, R. M. Karp (editor), SIAM-AMS Proceedings, 7:113--125, 1974.
• 20: Z Galil , R Giancarlo, Improved string matching with k mismatches, ACM SIGACT News, v.17 n.4, p.52-54, Spring 1986 [doi>10.1145/8307.8309]
• 21: D. Greene, M. Parnas and F. Yao. Multi-index hashing for information retrieval. Proc. of the Symposium on the Foundations of Computer Science, 1994, 722--731.
• 22: Roberto Grossi , Jeffrey Scott Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.397-406, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335351]
• 23: Torben Hagerup , Peter Bro Miltersen , Rasmus Pagh, Deterministic dictionaries, Journal of Algorithms, v.41 n.1, p.69-85, October 2001 [doi>10.1006/jagm.2001.1171]
• 24: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 25: Ramana M. Idury , Alejandro A. Schäffer, Dynamic Dictionary Matching with Failure Functions (Extended Abstract), Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.276-287, April 29-May 01, 1992
• 26: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 27: Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces, SIAM Journal on Computing, v.30 n.2, p.457-474, 2000 [doi>10.1137/S0097539798347177]
• 28: G M Landau , U Vishkin, Efficient string matching with k mismatches, Theoretical Computer Science, v.43 n.2-3, p.239-249, July 1986
• 29: G. M. Landau , U. Vishkin, Fast parallel and serial approximate string matching, Journal of Algorithms, v.10 n.2, p.157-169, June 1989 [doi>10.1016/0196-6774(89)90010-2]
• 30: Udi Manber , Sun Wu, An algorithm for approximate membership checking with application to password security, Information Processing Letters, v.50 n.4, p.191-197, May 25, 1994 [doi>10.1016/0020-0190(94)00032-8]
• 31: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 32: K. Mehlhorn. Data Structures and Efficient Algorithms, Vol. 1: Sorting and Searching, pp. 177--178. Springer Verlag, EATCS Monographs, 1984.
• 33: M. Minsky and S. Papert. Perceptrons. MIT Press, Cambridge, Mass., 1969.
• 34: S. C. Sahinalp , U. Vishkin, Efficient approximate and dynamic matching of patterns using a labeling paradigm, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.320, October 14-16, 1996
• 35: Baruch Schieber , Uzi Vishkin, On finding lowest common ancestors: simplification and parallelization, SIAM Journal on Computing, v.17 n.6, p.1253-1262, Dec. 1988 [doi>10.1137/0217079]
• 36: Shashi Shekhar , Sanjay Chawla , Siva Ravada , Andrew Fetterer , Xuan Liu , Chang-tien Lu, Spatial Databases-Accomplishments and Research Needs, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.45-55, January 1999 [doi>10.1109/69.755614]
• 37: E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14:249--260, 1995.
• 38: P. Weiner. Linear pattern matching algorithm. Proc. of the Symposium on Switching and Automata Theory, 1973, 1--11.
• 39: D. E. Willard. Log-logarithmic worst-case range queries are possible in space θ(n). Information Processing Letters, 17(2):81--84, 1983.
• 40: Andrew C. Yao , Frances F. Yao, Dictionary look-up with one error, Journal of Algorithms, v.25 n.1, p.194-202, Oct. 1997 [doi>10.1006/jagm.1997.0875]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms

Keywords:
approximate pattern matching, dictionary matching, dictionary query, suffix trees, text indexing, wildcards