ROLZ - Définition

Introduction

Les algorithmes de type ROLZ, pour Reduced Offset Lempel-Ziv, constituent une famille d'algorithmes de compression de données sans perte inventée par Malcolm Taylor en 1999 et dérivée de la famille des algorithmes de type LZ77.

Ce sont des algorithmes hybrides, faisant intervenir de la compression par dictionnaire et une simple modélisation de contextes.

Principe

ROLZ conserve le principe général de LZ77, qui consiste à remplacer des suites de symboles par des couples (position d'une occurrence précédente de la suite, longueur de la suite).

À la différence de ceux-ci cependant, la position n'est pas codée telle quelle, mais est remplacée par sa position dans une table de hachage (le codage de la longueur reste identique). L'algorithme utilise plusieurs tables de hachage parmi lesquelles une est choisie de façon symétrique à la compression et à la décompression grâce à une simple modélisation de contextes (comme un PPM de petit ordre).

Certaines variantes comme ROLZ3 sélectionnent une table de hachage par pondération de contextes, ce qui permet d'obtenir de meilleurs ratios de compression à une vitesse moindre.

Un algorithme de type ROLZ n'ayant qu'une unique suite de symboles par table de hachage est équivalent à un algorithme de type LZP.

Implémentations

ROLZ est implémenté dans le compresseur grand public WinRK, ainsi que dans un certain nombre de compresseurs expérimentaux comme RK, QUAD, RZM, BALZ...

Performances

Les algorithmes de type ROLZ permettent en général d'offrir de bons ratios de compression à une vitesse relativement élevée (inférieure à celle de purs LZ77, cependant).

L'algorithme est asymétrique, ce qui signifie que la décompression est significativement plus rapide que la compression.