Есть ли алгоритм для «идеального» сжатия?

Question

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

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

Рассмотрит битовые строки: а = "101010101010", b = "110100011010".

При использовании простой энтропии Shannon эти битовые строки должны иметь ту же самую энтропию, когда мы рассматриваем битовые строки как простые символы 0 и 1, но этот подход является ошибочным, потому что мы можем интуитивно видеть, что битстрона a имеет меньшую энтропию, чем bitstring b, потому что это просто шаблон повторяющихся 10. Имея это в виду, мы могли бы лучше понять фактическую энтропию источника, вычислив энтропию Шеннона для составных символов 00, 10, 01 и 11.

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

Я полагаю, чтобы быть более конкретными, чем вопрос в названии, у меня есть три основные вопрос:

ли кодирование Хаффмана с использованием отдельных бит в виде символов сжать битовые Подобно оптимально, даже с явным рисунком, который происходит, когда мы анализируем строку на уровне 2-битных символов? Если нет, можно ли оптимально сжать источник, пройдя через разные «уровни» (извините, если я уничтожаю терминологию здесь) кодирования Хаффмана, пока не будет найдена наилучшая степень сжатия? Может ли проходить различные «раунды» кодирования Хаффмана, в некоторых случаях увеличить степень сжатия? (ea сначала пройти через кодировку Хаффмана с символами длиной 5 бит, а затем пройти через кодирование Хаффмана для символов длиной 4 бита? huff_4bits(huff_5bits(bitstring)))

Answer 1

Как заявил Марк, общий ответ - « no», из-за сложности Колмогорова. Позвольте мне немного рассказать об этом.

сжатия в основном два шага: 1) Модель 2) Энтропия

Роль модели заключается в «угадать» следующие байты или поля, чтобы прибыть. Модель может иметь любую форму, и нет предела ее эффективности. Тривиальный пример - функция генератора случайных чисел: с внешней точки зрения она выглядит как шум и поэтому не может быть сжата. Но если вы знаете функцию генерации, бесконечно длинную последовательность можно сжать в небольшой набор кода - функцию генератора.

Вот почему существует «без ограничений», и сложность Колмогорова заключается в том, что: вы никогда не можете гарантировать, что нет лучшего способа «моделировать» данные.

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

Huffman является оптимальным по отношению к пределу Шеннона , если вы согласны с тем ограничением, что каждый символ должен быть закодирован с использованием целого числа бит. Это близкая, но несовершенная аппроксимация. Лучшее сжатие может быть достигнуто за счет использования дробных битов, что и предлагает Арифметические кодеры, или более поздних основанных на ANS Finite State Entropy coder. Оба приближаются к пределу Шеннона.

Предел Шеннона применяется только в том случае, если вы обрабатываете набор символов «индивидуально». Как только вы попытаетесь «объединить их» или найдите какие-либо корреляции между символами, вы «моделируете». И это территория Колмогорова Сложности, которая не является вычислимой.

Answer 2

Нет. Можно доказать, что даже алгоритма не определено, как хорошо совершенный компрессор. См. Kolmogorov Complexity.

Кодирование Хаффмана (или арифметическое кодирование) само по себе не приближается к лучшему сжатию. Другие методы должны использоваться, чтобы использовать преимущества избыточного порядка в данных.