116
3 Arbres, algorithmes et données
Par exemple, étant donné un texte aaaaaaaaaaaaaa... (ne contenant qu’une
longue suite du symbole a), les segments sont
LZ77 : | a | aa | aaaa | aaaaaaaa | . . .
LZ78 : | a | aa | aaa | aaaa | aaaaa | . . .
En d’autres termes, LZ77 définit comme nouveau segment le plus grand facteur
possible dans ce qui a déjà été lu, même si cela recouvre plusieurs segments.
L’algorithme LZ78 respecte les limites entre segments.
Pour LZ77, la transmission de chaque segment se fait grâce à un triplet du type
(position de l’occurrence reconnue, longueur du facteur, et bien sûr le
nouveau symbole). Pour LZ78, est transmis un couple (le rang du segment
trouvé dans le dictionnaire et le symbole à ajouter pour créer un nouveau segment).
La reconstruction du texte est simple puisqu’il suffit de réaliser « l’expansion des
références ».
Par exemple, les deux suites
LZ77 : <0,0,a> <0,0,b> <0,0,r> <1,1,c> <1,1,d> <1,4,†>,
LZ78 : <0,a> <0,b> <0,r> <1,c> <1,d> <1,b> <3,a> <0,†>,
encodent le texte «abracadabra†» (avec un symbole de terminaison † et en faisant
partir les indices de 0) et correspondent aux découpages en segments suivant :
LZ77 : | a | b | r | ac | ad | abra | †|,
LZ78 : | a | b | r | ac | ad | ab | ra | †|.
Dans l’exemple précédent, pour LZ78 et à la fin du processus, le dictionnaire est :
Rang 0 1 2 3 4
5
6
7
8
Mot
ε a b r ac ad ab ra †
Ainsi dans l’encodage LZ78 avec des couples, dans l’exemple précédent,
le couple <3, a> encode le 3ème segment du dictionnaire (r) suivi de la lettre a,
soit ra.
Pour LZ77, nous pourrions imaginer l’utilisation d’un trie des suffixes du texte
pour stocker efficacement tous les facteurs (en pratique, des structures de données
plus adaptées sont utilisées [227]). Pour LZ78, le processus de construction du
dictionnaire s’apparente à celui d’un arbre digital de recherche (DST). En effet
les nœuds d’un arbre digital de recherche construit à partir du texte sont en correspondance avec les phrases du dictionnaire (voir Jacquet et Szpankowski [145]).
3 Arbres, algorithmes et données
Par exemple, étant donné un texte aaaaaaaaaaaaaa... (ne contenant qu’une
longue suite du symbole a), les segments sont
LZ77 : | a | aa | aaaa | aaaaaaaa | . . .
LZ78 : | a | aa | aaa | aaaa | aaaaa | . . .
En d’autres termes, LZ77 définit comme nouveau segment le plus grand facteur
possible dans ce qui a déjà été lu, même si cela recouvre plusieurs segments.
L’algorithme LZ78 respecte les limites entre segments.
Pour LZ77, la transmission de chaque segment se fait grâce à un triplet du type
nouveau symbole). Pour LZ78, est transmis un couple
trouvé dans le dictionnaire et le symbole à ajouter pour créer un nouveau segment).
La reconstruction du texte est simple puisqu’il suffit de réaliser « l’expansion des
références ».
Par exemple, les deux suites
LZ77 : <0,0,a> <0,0,b> <0,0,r> <1,1,c> <1,1,d> <1,4,†>,
LZ78 : <0,a> <0,b> <0,r> <1,c> <1,d> <1,b> <3,a> <0,†>,
encodent le texte «abracadabra†» (avec un symbole de terminaison † et en faisant
partir les indices de 0) et correspondent aux découpages en segments suivant :
LZ77 : | a | b | r | ac | ad | abra | †|,
LZ78 : | a | b | r | ac | ad | ab | ra | †|.
Dans l’exemple précédent, pour LZ78 et à la fin du processus, le dictionnaire est :
Rang 0 1 2 3 4
5
6
7
8
Mot
ε a b r ac ad ab ra †
Ainsi dans l’encodage LZ78 avec des couples
le couple <3, a> encode le 3ème segment du dictionnaire (r) suivi de la lettre a,
soit ra.
Pour LZ77, nous pourrions imaginer l’utilisation d’un trie des suffixes du texte
pour stocker efficacement tous les facteurs (en pratique, des structures de données
plus adaptées sont utilisées [227]). Pour LZ78, le processus de construction du
dictionnaire s’apparente à celui d’un arbre digital de recherche (DST). En effet
les nœuds d’un arbre digital de recherche construit à partir du texte sont en correspondance avec les phrases du dictionnaire (voir Jacquet et Szpankowski [145]).