KiK-Modul-5.pdf

(190 KB) Pobierz
Kodowanie słownikowe.
Z
wykle ciągi generowane przez źródło danych zawierają często powtarzające się
sekwencje. Szczególnie jest to zauważalne w tekstach, gdzie poszczególne litery nie są
generowane w sposób niezależny a tworzą słowa, które powtarzają się w tekście z
różną częstotliwością. Słowa również nie są zbudowane losowo lecz na podstawie
reguł danego języka, które to reguły powodują, iż pewne sekwencje liter powtarzają się
bardzo często (np. ...wier...) a inne praktycznie nigdy (np. ...gkgd...).
N
aturalnym wydaje się więc stworzenie słownika często powtarzających się sekwencji
liter (wzorców). Zamiast kodować indywidualnie wszystkie symbole ciągu możemy
kodować całe wzorce za pomocą
odwołań do słownika
(indeksu) zawierającego te
wzorce.
O
czywiście nie miałoby sensu tworzenie słownika dla wszystkich możliwych
sekwencji liter, gdyż było by to znacznie mniej efektywne niż kodowanie każdej litery
z osobna. Kodujemy tylko
często powtarzające się sekwencje
- jeśli dana sekwencja
symboli występuje rzadko i nie ma jej w słowniku to możemy ją zakodować za pomocą
innej metody.
Przykład.
Mamy alfabet złożony z
32
liter. Załóżmy, że chcemy zakodować tekst składający się z
losowych czteroliterowych sekwencji liter (wzorców). Gdybyśmy chcieli przypisać każdej
literze z osobna słowo kodowe stałej długości to potrzebowalibyśmy
5
bitów na znak
( 2
5
= 32 ).
Dla zakodowania w ten sposób całej czteroliterowej sekwencji potrzebujemy
20 bitów.
Załóżmy teraz, że sekwencje nie są generowane z tym samym prawdopodobieństwem ale
pewna ich grupa - powiedzmy
256
sekwencji - jest generowana z prawdopodobieństwem
wyższym (powiedzmy
p).
Umieszczamy je w naszym słowniku. Słownik indeksujemy za
pomocą kodu
8
bitowego
( 2
8
= 256 ).
Jeśli jakaś sekwencja występuje w słowniku to generujemy
1
a za nią indeks wzorca
(8
bitów),
jeśli nie występuje to generujemy
0
a za nim 20-sto bitowy kod sekwencji. Wtedy
średnia liczba bitów na czteroliterową sekwencję będzie dana wzorem:
R = 9 p + 21(1- p) = 21 - 12p.
Sprawdzamy kiedy
R < 20
(inaczej zamiast kompresji otrzymamy plik dłuższy).
Będzie to
dla
p > 0.084
(zauważmy, że wartość ta jest stosunkowo duża, gdyż przy jednakowym
prawdopodobieństwie wszystkich sekwencji
p = 0.00025).
Kodowanie digramowe.
Jeśli posiadamy wcześniejszą wiedzę na temat rodzaju kodowanych danych to możemy
utworzyć tzw.
słownik statyczny,
który nie będzie się zmieniał podczas procesu
kodowania.
Jeśli na przykład kodujemy program napisany w języku Pascal to takie wzorce jak:
begin,
end, if, for, while, then, else
będą powtarzały się bardzo często i możemy je umieścić w
naszym słowniku.
Jak widać słownik statyczny będzie odpowiedni do kodowania tylko określonego rodzaju
tekstów - takich, dla których został zaprojektowany. Słownik zaprojektowany do
kodowania programów źródłowych w Pascalu nie będzie już efektywny przy kodowaniu
innych tekstów np. literackich (w tym przypadku zwykle zamiast kompresji
otrzymalibyśmy wzrost rozmiaru danych).
Jedną z najbardziej popularnych technik kodowania ze słownikiem statycznym jest
kodowanie digramowe. Słownik składa się tu ze wszystkich liter alfabetu źródła oraz tylu
par liter
(zwanych
digramami)
ile może się w nim zmieścić.
Jeśli na przykład stosujemy słownik statyczny o 256 elementach, a alfabet składa się z 56
liter to pozostałe 200 pozycji zostanie wypełnione najczęściej występującymi parami liter.
Koder digramowy odczytuje dwa znaki danych wejściowych i sprawdza czy para ta
znajduje się w słowniku:
- jeśli
tak
to generujemy jej indeks,
- jeśli
nie
to kodujemy pierwszy znak tej pary (jego indeksem), następny znak staje
się wtedy pierwszym znakiem kolejnego digramu - koder czyta wtedy następną literę
tekstu aby uzupełnić digram.
Procedurę tą powtarzamy aż do zakodowania całego tekstu.
Przykład.
Niech dane będzie źródło z alfabetem
{a, b, d, k, r}.
Na podstawie typowych tekstów
generowanych przez źródło tworzymy słownik. Załóżmy, że chcemy zakodować ciąg:
abrakadabra
101100110...
Koder czyta najpierw digram
ab
i sprawdza czy występuje on w słowniku.
Ponieważ
ab
jest w słowniku to zostaje zakodowane przez
101.
Teraz koder
czyta następną parę
ra,
digramu tego nie ma w słowniku więc dołaczamy kod
r
-
100
i czytamy następną literę
k.
Mamy teraz digram
ak,
który występuje
w słowniku i możemy go zakodować jego kodem
110.
Koder czyta następny
digram
ad
...
000 - a
001 - b
010 - k
011 - d
100 - r
101 - ab
110 - ak
111 - ar
Słownik dynamiczny.
Algorytm LZ77
W metodzie LZ77 (77 to rok publikacji a LZ to inicjały autorów) słownik jest tworzony
na podstawie poprzednio odczytanego i zakodowanego fragmentu tekstu. Ciąg
wejściowy jest przeglądany przez przesuwające się okno składające się z dwóch części:
-
bufora słownikowego
zawierającego ostatnio zakodowaną część ciągu,
-
bufora kodowania
zawierającego fragment ciągu, który ma być właśnie zakodowany.
cabra carab arakri rad
pozycja najdłuższego dopasowania (sekwencja
ara)
Koder szuka najdłuższego dopasowania w buforze słownikowym dla ciągu symboli w
buforze kodowania. Robi to znajdując kolejno symbole w buforze słownikowym równe
pierwszemu symbolowi w buforze kodowania - przesuwając wskaźnik od końca bufora
słownikowego w lewą stronę.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin