// Кодирование Тунсталла – оптимальное сжатие от переменной к фиксированной длине
Отображает последовательности переменной длины в коды фиксированной длины.
Словарь строится по распределению вероятностей символов.
Коды фиксированной длины обеспечивают простое и быстрое декодирование.
Кодирование Тунсталла строит словарь последовательностей переменной длины, отображаемых в двоичные коды фиксированной длины. Начиная с одиночных символов, алгоритм итеративно расширяет наиболее вероятную последовательность, добавляя каждый символ алфавита. В итоге получается оптимальный код "переменная→фиксированная длина", в котором более вероятные последовательности получают собственные кодовые слова.
Текст: 'aabaa' при P(a)=0.8, P(b)=0.2 Построение словаря (3‑битовые коды): Начально: a, b Расширить 'a': aa, ab Расширить 'aa': aaa, aab Расширить 'ab': aba, abb Итоговый словарь (8 кодов): aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 Кодирование: 'aabaa' → 001 100 (aab + aa)
Кодирование Тунсталла — это метод энтропийного кодирования с переменной длиной входа и фиксированной длиной выхода. В отличие от кода Хаффмана (фиксированная→переменная), Tunstall отображает последовательности переменной длины в кодовые слова фиксированной длины, что делает его идеальным для приложений с постоянной скоростью потока.
Хаффман: фиксированный ввод → переменный вывод (например, 'a' → '0', 'b' → '10'). Tunstall: переменный ввод → фиксированный вывод (например, 'aa' → '000', 'ab' → '001'). Tunstall лучше подходит для аппаратных реализаций и синхронизации, но обычно даёт чуть меньший коэффициент сжатия.
Начинают с одиночных символов. Затем повторяют: 1) находят последовательность с наибольшей вероятностью, 2) удаляют её и добавляют все возможные расширения на один символ, 3) продолжают до достижения нужного размера словаря (2^n для n‑битовых кодов).
Кодирование Тунсталла используется при сжатии речи, кодировании изображений и в системах, где требуется фиксированная скорость передачи. Особенно полезно в аппаратных реализациях и системах реального времени, где коды переменной длины усложняют временную синхронизацию.