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ę uzyskuje 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 Awraham Lempel oraz Ja’akow Ziw dlatego nazwy tego typu algorytmów często rozpoczynają się od pierwszych liter ich nazwisk (LZ*).

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.

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.

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ż

• kodowanie gramatykowe
• kompresja bezstratna
• kompresja stratna