Kody Huffmana: przykłady, aplikacje

W tej chwili niewiele osób myśli o tym fakcie,jak działa kompresja. W porównaniu do przeszłości, korzystanie z komputera stało się znacznie łatwiejsze. I praktycznie każda osoba pracująca z systemem plików używa archiwów. Ale niewiele osób myśli o tym, jak działają i na jakiej zasadzie jest kompresja plików. Pierwszą wersją tego procesu były kody Huffmana i nadal są używane w różnych popularnych archiwach. Wielu użytkowników nie myśli nawet, jak łatwo skompresować plik i zgodnie z którym systemem działa. W tym artykule przyjrzymy się, jak kompresja jest wykonywana, jakie niuanse pomagają przyspieszyć i uprościć proces kodowania, a my odkryjemy, na czym polega zasada konstruowania drzewa kodującego.

Historia algorytmu

Pierwszy algorytm skutecznykodowanie informacji elektronicznych było kodem zaproponowanym przez Huffmana w połowie XX wieku, a mianowicie w 1952 roku. Jest to obecnie główny podstawowy element większości programów stworzonych do kompresowania informacji. Obecnie jednym z najpopularniejszych źródeł wykorzystujących ten kod są archiwa ZIP, ARJ, RAR i wiele innych.

Ten algorytm Huffmana jest również używany dlakompresja obrazów JPEG i innych obiektów graficznych. Cóż, wszystkie nowoczesne faksy również używają kodowania, wynalezionego w 1952 roku. Pomimo faktu, że od momentu powstania kodu minęło tyle czasu, do dnia dzisiejszego jest on stosowany w najnowszych muszlach i sprzęcie starych i współczesnych typów.

Zasada wydajnego kodowania

Podstawą algorytmu Huffmana jest schemat,Pozwala na zastąpienie najbardziej prawdopodobnych, najczęściej spotykanych symboli z kodami systemu binarnego. A te, które są mniej powszechne, są zastępowane dłuższymi kodami. Przejście na długie kody Huffmana następuje dopiero po wykorzystaniu przez system wszystkich minimalnych wartości. Ta technika pozwala zminimalizować długość kodu każdego znaku oryginalnej wiadomości jako całości.

Ważne jest to, że na początkukodowanie prawdopodobieństwa wystąpienia liter powinno być już znane. To z nich powstanie ostateczna wiadomość. Na podstawie tych danych konstruowane jest drzewo kodu Huffmana, na podstawie którego zostanie przeprowadzony proces kodowania liter w archiwum.

Kod Huffmana, przykład

Aby zilustrować algorytm, weźmygraficzna wersja konstrukcji drzewa kodu. Aby ta metoda była skuteczna, warto wyjaśnić definicję niektórych wartości niezbędnych dla koncepcji tej metody. Zestaw łuków i węzłów, które są kierowane z węzła do węzła, jest zwykle nazywany wykresem. Samo drzewo jest wykresem z zestawem określonych właściwości:

• każdy węzeł może zawierać nie więcej niż jeden łuk;
• jeden z węzłów musi być korzeniem drzewa, to znaczy, żadne łuki nie powinny w ogóle wchodzić;
• jeśli zaczniesz poruszać się od rdzenia wzdłuż łuków, ten proces powinien pozwolić ci całkowicie wpaść do któregokolwiek z węzłów.

W kodach jest też coś takiegoHuffman jak liść drzewa. Jest to węzeł, z którego nie powinien się rozciągać żaden łuk. Jeśli dwa węzły są połączone łukiem, to jeden z nich jest rodzicielstwem, drugi jest dzieckiem, w zależności od tego, z którego węzła łuk wychodzi i wchodzi do niego. Jeśli dwa węzły mają ten sam węzeł nadrzędny, nazywa się je węzłami braterskimi. Jeśli oprócz liści, węzły wypadają w kilku łukach, to drzewo nazywa się binarne. Właśnie takie jest drzewo Huffman. Osobliwością węzłów tej konstrukcji jest to, że ciężar każdego z rodziców jest równy sumie ciężaru wszystkich kluczowych dzieci.

Algorytm konstrukcji drzewa Huffmana

Budowanie kodu Huffmana odbywa się z literalfabet wejściowy. Tworzona jest lista tych węzłów, które są wolne w przyszłym drzewie kodu. Waga każdego węzła na tej liście powinna być taka sama, jak prawdopodobieństwo wystąpienia litery wiadomości odpowiadającej temu węzłowi. W tym samym czasie, spośród kilku wolnych węzłów przyszłego drzewa, wybiera się ten, który waży najmniej. Co więcej, jeśli minimalne wskaźniki są obserwowane w kilku węzłach, możesz dowolnie wybrać dowolną z par.

Po tym, stworzenie rodzicawęzeł, który powinien ważyć tyle, ile suma tej pary węzłów. Następnie rodzic jest wysyłany na listę z wolnymi węzłami, a dzieci są usuwane. W takim przypadku łuki otrzymują odpowiednie wskaźniki, zer i jedynek. Proces ten powtarza się dokładnie tak długo, jak długo trwa opuszczenie tylko jednego węzła. Następnie cyfry binarne są zapisywane w kierunku od góry do dołu.

Poprawiona wydajność kompresji

Aby zwiększyć wydajność kompresji, musiszczas na zbudowanie drzewa kodu, aby wykorzystać wszystkie dane dotyczące prawdopodobieństwa liter w konkretnym pliku dołączonym do drzewa i zapobiec ich rozproszeniu w dużej liczbie dokumentów tekstowych. Jeśli najpierw przejdziesz przez ten plik, możesz natychmiast obliczyć statystyki określające, jak często znajdują się litery z obiektu, który ma być skompresowany.

Przyspieszenie procesu kompresji

Aby przyspieszyć algorytm, definicję literPowinien być przeprowadzany nie w zależności od prawdopodobieństwa wystąpienia litery, ale według częstotliwości jej występowania. Dzięki temu algorytm staje się łatwiejszy, a praca z nim jest znacznie przyspieszona. Pozwala to również uniknąć operacji związanych z zmiennymi przecinkami i podziałami.

Ponadto działa w tym trybie, dynamicznyKod Huffmana, a raczej sam algorytm, nie podlega żadnym zmianom. Wynika to głównie z faktu, że prawdopodobieństwa są wprost proporcjonalne do częstotliwości. Warto zwrócić szczególną uwagę na to, że końcowa waga pliku lub tak zwany węzeł główny będzie równa sumie liczby liter w obiekcie, który ma być przetwarzany.

Wniosek

Kody Huffmana - proste i ugruntowanealgorytm, który jest nadal używany przez wiele znanych programów i firm. Jego prostota i klarowność umożliwiają uzyskanie efektywnych wyników kompresji plików o dowolnej wielkości i znaczne zmniejszenie zajmowanej przestrzeni dyskowej. Innymi słowy, algorytm Huffmana jest długo studiowanym i dobrze opracowanym schematem, którego znaczenie nie zmniejsza się do dnia dzisiejszego.

A dzięki zdolności do zmniejszania rozmiaru plików,ich transmisja przez sieć lub w inny sposób staje się łatwiejsza, szybsza i wygodniejsza. Pracując z algorytmem, możliwe jest skompresowanie absolutnie dowolnej informacji bez szkody dla jej struktury i jakości, ale z maksymalnym efektem zmniejszania wagi pliku. Innymi słowy, kodowanie Huffmana było i pozostaje najbardziej popularną i aktualną metodą kompresowania rozmiaru pliku.