The string edit distance matching problem with moves

ABSTRACT

The edit distance between two strings S and R is defined to be the minimum number of character inserts, deletes and changes needed to convert R to S. Given a text string t of length n, and a pattern string p of length m, informally, the string edit distance matching problem is to compute the smallest edit distance between p and substrings of t. A well known dynamic programming algorithm takes time O(nm) to solve this problem, and it is an important open problem in Combinatorial Pattern Matching to significantly improve this bound.We relax the problem so that (a) we allow an additional operation, namely, substring moves, and (b) we approximate the string edit distance upto a factor of O(log n log*n). Our result is a near linear time deterministic algorithm for this version of the problem. This is the first known significantly subquadratic algorithm for a string edit distance problem in which the distance involves nontrivial alignments. Our results are obtained by embedding strings into L1 vector space using a simplified parsing technique we call Edit Sensitive Parsing (ESP). This embedding is approximately distance preserving, and we show many applications of this embedding to string proximity problems including nearest neighbors, outliers, and streaming computations with strings.

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: Stephen Alstrup , Gerth Stølting Brodal , Theis Rauhe, Pattern matching in dynamic texts, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.819-828, January 09-11, 2000, San Francisco, California, United States
• 3: 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
• 4: 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
• 5: Graham Cormode , Mike Paterson , Süleyman Cenk Sahinalp , Uzi Vishkin, Communication complexity of document exchange, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.197-206, January 09-11, 2000, San Francisco, California, United States
• 6: R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12151]
• 7: {Gal85} Z. Galil. Open problems in stringology. In Combinatorial Algorithms on Words, pages 1-8. Springer, 1985.
• 8: Ashish Goel , Piotr Indyk , Kasturi Varadarajan, Reductions among high dimensional proximity problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.769-778, January 07-09, 2001, Washington, D.C., United States
• 9: A. Goldberg , S. Plotkin , G. Shannon, Parallel symmetry-breaking in sparse graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.315-324, January 1987, New York, New York, United States [doi>10.1145/28395.28429]
• 10: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 11: 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]
• 12: Howard Karloff, Fast algorithms for approximately counting mismatches, Information Processing Letters, v.48 n.2, p.53-60, Nov. 8, 1993 [doi>10.1016/0020-0190(93)90177-B]
• 13: Richard M. Karp , Raymond E. Miller , Arnold L. Rosenberg, Rapid identification of repeated patterns in strings, trees and arrays, Proceedings of the fourth annual ACM symposium on Theory of computing, p.125-136, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804905]
• 14: Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276877]
• 15: Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
• 16: G M Landau , U Vishkin, Introducing efficient parallelism into approximate string matching and a new serial algorithm, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.220-230, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12152]
• 17: {MP80} W. J. Masek and M. S. Paterson. A faster algorithm computing string edit distances. Journal of Computer and System Sciences, 20:18-31, 1980.
• 18: S. Muthukrishnan , Süleyman Cenk Sahinalp, Approximate nearest neighbors and sequence comparison with block operations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.416-424, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335353]
• 19: {MSU97} K. Mehlhorn, R. Sundar, and C. Uhrig. Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica, 17(2):183-198, February 1997.
• 20: {Mye86} E. W. Myers. An O(ND) difference algorithm and its variations. Algorithmica, 1:251-256, 1986.
• 21: Sühleyman Cenk Sahinalp , Uzi Vishkin, Symmetry breaking for suffix tree construction, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.300-309, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195164]
• 22: {SV95} S. C. Sahinalp and U. Vishkin. Data compression using locally consistent parsing, 1995.
• 23: 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