Можно ли сжать данные до размера, который меньше предела сжатия данных Шеннона?

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

Эти документы могут помочь объяснить этот метод:

https://arxiv.org/pdf/1703.08127

http://www-video.eecs.berkeley.edu/papers/vdai/dcc2003.pdf

https://www.thinkmind.org/download.php?articleid=ctrq_2014_2_10_70019

Тем не менее, в первом документе, который я читал, с помощью этого метода они могли сжимать некоторый текст до предела Шеннона меньше (они не учитывали пространство, необходимое для сохранения частоты символов, и пространство, необходимое для сохранения мета данные файла). Я подумал об этом и обнаружил, что этот метод не очень эффективен для очень маленьких файлов, но, с другой стороны, он может хорошо работать с большими файлами. На самом деле я не очень хорошо понимаю этот алгоритм или предел Шеннона, я просто знаю, что это сумма вероятностей каждого символа, умноженная на обратной вероятности.$log_2$

Итак, у меня есть несколько вопросов:

1. Действительно ли этот метод сжатия сжимает файлы до размера, меньшего, чем предел Шеннона?

2. Существует ли какой-либо алгоритм сжатия, который сжимает файлы до предела Шеннона меньше (насколько я знаю, ответ на этот вопрос нет)?

3. Может ли когда-либо существовать метод сжатия, который сжимает файлы до предела Шеннона?

4. Если комбинаторное кодирование действительно сжимает файлы за пределом Шеннона, разве невозможно сжимать файл снова и снова, пока мы не достигнем нужного размера файла?

На самом деле я не совсем хорошо понимаю этот алгоритм или предел Шеннона, я просто знаю, что это сумма вероятностей каждого символа, умноженная на log2 обратной величины вероятности.

В этом суть. Предел Шеннона не является универсальным свойством строки текста. Это свойство строки текста плюс модель, которая обеспечивает (возможно, контекстно-зависимые) вероятности символов. Он говорит нам, насколько хорошо эта модель может сжимать текст, предполагая, что модель точна .

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

Легко показать, что вы можете сжать ниже предела Шеннона - возьмите читерский мошенник, у которого есть набор общих файлов, назначенных токенам. Указанные файлы хранятся в виде этих токенов. (Очевидно, что компрессор должен быть очень большим или использовать очень большую библиотеку.)

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

То, что вы не можете сделать, это иметь компрессор, который превышает предел Шеннона для всех файлов .

$1/2$$1/3$$1/6$$p$$log_2(1/p)$

Но если вы примените другую модель, вы получите другую последовательность вероятностей. Например, буква «и» встречается довольно редко, поэтому ее вероятность по всему тексту может составлять 3%, и это вероятность, которую вы должны присвоить этой букве, используя марковскую модель порядка 0 .

Но в английских текстах после «q» обычно идет «u», поэтому, используя модель порядка 1, вы можете назначить гораздо более высокую вероятность «u», идущему после «q», тем самым улучшая степень сжатия.

Более того, некоторые модели выводят меньше символов, чем вводимых, например, LZ77 заменяет повторы текста обратными ссылками, поэтому «abababab» превращается в «ab [2,8]».

Когда кто-то говорит об энтропии Шеннона некоторых данных, а не о данных, сжатых конкретной моделью, она обычно подразумевает энтропию Шеннона, созданную моделью порядка 0, то есть присваивает каждому символу его вероятность по всему тексту. Очевидно, что вы можете преодолеть эту разницу, применив к данным более сложную модель.

Другая возможная интерпретация текста: данный алгоритм сжатия даст вам лучшее сжатие одних текстов и худшее сжатие других. Однако пользователи обычно заботятся о некоторых типах файлов (HTML-страницы на английском языке, машинный код 80386) больше, чем другие (таблицы действительно случайных чисел, бессмысленный шум, выбранный для минимизации повторения). Любая схема сжатия обойдется тем, что лучше сжимает реальные данные, чем хуже, чем бесполезна при сжатии некоторых других типов строк.