• 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 dynamicznego kodowania Huffmana[ | edytuj kod]

    Dynamiczne kodowanie Huffmana to kodowanie danych o nieznanej statystyce. Statystykę buduje się w miarę napływania danych i co znak lub co daną liczbę znaków poprawia drzewo Huffmana.

    Zaletą kodowania dynamicznego jest to, że nie ma potrzeby przesyłania drzewa kodów. Zamiast tego identyczną procedurę poprawiania drzewa muszą przeprowadzać zarówno koder, jak i dekoder.

    Istnieją dwa algorytmy pozwalające poprawić drzewo 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.
    1. algorytm Fallera-Gallagera-Knutha (pomysłodawcami byli Newton Faller i Robert Gallager, metodę ulepszył Donald Knuth),
    2. algorytm Vittera (dalsze ulepszenia metody FGK opracowane przez Jeffreya Vittera).

    U podstaw algorytmu FGK leżą następujące założenia co do formy drzewa:

  • każdy węzeł drzewa oprócz liści ma zawsze dwóch potomków;
  • z każdym węzłem związany jest licznik: w liściach przechowuje liczbę wystąpień danego symbolu (lub wartość proporcjonalną), w pozostałych węzłach sumę liczników dzieci;
  • przy przejściu drzewa wszerz od prawej do lewej i odczycie liczników powiązanych z każdym węzłem uzyskuje się ciąg liczb nierosnących.
  • W algorytmie Vittera zaostrzone zostało ostatnie założenie:

    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.
  • również otrzymuje się ciąg liczb nierosnących, lecz w obrębie podciągów o tych samych wartościach na początku znajdują się te pochodzące z węzłów wewnętrznych, a na końcu z liści.
  • Gdy licznik w jakimś liściu zwiększy się, algorytmy modyfikują (przemieszczając niektóre węzły) jedynie niewielki fragment drzewa, zachowując wyżej wymienione własności. Algorytm Vittera jest nieco bardziej złożony, jednak daje lepsze wyniki, tj. krótsze kody niż algorytm FKG.

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

    Inne algorytmy kompresji bezstratnej[ | edytuj kod]

  • transformata Burrowsa-Wheelera
  • PPM


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



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

    Warto wiedzieć że... beta

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

    Reklama

    Czas generowania strony: 0.827 sek.