Zmodyfikowane kodowanie Huffmana - Modified Huffman coding

Zmodyfikowane kodowanie Huffmana jest używane w faksach do kodowania obrazów czarno-białych ( bitmap ). Łączy kody o zmiennej długości kodowania Huffmana z kodowaniem powtarzalnych danych w kodowaniu ciągłym .

Podstawowe kodowanie Huffmana zapewnia sposób kompresji plików, które mają wiele powtarzających się danych, takich jak plik zawierający tekst, w którym litery alfabetu są powtarzającymi się obiektami. Jednak pojedyncza linia skanowania zawiera tylko dwa rodzaje elementów - białe piksele i czarne piksele - które można przedstawić bezpośrednio jako 0 i 1. Ten „alfabet” składający się tylko z dwóch symboli jest zbyt mały, aby bezpośrednio zastosować kodowanie Huffmana . Ale jeśli najpierw użyjemy kodowania typu run-length, będziemy mogli zakodować więcej obiektów. Oto przykład zaczerpnięty z artykułu o kodowaniu run-length :

Hipotetyczna linia skanowania, w której B reprezentuje czarny piksel, a W reprezentuje biel, może wyglądać następująco: 

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

Po zastosowaniu algorytmu kompresji danych z kodowaniem długości serii (RLE) do powyższej hipotetycznej linii skanowania można go renderować w następujący sposób: 

12W1B12W3B24W1B14W

Tutaj widzimy, że oprócz dwóch pozycji „biały” i „czarny” mamy kilka różnych numerów. Liczby te zapewniają wiele dodatkowych elementów do użycia, więc kodowanie Huffmana można bezpośrednio zastosować do powyższej sekwencji, aby jeszcze bardziej zmniejszyć rozmiar.

Zobacz też

Zewnętrzne linki

  • „Zmodyfikowane kodowanie Huffmana z UNESCO” . Zarchiwizowane od oryginału w dniu 2002-06-28.