W tej chwili niewiele osób myśliJak działa kompresja plików? W porównaniu z przeszłością korzystanie z komputera osobistego stało się znacznie łatwiejsze. A prawie każda osoba pracująca z systemem plików korzysta z archiwów. Ale niewiele osób myśli o tym, jak działają i na jakiej podstawie kompresowane są pliki. Pierwszą wersją tego procesu były kody Huffmana i są one używane do dziś w różnych popularnych archiwach. Wielu użytkowników nawet nie myśli o tym, jak łatwo jest skompresować plik i jak to działa. W tym artykule przyjrzymy się, jak zachodzi kompresja, jakie niuanse pomagają przyspieszyć i uprościć proces kodowania, a także zrozumieć, jaka jest zasada budowania drzewa kodowania.
Historia algorytmu
Pierwszy algorytm skutecznego prowadzeniakodowanie informacji elektronicznych to kod zaproponowany przez Huffmana w połowie XX wieku, a konkretnie w 1952 roku. To on jest obecnie głównym podstawowym elementem większości programów przeznaczonych do kompresji informacji. Obecnie jednymi z najpopularniejszych źródeł korzystających z tego kodu są archiwa ZIP, ARJ, RAR i wiele innych.
Zasada wydajnego kodowania
Algorytm Huffmana oparty jest na schemaciepozwalające na zastąpienie najbardziej prawdopodobnych, najczęściej występujących znaków 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 wartości minimalnych. Ta technika pozwala zminimalizować długość kodu dla każdego symbolu oryginalnej wiadomości jako całości.
Przykład kodu Huffmana
Aby zilustrować algorytm, weźgraficzna wersja budowania drzewa kodu. Aby skutecznie wykorzystać tę metodę, warto doprecyzować definicję niektórych wartości niezbędnych do pojęcia tej metody. Zbiór wielu łuków i węzłów, które są skierowane od węzła do węzła, nazywa się grafem. Samo drzewo jest grafem 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 nie może w ogóle zawierać łuków;
- jeśli zaczniesz poruszać się po łukach od korzenia, proces ten powinien pozwolić ci całkowicie dostać się do dowolnego węzła.
Algorytm budowy drzewa Huffmana
Konstrukcja kodu Huffmana odbywa się z literalfabet wejściowy. Zostanie utworzona lista tych węzłów, które są wolne w przyszłym drzewie kodu. Waga każdego węzła na tej liście musi być taka sama jak prawdopodobieństwo wystąpienia litery komunikatu odpowiadającej temu węzłowi. Jednocześnie spośród kilku wolnych węzłów przyszłego drzewa wybierany jest 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.
Poprawa wydajności kompresji
W celu zwiększenia wydajności kompresji konieczne jest:konstruując drzewo kodu wykorzystuj wszystkie dane dotyczące prawdopodobieństwa wystąpienia liter w konkretnym pliku dołączonym do drzewa i nie dopuszczaj do ich rozrzucenia na dużą liczbę dokumentów tekstowych. Jeśli po raz pierwszy przejdziesz przez ten plik, możesz natychmiast obliczyć statystyki dotyczące tego, jak często znajdują się litery z obiektu, który ma być skompresowany.
Przyspiesz proces kompresji
Aby przyspieszyć algorytm, definicja literpowinna być przeprowadzona nie według prawdopodobieństwa pojawienia się danej litery, ale według częstotliwości jej występowania. Dzięki temu algorytm staje się prostszy, a praca z nim znacznie przyspieszona. Unika również operacji zmiennoprzecinkowych i dzielenia.
Wniosek
Kody Huffmana - proste i ugruntowanealgorytm, który jest nadal używany przez wiele znanych programów i firm. Jego prostota i zrozumiałość pozwalają na osiągnięcie efektywnych efektów kompresji plików o dowolnej wielkości oraz znaczne ograniczenie ich przestrzeni dyskowej. Innymi słowy, algorytm Huffmana jest od dawna badanym i rozwijanym schematem, którego znaczenie nie zmniejszyło się do dziś.
