|
La compression par antidictionnaire est basée sur l'utilisation des mots interdits. La méthode et les algorithmes utilisés permettent d'atteindre l'entropie sur des fichiers binaires équilibrés. Un autre avantage est qu'ils permettent de produire de très rapide décompresseur. Notre premier travail a consisté à trouver pour un fichier donné son antidictionnaire. C'est à dire l'ensemble de tous les mots binaires (puisque ce sont les mots les plus élémentaires) qui n'apparaissent pas dans le fichier. De cet ensemble de mots nous ne gardons ensuite que les mots minimaux, c'est à dire que nous rejettons les mots possédant un autre mot de cet antidictionnaire comme suffixe. Une fois l'antidictionnaire minimal réalisé, nous pouvons compresser le fichier : On parcours le fichier source et à chaque bit lu on regarde si l'antidictionnaire nous permet de deviner le bit suivant. Si c'est le cas, ce bit n'a pas besoin d'être écrit dans le fichier compressé. Sinon il devra etre écrit. --- Comment savoir si l'on peut deviner le bit suivant ? --- Lors du parcours du fichier source (bit par bit), on rajoute virtuellement le bit `1` à la fin de l'expression binaire jusqu'alors lue, et l'on regarde si cette nouvelle expression possède un suffixe appartenant à l'antidictionnaire. Si c'est la cas, cela signifie que notre suffixe se terminant par un `1` ne peut appartenir au texte. Par conséquent, dans notre exemple, le bit suivant est un `0` (puisque c'est la seule facon que le suffixe trouvé n'apparaisse pas dans le texte). Si aucun suffixe n'est trouvé alors on recommence en rajoutant cette fois-ci un `0` virtuel (à la place du `1`). Et suivant le même principe : si l'on trouve un suffixe appartenant à l'antidictionnaire, c'est que le bit suivant doit être un `1`. Et si aucun suffixe n'est trouvé, c'est qu'on ne peut pas le deviner. Il ne reste plus maintenant qu'à écrire dans un fichier l'expression binaire trouvée ainsi que les mots de l'antidictionnaire utilisés (et seulement ceux-ci). |