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

История

Кодирование по Танстеллу было предметом докторской диссертации в 1967 году, когда он работал в Технологическом институте Джорджии . Темой этой диссертации был «Синтез кодов с бесшумным сжатием» .

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

Свойства

В отличие от , одним из которых является кодирование Хаффмана , при кодировании Танстелла сопоставляются исходные символы с фиксированным количеством битов .

Как коды Танстелла, так и коды Лемпеля-Зива представляют слова переменной длины кодами фиксированной длины .

В отличие от кодирования ^{[ уточнить ]} , кодирование Танстелла анализирует источник с помощью кодовых слов переменной длины.

Можно показать , что для достаточно большого словаря количество битов на букву источника может быть сколь угодно близко к ${\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}$ каждый раз.

Ограничения

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

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

Примечания