Histoire de la compression de données au Japon, les prémices du Lha

[Frog]

Le magazine OBLIGEMENT a publié un article intéressant sur la compression de donnée. Si cela vous interesse, voici l'article dans son intégralité.
Vous pouvez si vous le souhaitez le lire directement sur OBLIGEMENT accompagné de photos.

Bonne lecture

Dossier : Histoire de la compression de données au Japon, les prémices du Lha
(Article écrit par Haruhiko Okumura et extrait de oku.edu.mie-u.ac.jp - mars 1998)


Note : traduction par David Brunet.

En 1987, un éditeur de magazine m'avait demandé de rédiger un article sur la compression de données. J'avais écrit un manuscrit et un programme d'accompagnement, je les avais envoyés à l'éditeur. Mais je les ai oubliés. On m'a ensuite dit que le magazine avait arrêté sa publication. J'ai donc posté mon programme, une simple implémentation de l'algorithme de compression LZSS (voir ci-dessous) sur PC-VAN, un gros BBS japonais géré par NEC. Nous étions le 1er mai 1988.

Plus tard, un certain nombre de programmeurs amateurs se rassemblèrent et commencèrent à améliorer ce programme. Le projet donna au final LArc, un outil de compression de Kazuhiko Miki, assez utilisé au Japon. Le Dr Miki était alors un médecin spécialiste travaillant dans un bureau gouvernemental. J'ai entendu dire qu'il avait quitté ses fonctions et avait commencé à travailler sur la promotion des logiciels freewares et sharewares.

L'algorithme LZSS est basé sur une idée très simple. Supposons que j'écrive "compression", mais que j'ai déjà utilisé ce mot dans le fichier. Si je l'avais déjà utilisé 57 caractères plus tôt, je pourrais aussi bien écrire "retourne de 57 caractères en arrière et lis 11 caractères" ou en abrégé : <57,11>. En général, lorsque j'ai déjà utilisé la chaîne de caractères parmi les 4096 derniers caractères, je code la chaîne avec la paire <position,longueur>.

Dans la terminologie de Storer [8], il s'agit d'un algorithme à dictionnaire glissant, analysé d'abord par Ziv et Lempel [14], puis par Storer et Szymanski [9], entre autres.

Les versions ultérieures de mes implémentations de LZSS et de LArc de Kazuhiko Miki utilisaient des arbres de recherche binaires pour accélérer la recherche de chaînes (voir Bell [1]).

Incidemment, il existe deux méthodes distinctes de Ziv-Lempel : le dictionnaire glissant [14] et le dictionnaire dynamique [15] dans la terminologie de Storer [8]. L'algorithme LZW [12] appartient à ce dernier. La plupart des outils de compression pré-LHarc, tels que "compress", "ARC" et "PKARC", utilisaient LZW.

Au cours de l'été 1988, j'écrivis un autre programme de compression, LZARI. Ce programme était basé sur l'observation suivante : chaque sortie de LZSS est soit un seul caractère, soit une paire <position,longueur>. Un seul caractère peut être codé sous forme d'entier compris entre 0 et 255. En ce qui concerne le champ <longueur>, si la plage de <longueur> est comprise entre 2 et 257, par exemple, elle peut être codée sous forme d'entier compris entre 256 et 511. Ainsi, je peux dire qu'il existe 512 types de "caractères" et que les "caractères" 256 à 511 sont accompagnés d'un champ <position>. Ces 512 "caractères" peuvent être codés en codage de Huffman, ou mieux encore, codés algébriquement. Le champ <position> peut être codé de la même manière. Dans LZARI, j'utilisais une compression algébrique adaptative [13],[2] pour coder les "caractères" et une compression algébrique statique pour coder le champ <position> (il y avait plusieurs versions de LZARI ; certaines d'entre elles étaient légèrement différentes de la description ci-dessus). La compression de LZARI était très compacte, et plutôt lente.

Haruyasu Yoshizaki, médecin et programmeur amateur, a travaillé très dur pour rendre LZARI plus rapide. Plus important encore, il a remplacé la compression algébrique de LZARI par le codage dynamique de Huffman.

Son programme, LZHUF, a eu beaucoup de succès. Il était beaucoup plus rapide que mon LZARI. En ce qui concerne le taux de compression, le codage de Huffman ne peut pas battre la compression algébrique, mais la différence s'est avérée très petite.

Haruyasu Yoshizaki a réécrit le moteur de compression de LZHUF en assembleur et a ajouté une astucieuse interface utilisateur. Son archiveur, nommé LHarc, est rapidement devenu le standard de facto parmi les utilisateurs japonais de BBS.

Après que le professeur Kenjirou Okubo, un mathématicien, ait introduit LHarc aux États-Unis, il est devenu mondialement célèbre. D'autres développeurs ont commencé à utiliser des techniques similaires : dictionnaire glissant et compressions statistiques comme celles de Huffman et de Shannon-Fano. Je me demandais pourquoi ils utilisaient Shannon-Fano plutôt que Huffman, dont la compression est censée être plus compacte que celle de Shannon-Fano. En fait, un livre très populaire sur la compression publié aux États-Unis contenait une description erronée et des exemples de programmes bogués. Les programmes Shannon-Fano surpassaient les performances de ceux (bogués) de Huffman sur de nombreux fichiers.

Bien que LHarc soit beaucoup plus rapide que LZARI, nous n'étions pas satisfaits par sa vitesse. Comme LHarc était basé sur le codage dynamique de Huffman, il devait mettre à jour l'arbre de Huffman chaque fois qu'il recevait un caractère. Haruyasu Yoshizaki et moi avons essayé d'autres algorithmes dynamiques de Huffman [5],[10],[11], mais les améliorations ne furent pas aussi importantes que nous le souhaitions.

J'ai donc pris une mesure différente : remplacer le codage dynamique de Huffman de LHarc par une méthode de Huffman statique.

L'algorithme de codage de Huffman statique traditionnel analyse d'abord le fichier d'entrée pour compter la distribution des caractères, puis construit l'arbre de Huffman et code le fichier. Dans mon approche, le fichier d'entrée est lu une seule fois. Il est d'abord compressé par une méthode de dictionnaire glissant comme LZARI et LHarc, et en même temps, les distributions des "caractères" (voir ci-dessus) et les positions sont comptées. La sortie de ce processus est stockée dans la mémoire principale. Lorsque le tampon mémoire est plein (ou que l'entrée est épuisée), les arbres de Huffman sont construits et le contenu semi-traité du tampon mémoire est réellement compressé et sorti.

Dans le codage statique de Huffman, l'arbre de Huffman doit être stocké dans le fichier compressé. Dans l'approche traditionnelle, ces informations consomment des centaines d'octets. Mon approche consistait à normaliser les arbres de Huffman de telle sorte que chaque sous-arbre de gauche ne soit pas plus profond que son homologue de droite et que les feuilles du même niveau soient triées par ordre croissant. De cette façon, l'arbre de Huffman peut être spécifié de manière unique par la longueur des mots de code. De plus, la table résultante est à nouveau compressée par le même algorithme de Huffman.

Pour simplifier le programme de décodage, l'arbre de Huffman est ajusté de manière à ce que la longueur des mots de code ne dépasse pas 16 bits. Comme cet ajustement est rarement nécessaire, l'algorithme est très simple. Il ne crée pas d'arbres de Huffman optimaux de longueur limitée (voir par exemple [6] pour un algorithme optimal). Incidemment, mon premier programme contenait un bogue qui a été rapidement signalé et corrigé par Haruyasu Yoshizaki.

Haruyasu Yoshizaki améliora également l'algorithme du dictionnaire glissant en utilisant une structure de données "arbre PATRICIA" (voir McCreight [7] et Fiala et Greene [4]).

Après avoir complété mon algorithme, j'ai appris que Brent [3] utilisait également un dictionnaire glissant et le codage de Huffman. Sa méthode, SLH, est simple et élégante, mais comme elle ne trouve pas la dernière correspondance la plus récente, la distribution de la position de la correspondance devient plate. Cela rend moins efficace le deuxième étage de compression de Huffman.

Sur la base de ces nouveaux algorithmes, Haruyasu Yoshizaki a commencé à réécrire son LHarc, mais cela lui a pris si longtemps (rappelez-vous qu'il était occupé en tant que médecin !) que j'ai décidé d'écrire mon propre archiveur. Ce dernier a été imprudemment nommé "ar" (j'incorporais au nom les numéros de version : par exemple "ar002" pour la version 0.02). J'aurais dû le nommer "har" (d'après mon nom) car "ar" se heurtait au nom de l'archiveur d'Unix. Je ne voulais pas que mon programme soit en concurrence avec LHarc, mais comme je voulais que beaucoup de personnes essayent l'algorithme, je l'ai écrit en C ANSI. C'est pour cette raison qu'il manquait beaucoup d'options et de gadgets pour faire d'ar un véritable archiveur.

Remarque : la version de "ar002" la plus souvent trouvée aux États-Unis présentait un bogue. La ligne 24 de maketbl.c devrait se lire ainsi :

while (i <= 16) {
   weight = 1U << (16 - i);  i++;
}

Le bogue ne se présente pas lorsqu'il est compilé par Turbo C.

Haruyasu Yoshizaki nous a finalement montré son nouvel archiveur écrit en C. Il s'appelait provisoirement LHx. Il a ensuite réécrit la logique principale en assembleur. Haruyasu Yoshizaki et moi avons écrit un article décrivant son nouvel archiveur, qui devait s'appeller LH, dans le numéro de janvier 1991 de "C Magazine" (en japonais). Le suffixe "arc" de LHarc a été délibérément abandonné car les gens qui s'occupaient de vendre ARC ne souhaitaient pas que d'autres utilisent ce nom.

Ensuite, nous avons appris qu'avec le nouveau DOS 5.0, "LH" voulait dire "LoadHigh", qui était une de ses commandes internes. Nous avons alors décidé de renommer LH en LHA.

De plus, on m'a dit que l'algorithme décrit dans Fiala et Greene [4] avait été breveté : "Compression de données de substitution textuelle avec une fenêtre de longueur finie", brevet US 4 906 991 du 6 mars 1990. En fait, ils ont obtenu trois brevets ! Les deux autres étaient :
"Démarrage, étapes et arrêt du codage unaire pour la compression de données", demande n°07/187,697.
"Encodage de la structure de données de l'arbre de recherche pour les systèmes de compression de données à substitution textuelle", demande n°07/187,699.
En outre, j'ai appris que la méthode de compression Ziv-Lempel d'origine (Eastman et al., Brevet US 4 464 650, 8/1984) et la méthode LZW (Welch, Brevet US 4 558 302, 12/1985) étaient brevetées. J'ai aussi entendu dire que Richard Stallman, de la Free Software Foundation, auteur de l'éditeur EMACS et chef du projet GNU, avait cessé d'utiliser le programme "compress" parce que son algorithme LZW avait été breveté.

Les algorithmes sont-ils brevetables ? (voir [16]). Si ces brevets devaient être pris au sérieux, tous les programmes de compression actuellement utilisés pourraient enfreindre certains de ces brevets. Heureusement, toutes les revendications formulées par ces algorithmes ne semblent pas valables.

Ce qui précède est une légère modification de ce que j'avais écrit en 1991. L'année 1991 a été une année très chargée pour moi. En 1992, j'ai rejoint la faculté de l'Université de Matsusaka. Cette opportunité aurait dû me donner plus de temps libre, mais il s'est avéré que j'ai été de plus en plus occupé. J'ai arrêté le bidouillage de mes algorithmes de compression ; Haruyasu Yoshizaki aussi.

Heureusement, toutes les bonnes choses dans LHA ont été reprises et toutes les mauvaises choses ont été abandonnées par le nouveau grand archiveur Zip et l'outil de compression gzip. J'admire les efforts de Jean-Loup Gailly et d'autres.

Un bref commentaire historique sur PKZIP : à une époque, un programmeur de PK et moi étions en étroit contact. Nous avons échangé beaucoup d'idées. Ce n'est donc pas étonnant que PKZIP et LHA soient si similaires.

Autre commentaire historique : LHICE et ICE n'ont certainement pas été écrits par Haruyasu Yoshizaki (ni par moi ni par personne que je connaisse). Je pense qu'elles sont des versions piratées de LHarc.

Références

[1] Timothy C. Bell. Better OPM/L text compression. IEEE Transactions on Communications, COM-34(12):1176--1182, 1986.

[2] Timothy C. Bell, John G. Cleary, and Ian H. Witten. Text Compression. Prentice Hall, 1990.

[3] R. P. Brent. A linear algorithm for data compression. The Australian Computer Journal, 19(2):64--68, 1987.

[4] Edward R. Fiala and Daniel H. Greene. Data compression with finite windows. Communications of the ACM, 32(4):490--505, 1989.

[5] Donald E. Knuth. Dynamic Huffman coding. Journal of Algorithms, 6:163--180, 1985.

[6] Lawrence L. Larmore and Daniel S. Hirschberg. A fast algorithm for optimal length-limited Huffman codes. Journal of the Association for Computing Machinery, 37(3):464--473, 1990.

[7] Edward M. McCreight. A space-economical suffix tree construction algorithm. Journal of the Association for Computing Machinery, 23(2):262--272, 1976.

[8] James A. Storer. Data Compression: Methods and Theory. Computer Science Press, Rockville, MD., 1988.

[9] James A. Storer and Thomas G. Szymanski. Data compression via textual substitution. Journal of the Association for Computing Machinery, 29(4):928--951, 1982.

[10] Jeffrey Scott Vitter. Design and analysis of dynamic Huffman codes. Journal of the Association for Computing Machinery, 34(4):825--845, 1987.

[11] Jeffrey Scott Vitter. Algorithm 673: Dynamic Huffman coding. ACM Transactions on Mathematical Software, 15(2):158--167, 1989.

[12] Terry A. Welch. A technique for high-performance data compression. IEEE Computer}, 17(6):8--19, 1984.

[13] Ian H. Witten, Radford M. Neal, and John G. Cleary. Arithmetic coding for data compression. Communications of the ACM, 30(6):520--540, 1987.

[14] Jacob Ziv and Abraham Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, IT-23(3):337--343, 1977.

[15] Jacob Ziv and Abraham Lempel. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, IT-24(5):530--536, 1978.

[16] Edward N. Zalta. Are algorithms patentable? Notices of the American Mathematical Society, 35(6):796--799, 1988.

[Frog]

Il y a aussi sur EAB plusieurs discussions sur les depackers Amiga :
Decompression en temps réel la plus rapide
Test et comparatif de compression/decompression sur 68000

Ca bosse dur sur les algorithmes les gars !!

[Lio]

il me semble qu'il y en a aussi un sur Amiga Impact écrit par Denis (le gars qui avait l'énorme collection de jeux Amiga en boîte, collection qui a brûlé dans l'incendie de sa maison)

[Frog]

pauvre Denis, je ne savais pas que sa maison avait brulé. J'espère qu'il va bien. Il venait regulièrement autrefois et proposait des scans et des jeux ipf. Je le lis parfois sur EAB.
Bigre toute une collection qui brule....

[Lio]

il me semble qu'il en a parlé ici aussi... mais comme son compte n'est plus actif (dlfrsilver est marqué comme invité) il est difficile de retrouver le sujet.

par contre on en a parlé sur AmigaImpact : https://www.amigaimpact.org/forums/topic/sale-coup-pour-dlfrsilver/
c'était en 2013 (p****n 6 ans déjà !)

bon sinon je pense que je confonds : Denis a publié un sujet sur la protection des jeux et pas sur la compression, mea culpa !