Pull to refresh

Comments 39

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

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

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

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


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

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

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

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

Articles