Кодировка Tunstall - Tunstall coding

В Информатика и теория информации, Кодировка Tunstall это форма энтропийное кодирование используется для сжатие данных без потерь.

История

Кодирование Tunstall было предметом докторской диссертации Брайана Паркера Танстолла в 1967 году, когда он работал в Технологическом институте Джорджии. Тема дипломной работы - "Синтез бесшумных кодов сжатия". ^[1]

Его дизайн является предшественником Лемпель-Зив.

Характеристики

В отличие от коды переменной длины, который включает в себя Хаффман и Кодирование Лемпеля – Зива, Код Tunstall - это код который отображает исходные символы в фиксированное количество бит.^[2]

И коды Танстолла, и коды Лемпеля – Зива представляют слова переменной длины кодами фиксированной длины.^[3]

В отличие от типичная кодировка набора Программа Tunstall анализирует стохастический источник с кодовыми словами переменной длины.

Это можно показать^[4]что для достаточно большого словаря количество бит на исходную букву может быть сколь угодно близко к ${\displaystyle H(U)}$, то энтропия источника.

Алгоритм

Алгоритм требует на входе входной алфавит ${\displaystyle {\mathcal {U}}}$, наряду с распределением вероятностей для каждого входного слова. также требуется произвольная константа ${\displaystyle C}$, который является верхней границей размера словаря, который он будет вычислять. ${\displaystyle D}$, строится в виде дерева вероятностей, в котором каждое ребро связано с буквой входного алфавита. Алгоритм выглядит следующим образом:

D: = дерево ${\displaystyle |{\mathcal {U}}|}$ листья, по одному на каждую букву в ${\displaystyle {\mathcal {U}}}$.Пока ${\displaystyle |D|<C}$: Преобразовать наиболее вероятный лист в дерево с помощью ${\displaystyle |{\mathcal {U}}|}$ листья.

Пример

Представим, что мы хотим закодировать строку «hello, world». Далее предположим (несколько нереалистично), что входной алфавит ${\displaystyle {\mathcal {U}}}$содержит только символы из строки "hello, world" - то есть 'h', 'e', ​​'l', ',', '', 'w', 'o', 'r', 'd'. Таким образом, мы можем вычислить вероятность каждого символа на основе его статистического появления во входной строке. Например, буква L появляется трижды в строке из 12 символов: ее вероятность равна ${\displaystyle 3 \over 12}$.

Инициализируем дерево, начиная с дерева ${\displaystyle |{\mathcal {U}}|=9}$ листья. Таким образом, каждое слово напрямую связано с буквой алфавита. 9 слов, которые мы получаем таким образом, могут быть закодированы в вывод фиксированного размера ${\displaystyle \lceil \log _{2}(9)\rceil =4}$ биты.

Затем мы берем лист с наибольшей вероятностью (здесь ${\displaystyle w_{1}}$) и преобразовать его в еще одно дерево ${\displaystyle |{\mathcal {U}}|=9}$ листьев, по одному для каждого символа. Мы повторно вычисляем вероятности этих листьев. Например, последовательность из двух букв L встречается один раз. Учитывая, что есть три появления букв, за которыми следует L, результирующая вероятность равна ${\displaystyle {1 \over 3}\cdot {3 \over 12}={1 \over 12}}$.

Мы получаем 17 слов, каждое из которых можно закодировать в вывод фиксированного размера ${\displaystyle \lceil \log _{2}(17)\rceil =5}$ биты.

Обратите внимание, что мы можем повторять и дальше, увеличивая количество слов на ${\displaystyle |{\mathcal {U}}|-1=8}$ каждый раз.

Ограничения

Кодирование Tunstall требует, чтобы алгоритм знал до операции синтаксического анализа, каково распределение вероятностей для каждой буквы алфавита. Кодирование Хаффмана.

Требование вывода блока фиксированной длины делает его меньше, чем Лемпель-Зив, который имеет аналогичный дизайн на основе словаря, но с выходом блока переменного размера.^{[требуется разъяснение ]}

Рекомендации

1. Танстолл, Брайан Паркер (сентябрь 1967). Синтез бесшумных кодов сжатия. Технологический институт Джорджии.
2. http://www.rle.mit.edu/rgallager/documents/notes1.pdf, Исследование алгоритма Танстолла на Массачусетский технологический институт
3. «Адаптивное кодирование источника переменной и фиксированной длины - кодирование Лемпеля-Зива».[1][2]
4. [3], Исследование алгоритма Танстолла из EPFL Отдел теории информации