Dynamiczne kodowanie Huffmana

Witam!
Chcę napisać program do kompresji za pomocą dynamicznych drzew Huffmana. Problem w tym, że nie mogę nigdzie znaleźć konkretnej informacji na temat istoty kompresji/dekompresji tą metodą. Wiem już jak się wprowadza nowy symbol do drzewa i jak się je aktualizuje, lecz nie wiem co po kolei powinien robić program przy kompresji/dekompresji. Dokładniej chodzi mi o konkretne kroki działania np. wyprowadź słowo -> zaktualizuj drzewo itp. Byłbym bardzo wdzięczny jeżeli ktoś mógłby mi pomóc ponieważ w internecie nie mogę znaleźć takiego jednoznacznego opisu. Z góry dzięki za pomoc.

hmm no przecieŻ samo kodowanie huffmana to wszedzie znajdziesz a dynamiczne to nie jest czasem ze obrabiasz jakis kawalek danych i dla niego tworzysz slownik, i tak w kolko ?

cepa napisał(a)

hmm no przecieŻ samo kodowanie huffmana to wszedzie znajdziesz a dynamiczne to nie jest czasem ze obrabiasz jakis kawalek danych i dla niego tworzysz slownik, i tak w kolko ?

Nie.
Przy dynamicznym kodowaniu huffmana przebudowuje się fragmenty drzewa w zależności od aktualnego rozkładu czestości wystąpień znaku.
Ogólnie algorytm kodowania jest taki:

1. Zbuduj drzewo dla jakiegoś wstępnego przybliżenia rozkładu znaków w strumieniu.
2. Wczytaj znak i zakoduj go.
3. Zmodyfikuj wagi na podstawie wczytanego znaku i przebuduj drzewo (są różne metody).
4. Wykonuj punkty 2-3 aż się nie skończy strumień.

Dekodowanie analogicznie.

Co do metod przebudowania drzewa, to z postu wnioskuję, że jakieś już znasz. Jeżeli nie to zapytaj kolegi google o FGK lub Vitter

Tzn. wiem, że drzewo jest tworzone na bieżąco i po kazdym symbolu (przy nowym jest dodawany do drzewa, przy już istniejącym w drzewie jest wyprowadzany kod) są aktualizowane wagi węzłów, a tym samym musi być zaktualizowana sama struktura drzewa. Wynika z tego, że drzewo zmienia się po wprowadzeniu praktycznie każdego symbolu do zakodowania. Ale nie wiem jak mam to zgrać tak, aby dekoder "umiał" to rozkodować :].

flangs napisał(a)

Ale nie wiem jak mam to zgrać tak, aby dekoder "umiał" to rozkodować :].

I to jest cała zabawa :)
Załóżmy, że na wstępie budujemy drzewo o równym rozkładzie częstości. Robi to zarółno koder jak i dekoder.
Jeżeli teraz mamy znak i zakodujemy go według aktualnego drzewa, to dekoder tak samo może ten pierwszy znak rozkodować, bo ma to samo drzewo.
Teraz, gdy aktualizujemy drzewo o znak, który właśnie zakodowaliśmy/odkodowaliśmy, to mamy identyczne drzewo w koderze i dekoderze.
Możemy więc spokojnie kontynuować dekodując kolejny znak i znowu modyfikując drzewo. Identyczne drzewo będziemy mieli zachowane w koderze i dekoderze, a właściwość kodów Huffmana zapewni nas, że nie będziemy mieli wątpliwości ile bitów odczytać.

No faktycznie :). Ale w takim razie w zakodowanym tekście muszę podać także alfabet w postaci ciągu, tak?

flangs napisał(a)

No faktycznie :). Ale w takim razie w zakodowanym tekście muszę podać także alfabet w postaci ciągu, tak?

Nie koniecznie. Koder i dekoder powinny znać alfabet a priori.
Jeżeli przyjmę, że moim alfabetem są znaki o kodach od 0 do 255, to taka informacja mi już wystarczy. Jeżeli przyjmę, że tylko małe literki alfabetu łacińskiego, to też mi wystarczy. Ciężko byłoby zrobić koder dla dowolnego alfabetu.
Za to może istnieć potrzeba przekazania wstępnego rozkładu częstości, tak jak konieczne jest to w statycznej wersji algorytmu. Tutaj jeżeli przyjmiemy jakiś rozkład z góry, to możemy tego uniknąć. Stracimy w ten sposób wydajność przy początku kodów, ale z czasem i tak osiągniemy odpowiednie kody. Można też zrobić pewne założenia. Np. jeżeli kodujemy tekst w języku polskim, to wstępny rozkład częstości możemy ustawić w koderze i dekoderze na znaną częstość występowania liter w języku polskim. Wówczas zachowamy dobre początkowe przybliżenie bez konieczności przesyłania tablicy częstości.

Muszę się nad tym głębiej zastanowić ;). Jeżeli natrafię jeszcze na jakiś poważniejszy problem, to zapytam. Nie mniej wielkie dzięki, bo bardzo mi pomogłeś :).

witam, ja mam male pytanko. jak sie wprowadza do drzewa nowy symbol. powiedzmy, ze mam alfabet ABCD, do tej pory w drzewie sa symbole A i B(wprowadzilismy slowo AB). a drzewo wyglada tak: kod dla A to {1}, dla B to {01}. kolejna litera jest C. co powinienem wyslac? jak dac informacje ze to nowa litera, skoro kod jest tylko binarny?

ok, juz znalazlem sopsob:) dla potomnych, jesli mamy slownik {DC} to jesli chcemy wprowadzic D to kodujemy je jako {pozycja slownika}10, natomiast C jako {pozycja slownika}110.
czyli liczba jedynek odpowiadajaca pozycji litery w slowniku(indeksujac od 1) + "0" na koncu.
z kolei {pozycja slownika} to jego kod w strukturze drzewa, bo slownik tez ma swoje miejsce.
no to tyle, chyba wsio jasne:)