Complexité de Lempel-Ziv
mesure de complexité en mathématiques / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Complexité de Lempel-Ziv?
Résumez cet article pour un enfant de 10 ans
La complexité de Lempel-Ziv est présentée pour la première fois dans l'article On the Complexity of Finite Sequences (IEEE Trans. On IT-22,1 1976), par deux informaticiens israéliens, Abraham Lempel et Jacob Ziv. Cette mesure de complexité est liée à la complexité de Kolmogorov, mais elle n'utilise comme seule fonction que la copie récursive.
Le mécanisme mis en œuvre dans cette mesure de complexité est à l'origine des algorithmes de compression de données sans perte LZ77, LZ78 et LZW. Bien que ne reposant que sur un principe élémentaire de recopie de mots, cette mesure de complexité n'est pas trop restrictive en ce sens qu'elle respecte les principales qualités attendues d'une telle mesure : elle n'octroie pas aux séquences avec certaines régularités une grande complexité et cette complexité est d'autant plus grande que la séquence est longue et peu régulière.