🚀 go-pugleaf

[Followup-To: pl.comp.programming]

On Mon, 20 Oct 1997, Przemysław Jachimiak wrote:

> Mam wielka prosbe do osób które posiadaja program (procedure) z dobrym
> algorytmem pakowania. Potrzeba jest wielka, bo trzeba napisac prace
> dyplomowa. 

Zacytuję fragment pewnego mojego listu:

-------- POCZĄTEK CYTATU

> Czy masz namiary na opis kompresji LZ po polsku? Zebralem kilka
> angielskich dokow i za nic nie moge zrozumiec o czym oni tam pisza. 

Mam tylko dwa opisy LZW po angielsku - jeden z opisu TIFFa, drugi jako
dodatek do opisu GIFa. Na tyle sensowne, że kiedyś sam zrobiłem LZW. Ale
teraz przeszedłem na LZ - inaczej Imploding (chyba LZ jest szerszą klasą,
do której należy LZW i Imploding; być może powinienem nazwać stosowany
przeze mnie algorytm Implodingiem, ale już wszystko jedno). Opisu LZ nie
mam. Chociaż przypomniałem sobie, że... 

Kiedyś rozmawiałem z mojim kolegą z liceum przez pliki tekstowe na
dyskietkach. Zwrócił się do mnie o pomoc w rozpakowywaniu pliku pewnej
gierki - chciał napisać do niej edytorek. Podał fragment spakowany i jak
on powinien wyglądać po rozpakowaniu. Oto część mojej odpowiedzi: 

-------- POCZĄTEK CYTATU (W CYTACIE)

Niestety nie umiem (nie da się) dokładnie odgadnąć algorytmu kompresji na
podstawie tego kawałka. Parę rzeczy jednak jest dla mnie oczywistych.
Owszem, jest to imploding, chociaż idea implodingu jest dość ogólna i
poszczególne implementacje znacznie się różnią między sobą; porównaj
zresztą programy PkLite, LzExe, ComPack, PgmPak, Diet, UcExe, Compress,
Paqj - wszystko to jest imploding, a każdy pakuje inaczej. Jednak w każdym
z tych przypadków (oprócz PgmPak) wspólny jest pewien pomysł, który nie
należy już do samego określenia implodingu; imploding Kuby K-Z go nie
stosuje. 

-------- (Kuba K-Z to nasz wspólny znajomy i nauczyciel informatyki w
naszym liceum. Wymyślił pewne przyspieszenie implodingu, którego nie udało
mi się z sukcesem zaimplementować - spowolniło ze dwa razy.  Oprócz tego
jego imploding operował na całych bajtach, a nie na bitach, i chyba gorzej
pakował.) 

Imploding wraz z tym pomysłem wygląda następująco. Algorytm pakujący
wypluwa równolegle dwa ciągi, które ja nazywam bajtowym i bitowym. Jak one
są zapisane, pokażę na przykładzie: dane postaci

  a AAAAAAAA b BBBBBBBB ccc CCCCCCCC ddddd DDDDDDDD e EEEEEEEE fffff FFFFFFFF

są zakodowane tak:

  abcccddd AAAAAAAA BBBBBBBB CCCCCCCC ddefffff DDDDDDDD EEEEEEEE FFFFFFFF. 

Często bity są grupowane po 16 a nie po 8, ale w WarCrafcie są po 8.

-------- (WarCraft to ta gierka, z której plik on próbował z moją
pomocą rozpakować)

Innymi słowy, algorytm rozpakowujący czyta bajt przez lodsb, a bit przez: 

    dec Licznik; jnz WTymSamym
    lodsb/lodsw; mov Bity,al/ax; mov Licznik,8/16
  WTymSamym: add Bity,Bity / shr Bity,1

(odczytany bit jest w CF). Wybór add/shr zależy od kolejności bitów w
grupie; w WarCrafcie potrzebne jest prawdopodobnie shr. 

Algorytm pakujący, zastanawiając się nad kolejnym bajtem, szuka w
poprzednio pakowanych danych ciągu zaczynającego się tak samo jak ciąg od
aktualnego miejsca. Jeśli nie znajdzie żadnego, to zapisuje bit 0 (ja)
albo 1 (WarCraft) i jeden bajt nie spakowany. Jeśli znajdzie, to wybiera
najdłuższy taki ciąg i zapisuje bit 1 (ja) albo 0 (WarCraft), a po nim
informację o odległości i długości kopii ciągu. Nie mam pojęcia, jak robi
to WarCraft. W tym miejscu są zresztą podstawowe różnice między
poszczególnymi implementacjami implodingu. Ja na przykład zapisuję starsze
bity odległości (bity powyżej ośmiu, ile - to zależy od pożądanego stopnia
kompresji;  dobre rezultaty dalą 4 bity w tym miejscu, co daje maksymalną
odległość 4096, zadziwiająco duża ilość danych pakuje się najlepiej
właśnie w tym przypadku), młodszy bajt odległości, dalej tyle bitów 0, ile
bitów ma liczba będąca długością, jeden bit 1, długość. Chodzi oczywiście
o to, żeby krótsze długości powtarzających się ciągów, jako częstsze, były
zapisywane krócej;  stwierdziłem eksperymentalnie, że wszystkie odległości
są w przybliżeniu jednakowo prawdopodobne, za to częstości poszczególnych
długości są bardzo zróżnicowane. 

Imploding dobrze zastępuje RLE; pomyśl dlaczego, tj. jak spakuje się
implodingiem ciąg bajtów 'AAAAAAAAAA'. 

-------- (Tu była próba analizy danego mi kawałka. Wycinam, bo
niepotrzebna) 

Dobrym sposobem poznawania algorytmów kompresji może być debugowanie
wyników PkLite'a itd., ewentualnie self-extract-archiwów, bo w tych
przypadkach procedura rozpakowywania z konieczności jest dość łatwa do
wyizolowania. Algorytm Rara można poznać teoretycznie jeszcze łatwiej, bo
jest dostępny unRar w wersji źródłowej, ale ten algorytm jest za
skomplikowany. Przy okazji - poluję na nowego Rara, wersja 2.ileś. 

-------- (Już nie poluję :-) )

Dziedzina kompresji danych jest bardzo rozległa, potrzebna, żywa i
ciekawa. Potrzebuje ona wielu zdolnych ludzi wymyślających coraz lepsze
algorytmy. Możesz się tym zainteresować, chociaż niestety nie mam żadnej
literatury na ten temat.

-------- KONIEC CYTATU (W CYTACIE)

Zastanawiałem się niedawno, czy tej starej korespondencji nie skasować :-) 
Na szczęście nie skasowałem. BTW: trzymam ją spakowaną właśnie RARem
2.ileś. 

Mnie podstaw Implodingu / LZ nauczył inny kolega z liceum. On sam
nauczył się go AFAIK debugując programy spakowane PkLitem albo czymś
podobnym. A opisu nigdy nie widziałem.

-------- KONIEC CYTATU

Opis musi Ci wystarczyć :-)

                                QRCZAK
    __("<             Marcin Kowalczyk
    \__/             qrczak@knm.org.pl
     ^^      http://kki.net.pl/qrczak/