Кодировка Tunstall

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

История [ править ]

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

Его конструкция является предшественницей Lempel – Ziv .

Свойства [ править ]

В отличие от кодов переменной длины , которые включают кодирование Хаффмана и Лемпеля – Зива, кодирование 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}} |}$

Пример [ править ]

Эта статья может потребовать очистки, чтобы соответствовать стандартам качества Википедии . Конкретная проблема: неверные вероятности. Помогите улучшить эту статью, если можете. ( Август 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

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

Ограничения [ править ]

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

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

Ссылки [ править ]

Викискладе есть медиафайлы, связанные с кодированием Tunstall .