Speeding-up Hirschberg and Hunt-Szymanski LCS Algorithms

• Autorzy: Crochemore, M. , Iliopoulos, C.S. , Pinzon, Y.J.
• Języki publikacji: EN

Abstrakty

EN

Two algorithms are presented that solve the problem of recovering the longest common subsequence of two strings. The first algorithm is an improvement of Hirschberg's divide-and-conquer algorithm. The second algorithm is an improvement of Hunt-Szymanski algorithm based on an efficient computation of all dominant match points. These two algorithms use bit-vector operations and are shown to work very efficiently in practice.

Słowa kluczowe

EN

longest common subsequence; bit-parallelism

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 56, nr 1,2
• Strony: 89-103
• Opis fizyczny: Bibliogr. 21 poz.., wykr.

Twórcy

autor

Crochemore, M.

autor

Iliopoulos, C.S.

autor

Pinzon, Y.J.

• Department of Computer Science, King's College London, London WC2R 2LS.England,

Bibliografia

• [1] A. Apostolico, Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings, Inform. Process. Lett., 23, 63-69, 1986.
• [2] A. Apostolico and C. Guerra, The longest common subsequence problem revisited, Algorithmica, 2, 315-336, 1987.
• [3] R. A. Baeza-Yates and G. H. Gonnet, A new approach to text searching, Comm. Assoc. Comput. Mach., 35, 74-82, 1992.
• [4] R. A. Baeza-Yates and G. Navarro, A faster algorithm for approximate string matching, Proceedings of the 3rd Symp. on Combinatorial Pattern Matching, LNCS 1075, 1-23, 1996.
• [5] M. Crochemore, C. S. Iliopoulos, Y. J. Pinzon and J. F. Reid, A fast bit-vector algorithm for the longest common subsequence problem, Proceedings of the 11th Australasian Workshop on Combinatorial Algorithms AWOCA’00, 74-82, 2000.
• [6] M. Crochemore, C. S. Iliopoulos, Y. J. Pinzon and J. F. Reid, A fast bit-vector algorithm for the longest common subsequence problem, Inform. Process. Lett., 80(6), 2001, pp. 279-285, 2001.
• [7] V. Danˇc´ık, Expected length of the longest common subsequences, PhD thesis, University of Warwick, 1994.
• [8] D.S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Comm. Assoc. Comput. Mach., 18:6, 341-343, 1975.
• [9] D.S. Hirschberg, Algorithms for the longest common subsequence problem, J. Assoc. Comput. Mach., 24:4, 664-675, 1977.
• [10] J.W. Hunt and T.G. Szymanski, A fast algorithm for computing longest common subsequences, Comm. Assoc. Comput. Mach., 20, 350-353, 1977.
• [11] V.I. Levenshtein, Binary codes capable of correcting deletions, insertions and reversals, Sov. Phys. Dokl., 6, 707-710, 1966.
• [12] U. Manber, E. Myers and S. Wu, A subquadratic algorithm for approximate limited expression matching, Algorithmica, 15, 50-67, 1996.
• [13] W.J. Masek and M.S. Paterson, A faster algorithm computing string edit distances, J. Comput. System Sci., 20, 18-31, 1980.
• [14] E. Myers, A fast bit-vector algorithm for approximate string matching based on dynamic programming, J. Assoc. Comput. Mach., 46:3, 395-415, 1999.
• [15] G. Navarro and M. Raffinot, A bit-parallel approach to suffix automata: fast extended string matching, Combinatorial Pattern Matching, LNCS 1448, 14-33, 1998.
• [16] N. Nakatsu, Y. Kambayashi, S. Yajima, A Longest common subsequence algorithm suitable for similar test strings, Acta Informatica, 18, 171-179, 1982.
• [17] M. Paterson, V. Danˇc´ık, Longest common subsequence, Proceedings of the 19th Intern. Symp. on Mathematical Foundations of Computer Science, LNCS 841, 127-142, 1994.
• [18] D. Sankoff and J.B. Kruskal (eds), Time warps, string edits, and macromolecules: the theory and practice of sequence comparison, Addison-Wesley, Reading, MA, 1983.
• [19] D. Sankoff and P.H. Sellers, Shortcuts, diversions and maximal chains in partially ordered sets, Discrete Mathematics, 4, 287-293, 1973.
• [20] R.A. Wagner and M.J. Fisher, The string-to-string correction problem, J. Assoc. Comput. Mach., 21:1, 168-173, 1974.
• [21] S. Wu and U. Manber, Fast text searching allowing errors, Comm. Assoc. Comput. Mach., 35, 83-91, 1992.