Хранение таблицы вероятностей при сжатии текста
Я делаю проект, в котором сравниваю различные типы методов сжатия текста, такие как Хаффман и Арифметика, для статической и адаптивной форм. Я делаю таблицу вероятностей для обоих, используя количество вхождений каждой буквы в тексте. Теперь для адаптивной формы получателю не нужна таблица вероятностей, но для статической формы нам необходимо также передать эту таблицу вероятностей получателю для декодирования сообщения. Теперь для сохранения этой таблицы потребуются дополнительные биты, которые следует учитывать при сравнении.
Итак, мой вопрос здесь:
- Какое лучшее решение для хранения таблицы вероятностей (в файле).
- Какое минимальное количество битов требуется для этого? (Я знаю, что это зависит от текста, но есть ли способ найти минимальные биты, необходимые для хранения таблицы).
Большое спасибо.
Решение
Один из распространенных способов передачи таблицы 0-го порядка (то есть таблицы, содержащей только один токен и не ожидающей просмотра), заключается в простом добавлении всех возможных символов в порядке убывания частоты. Вероятности обычно не нужно хранить, потому что для кодирования требуется только упорядоченный набор символов, а не их фактические вероятности.
Для схемы сжатия, кодирующей 8-битные токены и предполагающей, что все токены по крайней мере теоретически возможны, это будет означать 256 байтов служебной информации. Для случаев, когда возможна только подмножество байтов (например, сообщения, состоящие только из заглавных букв и цифр), таблица, конечно, будет меньше.
Другие решения
Из вероятностей вы назначаете длину кода для символов. Для создания кода получателю необходим список кортежей: (количество битов, количество символов), за которыми следуют символы в порядке их выделения для кода. Теперь вы можете поиграть с тем, как вы их кодируете.
Кодирование списка символов может использовать тот факт, что для каждого переданного символа количество битов, необходимых для следующих символов, уменьшается. В этом случае может помочь возможность указать на раннем этапе, что используется некоторое подмножество (скажем) 8-битных символов. Поскольку кодовые слова становятся длиннее, может быть удобно иметь кодировку для серии символов, а не передавать каждое из них — возможно, с помощью способа выразить серию из нескольких символов, где «дыры» могут быть выражены в некоторое количество битов, которое зависит от длины цикла — или начального символа, длины и битового вектора (учитывая, что количество битов для выражения длины зависит от начального символа и количества оставшихся символов, и есть Не нужно отправлять немного за первое и последнее в ассортименте!)
Кодирование таблицы кодов Хаффмана само по себе является целой игрой. Тогда для коротких сообщений таблица может быть серьезной накладной нагрузкой … в этом случае (небольшое) число часто используемых таблиц может дать лучшее сжатие.
Вы также можете возиться с кодировкой Хаффмана для длины кода каждого символа и отправлять их в порядке символов. Здесь может помочь механизм счетчика повторений, с его Хаффманом, и способ пропуска прогонов неиспользуемых символов (т. Е. Символов с нулевой длиной кода). Конечно, вы можете добавить таблицу первого уровня, чтобы указать кодировку для этого!
Другой подход — это число битовых векторов, по одному вектору для каждой длины кодового слова. Начиная с длины кодового слова с наибольшим количеством символов, испускают длину и битовый вектор, затем следующую наибольшую длину кода с меньшим битовым вектором … и так далее. Опять же, способ кодирования прогонов и диапазонов может сократить необходимое количество битов, и снова, по мере продолжения, биты, необходимые для этих битов, уменьшаются.
Вопрос в том, насколько чувствительно сравнение с размером таблицы кодов? Очевидно, что если он очень чувствителен, то важно исследовать, что можно сделать с помощью хитрости. Но эффективность любой данной схемы будет зависеть от того, насколько хорошо она подходит для сжатия «типичных» данных.