Kodowanie słownikowe

Kodowanie słownikowe – kodowanie danych za pomocą zastępowania kolejnych grup znaków, słów lub całych fraz symbolami opisującymi ich pozycję w słowniku. Kompresję uzyskuję się poprzez zastępowanie długich sekwencji krótkimi kodami adresu. Takie metody dobrze sprawdzają się np. w przypadku tekstów naturalnych (książki, czasopisma itp.) gdzie wiele słów a nawet całych fraz występuje wielokrotnie.

Słowniki

Algorytmy kompresji słownikowej różnią się strukturą słownika, jego inicjalizacją i aktualizacją oraz techniką adresowania dla sekwencji. Taką koncepcję zapoczątkowali w latach siedemdziesiątych Abraham Lempel oraz Jacob Ziv dlatego nazwy tego typu algorytmów często rozpoczynają się od pierwszych liter ich nazwisk (LZ*).[1]

Słownik statyczny

Słownik statyczny zawiera stałą liczbę słów. Może zawierać np. najczęściej występujące słowa, akronimy, skróty i frazy z danego języka lub wyrażenia specyficzne używane w publikacjach o określonym profilu. Elementy których brak jest w słowniku nie będą skompresowane.[2]

Słownik dynamiczny

Słownik dynamiczny składa się z elementów napotkanych na wejściu i modyfikowany jest w trakcie procesu kodowania i dekodowania. Może mieć różną liczbę słów jednak ma zwykle ograniczony rozmiar.[2]

Algorytmy

Algorytmy oparte na kodowaniu słownikowym to m.in.:

  • ze słownikiem dynamicznym: LZ77, LZ78, LZSS, LZW i pochodne.
  • ze słownikiem statycznym: ASCII

Zobacz też

Przypisy

  1. ↑ Władysław Skarbek: MULTIMEDIA Algorytmy i standardy kompresji. Warszawa: Akademicka Oficyna Wydawnicza PLJ, 1998, s. 80-81. ISBN 83-7101-385-X.
  2. ↑ a b Adam Drozdek: Wprowadzenie do kompresji danych. Wyd. II. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 76. ISBN 978-83-204-3309-8.