Комментарии 39
Теория ясна, спасибо.
А каким образом потом это число записывается и с какой необходимой точностью, чтобы обогнать Хаффмана?
Если даже никак, то есть ли какие-нибудь теоретические обоснования того, что этот алгоритм работает лучше?
А каким образом потом это число записывается и с какой необходимой точностью, чтобы обогнать Хаффмана?
Если даже никак, то есть ли какие-нибудь теоретические обоснования того, что этот алгоритм работает лучше?
Оно не «потом» записывается, оно сразу записывается. Когда вы получили диапазон 0.11-0.14, 0.1 можно записать и забыть. По факту хранятся и обсчитываются последние 16-32 бита диапазона, всё остальное уже записано.
Число записывается следующим образом: внутри полученного полуинтервала 
выбирается полуинтервал 
, где n — наименьшее из возможных, и в выходной файл пишется число 
в виде двоичной дроби — всё, что стоит после «0,».
выбирается полуинтервал , где n — наименьшее из возможных, и в выходной файл пишется число в виде двоичной дроби — всё, что стоит после «0,».Автор, кстати, забыл упомянуть, что на словах этот алгоритм чрезвычайно прост, но когда дело доходит до реализации, всплывает невероятное количество подводных камней. Нам в школе давали в качестве домашнего задания реализовать этот алгоритм на Haskell, и у меня ушло 3 недели, чтобы заставить его вменяемо работать, при том что перед глазами у меня был код на C.
P.S.: на задание реализовать PPMc, являющийся идейным наследником и обобщением арифмокодера, я благополучно забил :)
P.S.: на задание реализовать PPMc, являющийся идейным наследником и обобщением арифмокодера, я благополучно забил :)
Что же за школы у вас такие??!
habrahabr.ru/blogs/study/87800/
Статья, честно говоря, отстойная, поэтому расскажу свою версию, вкратце:
Питерская, частная, но бесплатная школа. Основной упор на математику и, меньше, программирование. Лично я сейчас учусь в 11 классе. На основном курсе математики (матанализ) только что начали рассказывать интегралы. На программировании весь прошлый год изучали алгоритмы сжатия (Шеннон, Хаффман, LZ77/78, LZW, арифметик, PPM, BZ2), с обязательным условием написания их на Haskell. В конце года начали заниматься Java, сейчас продолжаем. Летом, в лагере, были курсы: обязательный «Ряды в банаховых пространствах» и один из трёх на выбор: частичные группоиды, теория Галуа или теория групп. Сейчас ведутся ещё штук 5 (необязательных) спецкурсов с похожими названиями. Как-то так :)
Если интересно, могу попробовать написать свою статью, но ничего не обещаю.
Статья, честно говоря, отстойная, поэтому расскажу свою версию, вкратце:
Питерская, частная, но бесплатная школа. Основной упор на математику и, меньше, программирование. Лично я сейчас учусь в 11 классе. На основном курсе математики (матанализ) только что начали рассказывать интегралы. На программировании весь прошлый год изучали алгоритмы сжатия (Шеннон, Хаффман, LZ77/78, LZW, арифметик, PPM, BZ2), с обязательным условием написания их на Haskell. В конце года начали заниматься Java, сейчас продолжаем. Летом, в лагере, были курсы: обязательный «Ряды в банаховых пространствах» и один из трёх на выбор: частичные группоиды, теория Галуа или теория групп. Сейчас ведутся ещё штук 5 (необязательных) спецкурсов с похожими названиями. Как-то так :)
Если интересно, могу попробовать написать свою статью, но ничего не обещаю.
Почему же у нас в школе только задания типа «вывести четные числа от 1 до 100» на бейсике были? :(
суровые челябинские дети.
Скорость VS размер. Ничего нового, всегда приходилось выбирать из наиболее важного. Скажем, с трудом вы покодируете арифметическим сжатием на каком-нибудь Z80 с приемлемой скоростью (без аппаратного деления целых, про вещественные числа я не упоминаю). Хотя на компах нонешных — это конечно не проблема.
Арифметика быстрее Хаффмана, как ни странно, примерно раза в два. Деление целых ни разу не проблема, оно делается сдвигами. Более того, на старых х86 (8086-80286) процессорах оптимизированное вручную деление сдвигами работало быстрее аппаратной команды. Борландовские компиляторы, например, аппаратным DIV не пользовались.
Более того, на старых х86 (8086-80286) процессорах оптимизированное вручную деление сдвигами работало быстрее аппаратной команды. Борландовские компиляторы, например, аппаратным DIV не пользовались.
Сдвиги на старых процах пользовали только в случаях деления/умножения на степень двойки. Во всех остальных случаях — стандартные DIV и MUL. Борландовские компиляторы так и делали
А нельзя ли пример деления сдвигами скажем X/237?
Теорию категорий тоже в школе брали?
Судя по всему, ваш комментарий относится к ветке выше (Pastafarianist).
Вы удивитесь, но да. Правда, только в качестве необязательного спецкурса, но я лично знаю человека, который отсидел его целиком. И это не я.
Мало кто знает? Это же один из самых известных алгоритмов
Согласен. Если я не ошибаюсь, то первая практическая реализация
арифметического кодирования была описана (аж) в 1987 году:
www.stanford.edu/class/ee398a/handouts/papers/WittenACM87ArithmCoding.pdf
арифметического кодирования была описана (аж) в 1987 году:
www.stanford.edu/class/ee398a/handouts/papers/WittenACM87ArithmCoding.pdf
Алгоритмы это хорошо есть ли что-нибудь в действующим варианте? Например как Rar, 7-zip.
Насколько мне известно, одной из частей алгоритма RAR является арифметическое кодирование, точнее, его обобщение — один из алгоритмов семейства PPM. 7-zip тоже умеет использовать PPM (а именно, PPMd), наряду с другими алгоритмами, типа LZMA.
Не знаю есть ли архиваторы, использующие только арифметическое сжатие, но оно используется для дожатия без потерь на одном из шагов в jpeg-2000 и h264.
Освоил алгоритм Хаффмана очень быстро, даже реализовал адаптивные улучшения для него, а вот арифметическое сжатие мне долго не давалось из-за туговатых статей на 50 страниц. Спасибо за краткое и внятное объяснение. Наконец-то все встало на свои места.
Вроде бы Quantized Indexing дает лучшее сжатие для энтропии засчет меньших накладных расходов. К тому же никто не использует Arithmetic Coding в чистом виде. Как правило народ берёт Range Coder который быстрее, патентно-чист, и жмет чуть хуже за счет округлений. Как пример реализации советую посмотреть RC Дмитрия Шкарина (Shkarin).
Спасибо за статью (+), Хаффмана я как то даже писал на pascal во времена учебы. Но вот арифметическое кодирование я не смог раскусить на моменте реализации. По теории было все понятно. То что описано является основой, но большие вопросы занимает именно реализация, представления чисел с столь длинными хвостами после запятой.
я начинал было делать, но меня хватило лишь на размеры фраз до переполнения float :)
было бы здорово удивить продолжение стать, содержащем в себе ключ к реализации и ключ симбиозу арифметическому кодированию и адаптивного Хаффмана.
я начинал было делать, но меня хватило лишь на размеры фраз до переполнения float :)
было бы здорово удивить продолжение стать, содержащем в себе ключ к реализации и ключ симбиозу арифметическому кодированию и адаптивного Хаффмана.
en.wikipedia.org/wiki/Range_encoding дает хорошее объяснение реализации «почти AC». Хотя, конечно, краткий обзор применений было бы хорошо.
Так адаптивное кодирование делается примерно так же, как адаптивный Хаффман. Только в Хаффмане дерево перестраивается, а тут — таблица-статистика.
Для упрощения работы с дробями можно делать адаптацию не на каждый входной символ, а на каждый 1/2/4/8-й и т. д. (степень двойки) символ. Тогда фактически статистические веса, т.е. длины интервалов, сопоставляемых отдельным символам, будут конечными двоичными дробями, и можно работать в арифметике с фиксированной запятой — правда, ценой некоторой потери эффективности.
Для упрощения работы с дробями можно делать адаптацию не на каждый входной символ, а на каждый 1/2/4/8-й и т. д. (степень двойки) символ. Тогда фактически статистические веса, т.е. длины интервалов, сопоставляемых отдельным символам, будут конечными двоичными дробями, и можно работать в арифметике с фиксированной запятой — правда, ценой некоторой потери эффективности.
ну зато с fixed_point можно аппаратное решение реализовать в приемлемых ресурсах. LZRW вон сделали…
Из-за грёбанных патентов в jpeg до сих пор не применяется арифметическое сжатие.
А есть ведь ещё разработки типа типа PackJPG (и другие), обеспечивающие на 30% лучшее сжатие чем обычный jpeg при абсолютном байт-в-байт сходстве распакованной картинки, но тоже проблема — никаких плагинов для браузеров/просмотрщиков/редакторов.
А есть ведь ещё разработки типа типа PackJPG (и другие), обеспечивающие на 30% лучшее сжатие чем обычный jpeg при абсолютном байт-в-байт сходстве распакованной картинки, но тоже проблема — никаких плагинов для браузеров/просмотрщиков/редакторов.
Спасибо за статью. Есть книжка «Методы сжатия данных», к сожалению не помню авторов, там их целая могучая кучка выпускников МГУ. Если не ошибаюсь, 3е издание должно быть уже. Дак вот там для тех, кому интересно, расписаны и показаны огромное количество методов преобразований для сжатия, так и самого сжатия. Очень рекомендую к прочтению. Единственное — написана конечно тяжело. Но там и материал такой не для домохозяек…
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Арифметическое кодирование