Сжатие данных: Арифметическое кодирование неясно

Question

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

Марк Нельсон арифметического кодирование может быть расположено в

http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/

Answer 1

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

Это количество данных, как известно, доказано Шеннона, и могут быть вычислены просто используя следующую формулу: -log2 (р)

Например, если р = 50%, то вам необходимо 1 бит. И если p = 25%, вам нужно 2 бита.

Это достаточно просто для вероятностей, которые имеют мощность 2 (и в этом специальном случае достаточно кодирования хаффмана). Но что, если вероятность составляет 63%? Тогда вам понадобится -log2 (0,63) = 0,67 бит. Звучит сложно ...

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

Теперь, как это сделать?

Ну, это проще, чем кажется. Вы будете делить свой диапазон в зависимости от вероятностей. Например, если у вас есть диапазон из 100, 2 возможных события и вероятность 95% для 1-го, тогда первые 95 значений скажут «Событие 1», а последние 5 оставшихся значений скажут «Событие 2», ,

ОК, но на компьютерах мы привыкли использовать мощность 2. Например, с 16 битами у вас есть диапазон 65536 возможных значений. Просто сделайте то же самое: возьмите 1-й 95% диапазона (это 62259), чтобы сказать «Событие 1», а остальное - «Событие 2». У вас, очевидно, проблема «округления» (точность), но до тех пор, пока у вас достаточно значений для распространения, это не имеет большого значения. Кроме того, вы не ограничены двумя событиями, у вас может быть множество событий. Все, что имеет значение, - это то, что значения распределяются в зависимости от вероятностей каждого события.

ОК, но теперь у меня есть 62259 возможных значений, чтобы сказать «Событие 1» и 3277 сказать «Событие 2». Какой из них выбрать? Ну, любой из них будет делать. Wether это 1, 30, 5500 или 62256, это все равно означает «Событие 1».

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

Предположим, у меня есть «Событие 1». Так что теперь я должен выбрать любое значение между 0 и 62256. На следующее предположение, у меня есть тот же дистрибутив (95% Event 1, 5% Event 2). Я просто распределю карту распределения с этими вероятностями. За исключением того, что на этот раз он распределяется по 62256 значениям. И мы продолжаем так, уменьшая диапазон значений с каждой догадкой.

Итак, мы определяем «диапазоны», которые сужаются с каждой догадкой. Однако в какой-то момент есть проблема точности, потому что осталось очень мало значений.

Идея состоит в том, чтобы просто «раздуть» диапазон. Например, каждый раз, когда диапазон опускается ниже 32768 (2^15), вы выводите самый старший бит и умножаете остальные на 2 (эффективно смещая значения на один бит слева). Постоянно делая это, вы выставляете биты один за другим, поскольку они решаются рядом догадок.

Теперь соотношение с сжатием становится очевидным: когда диапазон сужается быстро (например: 5%), вы выводите много бит, чтобы получить диапазон выше предела. С другой стороны, когда вероятность очень велика, диапазон очень медленный. У вас даже может быть много догадок, прежде чем вывести свои первые бит. Вот как можно сжать событие до «доли бит».

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

Answer 2

Прежде всего, спасибо за представление меня к понятию арифметического сжатия!

я могу видеть, что этот метод имеет следующие шаги:

1. Создание отображения: Вычислить долю вхождения для каждой буквы, которая дает размер диапазона для каждого алфавита. Затем заказать их и назначить фактические диапазоны от 0 до 1
2. Учитывая сообщение рассчитать диапазон (довольно простой ИМХО)
3. Найдите оптимальный код

Третья часть немного сложнее. Используйте следующий алгоритм.

Пусть b - оптимальное представление. Инициализируйте его в пустую строку (''). Пусть x - минимальное значение, а y - максимальное значение.

1. двойные х и у: х = 2 * х, у = 2 * y
2. Если оба из них больше, чем 1 Append 1 до б. Перейдите к шагу 1.
3. Если оба они меньше 1, добавьте 0 к b. Переходите к шагу 1.
4. Если х < 1, но у> 1, затем добавить 1 к б и остановить

б по существу содержит дробную часть числа вы передающие. Например. Если b = 011, то фракция соответствует 0,011 в двоичном формате.

Какую часть реализации вы не понимаете?

Answer 3

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

Небольшой пример. Представьте, что у нас есть алфавит из 3 символов: 0, 1 и 2 с вероятностями 1/10, 2/10 и 7/10 соответственно. И мы хотим кодировать последовательность [1, 2].Сценарий даст следующий вывод (игнорировать -b N вариант на данный момент):

$ ./gen_map.py -b 6 -m "1,2,7" -e "1,2" 
000000111111|1111|111222222222222222222222222222222222222222222222 
------011222|2222|222000011111111122222222222222222222222222222222 
---------011|2222|222-------------00011111122222222222222222222222 
------------|----|-------------------------00111122222222222222222 
------------|----|-------------------------------01111222222222222 
------------|----|------------------------------------011222222222 
================================================================== 
000000000000|0000|000000000000000011111111111111111111111111111111 
000000000000|0000|111111111111111100000000000000001111111111111111 
000000001111|1111|000000001111111100000000111111110000000011111111 
000011110000|1111|000011110000111100001111000011110000111100001111 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
001100110011|0011|001100110011001100110011001100110011001100110011 
010101010101|0101|010101010101010101010101010101010101010101010101 

Первые 6 строк (до ==== линии) представляют собой диапазон от 0,0 до 1,0, который рекурсивно разделенного на интервалах, пропорциональных символьных вероятностей. Аннотированный первая строка:

[1/10][  2/10 ][     7/10      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 

Тогда мы подразделить каждый интервал снова:

[ 0.1][  0.2  ][     0.7      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 
     [ 0.7 ][.1][ 0.2 ][   0.7     ] 
------011222|2222|222000011111111122222222222222222222222222222222 
            [.1][ .2][ 0.7    ] 
---------011|2222|222-------------00011111122222222222222222222222 

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

Каждая строка соответствует символу на входе (в нашем случае - последовательности [1, 2]). Следуя подинтервалам для каждого входного символа, мы получим окончательный интервал, который мы хотим кодировать с минимальным количеством бит. В нашем случае это первый 2 подинтервал на второй линии:

  [ This one ] 
------011222|2222|222000011111111122222222222222222222222222222222 

После 7 линий (после ====) представляют собой тот же интервал от 0,0 до 1,0, но подразделены в соответствии с двоичной системе счисления. Каждая строка немного выводится, и, выбирая между 0 и 1, вы выбираете левый или правый полуинтервал. Например, биты 01 соответствует подпериода [0.25, 05) на второй линии:

    [ This one ] 
000000000000|0000|111111111111111100000000000000001111111111111111 

Идея арифметического кодера к выходным битам (0 или 1), пока соответствующий интервал не будет полностью внутри (или равно) интервал определяется по входной последовательности. В нашем случае это 0011. В строке ~~~~ показано, где у нас достаточно бит, чтобы однозначно идентифицировать требуемый интервал.

Вертикальные линии, образованные символом |, показывают диапазон битовых последовательностей (строк), которые могут использоваться для кодирования входной последовательности.