Rapidité du décodage de Huffman

Bonjour,


Après avoir implémenté les codages de Golomb/Rice, le codage arithmétique/par intervalles et testé un nouvel algo de compression combinant nombres premiers et codes de Rice [hyper efficace pour coder les multiples de nombres premiers et/ou pas mal de valeurs particulières, mais qui semble par contre moins efficace que le codage de Rice dans le cas général :( ], je viens de commencer l'implémentation du codage de Huffman.

Pour l'instant, j'utilise un arbre de Huffman statique (cf. je lis toutes les données d'un fichier avant de construire l'arbre de Huffman qui sera donc spécifique à ce fichier), mais pense adapter ça assez vite en un arbre dynamique ou semi-dynamique, cf. par blocs (ça dépendra du gain obtenu)

Les codages de Rice/Golomb et de Huffman ont pour points commun de générer un code dont la taiile des symboles les plus fréquents est plus petite que la taille des symboles les moins fréquents, les codes de Huffman ayant l'avantages d'être théoriquement optimaux

Enfin en théorie car mon implémentation du codage de Huffman à tendance à me générer des codes d'au moins deux bits pour les symboles les plus fréquents alors qu'avec un code sur un seul bit pour le symbole le plus fréquent, la compression devrait encore être meilleure, surtout quand 99% des caractères sont les mêmes :)
(mais bon, je suis vraiment persuadé que c'est mon implémentation qui a un pb à ce niveau là ...)

Pour en revenir au sujet, j'ai remarqué que les codes générés par mon codage de Huffman semblent universels (cf. deux codes distincts n'ont jamais le même préfixe => c'est peut-être de là que vient mon pb de codes à 2 bits minimum ...) et j'utilise actuellement pour la décompression une table de conversion "code de Huffman" -> "symbole non compressé" plutôt que de devoir parcourir [au moins partiellement] l'arbre de Huffman à chaque code/symbole de Huffman rencontré

Ca m'évite de devoir transmettre l'arbre pour la décompression (c'est une simple table de conversion "octet lu -> premier code de Huffman + taille de ce premier code + symbole décompressé" qui le remplace) , ce qui me permet de décoder plus rapidement plusieurs symboles lorsqu'ils sont présents dans le même octet + me donne de plus la possibilité d'effectuer un maximum de lectures/traitements octet/octet et de minimiser les lectures/traitements bit/bit
(je pense d'ailleurs très vite remplacer la lecture octet/octet par une lecture de 16 ou 32 bits à chaque fois, voir même 64/128 bits avec l'aide des registres MMX/SSE)

Je pense de plus étendre le principe en construisant une table de conversion qui me permette de générer directement plusieurs caractères en sortie lorsque plusieurs codes de Huffman sont compactés dans le même octet (et à plus forte raison quand ce sera un mot/double mot ou une valeur sur 64 ou 128 bits ...) , plutôt que de devoir retirer du dernier octet lu le code déjà décodé, cf. décalage à gauche du nombre de bits occupés par le dernier code rencontré, puis de tester à chaque fois pour chaque nouveau bit lu si c'est bien un code de huffman valide ou pas qui se trouve dans les bits de poids fort de l'octet ainsi mis à jour bit par bit (et si non, faire un nouvel essai en lisant un bit de plus et ainsi de suite ...)
[rectificatif : les bits de poids forts contiennent maintenant obligatoirement un code valide car j'y ajoute autant de bits lus que la taille du dernier code rencontré => ça va plus vite et ça me rajoute en plus la détection automatique d'éventuels codes erronés :) ]

=> quelqu'un aurait-ils des infos concernant le décodage de codes de Huffman directement à partir d'une table et ne nécessitant donc pas le stockage de l'arbre + le parcours partiel de cet arbre à chaque code rencontré ?
(c'est ce qui est fait dans les fichiers jpeg mais c'est fait avec des tables statiques alors que je voudrais un truc équivalent mais avec des tables qui puissent être dynamiquement mises à jour)

PS : ça ressemble une peu à ce qui est décrit dans ce pdf http://www.google.fr/url?sa=t&rct=j&...oiGi1g&cad=rja sauf que le décodage d'un symbole est fait en un seul coup, cf. il n'y a pas d'indirection vers des sous-tables
(mais je pense que vais sûrement rajouter cette indirection car ça rendra mon algo plus "générique/adaptable/APIsable")


@+
Yannoo

Mon implémentation de la compression de Huffman commence enfin à devenir fonctionnelle :)

Bon ok, le taux de compression n'est pas très faramineux car je reste persuadé qu'il y a un pb dans mon générateur d'arbre de Huffman
(qui génère des codes d'au moins 2 bits alors que je pense qu'un code d'un seul bit pour le symbole le plus courant serait plus optimal, du moins quand il est bien plus fréquent que la somme des fréquences de tous les autres ...)

Il y a de plus une copie de la table qui a permis de créer l'arbre de Huffman qui est stockée en entête du fichier .huf (ce qui rajoute à peu prêt 6 Ko au fichier),
=>je pense pouvoir assez fortement réduire cet entête en n'y stockant que les valeurs réellement utiles
(ça devrait réduire l'entête à qqchose de l'ordre du Ko, voir moins)

A noter que le décodeur lit pour l'instant les données compressées par blocs de 16 bits mais j'ai des pb de décodage sur le tout dernier symbole
=> il faut absolument que je rêgle ce pb avant de pouvoir commencer à traiter les données par blocs de 32 ou 64 bits ...

Et question rapidité, c'est encore à l'état de prémisses de prototypage donc ce n'est pas encore ça ... mais ça devrait venir vite assez une fois le pb du dernier symbole à décoder résolu :)

Car une fois ce pb rêglé, je pourrais alors passer à un traitement des données compressées par blocs de 32 bits (il fonctionne actuellement avec des blocs compressés de 16 bits), puis ensuite en 64/128 bits avec le MMX/SSE si ça se passe bien

Je retirerais ensuite enfin tous les fprint(stderr, ...) que j'y ai ajouté petit à petit afin de m'aider à débugger car ça à l'air de ralentir pas mal le traitement ...

+ je boucle pour l'instant sur chaque symbole compressé dans un bloc de 16 bits mais pense carrément mettre tous les symboles décompressés correspondants au bloc compressé dans la table de correspondances codes compressés -> valeurs décompressées
(cf. plutôt que d'aller dans la table chercher les symboles un par un, la table de correspondance me donnera directement toute la suite des symboles décompressés correspondants au bloc compressé de 8/16/32/64/128 bits)

Par contre, c'est là qu'il faudra que j'y gère des indirections afin de ne pas avoir à gérer une table de correspondance de plusieurs Mo car vu qu'en 16 bits ça fait déjà dans les 6 Ko, en 32 bits ça fera dans les 34 Mo et qqchose de l'ordre du giga-octet en 64 bits :(
=> même pas la peine de penser à gérer ça en 128 bits sans une bonne dose d'indirection dans la table ...

=> mais j'ai déjà une idée sur la méthode à utiliser pour gérer les indirections dans la table de correspondance ... qui devrait assez sûrement réduire la table de l'ordre du Mo maximum pour gérer des blocs de 128 bits + de permettre de générer cette table au moins des centaines de fois plus vite :)
[au bas mot car je ne serais pas du tout étonné que ça puisse même être plutôt de l'ordre de milliers ou de millions de fois ...]

=> avec tout ça, je pense que ça devrait y donner une accélération de l'ordre de 5x à 10x, voir même bien plus avec un peu de chance :)
(pour l'instant, la table de correspondance "multi-codes" n'est construite/gérée que du côté décodeur, cf. huffman_t Remap[100000] en tout début du source dehuffman.c, mais je pense rajouter dans un très proche avenir l'équivalent du côté codeur [avec la maj de cette table en dynamique bien sûr])


@+
Yannoo

Voici un exemple du pb du "symbole utilisé en très grande majorité mais toujours codé sur 2 bits à la place d'un seul" :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

Huffman compression by YLP v0.0   Read symbols :   Add code ASCII 97 (a) Add code ASCII 10 ( ) Add code ASCII 98 (b) Add code ASCII 99 (c) Add code ASCII 100 (d)     Generate Huffman forest :   ASCII 98 (0x0 3bits x1) [000]   * (0x0 2bits x2) [00]   ASCII 99 (0x1 3bits x1) [001]   * (0x0 1bits x6) [0]   ASCII 10 (0x1 2bits x4) [01]   * (0x0 0bits x65) []   * (0x2 2bits x1) [10]   ASCII 100 (0x5 3bits x1) [101]   * (0x1 1bits x59) [1]   ASCII 97 (0x3 2bits x58) [11]       Generated codes :   11 (ASCII=97 [a] code=3 nOccurences=58 bits/symbol=2 total=116 bits) 01 (ASCII=10 [ ] code=1 nOccurences=4 bits/symbol=2 total=8 bits) 000 (ASCII=98 [b] code=0 nOccurences=1 bits/symbol=3 total=3 bits) 001 (ASCII=99 [c] code=1 nOccurences=1 bits/symbol=3 total=3 bits) 101 (ASCII=100 [d] code=5 nOccurences=1 bits/symbol=3 total=3 bits)   Coded string :   (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 (a) 11 ... (a) 11 (a) 11 (a) 11 ( ) 01 (b) 000 ( ) 01 (c) 001 ( ) 01 (d) 101 ( ) 01 [000]   Compression : 17/65 = 26.15%

---

=> la branche des 1qqchose contient l'élement ASCII 100 qui devrait plutôt se trouver dans la branches des 0qqchose afin de donner un truc du style

1 ASCII 97 (58 occurrences 1 bit/symbole 58x1 = 58 bits)
00 ASCII 10 (4 occurrences 2 bits/symbole 4x2 = 8 bits)
011 ASCII 100 (1 occurence 3 bits/symbole 1x3 = 3 bits)
0100 ASCII 98 (1 occurence 4 bits/symbole 1x4 = 4 bits)
0101 ASCI 99 (1 occurrence 4 bits/symbole 1x4 = 4 bits)

soit **seulement** 77 bits à la place des 133 actuellement générés

=> mon générateur d'arbre de Huffman devrait donc normalement y compresser ces données à peu prêt 2x mieux qu'actuellement ...
(la compression devrait s'approcher des 13% avec ces données, soit un taux de compression d'environ 8x)

==> par contre, j'ai beau essayer d'analyser le code, je n'y trouve toujours pas la source du pb :(
(si ce n'est que ça génère des codes = 0 alors qu'il me semblerait plus logique/simple qu'il ne puisse pas en générer pour laisser l'entrée 0 libre afin de s'en servir comme marqueur de fin ou qqchose du style)

PS : le décodage "multi-codes par table[s] 8/16/32/64/128 bits" devrait arriver très vite du côté décodeur et faire ses premières apparitions dans la partie codeur d'ici quelques jours :)

PS2 : je pense temporairement repasser par le codage/décodage de Golomb/Rice car il me semble plus optimum pour gérer le cas d'une très forte fréquence d'un symbole par rapport aux autres et qu'il me permettra de générer beaucoup plus facilement/rapidement des données de tests "sur mesures pour tester les cas les plus problêmatiques" afin de m'aider à mettre au point cette table de conversion "code de qqchose -> séries de valeurs qu'il doit remplacer" en 8/16/32/64/128 bits
(en passant, ça me permettra d'y rajouter une gestion des symboles "par mots" plutôt que par caractère/symbole/valeur comme actuellement + des codes du style "x fois le symbole y" [cf. y incorporer une RLE quoi] )


@+
Yanooo

Ca a l'air passionnant, mais trop compliqué.... Je voulais quand même te dire que tu es lu ^^

C'est assez compliqué à la base mais j'espère bien en retirer assez vite qqchose de simple, rapide et fonctionnel :)

Je reviendrais donc sûrement dans quelques temps ... une fois que j'aurais gagné un ratio de l'ordre de 10x entre la vitesse et le taux de compression/décompression actuel ... avec une compression effective bien sûr :)

Heu ... avec 2 fonctions dans ce style :

int CompressData(void * original, int size, void *compressed)
[qui retourne la taille du bloc *original compressé dans *compressed ou < 0 en cas d'erreur]

et

int DecompressData(void *compressed, int size, void *decompressed)
[qui retourne la taille du bloc *compressed decompressé dans *decompressed ou <0 en cas d'erreur ]


=> ce serait toujours trop compliqué ???



@+
Yannoo

Je me permet de revenir car j'ai déjà gagné prêt de 20x sur la vitesse de construction de l'arbre de Huffman qui ne prend plus maintenant que 1 ms pour générer les codes de Huffman de mon fichier de test
(alors qu'il prenait avant 19 ms pour faire la même chose ...)

=> la ruse ? j'y ai simplement retiré l'affichage de l'arbre en mode texte :) :)

Côté décodeur, j'ai à peine doublé sa vitesses en commentant l'affichage des commentaires :(
(c'est l'initialisation du tableau de conversion qui prend maintenant 91% du temps ...)

+ je commence à avoir des doutes sur l'utilité de devoir passer par des tables 32/64/128 bits côté codeur et décodeur car ça semble pour l'instant plutôt ralentir qu'autre chose ...
(le passage par une table 16 bits est vraiment efficace mais vu le résultat sur le décodeur avec des tests en 32 bits, je commence franchement à en douter ...)


@+
Yannoo

J'ai radicalement modifié la structure de ma table de conversion
(c'était 256 recopies des 256 premières nodes huffman_t du tableau HuffmanNodes[] afin de pouvoir gérer les 65536 valeurs possibles [16 bits] à chaque lecture d'un bloc de donnée compressé et c'est maintenant devenues 256x256 index sur le tableau HuffmanCodes[])

=> le temps d'initalisation de la table de conversion "codes de Huffman -> première valeur décompressée" y est maintenant passé de 22 ms à 1 ms

==> temps total de décompression : 4 ms (26 ms avant la modif)
(le "taux de squattage" de l'initialisation de cette table sur le temps total entre le lancement de la décompression et le retour à l'invite de commande est passé de 91% à 15% avec mon fichier de test)

Côté compression c'est passé de 28 ms à 13 ms (plus de 2x plus rapide)
mais je pense que ça devrait très vite passer en dessous des 10 ms ...

Bon ok, c'est encore assez loin des 10x mais je n'ai même pas encore commencé à y implémenter la méthode de compression/décompression multi-codes :)

PS : en plus, ça a résolu mon pb du dernier caractère qui n'était pas systématiquement décompressé :)
(de l'autre côté, j'ai maintenant le pb inverse cad qu'il me rajoute des fois quelques caractères en plus à la fin mais ça devrait être relativement facile à corriger [bien plus facilement que dans l'autre sens ...] => j'ai fait quelques tests sur des .pdf, .tif, .doc et autres et ça à l'air de passer car c'est des 0 qu'il y rajoute)


@+
Yannoo

Côté codeur, la vitesse de génération des codes de Huffman s'est maintenant plus que largement améliorée car elle ne représente désormais même pas 5% du temps total nécessaire à la compression d'un gros fichier :)

Par exemple, ça donne ça sur un fichier texte de 6,5 Mo :

Initialisation : 4 ms

Lecture "à vide" : 72 ms
(simple comptage du nombre d'occurences / caractère dans le fichier)

Calcul de l'arbre de Huffman : 24 ms
(mais **seulement** 1 ms sans l'affichage de l'arbre [cf. verbose=0] :) )

Conversion/écriture séquentielle des caractères/codes compressés : 444 ms

=> les améliorations notables de performance sur le codeur ne peuvent donc désormais plus se faire qu'au niveau de la routine d'écriture séquentielle des caractères convertis en codes de Huffman dans le fichier compressé

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

int _bits_ = 0; unsigned char _idx_ = 0;   void WriteBits(unsigned int val, int bits) { unsigned int i;   for( i = bits ; i-- ; ) { _idx_ <<= 1; _idx_ |= (val >> i) & 0x1;   if( ++_bits_ == WRITE_BLOC ) { fwrite(&_idx_, WRITE_BLOC / 8, 1, stdout); _bits_ = 0; _idx_ = 0; } } }

---

et qui est intensivement appelée par la boucle principale qui compresse unitairement chaque caractère en entrée par un code de Huffman en sortie :
(c'est ici qu'est maintenant pris 80% du temps total nécessaire à la compression d'un fichier ...)

Code:

---

1 2 3 4 5 6 7

for( n = 0 ; fread(&c, 1, 1, file) == 1 ; n++ ) { bits += HuffmanCodes[c].nBits; WriteBits(HuffmanCodes[c].code, HuffmanCodes[c].nBits); }

---

ou cette variation qui paraît bien plus efficace
(car elle y minimise les accès en lecture, travaillant par groupe de 16 caractères à chaque fois)

Code:

---

1 2 3 4 5 6 7 8 9 10 11

for ( n = 0 ; (nread = fread(tread, 1, 16, file)) > 0 ; n+= nread) { for (j = 0 ; j < nread ; j++ ) { c = tread[j]; bits += HuffmanCodes[c].nBits; WriteBits(HuffmanCodes[c].code, HuffmanCodes[c].nBits); } }

---

=> c'est là que la gestion "multi-codes" va faire un malheur quand elle sera au point ...

PS : ce qui est hallucinant c'est que le codeur va déjà plus vite que le décodeur ... :)
(car le décodeur doit en plus vérifier qu'on est pas en fin de fichier à chaque lecture d'un bloc de 16 bits [ + surtout l'équivalent pour chaque bit retiré du buffer ...] + que je n'y ai pas encore implémenté le décodage "multi-codes" [mais ça devrait arriver assez vite, la partie théorique étant quasiment terminée])

PS2 : il y un très gros bug dans le décodeur quand les codes de Huffman dépasse 16 bits (j'ai uniquement trouvé le pb avec de gros fichier texte et des .pdf bien plus gros y sont passés sans pb)


@+
Yannoo

Pour l'instant, j'arrive à ces performances sur le codeur :

Huffman compression by YLP v0.2

Open the file big.txt : 1 ms

Init Huffman Codes : 5 ms

Read symbols : 45 ms
144 Mbits/s (6336 Kbytes)

Generate Huffman Table : 1 ms
348 Knodes/s (348 nodes)

Aggregate Codes : 0 ms
6488 Msyms/s (28774 Kbits / 6488 Ksyms = 4.541 bits/symbol)

Write the compressed data : 386 ms
76 Mbits/s (3599 Kbytes)

Compression : 3686165 / 6488666 = 56.81%

Input : 118.514 Mbits/s (6488666 bytes / 438 ms)
Output : 67.327 Mbits/s (3686165 bytes / 438 ms)

Total time : 438 ms

=> je pense que la mise en place de l'optimisation multi-codes sera effective dans les prochains jours
(cf. compacter "intelligemment" plusieurs codes de Huffman consécutifs dans des octets/mots/double-mots afin de permettre le décodage **direct** de 1, 2, 3 ou 4 octets compressés consécutifs via une "simple" table de conversion du côté décodeur => jusqu'à 28 valeurs décompressées d'un coup par la lecture/conversion d'une seule valeur 32 bits de codes compactés)

PS : c'est la partie "Write the compressed data" qui est concernée par le multi-code => je pense que ça devrait à peu prêt doubler les performances de conversion/déconversion et ça devrait faire qqchose comme du 150 Mb/s en E/S
(ok, c'est encore faible quand je vois que mon DD peut faire jusqu'à 450 Mb/s mais il n'y a plus qu'un rapport de 3x à gagner, contre un rapport d'environ 1000x il y a à peine plus d'une semaine :) )


@+
Yannoo

Je viens de tester le remplacement de la génération de l'arbre de Huffman (cf. codage caractère par caractère) par la génération d'un tableau mémorisant toutes les mots/syllabes/groupes de lettres différent(e)s trouvé(e)s
[cf. codage par mots/syllabes/groupe de lettres et non plus caractère par caractère].

Ce tableau est ensuite trié par nombre d'occurence en première clé, par le nombre de caractères en seconde clé puis par l'ordre lexicographique en troisième clé.

Puis les codes sont alors générés séquentiellement de la première entrée du tableau (le mot le plus commun) à la dernière entrée (la syllabe la moins commune, comportant le moins de lettres et "en dernière position lexicographique dans le groupe des syllabes ayant autant de lettres")
[en passant, ça m'a permis de retrouver comment générer séquentiellement des codes de Golomb incrémentaux grace à la formule codesize = (int)(log(++code) / log(2))*2 + 1 :) ]

=> j'y gagne entre 5 et 10% en taux de compression **MAIS** j'ai dû très grandement réduire la taille de mon fichier de texte big.txt de 6.5 Mo à un peu moins de 1 Mo pour avoir un temps de traitement "humain" :(
(presque une minute de calcul pour même pas 10% de compression de gagnée sur un fichier de 1 Mo => le ratio rapidité/compression y perd d'un facteur de 1000 ou qqchose comme ça ==> j'ai dû lacher l'affaire avec le fichier big.txt original de 6.5 Mo car il n'avait toujours terminé la génération des codes au boût de 10 minutes ... vs à peine 1 ms pour générer l'arbre de Huffman ===> y'a pas, Huffman c'est vraiment très fort :) )
[c'est la recherche/mémorisation des mots/syllabes déjà utilisés qui bouffe tout le temps CPU => ça me génére déjà 12430 symboles sur mon fichier de test de 1 Mo à la place de seulement 348 nodes pour l'arbre de Huffman qui marche caractère par caractère et sur un fichier 6x plus gros :( ]

Avec l'arbre de Huffman
Compression : 3686165 / 6488666 = 56.81%
Total time : 438 ms

vs

Avec la compression "par mot/syllabes/groupes de lettres"
compression = 47% (407228/824824)
et environ une minute de calcul
(je n'y ai pas mis encore implémenté le timing)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

Strings encoding v0.1 lines=1024 asize=3284 lines=2048 asize=5265 lines=3072 asize=6609 lines=4096 asize=7657 lines=5120 asize=8470 lines=6144 asize=9501 lines=7168 asize=10526 lines=8192 asize=11282 lines=9216 asize=11901 Generate compressed strings Sort compressed strings Symbol[0] = (x145452 43.3%) code=1, codesize=1, compressed=145452 bits, reduction=0.1 [145452 bits/1163616 bits] Symbol[1] = , (x10452 3.1%) code=2, codesize=3, compressed=31356 bits, reduction=0.4 [31356 bits/83616 bits] Symbol[2] = (x9999 3.0%) code=3, codesize=3, compressed=29997 bits, reduction=0.4 [29997 bits/79992 bits] Symbol[3] = the (x8635 2.6%) code=4, codesize=5, compressed=43175 bits, reduction=0.2 [43175 bits/207240 bits] Symbol[4] = . (x8478 2.5%) code=5, codesize=5, compressed=42390 bits, reduction=0.6 [42390 bits/67824 bits] Symbol[5] = " (x5579 1.7%) code=6, codesize=5, compressed=27895 bits, reduction=0.6 [27895 bits/44632 bits] Symbol[6] = of (x4734 1.4%) code=7, codesize=5, compressed=23670 bits, reduction=0.3 [23670 bits/75744 bits] Symbol[7] = and (x4209 1.3%) code=8, codesize=7, compressed=29463 bits, reduction=0.3 [29463 bits/101016 bits] Symbol[8] = to (x3749 1.1%) code=9, codesize=7, compressed=26243 bits, reduction=0.4 [26243 bits/59984 bits] Symbol[9] = a (x3166 0.9%) code=10, codesize=7, compressed=22162 bits, reduction=0.9 [22162 bits/25328 bits] Symbol[10] = I (x3057 0.9%) code=11, codesize=7, compressed=21399 bits, reduction=0.9 [21399 bits/24456 bits] Symbol[11] = in (x2731 0.8%) code=12, codesize=7, compressed=19117 bits, reduction=0.4 [19117 bits/43696 bits] Symbol[12] = that (x1911 0.6%) code=13, codesize=7, compressed=13377 bits, reduction=0.2 [13377 bits/61152 bits] Symbol[13] = was (x1903 0.6%) code=14, codesize=7, compressed=13321 bits, reduction=0.3 [13321 bits/45672 bits] Symbol[14] = - (x1785 0.5%) code=15, codesize=7, compressed=12495 bits, reduction=0.9 [12495 bits/14280 bits] Symbol[15] = ' (x1584 0.5%) code=16, codesize=9, compressed=14256 bits, reduction=1.1 [14256 bits/12672 bits] Symbol[16] = it (x1514 0.5%) code=17, codesize=9, compressed=13626 bits, reduction=0.6 [13626 bits/24224 bits] Symbol[17] = you (x1290 0.4%) code=18, codesize=9, compressed=11610 bits, reduction=0.4 [11610 bits/30960 bits] Symbol[18] = his (x1263 0.4%) code=19, codesize=9, compressed=11367 bits, reduction=0.4 [11367 bits/30312 bits] Symbol[19] = he (x1252 0.4%) code=20, codesize=9, compressed=11268 bits, reduction=0.6 [11268 bits/20032 bits] Symbol[20] = is (x1226 0.4%) code=21, codesize=9, compressed=11034 bits, reduction=0.6 [11034 bits/19616 bits] Symbol[21] = with (x1043 0.3%) code=22, codesize=9, compressed=9387 bits, reduction=0.3 [9387 bits/33376 bits] Symbol[22] = as (x1022 0.3%) code=23, codesize=9, compressed=9198 bits, reduction=0.6 [9198 bits/16352 bits] Symbol[23] = had (x1017 0.3%) code=24, codesize=9, compressed=9153 bits, reduction=0.4 [9153 bits/24408 bits] Symbol[24] = for (x1015 0.3%) code=25, codesize=9, compressed=9135 bits, reduction=0.4 [9135 bits/24360 bits] Symbol[25] = have (x956 0.3%) code=26, codesize=9, compressed=8604 bits, reduction=0.3 [8604 bits/30592 bits] Symbol[26] = my (x908 0.3%) code=27, codesize=9, compressed=8172 bits, reduction=0.6 [8172 bits/14528 bits] Symbol[27] = at (x902 0.3%) code=28, codesize=9, compressed=8118 bits, reduction=0.6 [8118 bits/14432 bits] Symbol[28] = which (x890 0.3%) code=29, codesize=9, compressed=8010 bits, reduction=0.2 [8010 bits/35600 bits] Symbol[29] = The (x823 0.2%) code=30, codesize=9, compressed=7407 bits, reduction=0.4 [7407 bits/19752 bits] Symbol[30] = ? (x783 0.2%) code=31, codesize=9, compressed=7047 bits, reduction=1.1 [7047 bits/6264 bits] Symbol[31] = be (x767 0.2%) code=32, codesize=11, compressed=8437 bits, reduction=0.7 [8437 bits/12272 bits] Symbol[32] = not (x765 0.2%) code=33, codesize=11, compressed=8415 bits, reduction=0.5 [8415 bits/18360 bits] Symbol[33] = were (x734 0.2%) code=34, codesize=11, compressed=8074 bits, reduction=0.3 [8074 bits/23488 bits] Symbol[34] = from (x679 0.2%) code=35, codesize=11, compressed=7469 bits, reduction=0.3 [7469 bits/21728 bits] Symbol[35] = by (x651 0.2%) code=36, codesize=11, compressed=7161 bits, reduction=0.7 [7161 bits/10416 bits] Symbol[36] = me (x637 0.2%) code=37, codesize=11, compressed=7007 bits, reduction=0.7 [7007 bits/10192 bits] Symbol[37] = on (x552 0.2%) code=38, codesize=11, compressed=6072 bits, reduction=0.7 [6072 bits/8832 bits] Symbol[38] = but (x548 0.2%) code=39, codesize=11, compressed=6028 bits, reduction=0.5 [6028 bits/13152 bits] Symbol[39] = upon (x529 0.2%) code=40, codesize=11, compressed=5819 bits, reduction=0.3 [5819 bits/16928 bits] Symbol[40] = It (x526 0.2%) code=41, codesize=11, compressed=5786 bits, reduction=0.7 [5786 bits/8416 bits] Symbol[41] = this (x521 0.2%) code=42, codesize=11, compressed=5731 bits, reduction=0.3 [5731 bits/16672 bits] Symbol[42] = 1 (x518 0.2%) code=43, codesize=11, compressed=5698 bits, reduction=1.4 [5698 bits/4144 bits] Symbol[43] = all (x514 0.2%) code=44, codesize=11, compressed=5654 bits, reduction=0.5 [5654 bits/12336 bits] Symbol[44] = said (x499 0.1%) code=45, codesize=11, compressed=5489 bits, reduction=0.3 [5489 bits/15968 bits] Symbol[45] = so (x463 0.1%) code=46, codesize=11, compressed=5093 bits, reduction=0.7 [5093 bits/7408 bits] Symbol[46] = Holmes (x460 0.1%) code=47, codesize=11, compressed=5060 bits, reduction=0.2 [5060 bits/22080 bits] Symbol[47] = him (x460 0.1%) code=48, codesize=11, compressed=5060 bits, reduction=0.5 [5060 bits/11040 bits] Symbol[48] = been (x451 0.1%) code=49, codesize=11, compressed=4961 bits, reduction=0.3 [4961 bits/14432 bits] Symbol[49] = s (x451 0.1%) code=50, codesize=11, compressed=4961 bits, reduction=1.4 [4961 bits/3608 bits] Symbol[50] = we (x449 0.1%) code=51, codesize=11, compressed=4939 bits, reduction=0.7 [4939 bits/7184 bits] Symbol[51] = one (x433 0.1%) code=52, codesize=11, compressed=4763 bits, reduction=0.5 [4763 bits/10392 bits] Symbol[52] = her (x432 0.1%) code=53, codesize=11, compressed=4752 bits, reduction=0.5 [4752 bits/10368 bits] Symbol[53] = an (x431 0.1%) code=54, codesize=11, compressed=4741 bits, reduction=0.7 [4741 bits/6896 bits] Symbol[54] = there (x403 0.1%) code=55, codesize=11, compressed=4433 bits, reduction=0.3 [4433 bits/16120 bits] Symbol[55] = very (x400 0.1%) code=56, codesize=11, compressed=4400 bits, reduction=0.3 [4400 bits/12800 bits] Symbol[56] = who (x381 0.1%) code=57, codesize=11, compressed=4191 bits, reduction=0.5 [4191 bits/9144 bits] Symbol[57] = or (x380 0.1%) code=58, codesize=11, compressed=4180 bits, reduction=0.7 [4180 bits/6080 bits] Symbol[58] = are (x378 0.1%) code=59, codesize=11, compressed=4158 bits, reduction=0.5 [4158 bits/9072 bits] Symbol[59] = your (x372 0.1%) code=60, codesize=11, compressed=4092 bits, reduction=0.3 [4092 bits/11904 bits] Symbol[60] = ! (x371 0.1%) code=61, codesize=11, compressed=4081 bits, reduction=1.4 [4081 bits/2968 bits] Symbol[61] = ; (x371 0.1%) code=62, codesize=11, compressed=4081 bits, reduction=1.4 [4081 bits/2968 bits] Symbol[62] = their (x365 0.1%) code=63, codesize=11, compressed=4015 bits, reduction=0.3 [4015 bits/14600 bits] Symbol[63] = out (x364 0.1%) code=64, codesize=13, compressed=4732 bits, reduction=0.5 [4732 bits/8736 bits] Symbol[64] = no (x361 0.1%) code=65, codesize=13, compressed=4693 bits, reduction=0.8 [4693 bits/5776 bits] Symbol[65] = He (x349 0.1%) code=66, codesize=13, compressed=4537 bits, reduction=0.8 [4537 bits/5584 bits] Symbol[66] = into (x348 0.1%) code=67, codesize=13, compressed=4524 bits, reduction=0.4 [4524 bits/11136 bits] Symbol[67] = would (x345 0.1%) code=68, codesize=13, compressed=4485 bits, reduction=0.3 [4485 bits/13800 bits] Symbol[68] = up (x344 0.1%) code=69, codesize=13, compressed=4472 bits, reduction=0.8 [4472 bits/5504 bits] Symbol[69] = could (x335 0.1%) code=70, codesize=13, compressed=4355 bits, reduction=0.3 [4355 bits/13400 bits] Symbol[70] = she (x330 0.1%) code=71, codesize=13, compressed=4290 bits, reduction=0.5 [4290 bits/7920 bits] Symbol[71] = 0 (x323 0.1%) code=72, codesize=13, compressed=4199 bits, reduction=1.6 [4199 bits/2584 bits] Symbol[72] = man (x321 0.1%) code=73, codesize=13, compressed=4173 bits, reduction=0.5 [4173 bits/7704 bits] Symbol[73] = = (x316 0.1%) code=74, codesize=13, compressed=4108 bits, reduction=1.6 [4108 bits/2528 bits] Symbol[74] = will (x305 0.1%) code=75, codesize=13, compressed=3965 bits, reduction=0.4 [3965 bits/9760 bits] Symbol[75] = they (x304 0.1%) code=76, codesize=13, compressed=3952 bits, reduction=0.4 [3952 bits/9728 bits] Symbol[76] = when (x301 0.1%) code=77, codesize=13, compressed=3913 bits, reduction=0.4 [3913 bits/9632 bits] Symbol[77] = 7 (x301 0.1%) code=78, codesize=13, compressed=3913 bits, reduction=1.6 [3913 bits/2408 bits] Symbol[78] = has (x293 0.1%) code=79, codesize=13, compressed=3809 bits, reduction=0.5 [3809 bits/7032 bits] Symbol[79] = little (x289 0.1%) code=80, codesize=13, compressed=3757 bits, reduction=0.3 [3757 bits/13872 bits] Symbol[80] = _ (x287 0.1%) code=81, codesize=13, compressed=3731 bits, reduction=1.6 [3731 bits/2296 bits] Symbol[81] = what (x286 0.1%) code=82, codesize=13, compressed=3718 bits, reduction=0.4 [3718 bits/9152 bits] Symbol[82] = You (x279 0.1%) code=83, codesize=13, compressed=3627 bits, reduction=0.5 [3627 bits/6696 bits] Symbol[83] = Mr (x274 0.1%) code=84, codesize=13, compressed=3562 bits, reduction=0.8 [3562 bits/4384 bits] Symbol[84] = 2 (x274 0.1%) code=85, codesize=13, compressed=3562 bits, reduction=1.6 [3562 bits/2192 bits] Symbol[85] = do (x272 0.1%) code=86, codesize=13, compressed=3536 bits, reduction=0.8 [3536 bits/4352 bits] Symbol[86] = them (x260 0.1%) code=87, codesize=13, compressed=3380 bits, reduction=0.4 [3380 bits/8320 bits]

---

...

Code:

---

1 2 3 4 5 6 7 8 9 10 11

Symbol[12427] = k (x1 0.0%) code=12428, codesize=27, compressed=27 bits, reduction=3.4 [27 bits/8 bits] Symbol[12428] = w (x1 0.0%) code=12429, codesize=27, compressed=27 bits, reduction=3.4 [27 bits/8 bits] Symbol[12429] = ~ (x1 0.0%) code=12430, codesize=27, compressed=27 bits, reduction=3.4 [27 bits/8 bits]     824824 characters in / 336063 strings out (12430 symbols, headersize=100519)   compression = 49.37 (407228/824824)   compression sans header = 37.18 (306709/824824)

---

Le bon côté, c'est que ça m'a fait réimplémenter WC [WorldCount) sans le vouloir :)

=> l'optimisation "par mots/syllabique" n'ayant pas tout l'air performante, je vais donc maintenant pouvoir revenir à 100% sur l'optimisation multi-codes qui devrait quant à elle être bien plus performante :)

PS : de l'autre côté, je vais regarder comment est faites l'implémentation de wc sous Linux => je pense qu'il doivent au moins aller de 100 à 1000x plus vite que moi pour compter/stocker tous les mots utilisés ...

PS2 : vu pour le wc => il ne fait que compter les mots/lignes/caractères, il ne compte pas le nombre de mots différents :(
(normal qu'il aille sans aucun pb dans les 1000x plus vite car il en fait 1000x moins ...)

PS3 : je pense que wc devrait devenir bien plus rapide s'il utilisait des lectures par blocs plutôt que des lectures caractère par caractère ...
[cf. ça marche via des c = getc() / isword(c) => 2 appels de fonction pour chaque caractère lu ...]


@+
Yannoo