Kod Tunstalla

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Kod Tunstallakod 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[edytuj | edytuj kod]

Dany jest alfabet oraz prawdopodobieństwa wystąpienia każdego z elementów Liczba słów kodowych o długości bitów wynosi i musi być większa od jedno słowo kodowe musi zostać zarezerwowane, do wykorzystania pozostaje więc słów.

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

  1. Początkowo drzewo składa się z korzenia mającego dzieci, zawierających wszystkie symbole z alfabetu.
  2. Dopóki liczba liści nie przekroczyła powtarzaj:
    • Znajdź liść o największym prawdopodobieństwie w którym zapisany jest ciąg
    • Jeśli jest jeszcze miejsce na liści, ten węzeł staje się rodzicem dla dzieci, zawierających ciąg przedłużony o symbole z alfabetu o prawdopodobieństwach W przeciwnym razie drzewo nie jest modyfikowane i następuje skok do kroku 3.
  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[edytuj | edytuj kod]

Dany jest alfabet zawierający trzy symbole o prawdopodobieństwach Zostanie użyty kod trzybitowy, tj. czyli dostępne maksymalnie 7 słów kodowych.

Konstruowanie kodu[edytuj | edytuj kod]

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):

  1. a (0.750000), b (0.200000), c (0.050000)
  2. aa (0.562500), ab (0.150000), ac (0.037500), b (0.200000), c (0.050000)
  3. 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).

Drzewo ciągów wejściowych
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[edytuj | edytuj kod]

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.

Przypisy[edytuj | edytuj kod]

  1. B. P. Tunstall, Synthesis of Noiseless Compression Codes, praca doktorska (Georgia Institute of Technology, 1967).

Bibliografia[edytuj | edytuj kod]