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



    Podstrony: 1 [2] [3]
    Przeczytaj także...
    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.Sygnał to abstrakcyjny model dowolnej mierzalnej wielkości zmieniającej się w czasie, generowanej przez zjawiska fizyczne lub systemy. Tak jak wszystkie zjawiska może być opisany za pomocą aparatu matematycznego, np. poprzez podanie pewnej funkcji zależnej od czasu. Mówimy, że sygnał niesie informację lub też umożliwia przepływ strumienia informacji.

    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. Od roku 2014 zostaje zastępowane kodowaniem Asymmetric Numeral Systems, które pozwala na szybsze implementacje przy podobnym stopniu kompresji.

    Program do kompresji plików – program do kodowania danych w taki sposób, aby zajmowały jak najmniej danych na dysku.Rekurencja, zwana także rekursją (ang. recursion, z łac. recurrere, przybiec z powrotem) to w logice, programowaniu i w matematyce odwoływanie się np. funkcji lub definicji do samej siebie.

    Ideą tego kodu jest przedstawienie ciągu wiadomości jako podprzedziału przedziału jednostkowego wyznaczonego rekursywnie na podstawie prawdopodobieństw wystąpienia tychże wiadomości generowanych przez źródło. Ciąg kodowy reprezentujący kodowane wiadomości jest binarnym zapisem wartości z wyznaczonego w ten sposób przedziału.

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

    Można udowodnić, że przy wyborze odpowiednio długiego ciągu wiadomości do zakodowania, średnia liczba symboli na wiadomość jest mniejsza od gdzie jest entropią źródła, lecz co najmniej równa samej entropii.

    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.

    Algorytm kodowania[ | edytuj kod]

    Dany jest zbiór symboli oraz stowarzyszony z nim zbiór prawdopodobieństw Jeden z symboli jest wyróżniony – jego wystąpienie oznacza koniec komunikatu, co zapobiega wystąpieniu niejednoznaczności; ewentualnie zamiast wprowadzenia dodatkowego symbolu można przesyłać długość kodowanego ciągu.

    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.Kodowanie Shannona – metoda kodowania, którą Claude E. Shannon przedstawił jako jeden z dowodów swojego podstawowego twierdzenia o kodowaniu.

    Na początku dany jest przedział który dzielony jest na podprzedziały o szerokościach równych kolejnym prawdopodobieństwom czyli otrzymywany jest ciąg podprzedziałów Kolejnym podprzedziałom (ozn. ) odpowiadają symbole ze zbioru

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

    Algorytm kodowania:

  • Dla kolejnych symboli c:
  • Określ, który podprzedział bieżącego przedziału odpowiada literze c – wynikiem jest
  • Weź nowy przedział – następuje zawężenie przedziału
  • Podziel ten przedział na podprzedziały w sposób analogiczny do tego, jak to miało miejsce na samym początku (chodzi o zachowanie proporcji szerokości podprzedziałów).
  • Zwróć liczbę jednoznacznie wskazującą przedział (najczęściej dolne ograniczenie, albo średnia dolnego i górnego ograniczenia).
  • Przykład 1.[ | edytuj kod]

    Na rysunku pokazano, jak zmienia się aktualny przedział w trzech pierwszych krokach kodowania. Kodowane są trzy symbole z czteroelementowego zbioru o prawdopodobieństwach w kolejności: pierwszy, trzeci, czwarty.

    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.

    Arithmetic encoding.svg

    Przykład 2.[ | edytuj kod]

    Niech ( – koniec komunikatu), prawdopodobieństwa

    Zakodowany zostanie ciąg

  • Początkowo przedział jest on dzielony na podprzedziały
  • Pierwszym kodowanym symbolem jest któremu odpowiada 3. podprzedział, zatem Nowy przedział znów jest dzielony:
  • Kolejnym kodowanym symbolem jest któremu odpowiada 1. podprzedział, zatem Nowy przedział znów jest dzielony:
  • Kolejnym kodowanym symbolem jest któremu odpowiada 2. podprzedział, zatem Nowy przedział znów jest dzielony:
  • Kolejnym kodowanym symbolem jest (ponownie) któremu odpowiada 1. podprzedział, zatem Nowy przedział znów jest dzielony:
  • Kolejnym kodowanym symbolem jest kończący kodowanie, któremu odpowiada 4. podprzedział, zatem
  • Na wyjście zostaje zapisana liczba identyfikująca ten przedział – może to być, jak wspomniano, jego dolne ograniczenie, czyli 0,802042.


  • Podstrony: 1 [2] [3]




    Reklama

    Czas generowania strony: 0.042 sek.