Algorytm Huffmana
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:
Algorytm Huffmana w języku C++Algorytm Huffmana w języku C++,
Algorytm Huffmana w języku JavaAlgorytm Huffmana w języku Java,
Algorytm Huffmana w języku PythonAlgorytm Huffmana w języku Python.
Więcej zadań? Sięgnij do Algorytm Huffmana – zadania maturalneAlgorytm Huffmana – zadania maturalne.
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.