A sublinear algorithm for weakly approximating edit distance

ABSTRACT

We show how to determine whether the edit distance between two given strings is small in sublinear time. Specifically, we present a test which, given two n-character strings A and B, runs in time o(n) and with high probability returns "CLOSE" if their edit distance is O(n^Α), and "FAR" if their edit distance is Ω(n), where Α is a fixed parameter less than 1. Our algorithm for testing the edit distance works by recursively subdividing the strings A and B into smaller substrings and looking for pairs of substrings in A, B with small edit distance. To do this, we query both strings at random places using a special technique for economizing on the samples which does not pick the samples independently and provides better query and overall complexity. As a result, our test runs in time Õ(n^{max(Α/2, 2Α - 1\)}) for any fixed Α < 1. Our algorithm thus provides a trade-off between accuracy and efficiency that is particularly useful when the input data is very large.We also show a lower bound of Ω(n^Α/2) on the query complexity of every algorithm that distinguishes pairs of strings with edit distance at most n^Α from those with edit distance at least n/6.

REFERENCES

• 1: W. Chang and E. Lawler. Approximate string matching in sublinear expected time. In Proceedings of the 31st IEEE Annual Symposium on Foundations of Computer Science, pages 116--124, Saint Louis, Missouri, 1990. IEEE Computer Society Press.
• 2: 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
• 3: 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
• 4: 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]
• 5: W. J. Masek and M. S. Paterson. A faster algorithm computing string edit distances. Journal of Computer and System Sciences, 20:18--31, 1980.
• 6: E. W. Myers. A sublinear algorithm for approximate keyword searching. Algorithmica, 12(4/5):345--374, Oct./Nov. 1994.
• 7: 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

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
approximation, string matching, sublinear algorithms