Kodowanie entropijne - Entropy coding

W teorii informacji o kodowanie entropii (lub kodowania entropii ), to kompresji bezstratnej system, który działa niezależnie od charakterystyk poszczególnych medium.

Jeden z głównych typów kodowania entropijnego tworzy i przypisuje unikalny kod bez prefiksu do każdego unikalnego symbolu, który występuje na wejściu. Te kodery entropijne następnie kompresują dane przez zastąpienie każdego symbolu wejściowego o stałej długości odpowiednim słowem kodowym wyjściowym bez prefiksów o zmiennej długości. Długość każdego słowa kodowego jest w przybliżeniu proporcjonalna do ujemnego logarytmu z prawdopodobieństwem wystąpienia tego słowa kodowego. Dlatego najczęściej używane symbole używają najkrótszych kodów.

Zgodnie z twierdzeniem Shannona o kodowaniu źródłowym , optymalna długość kodu dla symbolu to , gdzie jest liczbą symboli używanych do tworzenia kodów wyjściowych i jest prawdopodobieństwem symbolu wejściowego.

Dwie z najpopularniejszych technik kodowania entropijnego to kodowanie Huffmana i kodowanie arytmetyczne . Jeśli przybliżone charakterystyki entropii strumienia danych są znane z góry (zwłaszcza w przypadku kompresji sygnału ), przydatny może być prostszy kod statyczny. Te kody statyczne obejmują kody uniwersalne (takie jak kodowanie gamma Eliasa lub kodowanie Fibonacciego ) i kody Golomba (takie jak kodowanie jednoargumentowe lub kodowanie ryżu ).

Od 2014 roku kompresory danych zaczęły wykorzystywać rodzinę technik kodowania entropijnego Asymmetric Numeral Systems , która pozwala na połączenie współczynnika kompresji kodowania arytmetycznego z kosztem przetwarzania podobnym do kodowania Huffmana .

Entropia jako miara podobieństwa

Oprócz wykorzystania kodowania entropijnego jako sposobu kompresji danych cyfrowych, koder entropijny może być również używany do pomiaru stopnia podobieństwa między strumieniami danych a już istniejącymi klasami danych. Odbywa się to poprzez generowanie kodera/kompresora entropii dla każdej klasy danych; nieznane dane są następnie klasyfikowane przez podanie nieskompresowanych danych do każdego kompresora i sprawdzenie, który kompresor zapewnia najwyższą kompresję. Koder z najlepszą kompresją to prawdopodobnie koder wyszkolony na danych, które były najbardziej podobne do danych nieznanych.

Zobacz też

Bibliografia

Zewnętrzne linki