Хранение таблицы вероятностей при сжатии текста
Я делаю проект, в котором сравниваю различные типы методов сжатия текста, такие как Хаффман и Арифметика, для статической и адаптивной форм. Я делаю таблицу вероятностей для обоих, используя количество вхождений каждой буквы в тексте. Теперь для адаптивной формы получателю не нужна таблица вероятностей, но для статической формы нам необходимо также передать эту таблицу вероятностей получателю для декодирования сообщения. Теперь для хранения этой таблицы потребуются дополнительные биты, которые следует учитывать при сравнении.
Итак, мой вопрос здесь:
- Какое лучшее решение для хранения таблицы вероятностей (в файле).
- Какое минимальное количество битов требуется для этого? (Я знаю, что это зависит от текста, но есть ли способ найти минимальные биты, необходимые для хранения таблицы).
Большое спасибо.
2 ответа
Из вероятностей вы назначаете длину кода для символов. Для создания кода получателю необходим список кортежей: (количество битов, количество символов), за которыми следуют символы в порядке их выделения для кода. Теперь вы можете поиграть с тем, как вы их кодируете.
Кодирование списка символов может использовать тот факт, что для каждого переданного символа количество битов, необходимых для следующих символов, уменьшается. Здесь может помочь возможность указать на раннем этапе, что используется некоторое подмножество (скажем) 8-битных символов. Поскольку кодовые слова становятся длиннее, может быть удобно иметь кодировку для серии символов, а не передавать каждое из них - возможно, с помощью способа выразить серию из нескольких символов, где "дыры" могут быть выражены в некоторое количество битов, которое зависит от длины цикла - или начального символа, длины и битового вектора (учитывая, что количество битов для выражения длины зависит от начального символа и количества оставшихся символов, и есть Не нужно отправлять немного за первое и последнее в ассортименте!)
Кодировка таблицы кодов Хаффмана сама по себе является целой игрой. Тогда для коротких сообщений таблица может быть серьезной накладной нагрузкой... в этом случае (небольшое) число обычно полезных таблиц может дать лучшее сжатие.
Вы также можете возиться с кодировкой Хаффмана для длины кода каждого символа и отправлять их в порядке символов. Здесь может помочь механизм счетчика повторений, с его Хаффманом, и способ пропуска прогонов неиспользованных символов (т. Е. Символов с нулевой длиной кода). Конечно, вы можете добавить таблицу первого уровня, чтобы указать кодировку для этого!
Другой подход - это число битовых векторов, по одному вектору для каждой длины кодового слова. Начиная с длины кодового слова с наибольшим количеством символов, испускают длину и битовый вектор, затем следующую наибольшую длину кода с меньшим битовым вектором... и так далее. Опять же, способ кодирования прогонов и диапазонов может сократить необходимое количество битов, и снова, по мере выполнения, биты, необходимые для этих битов, уменьшаются.
Вопрос в том, насколько чувствительно сравнение с размером таблицы кодов? Очевидно, что если он очень чувствителен, то важно исследовать, что можно сделать с помощью хитрости. Но эффективность любой данной схемы будет зависеть от того, насколько хорошо она подходит для сжатия "типичных" данных.
Существует множество способов сохранить информацию о вероятности, которая нужна декомпрессору Хаффмана или арифметическому декомпрессору для декодирования сжатой информации в (точную копию) исходного открытого текста.
Как отметил Марк Адлер в связанном вопросе ( Сохранение таблицы кодов в сжатом файле после сжатия Хаффмана и построение дерева для распаковки из этой таблицы),
Вам не нужно передавать вероятности или дерево. Все, что требуется декодеру [Хаффмана], - это количество битов, назначенных каждому символу, и канонический способ присвоения битовых значений каждому символу, согласованный как кодером, так и декодером. См. Канонический код Хаффмана.
Я предполагаю, что вы используете байтовый код Хаффмана, в котором каждый сжатый код декодируется в один из 256 возможных байтов.
Возможно, самый простой способ сохранить эти длины в битах - это исчерпывающая таблица, содержащая ровно 256 битов, по одной на каждый возможный байт. Так, например, 65-я запись в таблице дает битовую длину буквы 'A' (65-й символ ASCII), которая может быть от 1 (когда A очень часто встречается) до, возможно, 12 (когда A чрезвычайно редко), или 0 (означает, что A никогда не встречается в этом тексте). Каждая длина легко умещается в 1 байт, так что длина таблицы составляет 256 байт.
(Почти всегда максимальная длина составляет 15 бит или меньше, поэтому обычно каждая длина может легко уместиться в полбайта, давая таблицу, которая всегда составляет ровно 128 байтов, но имеет дело с "патологическими" файлами данных, которые обманывают Хаффмана Алгоритм присвоения некоторым байтам открытого текста символа длиной более 15 бит может быть сложным. Некоторые системы специально проверяют, превышает ли максимальная длина 15 бит, и искусственно изменяют дерево Хаффмана, чтобы все длины не превышали 15 бит - иногда это называется дерево Хаффмана с ограниченной глубиной или кодирование Хаффмана с ограниченной длиной. Аналогично, стандарт JPEG ограничивает длину кода Хаффмана до 16 бит).
Более компактные (и более трудные для описания) подходы используются для хранения 4 таблиц Хаффмана битовой длины в изображениях JPEG и многих таблиц Хаффмана, используемых в потоке DEFLATE в таблице переменной длины, длина которой зависит от конкретных данных - но все они сначала сокращают информацию о вероятности, которая должна быть сохранена, только до битовой длины символов. (Возможно, вы могли бы просто использовать реализацию DEFLATE, а не писать и отлаживать что-то с нуля?)
Насколько я понимаю, арифметическое кодирование обычно использует более точную информацию о вероятности, по крайней мере, для наиболее часто встречающихся символов, чем коды Хаффмана. Скажите, пожалуйста, если вы найдете эффективный способ передать эту информацию получателю.
Один из распространенных способов передачи таблицы 0-го порядка (то есть таблицы, содержащей только один токен и не ожидающей просмотра), состоит в простом добавлении всех возможных символов в порядке убывания частоты. Вероятности обычно не нужно хранить, потому что для кодирования требуется только упорядоченный набор символов, а не их фактические вероятности.
Для схемы сжатия, кодирующей 8-битные токены и предполагающей, что все токены по крайней мере теоретически возможны, это будет означать 256 байтов служебной информации. Для случаев, когда возможен только поднабор байтов (например, сообщения, состоящие только из заглавных букв и цифр), таблица, конечно, будет меньше.