Compression par dictionnaire
Cet article est une ébauche concernant l’informatique.
Cet article est une ébauche concernant l’informatique.
Les algorithmes de compression par dictionnaire (en anglais : dictionary coder) sont une classe d'algorithme de compression sans perte. Ils procèdent par la recherche de similitudes entre le texte à compresser (ou tout autre type de fichier à compresser) et un ensemble de chaines de caractères (ou tout autre type de donnée) contenues dans une structure de données appelée « dictionnaire » (souvent implémenté sous forme d'un trie). Quand une similitude est trouvée, le texte correspondant est remplacé par une référence vers l'emplacement de cette chaîne dans le « dictionnaire ».
Méthodes et applications
Pour le principe : on établit une liste de mots fréquents, pour compresser un fichier quand on trouve un mot dans la liste, on remplace ce mot par sa position dans la liste.
On peut trouver deux types de fonctionnement :
- un dictionnaire calculé une fois pour toutes ;
- un dictionnaire qui évolue.
Si on prend par exemple un texte en français, le français contenant environ 200 000 mots, pour coder l'ensemble de ces mots il suffirait en principe de 18 bits (218= 262144), un mot français contenant 5 caractères en moyenne(donc 40 bits), on pourrait gagner un facteur de l’ordre de 55%.
Exemples
Lempel-Ziv-Oberhumer (LZO) est un algorithme de compression de données se focalisant sur la vitesse de décompression sans pertes à dictionnaire.
Avec LZ78 nous avons un dictionnaire mis à jour progressivement, à chaque étape, on cherche le mot le plus court qui ne soit pas présent dans le dictionnaire, on écrit la position du mot trouvé ainsi que la lettre à ajouter, on écrit le nouveau mot dans le dictionnaire puis on continue à partir de la suite.
| Source | dans dictionnaire | adresse | ajout | valeur |
|---|---|---|---|---|
| A | non trouvé | 1 | A | (0,A) |
| v | non trouvé | 2 | v | (0,v) |
| e | non trouvé | 3 | e | (0,e) |
| c | non trouvé | 4 | c | (0,c) |
| non trouvé | 5 | " " | (0," ") | |
| L | non(trouvé | 6 | L | (0,L) |
| Z | non trouvé | 7 | Z | (0,Z) |
| 7 | non trouvé | 8 | 7 | (0,7) |
| 8 | non trouvé | 9 | 8 | (0,8) |
| trouvé en 5 | ||||
| n | non trouvé | 10 | n | (5,n) |
| o | non trouvé | 11 | o | (0,o) |
| u | non trouvé | 12 | u | (0,u) |
| s | non trouvé | 13 | s | (0,s) |
| trouvé en 5 | ||||
| a | non trouvé | 14 | a | (5,a) |
| v | trouvé en 2 | |||
| o | trouvé en 11 | |||
| n | trouvé en 10 | |||
| s | trouvé en 13 | |||
| trouvé en 5 | ||||
| u | trouvé en 12 | |||
| n | trouvé en 10 | |||
| trouvé en 5 | ||||
| d | non trouvé | 15 | d | (0,d) |
Références
https://members.loria.fr/EJeandel/files/Codage/02-2x2.pdf
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.