×

Calcul de la distance par les sous-mots. (Computing the distance by subwords). (French) Zbl 0639.68063

Summary: This paper gives two methods to compute the shortest subsequence which distinguishes two different words u and v. The use of automata together with data structures for “union-find” questions leads to an algorithm almost linear in the length of uv.

MSC:

68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] AHU 74. A. V. AHO, J. E. HOPCROFT et J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974. Zbl0326.68005 MR413592 · Zbl 0326.68005
[2] CC 82. A. CARDON et M. CROCHEMORE, Partitioning a graph in O ( | A | log2 | V | ), Theor. Comput. Sci. vol. 19, 1982, p. 85-98. Zbl0478.68067 MR664414 · Zbl 0478.68067 · doi:10.1016/0304-3975(82)90016-0
[3] He 84. J. J. HEBRARD, Distances sur les mots. Application à la recherche de motifs, Thèse de 3e cycle, Université de Haute-Normandie, 1984.
[4] Hi 77. D. S. HIRSCHBERG, Algorithmes for the Longest Common Subsequence Problem, J. Assoc. Comput. Mach., vol. 24, 1977, p. 664-675. Zbl0402.68041 MR461985 · Zbl 0402.68041 · doi:10.1145/322033.322044
[5] HS 77. J. W. HUNT et T. G. SZYMANSKI, A Fast Algorithm for Computing Longest Common Subsequences, Comm. ACM., vol. 20, 1977, p. 350-353. Zbl0354.68078 MR436655 · Zbl 0354.68078 · doi:10.1145/359581.359603
[6] Lo 82. LOTHAIRE, Combinatorics on Words, Addition-Wesley, Reading, Mass., 1982. Zbl0514.20045 · Zbl 0514.20045
[7] Mo 70 H. L. MORGAN, Spelling Correction in Systems Programs, Comm. ACM., vol. 13, 1970, p. 90-94. Zbl0185.43403 · Zbl 0185.43403 · doi:10.1145/362007.362033
[8] M P 80. W. J. MASEK et M. S. PATERSON, A Faster Algorithm Computing String Edit Distances, J. Comput. and Sys. Sci., vol. 20, 1980, p. 18-31. Zbl0436.68044 MR566639 · Zbl 0436.68044 · doi:10.1016/0022-0000(80)90002-1
[9] NKY 82. N. NAKATSU, Y. KAMBAYASHI et S. YAJIMA, A Longest Common Subsequence Algorithm Suitable for Similar Test Strings, Acta Informatica, vol. 18, 1982, p. 171-179. Zbl0493.68041 MR687701 · Zbl 0493.68041 · doi:10.1007/BF00264437
[10] Se 74. P. H. SELLERS, An Algorithm for the Distance between two Finite Sequences, J. Combinatorial Theory, Series A, vol. 16, 1974, p. 253-258. Zbl0273.05015 MR342404 · Zbl 0273.05015 · doi:10.1016/0097-3165(74)90050-8
[11] Si 84. I. SIMON, An Algorithm to Distingsh Words Efficiently by their Subwords Communication at ”Combinatorial Algorithms on words” conference Maratea(1984).
[12] SK 83. D. SANKOFF et J. B. KRUSKAL, Time Warps, String Edits, and Macromolecules : the Theory and Practice of Sequence Comparison, Addison-Wesley, Reading, Mass., 1983. MR726027
[13] WF. 74. R. A. WAGNER et M. J. FISCHER, The String to String Correction Problem, J. Assoc. Comput. Mach., vol. 21, 1974, p. 168-173. Zbl0278.68032 MR356576 · Zbl 0278.68032 · doi:10.1145/321796.321811
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.