Kodowanie Huffmana

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Kodowanie Huffmana (ang. Huffman coding) – jedna z najprostszych i łatwych w implementacji metod kompresji bezstratnej. Została opracowana w 1952 roku przez Amerykanina Davida Huffmana.

Algorytm zachłanny (ang. greedy algorithm) – algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego. Innymi słowy algorytm zachłanny nie dokonuje oceny czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje decyzji lokalnie optymalnej, dokonuje on wyboru wydającego się w danej chwili najlepszym, kontynuując rozwiązanie podproblemu wynikającego z podjętej decyzji. Typowe zadanie rozwiązywane metodą zachłanną ma charakter optymalizacyjny. W dziedzinie sztucznej inteligencji zachłanna odmiana przeszukiwania lokalnego jest nazywana "podchodzeniem pod wzgórze".Kodowanie arytmetyczne – metoda kodowania źródłowego dyskretnych źródeł sygnałów, stosowana jako jeden z systemów w bezstratnej kompresji danych. Została wynaleziona przez Petera Eliasa około 1960 roku.

Algorytm Huffmana nie należy do najefektywniejszych obliczeniowo systemów bezstratnej kompresji danych, dlatego też praktycznie nie używa się go samodzielnie. Często wykorzystuje się go jako ostatni etap w różnych systemach kompresji, zarówno bezstratnej, jak i stratnej, np. MP3 lub JPEG. Pomimo że nie jest doskonały, stosuje się go ze względu na prostotę oraz brak ograniczeń patentowych. Jest to przykład wykorzystania algorytmu zachłannego.

Program do kompresji plików – program do kodowania danych w taki sposób, aby zajmowały jak najmniej danych na dysku.Kompresja danych (ang. data compression) – polega na zmianie sposobu zapisu informacji tak, aby zmniejszyć redundancję i tym samym objętość zbioru. Innymi słowy chodzi o wyrażenie tego samego zestawu informacji, lecz za pomocą mniejszej liczby bitów.

Kodowanie Huffmana[ | edytuj kod]

Drzewo Huffmana wygenerowane z frazy „TO BE OR NOT TO BE”

Dany jest alfabet źródłowy (zbiór symboli) oraz zbiór stowarzyszonych z nim prawdopodobieństw Symbolami są najczęściej bajty, choć nie ma żadnych przeszkód żeby było nimi coś innego (np. pary znaków). Prawdopodobieństwa mogą zostać z góry określone dla danego zestawu danych, np. poprzez wyznaczenie częstotliwości występowania znaków w tekstach danego języka. Częściej jednak wyznacza się je indywidualnie dla każdego zestawu danych.

MP3 ((ang.) MPEG-1/MPEG-2 Audio Layer 3) – algorytm kompresji stratnej dźwięku, przetworzonego uprzednio na sygnał cyfrowy. Popularnie zwany formatem MP3 lub standardem MP3. Jest zdefiniowany przez IETF w dokumencie RFC 5219.Kod Tunstalla - kod przyporządkowujący ciągom symboli kody o jednakowej długości; metoda została opracowana niezależnie przez B. P. Tunstalla (1967), G. L. Khodak (1969), J. Verhoffa (1977).

Kodowanie Huffmana polega na utworzeniu słów kodowych (ciągów bitowych), których długość jest odwrotnie proporcjonalna do prawdopodobieństwa Tzn. im częściej dany symbol występuje (może wystąpić) w ciągu danych, tym mniej zajmie bitów.

Entropia – w ramach teorii informacji jest definiowana jako średnia ilość informacji, przypadająca na pojedynczą wiadomość ze źródła informacji. Innymi słowy jest to średnia ważona ilości informacji niesionej przez pojedynczą wiadomość, gdzie wagami są prawdopodobieństwa nadania poszczególnych wiadomości.Asymmetric Numeral Systems (ANS, pol: asymetryczne systemy liczbowe) to rodzina kodowań entropijnych wprowadzonych przez dr Jarosława Dudę na przestrzeni lat 2006-2014, używanych w kompresji danych od 2014 roku z powodu poprawionej wydajności w porównaniu z używanymi dotychczas metodami: ANS pozwala połączyć stopień kompresji kodowania arytmetycznego (używa praktycznie dokładnych prawdopodobieństw), z kosztem przetwarzania podobnym jak w kodowaniu Huffmana (przybliżającym prawdopodobieństwa potęgami 1/2). W wariancie tANS jest to osiągnięte przez skonstruowanie automatu skończonego w celu przetwarzania dużego alfabetu bez użycia mnożenia. ANS jest użyte m.in. w kompresorze Facebook Zstandard i kompresorze Apple LZFSE.

Własności kodu Huffmana są następujące:

  • jest kodem prefiksowym; oznacza to, że żadne słowo kodowe nie jest początkiem innego słowa;
  • średnia długość słowa kodowego jest najmniejsza spośród kodów prefiksowych;
  • jeśli prawdopodobieństwa są różne, tzn. to długość kodu dla symbolu jest nie większa od kodu dla symbolu
  • słowa kodu dwóch najmniej prawdopodobnych symboli mają równą długość.
  • Kompresja polega na zastąpieniu symboli otrzymanymi kodami.

    Kompresja bezstratna (ang. lossless compression) – ogólna nazwa metod kompresji informacji do postaci zawierającej zmniejszoną liczbę bitów, pod warunkiem, że metoda ta gwarantuje możliwość odtworzenia informacji z postaci skompresowanej do identycznej postaci pierwotnej.Węzeł – sposób łączenia, mocowania oraz skracania lin, sznurków czy innych podobnych materiałów poprzez odpowiednie wiązanie lub przeplatanie. Węzły mogą służyć do łączenia ze sobą dwóch lub więcej lin, mocowania lin do innych przedmiotów czy do formowania pętli. Są stosowane w wielu dziedzinach na przykład: żeglarstwie, wspinaczce, makramie, turystyce i sztuce przetrwania (surwiwal, survival).


    Podstrony: 1 [2] [3] [4] [5]




    Warto wiedzieć że... beta

    1 (jeden, jedność) – liczba naturalna następująca po 0 i poprzedzająca 2. 1 jest też cyfrą wykorzystywaną do zapisu liczb w różnych systemach, np. w dwójkowym (binarnym), ósemkowym, dziesiętnym i szesnastkowym systemie liczbowym. Każda liczba całkowita jest podzielna przez 1.
    Kod prefiksowy lub przedrostkowy, także bezprefiksowy (ang. prefix code) – kod, w którym żadne ze słów kodowych nie jest przedrostkiem innego słowa; taki kod jest jednoznacznie dekodowalny. Dodatkowo każdy kod prefiksowy można reprezentować w formie drzew (dla kodów dwójkowych drzewo binarne).
    Dwójkowy system liczbowy, system binarny, bin – pozycyjny system liczbowy, w którym podstawą jest liczba 2. Do zapisu liczb potrzebne są tylko dwie cyfry: 0 i 1.
    PPM (ang. Prediction by partial matching – przewidywanie przez częściowe dopasowanie) to adaptacyjny algorytm kompresji danych oparty na kontekstowym modelowaniu statystycznym oraz predykcji. Algorytm PPM wykorzystuje układ symboli w strumieniu danych do przewidywania kolejnego symbolu. Zwykle predykcja opiera się na tworzeniu statystycznego rankingu występowania symboli. Pewna liczba poprzednich symboli wykorzystywanych w danym kroku do predykcji (n) jest określana jako rząd modelu PPM, który oznacza się jako PPM(n). Istnieją warianty algorytmu, w których rząd modelu nie jest z góry narzucany oznaczane jako PPM*. Jeżeli przewidywanie nie może zostać dokonane w oparciu o model o rzędzie n-tym to jego rząd jest zmniejszany o jeden. Proces jest powtarzany aż do uzyskania poprawnej predykcji lub, gdy strumień danych został wyczerpany. W tym momencie wykonywana jest ustalona predykcja.
    Prawdopodobieństwo – ogólne określenie jednego z wielu pojęć służących modelowaniu doświadczenia losowego poprzez przypisanie poszczególnym zdarzeniom losowym liczb, zwykle z przedziału jednostkowego (w zastosowaniach często wyrażanych procentowo), wskazujących szanse ich zajścia. W rozumieniu potocznym wyraz „prawdopodobieństwo” odnosi się do oczekiwania względem rezultatu zdarzenia, którego wynik nie jest znany (niezależnie od tego, czy jest ono w jakimś sensie zdeterminowane, miało miejsce w przeszłości, czy dopiero się wydarzy); w ogólności należy je rozumieć jako pewną miarę nieprzewidywalności.
    Transformata Burrowsa-Wheelera to algorytm użyteczny przy bezstratnej kompresji danych. Dane po przetworzeniu tą transformacją dają się znacznie lepiej skompresować za pomocą klasycznych algorytmów kompresji. Operuje ona na blokach, przy czym jest tym efektywniejsza im bloki te są większe. Zazwyczaj używa się bloków o rozmiarach kilkuset kilobajtów.
    JPEG (wym. dżej-peg lub jot-peg) – metoda kompresji statycznych obrazów rastrowych, przeznaczony głównie do stratnego zapisu obrazów naturalnych (pejzaży, portretów itp.), charakteryzujących się płynnymi przejściami barw oraz brakiem lub małą ilością ostrych krawędzi i drobnych detali.

    Reklama