Адаптивная арифметическая кодировка путаница

Question

Я путаю в точку адаптивного арифметического кодирования.

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

Однако, какова точка изменения вероятности после каждого символа?Почему бы вам не просто пройти весь файл и определить вероятности, а затем выполнить арифметическое кодирование в качестве второго прохода?

Дополнительно я не понимаю, как изменение вероятности символов влияет на сжатие?Если мы знаем истинные вероятности символов в файле, мы сжимаем, то сделает файл меньше?

Answer 1

Сначала рассмотрим «проходить через целый файл». Есть несколько предположений, которые стоит думать здесь.

Файлы

могут быть очень большими и проход их дважды могут быть дорогими. Это одна из причин, по которой большинство мировых стандартов сжатия основаны на блоках или окнах.

Есть ситуации, когда у вас нет «всего файла», например, в качестве канала связи. TLS (как минимум 1,3, как минимум) поддерживает сжатие, например.

Файлы

не всегда однородны. Архивы (например, tar ) - это случай. Статистическая модель, подходящая для одной части файла, может не подходить для другой части. Адаптивное кодирование адаптируется к этому тоже.

Для вашего окончательного вопроса, если и эндодер, так и декодер знали истинные вероятности символов в файле, который мы сжимаем, то это не нужно будет передаваться. И, действительно, мы иногда делаем это в реальном мире. Например, стандарт JPEG указывает таблицы кодирования по умолчанию для тех времен, когда они подходят, и позволяет энкодеру предоставлять свои собственные, когда они не являются.

Продавая статическую таблицу кодирования эффективно (то есть сжимая его) - это нетривиальная проблема, особенно для большого кода алфавита. Для хорошо разработанной схемы стоимость передачи таблицы должна быть равна «расходам на обучение» с использованием адаптивного кода.