Phantasie Conquest

et voilà, ça faisait longtemps que cette idée me trottait derrière la tête, et j'ai fini par franchir le pas ce week-end :
désormais, un blog séparé parlera de "compression", ce site restant réservé à la HP48, comme conçu initialement.

Il faut dire qu'il y a eu beaucoup de changements depuis 2 ans. A l'origine, je programmais essentiellement pour HP48, en partant d'une reprise d'un très vieux jeux que je n'avais pas terminé à l'époque. Le public se faisant logiquement de plus en plus rare sur cette plate forme, j'ai petit à petit orienté mon attention vers le monde PC.

Ce n'est donc pas un adieu, et les nouvelles concernant la HP48 continueront d'être publiées sur ce blog.
Pour la compression, désormais c'est …

[ Full reading ]

Et voici les résultats de la généralisation de l'algorithme de recherche par segments, et ils sont relativement bon, bien que surprenants.
En effet, je m'attendais à voir les fichiers textes bénéficier de cet algorithme en raison de la présence probable de longue suites d'espaces, mais en fait non, il n'y a pratiquement aucun impact. Ce sont surtout les fichiers binaires qui y gagnent, et notamment les plus lents.
C'est d'ailleurs la principale satisfaction de cette nouvelle version, la vitesse minimale augmente beaucoup, passant à environ 22Mo/s.

Au final, on obtient une vitesse moyenne de 28,7 Mo/s, soit pratiquement la même vitesse que l'ancienne version "OC", qui n'a plus lieu d'être puisque la version HC …

[ Full reading ]

Ce qui est vrai pour les suites de zéros peut également l'être pour des suites de n'importe quel caractère.
Il est exact que les "zéros" sont les plus fréquemment rencontrés, mais il existe aussi les longues suite de caractère "espace" pour les fichiers textes, et le caractère 0xFF (tous les bits à 1) est assez courant dans les fichiers binaires.
Rien n'interdit non plus à priori l'existence d'une longue suite d'un octet arbitraire.

Pour mieux mesurer cet effet, j'ai créé un petit test qui compte les segments rencontrés et leur taille. Nous obtenons ceci :

	Nb de répétitions	Taille moyenne des répétitions
calgary	1 115	12.7
firefox	18 085	9.5
enwik8	10 030	6.4

Ceci prouve que ces répétitions sont …

[ Full reading ]

Ca y est, les expérimentations sur les suites de zeros sont à peu près achevées, et c'est plutôt au point. Les deux modes de recherches, par segment et par séquence, s'enchaînent bien, se traduisant par de bonnes voire très bonnes performances.

Le résultat final est disponible sur la page de LZ4. La version HC, qui dispose de toutes ces nouveautés, est désormais presque aussi rapide que la version OC, tout en améliorant encore le taux de compression. La vitesse est désormais très stable, oscillant entre 17 et 30Mo/s suivant les cas de figure.

Au passage, j'en ai aussi profité pour mettre à jour la version d'origine ultra-rapide de LZ4, qui profite d'une petite amélioration de vitesse et de compression.

Pour les …

[ Full reading ]

Les premiers résultats sur un parser spécialisés dans les suites de zéros viennent de tomber, et ils sont assez encourageants.
En effet, ces suites de zeros sont fréquentes dans les fichiers binaires, et font énormément ralentir la recherche de séquences. En employant un traceur de segments, on arrive assez rapidement à des améliorations de vitesse très importantes. C'est donc très intéressant.

Le diable est dans les détails. S'il a été possible de concevoir ce traceur de segments assez rapidement, il a été nettement plus compliqué de l'intégrer parfaitement au mécanisme de recherche normal pour toutes les autres chaines. Ainsi, il manquait souvent quelques positions, aboutissant à un moindre choix et donc un taux de …

[ Full reading ]

Il ne faut pas se fier à l'image de ce billet, pour le moins trompeuse . Non, nous n'allons pas parler des avions japonais, mais plutôt des suites de zeros, véritables tueurs de performance pour les recherches.

Pour comprendre ce qu'il se passe, décrivons d'abord le mécanisme avec une simple chaîne de hash.
Imaginons une suite de "zeros", qui peut être assez longue, disons une bonne centaine (ce qui est loin d'être énorme).
Toutes les positions de cette suite sont référencées dans la table comme faisant partie de la même chaîne, en général celle qui a pour hash zéro. Lors de la prochaine séquence minimale ne comportant que des zéros, toutes ces positions seront valides, et donc testées. Nous allons donc …

[ Full reading ]

J'ai pris du retard dans les billets, passant plus de temps à développer, notamment une nouvelle structure de recherche, appelée MMC - pour Morphing Match Chain.
La bonne nouvelle, c'est que c'est une innovation. Hé oui, cette méthode est complètement originale, et permet d'améliorer grandement les performances par rapport à la simple chaîne de hash.

Pour les explications, c'est par ici si vous savez lire l'anglais.
J'essaierai aussi de faire une version française dans le temps.

Toutefois, il y a aussi une nouvelle un peu moins bonne : selon Bulat Ziganshin, le concepteur de FreeArc, cette méthode reste moins performante que l'arbre de recherche binaire (BST), notamment utilisée par 7zip. Ça semble crédible, puisque BST …

[ Full reading ]

Passons désormais aux choses sérieuses. Comment accélérer les recherches, maintenant qu'on a bien investigué les limites de la chaîne de hash.
La première idée que nous allons étudier est aussi la plus simple à concevoir : la double chaîne, aussi appelée double indexation.

Le principe est très simple : on garde la première chaîne de hash, traditionnelle, non modifiée.
Simplement, dès qu'on a atteint un certain seuil, nous passons sur la seconde chaîne.

Pour l'exemple, nous prendrons comme seuil 5 octets.
Au début, c'est comme d'habitude : on calcule le hash de la séquence minimale, on cherche la précédente occurrence dans la table de hash, et c'est parti, on pointe sur la première position de la chaîne, et on déduit …

[ Full reading ]

J'ai failli oublier, il existe une autre façon de définir une limite de recherche qui est très populaire; alors, avant de passer à plus compliqué, nous allons terminer ce sujet sur un dernier billet.

Nous avons défini une limite en "nombre de recherches maximal". Il est également possible de définir un "nombre d'octets répétés maximal" ou suffisant.
L'idée est la suivante : une fois qu'on a trouvé un nombre d'octets égal ou supérieur à la limite, on arrête la recherche et on passe à la suivante.

Cette idée est très populaire, car elle correspond à des restrictions usuelles dans les algorithmes de compression "historiques".
Tout d'abord, il est fréquent que le format de description …

[ Full reading ]