Kod Tunstalla

Kod Tunstalla – kod przyporządkowujący ciągom symboli kody o jednakowej długości; metoda została opracowana niezależnie przez B. P. Tunstalla (1967)^[1], G. L. Khodak (1969), J. Verhoffa (1977).

Dzięki operowaniu na ciągach symboli można uzyskać kompresję danych. W kodowaniu brane jest pod uwagę prawdopodobieństwo bezwarunkowe symboli – słowa kodowe są przypisywane najbardziej prawdopodobnym ciągom.

Ponadto stosowanie słów kodowych jednakowej długości uodparnia komunikat na pewne błędy transmisji – nawet jeśli wartość jakiegoś bitu zostanie zmienione, to błąd ten wpłynie wyłącznie na jedno słowo kodowe (i powiązany z nim podciąg); przy kodowaniu za pomocą słów o zmiennej długości (np. Huffmana, Golomba) przekłamanie bitu wpływa także na pewną ilość kolejnych słów kodowych.

Tworzenie słów kodowych

Dany jest alfabet $\{x_{1},x_{2},\dots ,x_{n}\},$ oraz prawdopodobieństwa wystąpienia każdego z elementów $\{p_{1},p_{2},\dots ,p_{n}\}.$ Liczba słów kodowych o długości $k$ bitów wynosi $2^{k}$ i musi być większa od $n;$ jedno słowo kodowe musi zostać zarezerwowane, do wykorzystania pozostaje więc $2^{k}-1$ słów.

Algorytm przyporządkowywania ciągom symboli słów kodowych wykorzystuje drzewa stopnia $n.$ Z każdym liściem związany jest kodowany ciąg oraz jego prawdopodobieństwo (iloczyn prawdopodobieństw $p_{i}$ wszystkich symboli wchodzących w skład ciągu).

Początkowo drzewo składa się z korzenia mającego $n$ dzieci, zawierających wszystkie symbole z alfabetu.
Dopóki liczba liści nie przekroczyła $2^{k}-1$ $2^{k}-1$ powtarzaj:
- Znajdź liść o największym prawdopodobieństwie $P,$ w którym zapisany jest ciąg $X$
- Jeśli jest jeszcze miejsce na $n-1$ liści, ten węzeł staje się rodzicem dla $n$ dzieci, zawierających ciąg $X$ przedłużony o symbole z alfabetu $(Xx_{1},Xx_{2},\dots ,Xx_{n}),$ o prawdopodobieństwach $(P\cdot p_{1},P\cdot p_{2},\dots ,P\cdot p_{n}).$ W przeciwnym razie drzewo nie jest modyfikowane i następuje skok do kroku 3.
Przypisz ciągom zapisanym w liściach słowa kodowe.

Ze względu na sposób tworzenia kodów, ciągi zapisane w liściach spełniają własność przedrostkową, żaden ciąg nie jest prefiksem innego.

Za pomocą kodu Tunstalla nie można w całości zakodować wszystkich komunikatów składających się z liter alfabetu źródłowego. Słowo kodowe z całą pewnością nie zostanie nigdy przypisane symbolowi o największym prawdopodobieństwie, a także wielu innym ciągom (co już zależy od danych i rozkładu prawdopodobieństwa). Ciągi których nie da się przedstawić kodem Tunstalla mogą wystąpić na końcu komunikatu, nie są jednak dłuższe niż najdłuższy ciąg z przypisanym kodem. Z tego powodu potrzebny jest dodatkowe, rezerwowane na początku słowo kodowe, sygnalizujące wystąpienie takiej sytuacji i końcówka jest wówczas kodowana w jakiś inny sposób.

Przykład kodowania

Dany jest alfabet zawierający trzy symbole $\{a,b,c\}$ o prawdopodobieństwach $\{0.75,0.20,0.05\}.$ Zostanie użyty kod trzybitowy, tj. $k=3,$ czyli dostępne maksymalnie 7 słów kodowych.

Konstruowanie kodu

Najpierw zostaną utworzone kody. Zostanie użyty praktyczny algorytm iteracyjny, nie wymagający konstruowania drzewa bezpośrednio, lecz operujący jedynie na zbiorze liści. Dodanie potomków do liścia o największym prawdopodobieństwie jest równoważne usunięciu tego liścia ze zbioru i wstawieniu nowych elementów.

Kolejne kroki algorytmu (na czerwono zaznaczony usuwany liść, nowe liście z poprzedniej iteracji pogrubiono):

a (0.750000), b (0.200000), c (0.050000)
aa (0.562500), ab (0.150000), ac (0.037500), b (0.200000), c (0.050000)
aaa (0.421875), aab (0.112500), aac (0.028125), ab (0.150000), ac (0.037500), b (0.200000), c (0.050000)

Utworzono 7 słów kodowych, jedno zostało zarezerwowane (oznaczone znakiem zapytania).

ciąg	kod (dwójkowo)
aaa	000
aab	001
aac	010
ab	011
ac	100
b	101
c	110
?	111

Warto tutaj zauważyć, to co zostało powiedziane wcześniej, że kod Tunstalla nie uwzględnia wszystkich możliwych ciągów – nie ma tutaj np. kodu dla ciągów ‘a’, ani ‘aa’.

Kodowanie komunikatu

Zostanie zakodowany komunikat ‘aaaabbbaaaaccaabbaaabaa’, składający się z 22 symboli.

aaa	ab	b	b	aaa	ac	c	aab	b	aaa	b	aa
000	011	101	101	000	100	110	001	101	000	101	111	kod(‘a’) kod(‘a’)

Dla dwóch ostatnich znaków, ciągu ‘aa’, nie istnieje słowo kodowe, dlatego wysyłany jest specjalny kod 111, zaś one same są zapisywane wprost.

Jeśli przyjąć, że pojedynczy znak można zapisać na dwóch bitach, wówczas rozmiar wejściowego ciągu wynosi 44 bity. Koder natomiast wypisał 12 kodów 3-bitowych oraz 2 kody 2-bitowe (końcówka), co w sumie daje 40 bitów na zakodowany komunikat – o 4 mniej.