Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 18
я могу всё это почитать в приведённой литературе?? не?
Было бы не плохо, если бы Вы в следующей статье (если таковая планируется) рассказали о более сложных алгоритмах, например о Deflate, с примерами работы. Например на примере Gzip. Тема обширная и очень интересная.
Спасибо за статью.
Спасибо за статью.
Архивирование также может давать выигрыш в скорости, т.к. жесткие диски являются медленными относительно других узлов компьютера.
Реквестирую код арифмокодера на чём-нибудь высокоуровневом. Я в своё время писал на Haskell; было бы интересно увидеть на чём-нибудь типа Python.
На асме было бы еще интереснее. В арифметоде надо числа произвольной разрядности, в языках высокого уровня с этим или сложно, или долго, или никак.
Когда вы кодируете арифметическим методом, рано или поздно старшие биты стабилизируются. Например, если у вас на каком-то этапе интервал стал короче 1/16, то первые четыре бита нашего числа (представляющего закодированную последовательность) уже никогда не изменятся. Их можно не хранить в памяти — сбросить в выходной поток и забыть. Если был очень редкий символ — скажем, с частотой менее 1/1024, в выходной поток можно сбросить сразу 10 бит.
При сбрасывании битов в выходной поток освобождается место в регистрах, хранящих текущее состояние кодера — левую границу интервала и его длину.
А ограниченная разрядность этих регистров приводит к некоторому уменьшению эффективности сжатия, а не к каким-то искажениям.
Так что можно обойтись без чисел произвольной разрядности.
При сбрасывании битов в выходной поток освобождается место в регистрах, хранящих текущее состояние кодера — левую границу интервала и его длину.
А ограниченная разрядность этих регистров приводит к некоторому уменьшению эффективности сжатия, а не к каким-то искажениям.
Так что можно обойтись без чисел произвольной разрядности.
> Если вероятность появления элемента si равна p(si), то наиболее выгодно будет представить этот элемент — log2p(si) битами
Это если у нас двоичная система счистления?
Это если у нас двоичная система счистления?
Сжатие информации без потерь. Часть перваяНазвание статьи и её размер как бы намекают, что без потерь сильно сжать не получится ;-)
А можно было бы строить префиксное множество символов вне зависимости от частоты появления кодируемых символов в входном потоке, а потом меньшим по количеству бит префиксам сопоставлять входные символы с большей частотой появления? В примере, в процессе построения префиксного множества фигурируют вероятности, хотя мне видится построение множества префиксов, зависящем только от количества символов входного алфавита. Т.е. тут хочется акцентировать внимание именно на алгоритм построения множества префиксов, а сопоставление элементам этого множества символов входного потока всегда происходит по одному принципу меньшим по длине кодам большие вероятности. Было бы интересно узнать какие еще множества префиксов и как можно строить?
Подобный подход используется в deflate в одном из быстрых-но-слабых режимов кодирования: там есть некая стандартная таблица префиксных кодов. Частоты символов, конечно, анализируются заранее, но вместо построения оптимальных кодов Хаффмана в этом режиме используется известная таблица префиксных кодов, не оптимальная. Достигается более слабое, но более быстрое сжатие.
Другая версия подобного подхода используется для сжатия остаточного сигнала в кодере FLAC. Там звук аппроксимируется полиномами, и вычисляется остаточный сигнал — отличие того, что было, и того, что получилось в результате аппроксимации. Аппроксимация построена так, что этот остаточный сигнал имеет гауссово распределение. Для последовательностей с таким распределением уже построены оптимальные префиксные коды — они называются кодами Райса. Таблица не строится каждый раз заново, используется уже известная.
Другая версия подобного подхода используется для сжатия остаточного сигнала в кодере FLAC. Там звук аппроксимируется полиномами, и вычисляется остаточный сигнал — отличие того, что было, и того, что получилось в результате аппроксимации. Аппроксимация построена так, что этот остаточный сигнал имеет гауссово распределение. Для последовательностей с таким распределением уже построены оптимальные префиксные коды — они называются кодами Райса. Таблица не строится каждый раз заново, используется уже известная.
Можно. Более того, если вы кодируете текст на естественном языке, то можно вообще не производить никакого анализа входного потока, так как частотные характеристики текстов на разных языках легко найти в интернете; поэтому можно заранее составить таблицу кодов для определенного количества символов (скажем, 33 буквы, еще 33 заглавные буквы, 10 цифр и основные знаки препинания).
Немного вопрос поставлю иначе, в случае равно вероятностного распределения появления символов алфавита во входном потоке (т.е. вероятность появления любого символа алфавита в потоке приблизительно одинакова), ключевым вопросом станет нахождение оптимального множества префиксов для заданного количества символов в алфавите. А целевая функция это суммарная длина всех префиксов. И являются ли коды Райса как раз примером одного из таких множеств?
Насколько я понимаю, нет, не являются (пусть кто-нибудь поправит меня, если я ошибаюсь). Коды Райса являются частным случаем кодов Голомба. Последние, в свою очередь, являются оптимальными для алфавитов с геометрическим распределением. Эти коды отлично подходят для кодирования аналоговых сигналов по следующим причинам (вообще это тема для отдельной статьи, но постараюсь объяснить вкратце).
При кодировании, например, звука, мы можем использовать так называемое Predictive Coding (адекватного русскоязычного аналога не нашел, но это можно перевести как «предиктивное», или «предсказывающее», кодирование). Суть в том, что мы подбираем функцию, которая более-менее точно аппроксимирует наш входной поток. Естественно, она делает это с погрешностью.
В то же время, очевидно, что (если мы подбираем аппроксимирующую функцию достаточно точно), для большей части данных ошибка аппроксимации будет незначительна. Иначе говоря, величина ошибки предсказания подчиняется Гауссовому, или, возможно, геометрическому распределению (большие ошибки встречаются реже, чем незначительные).
Соответственно, мы можем закодировать величину этой ошибки кодами Голомба, которые являются оптимальными для таких данных. Вообще, использование того или иного вида кодов сильно зависит от входных данных, поэтому если вы хотите сжать что-то достаточно эффективно, то нужно ответственно подойти к выбору метода кодирования для вашего конкретного типа данных.
При кодировании, например, звука, мы можем использовать так называемое Predictive Coding (адекватного русскоязычного аналога не нашел, но это можно перевести как «предиктивное», или «предсказывающее», кодирование). Суть в том, что мы подбираем функцию, которая более-менее точно аппроксимирует наш входной поток. Естественно, она делает это с погрешностью.
В то же время, очевидно, что (если мы подбираем аппроксимирующую функцию достаточно точно), для большей части данных ошибка аппроксимации будет незначительна. Иначе говоря, величина ошибки предсказания подчиняется Гауссовому, или, возможно, геометрическому распределению (большие ошибки встречаются реже, чем незначительные).
Соответственно, мы можем закодировать величину этой ошибки кодами Голомба, которые являются оптимальными для таких данных. Вообще, использование того или иного вида кодов сильно зависит от входных данных, поэтому если вы хотите сжать что-то достаточно эффективно, то нужно ответственно подойти к выбору метода кодирования для вашего конкретного типа данных.
Спасибо, доступно и приятно изложено. Очень хорошо, что начали с азов — не пришлось морщить лоб на втором абзаце :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сжатие информации без потерь. Часть первая