Witam
Obecnie implementuję sobie różne algorytmy kompresji (w Ocaml'u). Zastanawia mnie sposób kodowania liczb w alg. LZW.
Jak wiadomo na początku mam na stałe ustalone numery kodów 0-255 dla jednoznakowych ciągów a następnie każdy dodawany ciąg (będący złożeniem ciągu ze słownika i znaku powodującego niedopasowanie) dostaje kolejny numer.
Zastanawiam się jak sprytnie rozwiązać problem kodowania tych numerów.
Zasadniczo problem jest taki. Rozpatruję strumień znaków i generuje pewne numery (przypisane do ciągów z LZW). Mógłbym określić jakieś górne ograniczenie na liczbę ciągów jakie zapiszę, czyli ograniczę tym samym długość wejściowego pliku, a następie zapisywać te nieujemne liczby binarnie np. za pomocą 4 bajtów. Czy można zrobić to jakoś sprytniej bez wprowadzania takiego ograniczenia?
Myślałem nad chwytem, który używany jest w alg. BZIP2 w drugim użyciu RLE, a mianowicie mamy alfabet A={S, T, E}.
E (End) oznacza koniec zapisu pojedyńczej liczby. Symbole S (single) i T (twice) tworzą zapis liczby "jakby w postaci binarnej" tj.
z wjeścia odczytujemy S T T E co oznacza liczbę 13.
1 2 4 8 16 Kolejne potęgi 2
S T T Odczytany ciąg
1 4 8 1+4+8=13
Odczytanie S na pozycji j=0,1,... dodaje do wyniku 2j. Odczytanie T na pozycji j dodaje do wyniku 2 * 2j.
Pewnie aby efektywnie wykorzystać zapis wszystkie bity powinienem zastosować czwórkę E, S, T, Q (Q daje 4 * 2^j).
Jak Wy byście zapisywali kody-numery dla ciągów z LZW?
Pozdrawiam i z góry dziękuję za odpowiedź
Bazyli