Арифметическое кодирование

    Сейчас существует множество алгоритмов сжатия информации. Большинство из них широко известны, но есть и некоторые весьма эффективные, но, тем не менее, малоизвестные алгоритмы. Эта статья рассказывает о методе арифметического кодирования, который является лучшим из энтропийных, но тем не менее мало кто о нём знает.
    Прежде чем рассказывать об арифметическом кодировании, надо сказать пару слов об алгоритме Хаффмана. Этот метод эффективен, когда частоты появления символов пропорциональны 1/2n (где n – натуральное положительное число). Это утверждение становится очевидным, если вспомнить, что коды Хаффмана для каждого символа всегда состоят из целого числа бит. Рассмотрим ситуацию, когда частота появление символа равна 0,2, тогда оптимальный код для кодирования это символа должен иметь длину –log2(0,2)=2,3 бита. Понятно, что префиксный код Хаффмана не может иметь такую длину, т.е. в конечном итоге это приводит к ухудшению сжатия данных.
    Арифметическое кодирование предназначено для того, чтобы решить эту проблему. Основная идея заключается в том, чтобы присваивать коды не отдельным символам, а их последовательностям.
    Вначале рассмотрим идею, лежащую в основе алгоритма, затем рассмотрим небольшой практический пример.
    Как и во всех энтропийных алгоритмах мы обладаем информацией о частоте использования каждого символа алфавита. Эта информация является исходной для рассматриваемого метода. Теперь введём понятие рабочего отрезка. Рабочим называется полуинтервал [a;b) с расположенными на нём точками. Причём точки расположены т.о., что длины образованных ими отрезков равны частоте использования символов. При инициализации алгоритма a=0 b=1.
    Один шаг кодирования заключается в простой операции: берётся кодируемый символ, для него ищется соответствующий участок на рабочем отрезке. Найденный участок становится новым рабочим отрезком (т.е. его тоже необходимо разбить с помощью точек).
    Эта операция выполняется для некоторого количества символов исходного потока. Результатом кодирования цепочки символов является любое число (а также длина его битовой записи) с итогового рабочего отрезка (чаще всего берётся левая граница отрезка).
    Звучит это довольно сложно. Давайте попробуем разобраться с помощью небольшого примера. Закодируем сообщение «ЭТОТ_МЕТОД_ЛУЧШЕ_ХАФФМАНА» с помощью описанного метода.



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



    Берём первый символ из потока, это символ «Э». Соответствующий ему отрезок – отрезок [0,96;1). Если бы мы хотели закодировать один символ, то результатом кодирования было бы любое число из этого отрезка. Но мы не остановимся на одном символе, а добавим ещё один. Символ «Т». Для этого составим новый рабочий отрезок с a=0,96 и b=1. Разбиваем этот отрезок точками точно так же как мы сделали это для исходного отрезка и считываем новый символ «Т». Символу «Т» соответствует диапазон [0,24;0,36), но наш рабочий отрезок уже сократился до отрезка [0,96;1). Т.е. границы нам необходимо пересчитать. Сделать это можно с помощью двух следующих формул: High=Lowold+(Highold-Lowold)*RangeHigh(x), Low=Lowold+(Highold-Lowold)*RangeLow(x), где Lowold – нижняя граница интервала, Highold – верхняя граница интервала RangeHigh и RangeLow – верхняя и нижняя границы кодируемого символа.
    Пользуясь этими формулами, закодируем первое слово сообщения целиком:



    Результатом кодирования будет любое число из полуинтервала [0,97218816; 0,97223424).
    Предположим, что результатом кодирования была выбрана левая граница полуинтервала, т.е. число 0,97218816.
    Рассмотрим процесс декодирования. Код лежит в полуинтервале [0,96;1). Т.е. первый символ сообщения «Э». Чтобы декодировать второй символ (который кодировался в полуинтервале [0,96;1)) полуинтервал нужно нормализовать, т.е. привести к виду [0;1). Это делается с помощью следующей формулы: code=(code-RangeLow(x))/(RangeHigh(x)-RangeLow(x)), где code – текущее значение кода.
    Применяя эту формулу, получаем новое значение code=(0,97218816-0,96)/(1-0,96)= 0,304704. Т.е. второй символ последовательности «Т».
    Снова применим формулу: code=(0,304704-0,24)/(0,36-0,24)= 0,5392. Третий символ последовательности – «О».
    Продолжая декодирование, по описанной схеме мы можем полностью восстановить исходный текст.

    Т.о. мы с вами рассмотрели алгоритм кодирования и декодирования с помощью самого эффективного из всех энтропийных алгоритмов. Надеюсь, из этой статьи вы узнали что-то новое и поняли основные идеи, лежащие в алгоритме арифметического кодирования.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 39

      0
      Теория ясна, спасибо.
      А каким образом потом это число записывается и с какой необходимой точностью, чтобы обогнать Хаффмана?
      Если даже никак, то есть ли какие-нибудь теоретические обоснования того, что этот алгоритм работает лучше?
        0
        Оно не «потом» записывается, оно сразу записывается. Когда вы получили диапазон 0.11-0.14, 0.1 можно записать и забыть. По факту хранятся и обсчитываются последние 16-32 бита диапазона, всё остальное уже записано.
          +4
          Число записывается следующим образом: внутри полученного полуинтервала выбирается полуинтервал , где n — наименьшее из возможных, и в выходной файл пишется число в виде двоичной дроби — всё, что стоит после «0,».
            +2
            Автор, кстати, забыл упомянуть, что на словах этот алгоритм чрезвычайно прост, но когда дело доходит до реализации, всплывает невероятное количество подводных камней. Нам в школе давали в качестве домашнего задания реализовать этот алгоритм на Haskell, и у меня ушло 3 недели, чтобы заставить его вменяемо работать, при том что перед глазами у меня был код на C.
            P.S.: на задание реализовать PPMc, являющийся идейным наследником и обобщением арифмокодера, я благополучно забил :)
              +19
              Что же за школы у вас такие??!
                +1
                habrahabr.ru/blogs/study/87800/

                Статья, честно говоря, отстойная, поэтому расскажу свою версию, вкратце:

                Питерская, частная, но бесплатная школа. Основной упор на математику и, меньше, программирование. Лично я сейчас учусь в 11 классе. На основном курсе математики (матанализ) только что начали рассказывать интегралы. На программировании весь прошлый год изучали алгоритмы сжатия (Шеннон, Хаффман, LZ77/78, LZW, арифметик, PPM, BZ2), с обязательным условием написания их на Haskell. В конце года начали заниматься Java, сейчас продолжаем. Летом, в лагере, были курсы: обязательный «Ряды в банаховых пространствах» и один из трёх на выбор: частичные группоиды, теория Галуа или теория групп. Сейчас ведутся ещё штук 5 (необязательных) спецкурсов с похожими названиями. Как-то так :)

                Если интересно, могу попробовать написать свою статью, но ничего не обещаю.
                  0
                  Жесть. Из вас что, из каждого планируют вырастить Ландау? :)
                    0
                    Грамотно у Вас учителя подходят к обучению. Респект им.
                      0
                      Подходят-то грамотно, но за свою психику после матана с 8ого класса неручаюсь.
                        0
                        Держитесь, сударь. Еще вся жизнь впереди.
                  +7
                  Почему же у нас в школе только задания типа «вывести четные числа от 1 до 100» на бейсике были? :(
                    +5
                    суровые челябинские дети.
                  +2
                  Скорость VS размер. Ничего нового, всегда приходилось выбирать из наиболее важного. Скажем, с трудом вы покодируете арифметическим сжатием на каком-нибудь Z80 с приемлемой скоростью (без аппаратного деления целых, про вещественные числа я не упоминаю). Хотя на компах нонешных — это конечно не проблема.
                    +2
                    Арифметика быстрее Хаффмана, как ни странно, примерно раза в два. Деление целых ни разу не проблема, оно делается сдвигами. Более того, на старых х86 (8086-80286) процессорах оптимизированное вручную деление сдвигами работало быстрее аппаратной команды. Борландовские компиляторы, например, аппаратным DIV не пользовались.
                      0
                      Более того, на старых х86 (8086-80286) процессорах оптимизированное вручную деление сдвигами работало быстрее аппаратной команды. Борландовские компиляторы, например, аппаратным DIV не пользовались.


                      Сдвиги на старых процах пользовали только в случаях деления/умножения на степень двойки. Во всех остальных случаях — стандартные DIV и MUL. Борландовские компиляторы так и делали
                        0
                        А нельзя ли пример деления сдвигами скажем X/237?
                        0
                        Теорию категорий тоже в школе брали?
                          +1
                          Судя по всему, ваш комментарий относится к ветке выше (Pastafarianist).
                            +1
                            Вы удивитесь, но да. Правда, только в качестве необязательного спецкурса, но я лично знаю человека, который отсидел его целиком. И это не я.
                          +9
                          Мало кто знает? Это же один из самых известных алгоритмов
                          +2
                          Алгоритмы это хорошо есть ли что-нибудь в действующим варианте? Например как Rar, 7-zip.
                            +1
                            Насколько мне известно, одной из частей алгоритма RAR является арифметическое кодирование, точнее, его обобщение — один из алгоритмов семейства PPM. 7-zip тоже умеет использовать PPM (а именно, PPMd), наряду с другими алгоритмами, типа LZMA.
                              +1
                              LZMA, если я не ошибаюсь, использует разновидность арифметического кодирования — интервальное кодирование (оно работает быстрее). Да и в любых LZ-based архиваторах выходная последовательность дожимается либо арифметиком, либо хаффманом. В обычном Zip вроде бы используется хаффман.
                              0
                              Не знаю есть ли архиваторы, использующие только арифметическое сжатие, но оно используется для дожатия без потерь на одном из шагов в jpeg-2000 и h264.
                                0
                                Dirac.

                                ЕМНИП на арифметическое кодирование, в отличие от Хаффмана, до сих пор не все патенты истекли.
                                  0
                                  зато его вариант — range coding — свободен
                              +1
                              Освоил алгоритм Хаффмана очень быстро, даже реализовал адаптивные улучшения для него, а вот арифметическое сжатие мне долго не давалось из-за туговатых статей на 50 страниц. Спасибо за краткое и внятное объяснение. Наконец-то все встало на свои места.
                                0
                                Вроде бы Quantized Indexing дает лучшее сжатие для энтропии засчет меньших накладных расходов. К тому же никто не использует Arithmetic Coding в чистом виде. Как правило народ берёт Range Coder который быстрее, патентно-чист, и жмет чуть хуже за счет округлений. Как пример реализации советую посмотреть RC Дмитрия Шкарина (Shkarin).
                                  0
                                  Спасибо за статью (+), Хаффмана я как то даже писал на pascal во времена учебы. Но вот арифметическое кодирование я не смог раскусить на моменте реализации. По теории было все понятно. То что описано является основой, но большие вопросы занимает именно реализация, представления чисел с столь длинными хвостами после запятой.
                                  я начинал было делать, но меня хватило лишь на размеры фраз до переполнения float :)
                                  было бы здорово удивить продолжение стать, содержащем в себе ключ к реализации и ключ симбиозу арифметическому кодированию и адаптивного Хаффмана.
                                    +1
                                    en.wikipedia.org/wiki/Range_encoding дает хорошее объяснение реализации «почти AC». Хотя, конечно, краткий обзор применений было бы хорошо.
                                      0
                                      Жаль этой ссылки не было в 2002 году…
                                      +1
                                      Так адаптивное кодирование делается примерно так же, как адаптивный Хаффман. Только в Хаффмане дерево перестраивается, а тут — таблица-статистика.

                                      Для упрощения работы с дробями можно делать адаптацию не на каждый входной символ, а на каждый 1/2/4/8-й и т. д. (степень двойки) символ. Тогда фактически статистические веса, т.е. длины интервалов, сопоставляемых отдельным символам, будут конечными двоичными дробями, и можно работать в арифметике с фиксированной запятой — правда, ценой некоторой потери эффективности.
                                        0
                                        ну зато с fixed_point можно аппаратное решение реализовать в приемлемых ресурсах. LZRW вон сделали…
                                      0
                                      Из-за грёбанных патентов в jpeg до сих пор не применяется арифметическое сжатие.
                                      А есть ведь ещё разработки типа типа PackJPG (и другие), обеспечивающие на 30% лучшее сжатие чем обычный jpeg при абсолютном байт-в-байт сходстве распакованной картинки, но тоже проблема — никаких плагинов для браузеров/просмотрщиков/редакторов.
                                        0
                                        Тут ещё можно вспомнить и JPEG2000, который тоже из-за патентов в народ так и не вышел, хоть и неплох,
                                        0
                                        Спасибо за статью. Есть книжка «Методы сжатия данных», к сожалению не помню авторов, там их целая могучая кучка выпускников МГУ. Если не ошибаюсь, 3е издание должно быть уже. Дак вот там для тех, кому интересно, расписаны и показаны огромное количество методов преобразований для сжатия, так и самого сжатия. Очень рекомендую к прочтению. Единственное — написана конечно тяжело. Но там и материал такой не для домохозяек…
                                          +1
                                          Авторы: Дмитрий Ватолин, Александр Ратушняк, Максим Смирнов и Юкин (имени не помню).

                                          Частично книгу можно взять на сайте compression.ru
                                          • UFO just landed and posted this here

                                          Only users with full accounts can post comments. Log in, please.