• 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ęć.

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

    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".Zero (zapisywane jako 0) – element neutralny dodawania; najmniejsza nieujemna liczba. To, czy zero jest uznawane za liczbę naturalną, jest kwestią umowy – czasem włącza się, a czasem wyklucza się je z tego zbioru. Zero nie jest ani liczbą pierwszą, ani liczbą złożoną.

    Spis treści

  • 1 Kodowanie Huffmana
  • 2 Algorytm statycznego kodowania Huffmana
  • 2.1 Przykład
  • 2.2 Praktyczne zastosowanie
  • 2.3 Przykład kodowania po 2 znaki naraz
  • 3 Kodowanie Huffmana z mniejszymi wymaganiami pamięciowymi
  • 4 Algorytm dynamicznego kodowania Huffmana
  • 5 Inne algorytmy kompresji bezstratnej
  • 6 Zobacz też
  • 7 Przypisy
  • 8 Bibliografia
  • 9 Linki zewnętrzne
  • 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.Program do kompresji plików – program do kodowania danych w taki sposób, aby zajmowały jak najmniej danych na dysku.

    Kodowanie Huffmana[]

    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.

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

    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.

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

    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]



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

    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

    Czas generowania strony: 0.035 sek.