Kodowanie Huffmana to jedna z najprostszych i łatwych w implementacji metod kompresji bezstratnej. Została opracowana w 1952 roku przez Amerykanina Davida Huffmana. Algorytm Huffmana nie należy do najefektywniejszych systemów bezstratnej kompresji danych, dlatego też praktycznie nie używa się go samodzielnie. Często wykorzystuje się go jako ostatni etap w różnych systemach kompresji, zarówno bezstratnej jak i stratnej, np. MP3 lub JPEG. Pomimo, że nie jest doskonały, stosuje się go ze względu na prostotę oraz brak ograniczeń patentowych.
Algorytm: Dany jest alfabet źródłowy (zbiór symboli) oraz zbiór stowarzyszonych z nim prawdopodobieństw . Symbolami są najczęściej bajty, choć nie ma żadnych przeszkód żeby było nimi coś innego (np. pary znaków). Prawdopodobieństwa mogą zostać z góry określone dla danego zestawu danych, np. poprzez wyznaczenie częstotliwości występowania znaków w tekstach danego języka. Częściej jednak wyznacza się je indywidualnie dla każdego zestawu danych. Kodowanie Huffmana polega na utworzeniu słów kodowych (ciągów bitowych), których długość jest odwrotnie proporcjonalna do prawdopodobieństwa pi. Tzn. im częściej dane słowo występuje (może wystąpić) w ciągu danych, tym mniej zajmie bitów. Własności kodu są następujące:
  • kod Huffmana jest kodem prefiksowym; oznacza to, że żadne słowo kodowe nie jest początkiem innego słowa;
  • jeśli prawdopodobieństwa są różne, tzn. pj > pi, to długość kodu dla symbolu xj jest niewiększa od kodu dla symbolu xi;
  • słowa kodu dwóch najmniej prawdopodobnych symboli mają równą długość;
  • dwa najdłuższe symbole różnią się tylko jednym, ostatnim bitem.
Kompresja polega na zastąpieniu symboli otrzymanymi kodami.
Source: Wiki