• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Kodowanie Huffmana



    Podstrony: [1] 2 [3] [4] [5]
    Przeczytaj także...
    Patent – potocznie: dokument wydawany przez urzędy patentowe; właściwie: ograniczone w czasie prawa właściciela rozwiązania technicznego do wyłącznego korzystania z wynalazku bądź wynalazków będących przedmiotem patentu w celach zawodowych lub zarobkowych na terenie państwa, które decyzją administracyjną patentu udzieliło, pod warunkiem wniesienia opłat za co najmniej pierwszy okres ochrony od daty zgłoszenia.Pamięć – zdolność do rejestrowania i ponownego przywoływania wrażeń zmysłowych, skojarzeń, informacji, występująca u ludzi, niektórych zwierząt i w komputerach. W każdym z tych przypadków proces zapamiętywania ma całkowicie inne podłoże fizyczne oraz podlega badaniom naukowym w oparciu o różne zestawy pojęć.
    Algorytm statycznego kodowania Huffmana[ | edytuj kod]

    Algorytm Huffmana:

    1. Określ prawdopodobieństwo (lub częstość występowania) dla każdego symbolu ze zbioru S.
    2. Utwórz listę drzew binarnych, które w węzłach przechowują pary: symbol, prawdopodobieństwo. Na początku drzewa składają się wyłącznie z korzenia.
    3. Dopóki na liście jest więcej niż jedno drzewo, powtarzaj:
      1. Usuń z listy dwa drzewa o najmniejszym prawdopodobieństwie zapisanym w korzeniu.
      2. Wstaw nowe drzewo, w którego korzeniu jest suma prawdopodobieństw usuniętych drzew, natomiast one same stają się jego lewym i prawym poddrzewem. Korzeń drzewa nie przechowuje symbolu.

    Drzewo, które pozostanie na liście, jest nazywane drzewem Huffmana – prawdopodobieństwo zapisane w korzeniu jest równe 1, natomiast w liściach drzewa zapisane są symbole.

    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 jest algorytmem niedeterministycznym, ponieważ nie określa, w jakiej kolejności wybierać drzewa z listy, jeśli mają takie samo prawdopodobieństwo. Nie jest również określone, które z usuwanych drzew ma stać się lewym bądź prawym poddrzewem. Jednak bez względu na przyjęte rozwiązanie średnia długość kodu pozostaje taka sama.

    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.

    Na podstawie drzewa Huffmana tworzone są słowa kodowe; algorytm jest następujący:

    1. Każdej lewej krawędzi drzewa przypisz 0, prawej 1 (można oczywiście odwrotnie).
    2. Przechodź w głąb drzewa od korzenia do każdego liścia (symbolu):
      1. Jeśli skręcasz w prawo, dopisz do kodu bit o wartości 1.
      2. Jeśli skręcasz w lewo, dopisz do kodu bit o wartości 0.

    Długość słowa kodowego jest równa głębokości symbolu w drzewie, wartość binarna zależy od jego położenia w drzewie.

    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).
    Przykład

    Przykład[ | edytuj kod]

    Dany jest zbiór symboli o prawdopodobieństwach wystąpienia odpowiednio

    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.

    Kodowanie alfabetu źródłowego zgodnie z algorytmem (oznaczenia jak na rysunku obok):

    1. Łączenie symboli (A) i (B), co powoduje powstanie (A + B) = 0,3; (C) = 0,3; (D) = 0,4.
    2. Łączenie drzewa (A + B) z symbolem (C), uzyskując elementy ((A + B) + C) = 0,6 i (D) = 0,4.
    3. Łączenie drzewa ((A + B) + C) z symbolem (D). Teraz pozostaje tylko jeden wolny węzeł (korzeń) – otrzymujemy drzewo (((A + B) + C) + D) = 1,0.
    4. Pozostaje obliczenie kodów poszczególnych symboli:
    5. A = lewo, lewo, lewo = 000
    6. B = lewo, lewo, prawo = 001
    7. C = lewo, prawo = 01
    8. D = prawo = 1

    Jak łatwo sprawdzić, średnia długość kodu wyniesie:

    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).

    Jest to mniej niż 2 bity potrzebne w trywialnym kodowaniu o stałej długości znaku. Z kolei entropia źródła wynosi: – optymalne kodowanie powinno charakteryzować się taką właśnie średnią długością kodu. Jednak widać, że jest ona większa – efektywność wynosi w tym przypadku

    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).

    Dekodowanie jest procesem odwrotnym. Rozpatrywanym ciągiem będzie który zakodowany jest jako Przechodząc drzewo za każdym razem od korzenia do węzła terminalnego, według bitów w kodzie, otrzymuje się odpowiednie symbole:

    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.
  • 000 [lewy, lewy, lewy] następuje dotarcie do liścia A
  • 001 [lewy, lewy, prawy] następuje dotarcie do liścia B
  • 01 [lewy, prawy] następuje dotarcie do liścia C
  • 1 [prawy] następuje dotarcie do liścia D
  • Praktyczne zastosowanie[ | edytuj kod]

    Jednym z głównych problemów stosowania statycznego algorytmu Huffmana jest konieczność transmisji całego drzewa lub całej tablicy prawdopodobieństw. W przypadku transmisji drzewa węzły są odwiedzane w porządku preorder, węzeł wewnętrzny może zostać zapisany na jednym bicie (ma zawsze dwóch synów), liście natomiast wymagają jednego bitu plus takiej liczby bitów, jaka jest potrzebna do zapamiętania symbolu (np. 8 bitów). Np. drzewo z przykładu powyżej może zostać zapisane jako: (1, 0, ‘D’, 1, 0, ‘C’, 1, 0, ‘B’, 0, ‘A’), czyli 7 + 4 · 8 = 39 bitów.

    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.

    Lepszą kompresję, kosztem jednak bardzo szybkiego wzrostu wymagań pamięciowych, uzyskuje się, kodując kilka kolejnych znaków naraz, nawet jeżeli nie są one skorelowane.

    Przykład kodowania po 2 znaki naraz[ | edytuj kod]

    Zbiór symboli jak w poprzednim przykładzie o prawdopodobieństwach wystąpienia odpowiednio Jeśli liczba symboli jest nieparzysta, to należy przyjąć jakąś konwencję postępowania z pierwszym lub ostatnim symbolem. Nie jest to w praktyce duży problem. Następuje kodowanie:

    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.Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.
  • Łączenie symboli parami – AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD o prawdopodobieństwach odpowiednio – {0,01; 0,02; 0,03; 0,04; 0,02; 0,04; 0,06; 0,08; 0,03; 0,06; 0,09; 0,12; 0,04; 0,08; 0,12; 0,16}.
  • Drzewo rośnie zgodnie z poniższymi krokami:
    1. (AA + AB) = 0,03;
    2. (BA + AC) = 0,05;
    3. (CA + (AA + AB)) = 0,06;
    4. (BB + AD) = 0,08;
    5. (DA + (BA + AC)) = 0,09;
    6. (BC + CB) = 0,12;
    7. ((CA + (AA + AB)) + BD) = 0,14;
    8. (DB + (BB + AD)) = 0,16;
    9. ((DA + (BA + AC)) + CC) = 0,18;
    10. (CD + DC) = 0,24;
    11. ((BC + CB) + ((CA + (AA + AB)) + BD)) = 0,26;
    12. (DD + (DB + (BB + AD))) = 0,32;
    13. (((DA + (BA + AC)) + CC) + (CD + DC)) = 0,42;
    14. (((BC + CB) + ((CA + (AA + AB)) + BD)) + (DD + (DB + (BB + AD)))) = 0,58;
    15. ((((DA + (BA + AC)) + CC) + (CD + DC)) + (((BC + CB) + ((CA + (AA + AB)) + BD)) + (DD + (DB + (BB + AD))))) = 1,0.
  • Zatem odpowiednim parom znaków odpowiadają:

    Donald Ervin Knuth (ur. 10 stycznia 1938 r. w Milwaukee) – amerykański matematyk, informatyk, emerytowany profesor na katedrze informatyki Uniwersytetu Stanforda.Kodowanie Shannona-Fano – metoda kompresji bezstratnej autorstwa Roberta Fano. Kodowanie to dla dyskretnego źródła danych znajduje kod prefiksowy, który charakteryzuje się dość dobrą efektywnością – lepszą od kodowania Shannona (słowa kodowe krótsze o 1 bit), nie tworzy jednak optymalnych kodów. Kodowanie Shannona-Fano jest używane w kompresorze ZIP, przy wybranej metodzie kompresji implode.
  • AA – 101010
  • AB – 101011
  • AC – 00011
  • AD – 11111
  • BA – 00010
  • BB – 11110
  • BC – 1000
  • BD – 1011
  • CA – 10100
  • CB – 1001
  • CC – 001
  • CD – 010
  • DA – 0000
  • DB – 1110
  • DC – 011
  • DD – 110
  • Średnia liczba bitów przypadająca na parę symboli to 3,73, a więc średnia liczba bitów na symbol to 1,865. Jest to znacznie lepsza kompresja (6,75% zamiast 5% przy maksymalnej możliwej 7,68%) niż w poprzednim przykładzie. Używając większej liczby znaków, można dowolnie przybliżyć się do kompresji maksymalnej, jednak znacznie wcześniej wyczerpie się pamięć, ponieważ wymagania pamięciowe rosną wykładniczo do liczby kompresowanych jednocześnie symboli.

    Kod (łac. codex – spis) – ciąg składników sygnału (kombinacji sygnałów elementarnych, np. kropek i kresek, impulsów prądu, symboli) oraz reguła ich przyporządkowania składnikom wiadomości (np. znakom pisma). W niektórych zastosowaniach, głównie przy przesyłaniu informacji podlegających utajnieniu, zwany jest szyfrem. Kody są stosowane m.in. w telegrafii, w technice cyfrowej.ASCII [aski] (ang. American Standard Code for Information Interchange) – 7-bitowy kod przyporządkowujący liczby z zakresu 0-127: literom (alfabetu angielskiego), cyfrom, znakom przestankowym i innym symbolom oraz poleceniom sterującym. Na przykład litera "a" jest kodowana liczbą 97, a znak spacji jest kodowany liczbą 32.

    Kodowanie Huffmana z mniejszymi wymaganiami pamięciowymi[ | edytuj kod]

    Jeśli kodowane są pary symboli (tak jak w przykładzie powyżej) albo trójki symboli, czy ogólnie n-tki symboli, to rozmiar drzewa Huffmana rośnie znacząco – drzewo Huffmana należy zapisać razem z zakodowanym komunikatem, aby można go było zdekodować; zatem im większe drzewo, tym dłuższe stają się kody rzadziej występujących symboli. C. Weaver zaproponował modyfikację algorytmu Huffmana, która redukuje pamięć potrzebną do zapamiętania drzewa. Pomysł został opracowany przez Michaela Hankamera, który opublikował wyniki w artykule „A modified Huffman procedure with reduced memory requirement” (IEEE Transactions on Communication COM-27, 1979, s. 930–932).

    Krawędź grafu jest to para (zbiór dwuelementowy) wyróżnionych wierzchołków grafu, czyli takich, które są ze sobą połączone (sąsiednie). W reprezentacji graficznej jest to linia łącząca te wierzchołki. W szczególności krawędź może łączyć dwa te same wierzchołki i jest wówczas nazywana pętlą. Krawędź skierowaną, czyli będącą parą uporządkowanych wierzchołków, nazywamy łukiem.Średnia - w najogólniejszej wersji dowolna funkcja Parser nie mógł rozpoznać(nieznany błąd): mu (a_{{1}},ldots ,a_{{n}})

    Modyfikacja polega na wprowadzeniu dodatkowego symbolu nazywanego ELSE, który zastępuje wszystkie rzadko występujące symbole – jeśli pojedynczy symbol opisuje N bitów, to symbol trafi do zbioru ELSE, gdy jego prawdopodobieństwo Prawdopodobieństwo przypisane do ELSE jest równe sumie zastępowanych przez niego symboli. Przy kodowaniu symbolu należącego do klasy ELSE zapisywany jest kod dla ELSE oraz nieskompresowany symbol; np. gdy kod ELSE to to przy kodowaniu symbolu ‘H’ (kod ASCII ) zapisane zostanie

    Bit (w ang. kawałek, skrót od binary digit, czyli cyfra dwójkowa) – najmniejsza ilość informacji potrzebna do określenia, który z dwóch równie prawdopodobnych stanów przyjął układ. Jednostka logiczna.Kod Golomba - kod binarny zmiennej długości, służący kodowaniu liczb całkowitych nieujemnych, o potencjalnie nieograniczonej wartości. Został opracowany w 1960 roku przez Solomona W. Golomba.

    Dzięki temu drzewo staje się mniejsze, ponieważ zachowuje tylko symbole nienależące do ELSE – co w zupełności wystarczy, ponieważ symbole ze zbioru ELSE są bezpośrednio zapisane w komunikacie. Zastosowanie tej modyfikacji może nawet nieco polepszyć stopień kompresji w stosunku do niezmodyfikowanej wersji algorytmu.

    Implementacja (wdrożenie, przystosowanie, realizacja, łac.ang. implementation) – w informatyce – proces przekształcania abstrakcyjnego opisu systemu lub programu na obiekt fizyczny: komputer lub działający program zapisany w konkretnym języku programowania; także obiekt fizyczny będący efektem takiego przekształcenia, np. implementacja systemu operacyjnego (wdrożenie systemu) lub kompilatora dla konkretnego typu komputera.Bajt (dop. bajtu lub bajta) – najmniejsza adresowalna jednostka informacji pamięci komputerowej, składająca się z bitów.


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



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.878 sek.