rzip
| Écrit en | C |
|---|---|
| Système d'exploitation | Type Unix |
| Licence | Licence publique générale GNU version 2 ou ultérieure |
| Site web | rzip.samba.org |
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.
Algorithme de compression[modifier | modifier le code]
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, lorsqu'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 pas capables de profiter de cette redondance, réalisant ainsi un taux de compression bien moindre que rzip.
L'interface intermédiaire entre les deux étapes est un flux de données alignées à l'octet composé de deux 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 65 535 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.
Implémentation de référence[modifier | modifier le code]
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.
Avantages[modifier | modifier le code]
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 900 Mo, 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 www.linux-mag.com . Une autre est disponible sur le site de rzip.
Désavantages[modifier | modifier le code]
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.
Historique[modifier | modifier le code]
rzip a originellement été écrit par Andrew Tridgell au cours de sa thèse de doctorat. Il est publié sous licence GPL version 2 ou suivantes.
Voir aussi[modifier | modifier le code]
- 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).
