- Algorithme de Karp-Miller-Rosenberg
-
L'algorithme de Karp-Miller-Rosenberg est un algorithme de détection de répétitions dans une structure de données (chaînes de caractères, arbres, tableaux). Il est l'œuvre de Richard Karp, Raymond Miller et Arnold Rosenberg et date de 1972[1].
La version originelle de l'algorithme KMR est séquentielle. Sa complexité est quasi-linéaire en la taille de la structure en entrée. La version originelle a été dépassée par d'autres algorithmes. Cependant, l'adaptation de l'algorithme KMR en une version parallélisée est efficace[2]. Il existe aussi une version généralisée de l'agorithme KMR qui prend plusieurs chaînes de caractères en entrée[3].
Références
- Richard M. Karp, Raymond E. Miller, Arnold L. Rosenberg, Rapid identification of repeated patterns in strings, trees and arrays, in Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972, pp. 125-136. DOI:10.1145/800152.804905.
- Maxime Crochemore, Wojciech Rytter, Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Theoretical Computer Science, vol. 88, no. 1, sept. 1991, pp. 59-82. DOI:10.1016/0304-3975(91)90073-B.
- Anne M. Landraud, Jean-François Avril, Philippe Chrétienne, An Algorithm for Finding a Common Structure Shared by a Family of Strings, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 8, Aug. 1989, pp. 890-895. DOI:10.1109/34.31450.
Catégorie :- Algorithme sur les chaînes de caractères
Wikimedia Foundation. 2010.
