// Kodowanie Tunstalla – optymalna kompresja od długości zmiennej do stałej
Mapuje sekwencje o zmiennej długości na kody o stałej długości.
Słownik budowany jest na podstawie rozkładu prawdopodobieństwa symboli.
Kody o stałej długości umożliwiają prostą i szybką dekodację.
Kodowanie Tunstalla buduje słownik sekwencji o zmiennej długości, które są mapowane na binarne kody o stałej długości. Zaczynamy od pojedynczych symboli, a następnie iteracyjnie rozszerzamy sekwencję o najwyższym prawdopodobieństwie poprzez dodanie każdego symbolu alfabetu. Powstaje optymalny kod od zmiennej do stałej długości, w którym bardziej prawdopodobne sekwencje otrzymują własne słowa kodowe.
Tekst: 'aabaa' przy P(a)=0.8, P(b)=0.2 Budowa słownika (kody 3‑bitowe): Początkowo: a, b Rozszerz 'a': aa, ab Rozszerz 'aa': aaa, aab Rozszerz 'ab': aba, abb Końcowy słownik (8 kodów): aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 Kodowanie: 'aabaa' → 001 100 (aab + aa)
Kodowanie Tunstalla to metoda kodowania entropijnego o zmiennej długości wejścia i stałej długości wyjścia. W przeciwieństwie do kodowania Huffmana (stała→zmienna), Tunstall mapuje sekwencje o zmiennej długości na słowa kodowe o stałej długości, co jest idealne dla zastosowań wymagających stałej przepływności bitów.
Huffman: stałe wejście → zmienne wyjście (np. 'a' → '0', 'b' → '10'). Tunstall: zmienne wejście → stałe wyjście (np. 'aa' → '000', 'ab' → '001'). Tunstall jest korzystniejszy dla sprzętu i synchronizacji, ale zwykle daje nieco niższy współczynnik kompresji.
Zaczynamy od pojedynczych symboli. Następnie powtarzamy: 1) znajdujemy sekwencję o najwyższym prawdopodobieństwie, 2) usuwamy ją i dodajemy wszystkie możliwe rozszerzenia o jeden symbol, 3) kontynuujemy, aż osiągniemy pożądany rozmiar słownika (2^n dla kodów n‑bitowych).
Kodowanie Tunstalla jest stosowane w kompresji mowy, kodowaniu obrazów oraz w sytuacjach, w których wymagana jest stała szybkość wyjściowa. Jest szczególnie przydatne w implementacjach sprzętowych i systemach czasu rzeczywistego, gdzie kody o zmiennej długości komplikowałyby synchronizację.