Algorytm Huffmana służy do kompresji lub kodowania danych. Normalnie każdy znak w pliku tekstowym jest przechowywany jako osiem bitów (cyfry, 0 lub 1), które są odwzorowywane na ten znak przy użyciu kodowania zwanego ASCII. Plik zakodowany w Huffmana rozbija sztywną 8-bitową strukturę tak, że najczęściej używane znaki są przechowywane w zaledwie kilku bitach ('a' może być "10" lub "1000" zamiast ASCII, czyli "01100001"). Najmniej popularne znaki często zajmują znacznie więcej niż 8 bitów ('z' może być "00100011010"), ale ponieważ występują tak rzadko, kodowanie Huffmana, ogólnie rzecz biorąc, tworzy znacznie mniejszy plik niż oryginał.
Kroki
Część 1 z 2: Kodowanie
Krok 1. Policz częstotliwość każdego znaku w pliku do zakodowania
Dołącz fikcyjny znak, aby oznaczyć koniec pliku - będzie to ważne później. Na razie nazwij go EOF (koniec pliku) i oznacz go jako mający częstotliwość 1.
Na przykład, jeśli chcesz zakodować plik tekstowy z napisem „ab ab cab”, miałbyś „a” z częstotliwością 3, „b” z częstotliwością 3, „” (spacja) z częstotliwością 2, „c” z częstotliwością 1, oraz EOF z częstotliwością 1
Krok 2. Przechowuj znaki jako węzły drzewa i umieść je w kolejce priorytetowej
Będziesz budować duże drzewo binarne z każdym znakiem jako liściem, więc powinieneś przechowywać znaki w takim formacie, aby mogły stać się węzłami drzewa. Umieść te węzły w kolejce priorytetowej z częstotliwością każdego znaku jako priorytetem węzła.
- Drzewo binarne to format danych, w którym każda część danych jest węzłem, który może mieć maksymalnie jednego rodzica i dwoje dzieci. Często jest rysowany jako rozgałęzione drzewo, stąd nazwa.
- Kolejka to zbiór danych o trafnej nazwie, w którym pierwsza rzecz, która trafia do kolejki, jest również pierwszą rzeczą, która wychodzi (jak czekanie w kolejce). W kolejce priorytetowej dane są przechowywane w kolejności ich priorytetów, tak aby pierwsza rzecz, która wyjdzie, to najpilniejsza rzecz, rzecz o najniższym priorytecie, a nie pierwsza rzecz w kolejce.
- W przykładzie „ab ab cab” kolejka priorytetowa wyglądałaby tak: {'c':1, EOF:1, ' ':2, 'a':3, 'b':3}
Krok 3. Zacznij budować swoje drzewo
Usuń (lub usuń z kolejki) dwie najpilniejsze rzeczy z kolejki priorytetowej. Utwórz nowy węzeł drzewa, który będzie rodzicem tych dwóch węzłów, przechowując pierwszy węzeł jako jego lewy potomek, a drugi jako jego prawy potomek. Priorytet nowego węzła powinien być sumą priorytetów jego dziecka. Następnie umieść ten nowy węzeł w kolejce priorytetowej.
Kolejka priorytetowa wygląda teraz tak: {' ':2, nowy węzeł:2, 'a':3, 'b':3}
Krok 4. Zakończ budowę swojego drzewa:
powtarzaj powyższy krok, aż w kolejce będzie tylko jeden węzeł. Zauważ, że oprócz węzłów, które utworzyłeś dla znaków i ich częstotliwości, będziesz także dekolejkować, zamieniać w drzewa i ponownie umieszczać w kolejce węzły nadrzędne, węzły, które same są drzewami.
- Kiedy skończysz, ostatni węzeł w kolejce będzie korzeniem drzewa kodowania, a wszystkie inne węzły będą od niego odchodzić.
- Najczęściej używanymi znakami będą liście znajdujące się najbliżej wierzchołka drzewa, natomiast rzadko używane znaki będą umieszczone na dole drzewa, dalej od korzenia.
Krok 5. Utwórz mapę kodowania. Przejdź po drzewie, aby dotrzeć do każdej postaci. Za każdym razem, gdy odwiedzasz lewe dziecko węzła, jest to „0”. Za każdym razem, gdy odwiedzasz właściwe dziecko węzła, jest to „1”. Kiedy dotrzesz do postaci, zapisz ją z sekwencją zer i jedynek, które zajęło jej dotarcie. Ta sekwencja jest tym, co znak będzie zakodowany w skompresowanym pliku. Przechowuj postacie i ich sekwencje na mapie.
- Na przykład zacznij od korzenia. Odwiedź lewe dziecko korzenia, a następnie odwiedź lewe dziecko tego węzła. Ponieważ węzeł, w którym się teraz znajdujesz, nie ma żadnych dzieci, osiągnąłeś postać. To jest ' '. Ponieważ dwukrotnie przeszedłeś w lewo, aby się tu dostać, kodowanie znaku „” to „00”.
- Dla tego drzewa mapa będzie wyglądać tak: {' ':"00", 'a':"10", 'b':"11", 'c':"010", EOF:"011"}.
Krok 6. W pliku wyjściowym dołącz mapę kodowania jako nagłówek
Umożliwi to dekodowanie pliku.
Krok 7. Zakoduj plik
Dla każdego znaku w pliku, który ma zostać zakodowany, napisz sekwencję binarną, którą zachowałeś na mapie. Po zakończeniu kodowania pliku upewnij się, że dodałeś EOF na końcu.
- W przypadku pliku „ab ab cab” zakodowany plik będzie wyglądał następująco: „1011001011000101011011”.
- Pliki są przechowywane w bajtach (8 bitów lub 8 cyfr binarnych). Ponieważ algorytm kodowania Huffmana nie używa formatu 8-bitowego, zakodowane pliki często nie będą miały długości będącej wielokrotnością 8. Pozostałe cyfry zostaną wypełnione zerami. W takim przypadku na końcu pliku zostaną dodane dwa zera, co wygląda jak kolejna spacja. To może być problem: skąd dekoder wiedziałby, kiedy przestać czytać? Jednakże, ponieważ dodaliśmy znak końca pliku, dekoder przejdzie do tego, a następnie zatrzyma się, ignorując wszystko, co zostało dodane później.
Część 2 z 2: Dekodowanie
Krok 1. Przeczytaj plik zakodowany w formacie Huffmana
Najpierw przeczytaj nagłówek, który powinien być mapą kodowania. Użyj tego, aby zbudować drzewo dekodujące w ten sam sposób, w jaki zbudowałeś drzewo, którego użyłeś do zakodowania pliku. Dwa drzewa powinny być identyczne.
Krok 2. Wczytaj binarną jedną cyfrę na raz
Przechodź przez drzewo podczas czytania: jeśli czytasz jako „0”, przejdź do lewego dziecka węzła, w którym się znajdujesz, a jeśli czytasz jako „1”, przejdź do prawego dziecka. Kiedy dotrzesz do liścia (węzła bez dzieci), dotarłeś do postaci. Napisz znak do zdekodowanego pliku.
Ze względu na sposób, w jaki znaki są przechowywane w drzewie, kody dla każdego znaku mają właściwość prefiksu, dzięki czemu kodowanie binarne żadnego znaku nie może nigdy wystąpić na początku kodowania innego znaku. Kodowanie każdego znaku jest całkowicie unikalne. To znacznie ułatwia dekodowanie
Krok 3. Powtarzaj, aż dojdziesz do EOF
Gratulacje! Odkodowałeś plik.
