Segments : généralisation

[Yann]

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 bien présentes. Elles sont assez nombreuses, mais cependant relativement petites (notamment pour enwik8).

A comparer aux répétitions de zéros :

	Nb de répétitions	Taille moyenne des répétitions
calgary	1 605	92.7
firefox	10 654	54.4
enwik8	0	0

On constate que les répétitions de zéros ne sont pas spécialement plus nombreuses, mais sont surtout beaucoup plus longues !
C'est d'ailleurs le principal problème qu'elles posent, et la raison pour laquelle un algorithme spécial est nécessaire.


La méthode de détection de segments, employée avec succès dans la dernière version de LZ4HC, peut être étendue à toute suite d'octets, moyennant un test et une structure de repères légèrement plus complexes.
Nous verrons dans un prochain billet si ce pari est probant.