R7yQWwRDJRzpo
Zdjęcie przedstawia fale na powierzchni plastiku, który załamuje światło w różne sposoby. Fotografia jest w kolorze zielonym, widoczne są na nim białe linie.

Algorytm Huffmana

Źródło: Michael Dziedzic, domena publiczna.

Zdarza się, że pewne informacje są zapisywane w postaci nadmiarowej, czyli z wykorzystaniem zbyt dużej liczby bitów. Aby zmniejszyć zużycie zasobów komputera możemy dokonać kompresji danych – to znaczy zakodować informacje w taki sposób, aby zaoszczędzić miejsce w pamięci komputera albo na dysku twardym.

Kompresję danych możemy podzielić na stratną i bezstratną. Jednym z algorytmów kompresji bezstratnej jest algorytm Huffmana. Stosując go, uzyskujemy – po rozkodowaniu danych – informację niezmienioną, identyczną jak początkowa. Algorytmu Huffmana używa się jako ostatniego etapu w różnych systemach kompresji, zarówno bezstratnej, jak i stratnej np. w formatach kompresji obrazu i dźwięku, np. JPEG, MPEG oraz MP3.

Implementacje omawianego zagadnienia w poszczególnych językach programowania znajdziesz w e‑materiałach:

Więcej zadań? Sięgnij do Algorytm Huffmana – zadania maturalnePI3BBhNy7Algorytm Huffmana – zadania maturalne.

Twoje cele
  • Dowiesz się, na czym polega algorytm Huffmana i poznasz listę czynności wykonywanych podczas jego realizacji.

  • Przeanalizujesz kodowanie przykładowego wyrazu zgodnie z algorytmem Huffmana.

  • Nauczysz się odkodowywać ciąg znaków, korzystając z drzewa Huffmana.