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 L. Rosenberg et date de 1972[1].
La version originelle de l'algorithme KMR est séquentielle. Sa complexité en temps 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'algorithme 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.
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.