Segments : généralisation

View previous topic View next topic Go down

Segments : généralisation

Post  Yann on Sat 13 Nov - 16:09

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.

Yann
Admin

Number of posts : 174
Registration date : 2008-05-01

http://phantasie.tonempire.net

Back to top Go down

View previous topic View next topic Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum