rzip
Un article de Wikipédia, l'encyclopédie libre.
rzip est un logiciel libre de compression de données à grande échelle, construit autour d'une recherche de chaînes initiale de type LZ77 avec une fenêtre de recherche de 900 MB, suivi d'une transformation de Burrows-Wheeler (BWT) de type Bzip2 et enfin un codage entropique (Huffman) par lot de 900 ko.
Sommaire |
[modifier] Algorithme de compression
rzip opère en 2 étapes. La première trouve et code de longues séquences de données répétitives sur des distances potentiellement très longues (900 Mo) au sein du fichier d'entrée. La deuxième étape est d'appliquer un algorithme de compression standard (bzip2) afin de compresser la sortie de la première étape.
Le besoin de compresser des fichiers contenant des redondances à longue distance est de nos jours très répandu. Par exemple, lorsque un ensemble de répertoires d'utilisateurs est compressé, il peut exister plusieurs copies du même fichier, tout du moins de contenus très semblables. Un autre exemple au sein d'un même fichier est une image en plusieurs exemplaires dans un document. La plupart des programmes de compression ne seront capables de profiter de cette redondance, réalisant ainsi un taux de compression bien moindre que rzip.
L'interface intermédiaire entre les 2 étapes est un flux de données alignées à l'octet composé de 2 types de commandes:
- une valeur littérale ("add", signifiant ajout) de longueur et les données
type:8 = 0 compte:16 = 1..65535 données:8..∞ = données brutes à insérer (n octets entiers)
- une correspondance ("copy", signifiant copie) avec des paramètres de longueur et de position relative:
type:8 = 1 compte:16 = 31..65535 position:32 = position relative de la zone source à copier
Les opérations sur des longueurs de plus de 65535 octets sont découpées en autant de commandes que nécessaire. La fin de flux est indiquée via une commande "add" de longueur nulle (type=0,compte=0), qui est suivie immédiatement par un somme de contrôle de type CRC-32.
[modifier] Implémentation de référence
Un algorithme à somme de contrôle roulant basé sur celui de rsync est utilisé pour localiser les correspondances possibles dans une telle quantité de données. Lorsque les tables de hachage se remplissent, les signatures précédentes ("tags") sont rejetées de manière à fournir une couverture plutôt bonne, avec une granularité de correspondance décroissant progressivement avec la distance. Cette implémentation ne tente pas de recherche pour des correspondances de moins de 31 octets consécutifs.
[modifier] Avantages
La différence centrale entre rzip et d'autres algorithmes de compression connus est sa capacité à bénéficier des redondances à très longue distance. Ainsi, l'algorithme deflate utilisé dans gzip possède une fenêtre de recherche d'au maximum 32 ko. La transformation de Burrows-Wheeler, algorithme de tri de blocs, utilisée dans bzip2 est limitée à un historique de 900 ko. Celui dans rzip peut atteindre 900Mo, plusieurs ordres de grandeur plus grand que gzip ou bzip2. De manière intéressante, rzip est souvent plus rapide que bzip2, alors qu'il utilise la bibliothèque bzip2. Ceci est dû au fait que rzip alimente bzip2 avec un flux de données de taille réduite, réduisant de même le travail à effectuer pour bzip2. Une comparaison simple même si trop petite pour un résultat pouvant faire autorité est disponible sur [1]. Une autre est disponible sur le site de rzip.
[modifier] Désavantages
rzip n'est pas adapté à tout type d'utilisation. Les deux plus gros inconvénients de rzip est qu'il ne peut être pipeliné (il ne peut ni écrire sur la sortie ni lire sur l'entrée standard), et qu'il consomme beaucoup de mémoire: une exécution typique sur un gros fichier peut nécessiter plusieurs centaines de Mo de mémoire. Si une grande quantité de RAM est disponible, et qu'un fort taux de compression est requis, rzip gagnerait à être utilisé, sinon, des méthodes alternatives telles que gzip et bzip2, moins gourmandes, sont recommandées.
[modifier] Historique
rzip a originellement été écrit par Andrew Tridgell au cours de sa thèse de PhD. Il est publié sous licence GPL version 2 ou suivantes.
[modifier] Voir aussi
- rsync, par le même auteur (Andrew Tridgell) et contenant un algorithme de recherche de correspondance équivalent à la première étape de rzip.
- lrzip, une amélioration incrémentale à 'rzip' permettant de remplacer la seconde étape bzip2 par au choix LZMA, LZO, ou rien (la compression est alors brute, uniquement avec dictionnaire). Son auteur est Con Kolivas, qui indique que 'lrzip' signifie 'Long Range ZIP' (ZIP à longue distance).
