Gene Myers
Abstract
The approximate string matching problem is to find all locations at which a query of lengthm matches a substring of a text of length n with k-or-fewer differences. Simple and practical bit-vector algorithms have been designed for this problem, most notably the one used in agrep. These algorithms compute a bit representation of the current state-set of the k-difference automaton for the query, and asymptotically run in either O(nm/w) or O(nm log σ/w) time where w is the word size of the machine (e.g., 32 or 64 in practice), and σ is the size of the pattern alphabet. Here we present an algorithm of comparable simplicity that requires only O(nm/w) time by virtue of computing a bit representation of the relocatable dynamic programming matrix for the problem. Thus, the algorithm's performance is independent of k, and it is found to be more efficient than the previous results for many choices of k and smallm.
Moreover, because the algorithm is not dependent on k, it can be used to rapidly compute blocks of the dynamic programming matrix as in the 4-Russians algorithm of Wu et al.(1996). This gives rise to an O(kn/w) expected-time algorithm for the case where m may be arbitrarily large. In practice this new algorithm, that computes a region of the dynamic progr amming (d.p.) matrx w entries at a time using the basic algorithm as a subroutine is significantly faster than our previous 4-Russians algorithm, that computes the same region 4 or 5 entries at a time using table lookup. This performance improvement yields a code that is either superior or competitive with all existing algorithms except for some filtration algorithms that are superior when k/m is sufficiently small.
- BAEZA-YATES, R. A., AND GONNET, G.H. 1992. A new approach to text searching. Commun. A CM 35, 74-82. Google Scholar
- BAEZA-YATES, R. A., AND NAVARRO, G. 1996. A faster algorithm for approximate string matching. In Proceedings of the 7th Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, Vol. 1075. Springer-Verlag, New York, pp. 1-23. Google Scholar
- BAEZA-YATES, R.A. AND NAVARRO, G. 1999. Analysis for algorithm engineering: Improving an algorithm for approximate pattern matching. Unpublished manuscript.Google Scholar
- CHAO, K.M., HARDISON, R.C., AND MILLER, W. 1992. Recent developments in linear-space alignment methods: A survey. J. Comput. Biol. 1, 271-291.Google Scholar
- CHANG, W. I., AND LAMPE, J. 1992. Theoretical and empirical comparisons of approximate string matching algorithms. In Proceedings of the 3rd Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 644. Springer-Verlag, New York, pp. 172-181. Google Scholar
- CHANG, W.I. AND LAWLER, E.L. 1994. Sublinear expected time approximate matching and biological applications. Algorithmica 12, 327-344.Google Scholar
- CHAO, K.M., HARDISON, R.C., AND MILLER, W. 1992. Recent developments in linear-space alignment methods: A survey. J. Comput. Biol. 1, 271-291.Google Scholar
- CHAO, K. M., PEARSON, W. R., AND MILLER, W. 1992. Aligning two sequences within a specified diagonal band. Comput. Appl. BioSciences 8, 481-487.Google Scholar
- COBBS, A. 1995. Fast approximate matching using suffix trees. In Proceedings of the 6th Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 937. Springer-Verlag, New York, pp. 41-54.Google Scholar
- GALm, Z., AND PARK, K. 1990. An improved algorithm for approximate string matching. SIAM J. Comput. 19, 989-999. Google Scholar
- LANDAU, G. M., AND VISHKIN, U. 1988. Fast string matching with k differences. J. Comput. Syst. Sci. 37, 63-78. Google Scholar
- MASEK, W. J., AND PATERSON, M.S. 1980. A faster algorithm for computing string edit distances. J. Comput. Syst. Sci. 20, 18-31.Google Scholar
- MYERS, E.W. 1994. A sublinear algorithm for approximate keywords searching. Algorithmica 12, 345-374.Google Scholar
- PEVZNER, P., AND WATERMAN, M.S. 1995. Multiple filtration and approximate pattern matching. Algorithmica 13, 135-154.Google Scholar
- SELLERS, P.H. 1980. The theory and computations of evolutionary distances: Pattern recognition. J. Algorithms 1,359-373.Google Scholar
- SUTINEN, E., AND TARHIO, J. 1996. Filtration with q-samples in approximate string matching. In Proceedings of the 7th Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 1075. Springer-Verlag, New York, pp. 50-63. Google Scholar
- UKKONEN, E. 1985. Finding approximate patterns in strings. J. Algorithms 6, 132-137.Google Scholar
- UKKONEN, E. 1992. Approximate string-matching with q-grams and maximal matches. Theoret. Comput. Sci. 92, 191-211. Google Scholar
- UKKONEN, E. 1993. Approximate string matching over suffix trees. In Proceedings of the 4th Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 684. Springer-Verlag, New York, pp. 228-242. Google Scholar
- WAGNER, R.A., AND FISCHER, M.J. 1974. The string to string correction problem. J. ACM 21, 168-173. Google Scholar
- Wu, S., AND MANBER, U. 1992. Fast text searching allowing errors. Commun. ACM 35, 10, 83-91. Google Scholar
- Wu, S., MANBER, U., AND MYERS, G. 1996. A subquadratic algorithm for approximate limited expression matching. Algorithmica 15, 50-67.Google Scholar
- WRIGHT, A.H. 1994. Approximate string matching using within-word parallelism. Soft. Pract. Exper. 24, 337-362. Google Scholar
Index Terms
- A fast bit-vector algorithm for approximate string matching based on dynamic programming
Recommendations
A fast bit-parallel multi-patterns string matching algorithm for biological sequences
ISB '10: Proceedings of the International Symposium on BiocomputingThe problem of searching occurrences of a pattern P[0...m-1] in the text T[0...n-1>with m ≤ n, where the symbols of P and T are drawn from some alphabet Σ of size σ, is called exact string matching problem. In the present day, pattern matching is a ...
Increased bit-parallelism for approximate and multiple string matching
Bit-parallelism permits executing several operations simultaneously over a set of bits or numbers stored in a single computer word. This technique permits searching for the approximate occurrences of a pattern of length m in a text of length n in time O(...
Bit-Parallel Witnesses and Their Applications to Approximate String Matching
We present a new bit-parallel technique for approximate string matching. We build on two previous techniques. The first one, BPM (Myers, 1999), searches for a pattern of length m in a text of length n permitting k differences in $O(\lceil m/w \rceil n)$ ...
Comments