Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2003 | Vol. 56, nr 1,2 | 89-103
Tytuł artykułu

Speeding-up Hirschberg and Hunt-Szymanski LCS Algorithms

Wybrane pełne teksty z tego czasopisma
Warianty tytułu
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
Wydawca

Rocznik
Strony
89-103
Opis fizyczny
Bibliogr. 21 poz.., wykr.
Twórcy
autor
  • Department of Computer Science, King's College London, London WC2R 2LS.England, mac@univ-mlv.fr
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS2-0004-0125
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.