Уменьшают ли алгоритмы сжатия без потерь энтропию?

35

Энтропия Шеннона измеряет информацию, содержащуюся в сообщении, в отличие от той части сообщения, которая определена (или предсказуема). Примеры последних включают избыточность в структуре языка или статистических свойствах, связанных с частотой встречаемости пар букв или слов, триплетов и т. Д.

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

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

Согласно немецкой Википедии

Entropiekodierer werden häufig mit andderen Kodierern kombiniert. Dabei dienen vorgeschaltete Verfahren dazu, умереть Entropie der Daten zu verringern.

По-английски:

Энтропийные кодеры часто комбинируются с другими кодерами. Предыдущие шаги служат для уменьшения энтропии данных.

т. е. bzip2 использует преобразование Берроуза-Уилера с последующим преобразованием «движение вперед» перед применением энтропийного кодирования (в данном случае кодирование Хаффмана).

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

information-theory data-compression entropy Роберт
источник

1

Может быть, способ оценить энтропию, хотя.

труба

39

Многие случайные описания энтропии сбивают с толку таким образом, потому что энтропия не так аккуратна и опрятна, как иногда представляется. В частности, стандартное определение энтропии Шеннона предусматривает, что оно применяется только тогда, когда, как говорит Википедия, «информация, связанная с независимыми событиями, является аддитивной».

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

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

Марковские процессы

Марковский процесс генерирует серию событий, в которых самое последнее событие выбирается из распределения, которое зависит от одного или нескольких предыдущих событий. Очевидно, что огромное количество явлений реального мира лучше моделировать как марковские процессы, чем как дискретные, независимые распределения вероятностей. Например: текст, который вы читаете прямо сейчас!

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

H (S) = - \sum_{i} p_{i} \sum_{j} p_{i} (j) \log p_{i} (j)

$H(\mathcal{S}) = - \sum_i p_i \sum_j \ p_i (j) \log p_i (j)$

Это также можно представить так :

H (Y) = - \sum_{i j} μ_{i} P_{i j} \log P_{i j}

$H(Y) = - \sum_{ij} \mu_i P_{ij} \log P_{ij}$

Снова цитируя Википедию, здесь « $\mu_i$ - асимптотическое распределение цепи», то есть общая вероятность того, что данное событие произойдет в течение длительного горизонта.

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

Они побежали к дереву
Дерево побежало к ним
Дерево они побежали

Но энтропия Шеннона оценит все три строки как одинаково вероятные. Энтропия марковского процесса учитывает разницу, и в результате она присваивает процессу более низкую скорость энтропии.

Уровень энтропии зависит от модели

Если вы уменьшите масштаб, вот общая картина: уровень энтропии заданной последовательности событий из неизвестного источника зависит от модели. Вы будете назначать разные скорости энтропии для определенной серии событий в зависимости от того, как вы смоделировали процесс, который их сгенерировал.

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

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

senderle
источник

2

Большое спасибо! Это прекрасно объясняет, в чем заключалась ошибка в моих рассуждениях.

Роберт

Ваш ответ был бы еще лучше, если бы в качестве примеров смоделированных процессов использовались декомпрессоры данных, изображений и аудио. Например, при сжатии данных LZ модель предполагает машину (декодер), которая принимает в качестве входных команд, например, (D, L): «копировать на выход L смежных символов со смещения D относительно текущей выходной позиции» или (c): « скопировать символ c в текущую позицию вывода ». Кодер LZ преобразует свой входной поток символов в командный язык декодера, и поток командных символов имеет энтропию (и длину), отличную от кодированного потока. Другие виды сжатия имеют разные машины.

piiperi

@piiperi, что звучит полезно - хотя я не знаю ни одной из этих деталей. (Я подхожу к вопросу с точки зрения машинного обучения.)

senderle

@senderle Я имел в виду расширение главы «Коэффициенты энтропии зависит от модели» с некоторыми конкретными примерами процесса. Вы говорите о процессе, который генерирует события, и компоненты обработки данных, изображений, видео, аудио и т. Д. Компрессоров можно рассматривать как такие процессы. Чистый энтропийный кодер - последний шаг конвейера сжатия данных. Ни один из этапов конвейера действительно "не уменьшает энтропию". Вместо этого каждый из них создает инструкции для машины, которая может воспроизводить исходный поток символов. И каждый поток команд имеет различную энтропию и часто разную (то есть более короткую) длину.

piiperi

12

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

Люк Шварцкопфф
источник

Так используются ли дополнительные шаги в алгоритмах сжатия перед энтропийным кодированием, чтобы энтропийный кодер приблизился к энтропии? Разве энтропийный кодер сам по себе не приближается к энтропии применительно к произвольному сообщению?

Роберт

На самом деле, это не так (в зависимости от точного значения «близко»).

Grimmy

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

Люк Шварцкопфф

Нет, преобразование перемещения вперед не выводит отдельный список, который должен быть передан в декодер. Если вы не имеете в виду первоначальный список.

user253751

Ааа, ты прав, это был не лучший пример :)

Люк Шварцкопф

6

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

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

Более реальным примером является сжатие PNG. Это энтропийный компрессор DEFLATE, представляющий собой комбинацию Lempel-Ziff и Huffman. Это означает, что он лучше всего работает со значениями и шаблонами, которые часто повторяются. Большинство соседних пикселей имеют тенденцию быть схожими цветами. Таким образом, каждой строке назначается фильтр, который превращает исходные значения пикселей в дифференциальное кодирование. Таким образом, значения, которые в конечном итоге закодированы с помощью DEFLATE, в основном близки к 0. В крайнем случае это превратит плавный градиент из всех различных значений в одно значение по всей строке, над которой часть LZ или DEFLATE выполняет очень быструю работу.

чокнутый урод
источник

Означает ли это, что кажущаяся энтропия отличается от фактического информационного содержания сообщения? Как это связано с реальной энтропией сообщения?

Роберт

под «кажущейся энтропией» я подразумеваю энтропию, до которой энтропийное кодирование может сжиматься. Разные кодировщики будут иметь разные шаблоны, которые они ищут. Хаффман справляется лучше всего, когда часто используются одни и те же символы, часто используется, lempel-ziff справляется лучше, когда куски повторяются и т. Д.

чокнутый урод

Но алгоритмы Лемпеля-Зива не являются алгоритмами энтропийного кодирования, верно? Я не понимаю, почему они используются перед энтропийными кодерами, например, в LZMA, когда энтропийный кодер сам по себе может предположительно сжать сообщение до минимума.

Роберт

1

@kutschkem Означает ли это, что энтропия не является абсолютной мерой информационного содержания сообщения, а связана с тем, что определяется как символ (например, один символ считается символом, а 1 бит считается символом)? Я думаю, это объясняет, где мои предположения были неверны.

Роберт

1

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

кучкем

6

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

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

Теперь реальные сообщения обычно не имеют этого свойства независимости. Например, если вы видите Q, вполне вероятно, что следующая буква - U. И так далее. Все еще возможно применить алгоритм энтропийного кодера к реальному сообщению, где каждый символ не выбран независимо от остальных. Алгоритм по-прежнему будет без потерь, его все еще можно будет использовать для сжатия, и на практике он все равно будет часто сокращать длину сообщения. Однако это не сокращает его до минимально возможной длины. Это не сжимает сообщение к чему-то, чья длина равна энтропии сообщения; это сжимает это меньше чем это.

Как только вы осознаете это свойство энтропийных энкодеров, парадокс испаряется.

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

DW
источник

2

Слово «энтропия», если его часто употребляют немного свободно, относится к двум различным вещам:

«Общее количество информации» в сообщении или системе
«Плотность» информации, или насколько плотно информация упакована.

Цитата ОП о записи Википедии для https://en.wikipedia.org/wiki/Entropy_(information_theory) относится к первому:

Shannon's entropy measures the information contained in a message

Но (по крайней мере, когда я пишу это) та же статья начинается с:

Information entropy is the average rate at which information is produced by a stochastic source of data.

Итак, один - это количество, а другой - скорость (аналогично расстоянию и скорости). Их иногда называют «расширенными» и «интенсивными» свойствами (см. Https://en.wikipedia.org/wiki/Intensive_and_extensive_properties#Extensive_properties ).

Классическим примером различия является знаменитый сигнал фонаря Пола Ревера: «один - по суше, а два - по морю». 1 бит полной информации (если мы проигнорируем дело «нет, если я еще не добрался до Северной Церкви»). Если бы Павел добавил еще один набор фонарей в каждое окно здания, это было бы «избыточно»: больше никакой информации, поэтому та же самая «полная» или «обширная» энтропия; но намного больше длина сообщения, намного более низкая "интенсивная" энтропия.

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

Следует помнить еще две важные вещи:

Во-первых, мы обычно не знаем «истинную» энтропию системы в любом смысле. Наивный наблюдатель не знает, будет ли «3 фонаря» другим сообщением, или сигналы в другом окне избыточны или нет. Если Пол делает свою поездку привычкой, мы можем посчитать и посмотреть, соответствуют ли окна друг другу. Но, возможно, мы просто не смотрели достаточно долго, чтобы увидеть редкие (и, вероятно, важные!) Исключения.
Во-вторых, важно, как вы измеряете. Попробуйте попытаться оценить, сколько сообщается каждой последовательной буквой текста (это показатель, так что «интенсивная» энтропия, также иногда называемая «относительной энтропией»):
- Если вы просто заметили, что люди посылают текст в 8-битных единицах, ваша первая «оценка» может составлять 8 бит на букву.
- Если вы посчитаете количество используемых различных букв, вы оцените log2 (26) или 4,7 бита на букву (чуть выше, если учесть пробелы, регистр и т. Д.).
- Если вы считаете, что «е» является лучшей ставкой для «следующей буквы», чем «z», вы будете измерять частоту букв и получите около 4,14 (см. Http://people.seas.harvard.edu/~jones/cscie129/ документы / stanford_info_paper / entropy_of_english_9.htm ).
- Если вы посчитаете буквенные пары, вы выберете такие шаблоны, как «qu», «th» и т. Д., И получите около 3,56.
- Если вы посчитаете последовательности до примерно 5 букв, вы получите еще более низкие значения, и в качестве бонуса вы можете довольно надежно отличить, на каком языке используется текст).
- Если вы столь же проницательны и сообразительны, как Н.Г. Бертон и Дж.К.Р. Ликлайдер в «Долгосрочных ограничениях в статистической структуре печатного английского языка» (Американский журнал психологии 68 (1955)), вы можете получить до 10 последовательностей: 0000 букв подряд и найдите еще одно значение энтропии.

Но, конечно, сообщения могут (и имеют) иметь много паттернов, которые не моделируются такими n-граммными методами, поэтому «истинная» энтропия еще ниже.

Если вы смоделируете теоретический бесконечный источник с совершенно случайным распределением токенов по Зипфиану, вы сможете рассчитать обширную и интенсивную энтропию, которая будет зависеть только от количества возможных различных токенов. Графики того, как каждый тип энтропии выглядит при увеличении этого числа, приведены в [ http://www.derose.net/steve/writings/dis Диссертация / Diss.0.html] . Они ведут себя совершенно по-разному:

всего (обширно): http://www.derose.net/steve/writings/dis Диссертация/ Graph13.png
родственник (интенсивный): http://www.derose.net/steve/writings/dis Диссертация/ Graph14.png

Надеюсь, что это помогает или хотя бы интересно ...

TextGeek
источник

1

Я подозреваю, что формулировка в немецкой Википедии ошибочна. Компрессоры увеличивают энтропию. То есть не общая энтропия, а энтропия на бит : плотность информации. Например, для сжатия данных применяется некоторая кодировка длины и словарная схема. Теперь та же информация упакована в меньшее количество битов, поэтому каждый бит несет больше информации. Последующее кодирование Хаффмана делает немного больше того же самого; это просто еще один уровень сжатия.

Kaz
источник

Уменьшают ли алгоритмы сжатия без потерь энтропию?

Ответы:

Марковские процессы

Уровень энтропии зависит от модели