DOWNLOAD:
* LHA 2.11_S.EXE (Source Code)
Storia della compressione dei dati in Giappone
Nel 1987, un editore di una rivista mi chiese di
scrivere un articolo sulla compressione dei dati.
Ho scritto un manoscritto e un programma di
accompagnamento, li ho inviati all'editore e me
ne sono dimenticato. La volta successiva che
l'ho sentito mi è stato detto che la rivista era
stata interrotta. Così ho caricato il mio
programma, una semplice implementazione
dell'algoritmo di compressione LZSS (vedi sotto)
su PC-VAN , una grande BBS giapponese gestita da
NEC. Era il 1 maggio 1988.
Presto un certo numero di programmatori per
hobby si riunì e iniziò a migliorare quel
programma. Il progetto è culminato
nell'archiviatore LArc di Kazuhiko Miki , che è
stato ampiamente utilizzato in Giappone. (Il
dottor Miki era allora uno specialista medico
che lavorava in un ufficio governativo. Ho
sentito che ha lasciato l'incarico e ha iniziato
a lavorare sulla promozione di
freeware/shareware.)
L'algoritmo LZSS si basa su un'idea molto
semplice. Supponiamo che scriva qui "compressione".
Ma probabilmente ho già usato quella parola
prima in questo file. Se ho usato quella parola
57 caratteri prima, potrei anche scrivere "vai
indietro di 57 caratteri e leggi 11 caratteri" o
<57,11> in breve. In generale, quando ho già
utilizzato la stringa di caratteri tra i recenti
4096 caratteri, ad esempio, codifico la stringa
con una coppia <posizione,lunghezza>.
Nella terminologia di Storer [8] , questo è un
algoritmo di dizionario scorrevole, analizzato
prima da Ziv e Lempel [14] e poi da Storer e
Szymanski [9] , tra gli altri.
Versioni successive delle mie implementazioni
LZSS e LArc di Miki usavano alberi di ricerca
binari per rendere più veloce la ricerca di
stringhe; vedi Campana [1] .
Per inciso, ci sono due distinti metodi Ziv-Lempel
(LZ): dizionario scorrevole [14] e dizionario
dinamico [15] nella terminologia di Storer [8] .
L'algoritmo LZW [12] appartiene a quest'ultimo.
La maggior parte degli strumenti di compressione
pre- LHarc , come 'compress', 'ARC' e 'PKARC',
usavano LZW.
Durante l'estate del 1988, ho scritto un altro
programma di compressione, LZARI . Questo
programma si basa sulla seguente osservazione:
Ogni output di LZSS è un singolo carattere o una
coppia <posizione,lunghezza>. Un singolo
carattere può essere codificato come un numero
intero compreso tra 0 e 255. Per quanto riguarda
il campo <lunghezza>, se l'intervallo di <lunghezza>
è compreso tra 2 e 257, ad esempio, può essere
codificato come un numero intero compreso tra
256 e 511. Pertanto, Posso dire che ci sono 512
tipi di "caratteri", ei "caratteri" da 256 a 511
sono accompagnati da un campo <posizione>.
Questi 512 "caratteri" possono essere codificati
da Huffman, o meglio ancora, codificati
algebricamente. Il campo <posizione> può essere
codificato nello stesso modo. In LZARI ho
utilizzato una compressione algebrica adattiva
[13] ,per codificare i "caratteri" e la
compressione algebrica statica per codificare il
campo <posizione>. (C'erano diverse versioni di
LZARI ; alcune erano leggermente diverse dalla
descrizione precedente.) La compressione di
LZARI era molto stretta, anche se piuttosto
lenta.
Haruyasu Yoshizaki (Yoshi), medico e guru
programmatore per hobby, ha lavorato molto
duramente per rendere LZARI più veloce.
Soprattutto, ha sostituito la compressione
algebrica di LZARI con la codifica dinamica di
Huffman.
Il suo programma, LZHUF , ha avuto molto
successo. Era molto più veloce del mio LZARI .
Per quanto riguarda il rapporto di compressione,
Huffman non può battere la compressione
algebrica, ma la differenza si è rivelata molto
piccola.
Yoshi ha riscritto il motore di compressione di
LZHUF in assembler e ha aggiunto un'elegante
interfaccia utente. Il suo archiviatore, LHarc ,
divenne presto lo standard de facto tra gli
utenti BBS giapponesi. Dopo che il Prof.
Kenjirou Okubo, un matematico, ha introdotto
LHarc negli Stati Uniti, è diventato famoso in
tutto il mondo. Altri fornitori hanno iniziato a
utilizzare tecniche simili: dizionario
scorrevole più compressioni statistiche come
Huffman e Shannon-Fano. (Mi chiedevo perché
usassero Shannon-Fano piuttosto che Huffman che
è garantito per comprimere meglio di Shannon-Fano.
Come si è scoperto, un libro allora popolare
sulla compressione pubblicato negli Stati Uniti
conteneva una descrizione errata e programmi di
esempio difettosi, in modo tale che Shannon -Fano
ha superato Huffman (buggy) su molti file.)
Sebbene LHarc fosse molto più veloce di LZARI ,
non eravamo del tutto soddisfatti della sua
velocità. Poiché LHarc era basato su Huffman
dinamico, doveva aggiornare l'albero di Huffman
ogni volta che riceveva un personaggio. Yoshi e
io abbiamo provato altri algoritmi dinamici di
Huffman [5] , [10] , [11] , ma i miglioramenti
non sono stati così grandi come desideravamo.
Quindi ho fatto un passo diverso: sostituire
l'Huffman dinamico di LHarc con un metodo
Huffman statico.
L'algoritmo di codifica Huffman statico
tradizionale analizza prima il file di input per
contare la distribuzione dei caratteri, quindi
crea l'albero di Huffman e codifica il file. Nel
mio approccio, il file di input viene letto solo
una volta. Viene prima compresso con un metodo
di dizionario scorrevole come LZARI e LHarc , e
allo stesso tempo vengono contate le
distribuzioni dei "caratteri" (vedi sopra) e le
posizioni. L'output di questo processo viene
memorizzato nella memoria principale. Quando il
buffer in memoria è pieno (o l'input è esaurito),
vengono costruiti gli alberi di Huffman e il
contenuto parzialmente elaborato del buffer
viene effettivamente compresso ed emesso.
In Huffman statico, l'albero di Huffman deve
essere memorizzato nel file compresso.
Nell'approccio tradizionale queste informazioni
consumano centinaia di byte. Il mio approccio è
stato quello di standardizzare gli alberi di
Huffman in modo che (1) ogni sottoalbero
sinistro non sia più profondo della sua
controparte destra e (2) le foglie allo stesso
livello siano ordinate in ordine crescente. In
questo modo l'albero di Huffman può essere
specificato in modo univoco dalla lunghezza
delle parole in codice. Inoltre, la tabella
risultante viene nuovamente compressa dallo
stesso algoritmo di Huffman.
Per semplificare il programma di decodifica,
l'albero di Huffman è regolato in modo che la
lunghezza delle parole di codice non superi i 16
bit. Poiché questa regolazione è raramente
necessaria, l'algoritmo è reso molto semplice.
Non crea alberi Huffman ottimali di lunghezza
limitata; si veda ad esempio [6] per un
algoritmo ottimo. Per inciso, il mio primo
programma aveva un bug qui, che è stato
rapidamente segnalato e corretto da Yoshi.
Anche l'algoritmo del dizionario scorrevole è
migliorato da Yoshi utilizzando una struttura
dati "PATRICIA tree"; vedi McCreight [7] e Fiala
e Greene [4] .
Dopo aver completato il mio algoritmo, ho
appreso che Brent [3] utilizzava anche un
dizionario scorrevole più la codifica di
Huffman. Il suo metodo, SLH , è semplice ed
elegante, ma poiché non trova la corrispondenza
più lunga più recente, la distribuzione della
posizione della partita diventa piatta. Ciò
rende la compressione di Huffman di secondo
stadio meno efficiente.
Sulla base di questi nuovi algoritmi, Yoshi
iniziò a riscrivere il suo LHarc , ma gli ci
volle così tanto tempo (ricordate che era un
dottore impegnato!) che decisi di scrivere il
mio archiviatore. Il mio archiviatore è stato
sconsideratamente chiamato 'ar'. (In realtà ho
aggiunto i numeri di versione come in 'ar002'
per la versione 0.02.) Avrei dovuto chiamarlo 'har'
(dopo il mio nome), diciamo, perché 'ar' collide
con il nome dell'archiviatore di UNIX. Non
volevo che il mio programma competesse con LHarc
, ma volevo che molte persone provassero
l'algoritmo, quindi l'ho scritto in puro ANSI C.
Questo è il motivo per cui ad 'ar' mancavano
molti campanelli e fischietti necessari per un
vero archiviatore.
Nota: la versione di 'ar002' trovata più spesso
negli Stati Uniti aveva un bug. La riga 24 di
maketbl.c dovrebbe contenere, ovviamente,
mentre (i <= 16) {
peso[i] = 1U << (16 - i); io++;
}
In qualche modo il bug non si è presentato
quando è stato compilato da Turbo C.
Yoshi ci ha finalmente mostrato il suo nuovo
archiviatore scritto in C. Si chiamava
provvisoriamente LHx . Ha quindi riscritto la
logica principale in assembler. Yoshi ed io
abbiamo scritto un articolo che descriveva il
suo nuovo archiviatore, che si sarebbe chiamato
LH , nel numero di gennaio 1991 di "C Magazine"
(in giapponese). Il suffisso 'arc' di LHarc è
stato deliberatamente eliminato perché le
persone che hanno venduto ARC non volevano che
altri usassero il nome.
Poi abbiamo appreso che per il nuovo DOS 5.0, LH
significava LoadHigh, un comando interno.
Abbiamo deciso di rinominare LH in LHA .
Inoltre, mi è stato detto che l'algoritmo
descritto in Fiala e Greene [4] è stato
brevettato ("Textual Substitution Data
Compression With Finite Length Search Windows",
brevetto USA 4,906,991, 6 marzo 1990. In realtà
hanno ottenuto tre brevetti! Gli altri due erano:
"Start, Step, Stop Unary Encoding for Data
Compression", Application Ser. No. 07/187,697, e
"Search Tree Data Structure Encoding for Textual
Substitution Data Compression Systems,"
Application Ser. No. 07/187,699.)
Inoltre, ho appreso che il metodo originale di
compressione Ziv-Lempel (Eastman et al., US
Patent 4,464,650, 8/1984) e il metodo LZW
(Welch, 4,558,302, 12/1985) sono stati
brevettati. Ho anche sentito che Richard
Stallman, della Free Software Foundation, autore
dell'editor EMACS e leader del progetto GNU, ha
smesso di usare il programma "compress" perché
il suo algoritmo LZW è stato brevettato.
Gli algoritmi sono brevettabili? (Vedi [16] .)
Se questi brevetti dovessero essere presi sul
serio, tutti i programmi di compressione
attualmente in uso potrebbero violare alcuni di
questi brevetti. (Fortunatamente, non tutte le
affermazioni fatte da quei brevetti di algoritmi
sembrano essere valide.)
Quanto sopra è una leggera modifica di quanto ho
scritto nel 1991. Il 1991 è stato un anno molto
intenso per me. Nel 1992 sono entrato a far
parte della facoltà dell'Università di Matsusaka.
Questa opportunità avrebbe dovuto darmi più
tempo libero, ma alla fine sono diventato sempre
più impegnato. Ho smesso di hackerare i miei
algoritmi di compressione; così ha fatto Yoshi.
Fortunatamente, tutte le cose buone in LHA sono
state rilevate e tutte le cose cattive
abbandonate dal nuovo fantastico archiviatore
zip e dallo strumento di compressione gzip .
Ammiro gli sforzi di Jean-loup Gailly e altri.
Un breve commento storico su PKZIP : Un tempo io
e un programmatore di PK eravamo in stretto
contatto. Abbiamo scambiato molte idee. Non c'è
da stupirsi che PKZIP e LHA siano così simili.
Un altro commento storico: LHICE e ICE non sono
sicuramente scritti da Yoshi (o da me o da
chiunque conosca). Penso che siano versioni
contraffatte di LHarc .
RIFERIMENTI
[1]
Timothy C. Bell. Migliore compressione del testo
OPM/L. Transazioni IEEE sulle comunicazioni,
COM-34(12):1176--1182, 1986.
[2]
Timothy C. Bell, John G. Cleary e Ian H. Witten.
Compressione del testo . Prentice Hall, 1990.
[3]
R.P. Brent. Un algoritmo lineare per la
compressione dei dati. The Australian Computer
Journal, 19(2):64-68, 1987.
[4]
Edward R. Fiala e Daniel H. Greene. Compressione
dei dati con finestre finite. Comunicazioni
dell'ACM, 32(4):490--505, 1989.
[5]
Donald E. Knuth. Codifica dinamica di Huffman.
Journal of Algorithms, 6:163-180, 1985.
[6]
Lawrence L. Larmore e Daniel S. Hirschberg. Un
algoritmo veloce per codici di Huffman ottimali
di lunghezza limitata. Journal of the
Association for Computing Machinery,
37(3):464--473, 1990.
[7]
Edward M. McCreight. Un algoritmo di costruzione
dell'albero dei suffissi economico in termini di
spazio. Journal of the Association for Computing
Machinery, 23(2):262--272, 1976.
[8]
James A. Conservatore. Compressione dei dati:
metodi e teoria . Computer Science Press,
Rockville, MD, 1988.
[9]
James A. Storer e Thomas G. Szymanski.
Compressione dei dati tramite sostituzione
testuale. Journal of the Association for
Computing Machinery, 29(4):928-951, 1982.
[10]
Jeffrey Scott Vitter. Progettazione e analisi di
codici dinamici di Huffman. Journal of the
Association for Computing Machinery,
34(4):825--845, 1987.
[11]
Jeffrey Scott Vitter. Algoritmo 673: codifica
dinamica di Huffman. Transazioni ACM sul
software matematico, 15(2):158-167, 1989.
[12]
Terry A. Welch. Una tecnica per la compressione
dei dati ad alte prestazioni. Computer IEEE},
17(6):8-19, 1984.
[13]
Ian H. Witten, Radford M. Neal e John G. Cleary.
Codifica aritmetica per la compressione dei dati.
Comunicazioni dell'ACM, 30(6):520--540, 1987.
[14]
Jacob Ziv e Abramo Lempel. Un algoritmo
universale per la compressione sequenziale dei
dati. IEEE Transactions on Information Theory,
IT-23(3):337--343, 1977.
[15]
Jacob Ziv e Abramo Lempel. Compressione di
singole sequenze tramite codifica a velocità
variabile. IEEE Transactions on Information
Theory, IT-24(5):530--536, 1978.
[16]
Edward N.Zalta. Gli algoritmi sono brevettabili?
Avvisi dell'American Mathematical Society,
35(6):796--799, 1988.
Haruhiko Okumura,
okumura@matsusaka-u.ac.jp
Ultima modifica: Mar 17 Mar 17:02:03 1998