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


Содержание

АЛГОРИТМЫ СЖАТИЯ

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

Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов. Арифметическое кодирование является оптимальным, достигая теоретической границы степени сжатия. Арифметическое кодирование – блочное и выходной код является уникальным для каждого из возможных входных сообщений; его нельзя разбить на коды отдельных символов, в отличие от кодов Хаффмана, которые являются неблочными, т.е. каждой букве входного алфавита ставится в соответствие определенный выходной код.

Текст, сжатый арифметическим кодером, рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия можно представить как последовательность двоичных цифр из записи этой дроби. Каждый символ исходного текста представляется отрезком на числовой оси с длиной, равной вероятности его появления и началом, совпадающим с концом отрезка символа, предшествующего ему в алфавите. Сумма всех отрезков, очевидно должна равняться единице. Если рассматривать на каждом шаге текущий интервал как целое, то каждый вновь поступивший входной символ “вырезает” из него подинтервал пропорционально своей длине и положению.

Построение интервала для сообщения «АБВГ. » :

Поясним работу метода на примере:

Пусть алфавит состоит из двух символов: “a” и “b” с вероятностями соответственно 3/4 и 1/4.

Рассмотрим (открытый справа) интервал [0, 1). Разобьем его на части, длина которых пропорциональна вероятностям символов. В нашем случае это [0, 3/4) и [3/4, 1). Суть алгоритма в следующем: каждому слову во входном алфавите соответствует некоторый подинтервал из [0, 1). Пустому слову соответствует весь интервал [0, 1). После получения каждого очередного символа арифметический кодер уменьшает интервал, выбирая ту его часть, которая соответствует вновь поступившему символу. Кодом сообщения является интервал, выделенный после обработки всех его символов, точнее, число минимальной длины, входящее в этот интервал. Длина полученного интервала пропорциональна вероятности появления кодируемого текста.

Выполним алгоритм для цепочки “aaba”:

Шаг Просмотренная цепочка Интервал
“” [0, 1) = [0, 1)
1 “a” [0, 3/4) = [0, 0.11)
2 “aa” [0, 9/16) = [0, 0.1001)
3 “aab” [27/64, 36/64) = [0.011011, 0.100100)
4 “aaba” [108/256, 135/256) = [0.01101100, 0.10000111)

На первом шаге мы берем первые 3/4 интервала, соответствующие символу «а», затем оставляем от него еще только 3/4. После третьего шага от предыдущего интервала останется его правая четверть в соответствии с положением и вероятностью символа «b». И, наконец, на четвертом шаге мы оставляем лишь первые 3/4 от результата. Это и есть интервал, которому принадлежит исходное сообщение.

В качестве кода можно взять любое число из диапазона, полученного на шаге 4. Возникает вопрос: «А где же здесь сжатие? Исходный текст можно было закодировать четырьмя битами, а мы получили восьмибитный интервал». Дело в том, что в качестве кода мы можем выбрать, например, самый короткий код из интервала, равный 0.1 и получить четырехкратное сокращение объема текста. Для сравнения, код Хаффмана не смог бы сжать подобное сообщение, однако, на практике выигрыш обычно невелик и предпочтение отдается более простому и быстрому алгоритму из предыдущего раздела.

Кодирование информации, как основа уменьшения объема информационного массива

экономические науки

  • Воробьева Татьяна Юрьевна , студент
  • Башкирский государственный аграрный университет

  • Похожие материалы

    Сжатие информации — проблема, имеющая достаточно давнюю историю, гораздо более давнюю, нежели история развития вычислительной техники, которая (история) обычно шла параллельно с историей развития проблемы кодирования и шифровки информации.

    Все алгоритмы сжатия оперируют входным потоком информации, минимальной единицей которой является бит, а максимальной — несколько бит, байт или несколько байт.

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

    Кодировщик переделывает символ на входе в код на выходе, используя вероятности символов, которые поставляет ему моделировщик. В данной статье речь пойдет о двух самых распространенных и известных методах кодирования информации во время сжатия: кодирование Хаффмана (Huffman) и арифметическое кодирование и его разновидности.

    Кодирование Хаффмана

    Этот метод кодирования появился очень давно и получил широкое распространение из-за простоты реализации и высокой скорости. Метод не требует огромных вычислительных мощностей в отличие от арифметического кодирования, производящего целочисленные умножения и деления. На заре компьютерной эры метод оказался простым в применении.

    Для работы алгоритма необходимо иметь таблицу значений вероятностей различных символов, которые могут встретиться в данный момент кодирования (в данном месте обрабатываемого текста, где кодер в данный момент будет кодировать очередной символ).

    На основе этой таблицы строится бинарное дерево Хаффмана следующим образом:

    1. Отсортировать символы по возрастанию вероятности их появления
    2. Первые два символа в получившемся ряде объединить в один, сопоставив первому символу ноль, второму символу — единицу. Вероятности этих двух символов сложить.
    3. Если в ряде остался один символ, то закончить, иначе перейти к пункту 1

    Пример построения дерева

    Предположим, что мы имеем алфавит из 8 символов. Подпрограмма, осуществляющая моделирование задает нам следующие возможные вероятности этих символов:
    A — 7%, B — 13%, C — 2%, D — 28%, E — 14%, F — 22%, G — 10%, H — 4%.

    Сортируем символы по возрастанию вероятности:
    C — 2%, H — 4%, A — 7%, G — 10%, B — 13%, E — 14%, F — 22%, D — 28%.

    Левые два объединяем в один:
    CH — 6%, A — 7%, G — 10%, B — 13%, E — 14%, F — 22%, D — 28%.

    В данном случае сортировка не требуется. Заметим также, что для символа C теперь появился код 0, для H — 1. Эти символы находятся в самом низу кроны дерева Хаффмана (дерево растет вниз, т.е. крона его внизу), и к ним впоследствии будут добавлены новые узлы дерева, которые будут стоять выше. Пока же дерево выглядит следующим образом:

    Снова объединяем два левых символа в один:
    CHA — 13%, G — 10%, B — 13%, E — 14%, F — 22%, D — 28%.

    После сортировки получим:
    G — 10%, CHA — 13%, B — 13%, E — 14%, F — 22%, D — 28%.


    Дерево выглядит следующим образом:

    Когда мы обработаем все символы дерево примет вид:

    Теперь, чтобы закодировать любой символ нужно пройти от корня дерева до символа запоминая биты, определяющие направление движения. Коды символов получились следующие:
    A — 1111, B — 000, C — 11100, D — 01, E — 001, F — 10, G — 110, H — 11101.

    Таким образом, самые вероятные символы: D и F имеют наименьшую длину кода: 2 бита, а менее вероятные символы имеют коды большей длины. Все коды уникально идентифицируют символ, т.е. из кода можно получить исходный текст в полном объеме.

    Недостаток метода Хаффмана

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

    Представим себе, что символ встречается в тексте с 99% вероятностью. Метод Хаффмана присвоит этому символу код 1, длиной в 1 бит. Имея файл размером 1 Мбайт, сжат он будет до 1 бит/байт, т.е. до 128 Кбайт, хотя сжать его можно гораздо эффективней: буквально до нескольких сот байт! Арифметическое кодирование лишено этого недостатка [1].

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

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

    Таблица накопительных счетчиков устроена так, что частота появления N + 1 — го символа алфавита равна разности его счетчика и счетчика N — го символа. Другими словами, если мы имеем алфавит из 8 символов с частотами 7, 9, 2, 16, 22, 14, 11 и 55 соответственно, то таблица накопительных счетчиков будет следующей: 7, 16, 18, 34, 56, 70, 81, 136.

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

    Принцип кодирования

    Для кодирования символов необходимо разбить полуинтервал [0; 1] на части. Каждая часть символизирует частоту повторения символа таким образом, что отношение длины интервала символа к длине всего интервала численно равно величине вероятности. Для примера возьмем алфавит из четырех символов с частотами: 23, 16, 82 и 5. Разделим интервал в соответствии с вероятностями этих символов на четыре подинтервала: [0, 0.1825], [0.1825, 0.3095], [0.3095, 0.9604] и [0.9604, 1]. Ширина третьего интервала самая большая т.к. третий символ наиболее вероятен.

    Для кодирования задаются два числа — левый и правый края текущей области в интервале, которые сначала имеют значения 0 и 1 соответственно. При кодировании текущая область интервала сужается с каждым новым закодированным символом следующим образом:
    Li = Li – 1 + Rng i – 1 * li
    Hi = Hi — 1 — Rngi — 1 * (1 — hi)

    Здесь L и H — границы текущей области интервала на соответствующем шаге, Rng — ширина текущей области на том же шаге, l и h — соответственно нижняя и верхняя границы интервала кодируемого символа.

    Когда кодирование всех символов сообщения будет закончено числа L и H нужно записать в выходной поток, они и будут закодированным сообщением. Замечу, что оба числа записывать необязательно: для декодирования достаточно записать число, принадлежащее этому интервалу. Запись сообщения производится тем количеством бит, которое необходимо для представления числа с получившейся точностью, т.о. чем больше сообщение, тем с большей точностью необходимо записывать эти числа, увеличивая длину выходного сообщения.

    Реализация кодирования

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

    Также в компьютерной реализации арифметического кодирования применяют масштабирование текущего интервала, путем его расширения, если длина интервала становится меньше какого-либо значения. Расширение основано на наблюдении, что начиная с какого-то закодированного символа ширина интервала изменяется незначительно и уже не может выйти за определенные рамки.


    Например, если обе границы текущего интервала (верхняя и нижняя) находятся в меньшей [0, 0.5] половине единичного интервала, то они уже никак не смогут попасть в верхнюю, так как интервал может сужаться только внутрь. В данном случае можно записать в выходной поток первый, уже известный бит числа, которое должно быть сформировано на выходе и расширить интервал, растянув нижнюю половину интервала в два раза. Далее с растянутым интервалом работают как с начальным [2].

    Range — кодирование

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

    Быстрое кодирование

    Быстрое кодирование обладает недостатком, присущим алгоритму Хаффмана, но позволяет не производить сортировку таблицы символов по частоте их встречаемости. Быстрота достигнута путем замены умножения битовыми сдвигами, т.е. в данном случае используется только умножение и деление на степень двойки.

    Ширина интервала в данном случае округляется в большую сторону до ближайшей степени двойки, из-за чего становится возможным значительно ускорить алгоритм, но плата в данном случае — снижение степени сжатия из-за потери точности, в некоторых случаях очень существенной. Этот алгоритм следует рассматривать как альтернативу алгоритму Хаффмана.

    Метод Хаффмана широко используется, но постепенно вытесняется арифметическим сжатием. Свою роль в этом сыграло то, что закончились сроки действия патентов, ограничивающих использование арифметического сжатия. Кроме того, алгоритм Хаффмана не является оптимальным. Он приближает относительные частоты появления символа в потоке частотами, представляющими собой отрицательные степени двойки, в то время как арифметическое сжатие дает лучшую степень приближения частоты.

    Список литературы

    1. Винокуров И.В. Классификация и кодирование информации. [Электронный ресурс].URL: https://www.google.ru (дата обращения 25.05.16).
    2. Елинова Г.Г. Информационные технологии в профессиональной деятельности: краткий курс лекций. Оренбург ГОУ ОГУ, 2004. -39 с.
    3. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ XXI ВЕКА Абхалимова Р.С., Шарафутдинов А.Г. Экономика и социум. 2014. № 2-5 (11). С. 234-236.
    4. ОСОБЕННОСТИ ФУНКЦИОНИРОВАНИЯ ЛИЧНЫХ ПОДСОБНЫХ ХОЗЯЙСТВ В РЕГИОНАЛЬНЫХ АГРАРНЫХ КЛАСТЕРАХ
    5. Шарафутдинов А.Г.В сборнике: Актуальные вопросы экономико-статистического исследования и информационных технологий сборник научных статей: посвящается 40-летию создания кафедры «Статистики и информационных систем в экономике». МСХ РФ, Башкирский государственный аграрный университет. Уфа, 2011. С. 129-131.

    Электронное периодическое издание зарегистрировано в Федеральной службе по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор), свидетельство о регистрации СМИ — ЭЛ № ФС77-41429 от 23.07.2010 г.

    Соучредители СМИ: Долганов А.А., Майоров Е.В.

    Программа для арифметического кодирования.


    Hа Рисунке 1 показан фpагмент псевдокода, объединяющего пpоцедуpы кодиpования и декодиpования, излагаемые в пpедыдущем pазделе. Символы в нем нумеpуются как 1,2,3. Частотный интеpвал для i-го символа задается от cum_freq[i] до cum_freq[i-1]. Пpи убывании i cum_freq[i] возpастает так, что cum_freq[0] = 1. (Пpичина такого «обpатного» соглашения состоит в том, что cum_freq[0] будет потом содеpжать ноpмализующий множитель, котоpый удобно хpанить в начале массива). Текущий pабочий интеpвал задается в [low; high] и будет в самом начале pавен [0; 1) и для кодиpовщика, и для pаскодиpовщика.

    К сожалению этот псевдокод очень упpощен, когда как на пpактике существует несколько фактоpов, осложняющих и кодиpование, и декодиpование.

    Реализация модели.

    Сама pеализация обсуждается в следующем pазделе, а здесь мы коснемся только интеpфейса с моделью (стpоки 20-38). В языке Си байт пpедставляет собой целое число от 0 до 255 (тип char). Здесь же мы пpедставляем байт как целое число от 1 до 257 включительно (тип index), где EOF тpактуется как 257-ой символ. Пpедпочтительно отсоpтиpовать модель в поpядке убывания частот для минимизации количества выполнения цикла декодиpования (стpока 189). Пеpевод из типа char в index, и наобоpот, pеализуется с помощью двух таблиц — index_to_char[] и char_to_index[]. В одной из наших моделей эти таблицы фоpмиpуют index пpостым добавлением 1 к char, но в дpугой выполняется более сложное пеpекодиpование, пpисваивающее часто используемым символам маленькие индексы.

    Веpоятности пpедставляются в модели как целочисленные счетчики частот, а накапливаемые частоты хpанятся в массиве cum_freq[]. Как и в пpедыдущем случае, этот массив — «обpатный», и счетчик общей частоты, пpименяемый для ноpмализации всех частот, pазмещается в cum_freq[0]. Hакапливаемые частоты не должны пpевышать установленный в Max_frequency максимум, а pеализация модели должна пpедотвpащать пеpеполнение соответствующим масштабиpованием. Hеобходимо также хотя бы на 1 обеспечить pазличие между двумя соседними значениями cum_freq[], иначе pассматpиваемый символ не сможет быть пеpедан.

    Пpиpащаемая пеpедача и получение.

    В отличие от псеводокода на pисунке 1, пpогpамма 1 пpедставляет low и high целыми числами. Для них, и для дpугих полезных констант, опpеделен специальный тип данных code_value. Это — Top_value, опpеделяющий максимально возможный code_value, First_qtr и Third_qtr, пpедставляющие части интеpвала (стpоки 6-16). В псевдокоде текущий интеpвал пpедставлен чеpез [low; high), а в пpогpамме 1 это [low; high] — интеpвал, включающий в себя значение high. Hа самом деле более пpавильно, хотя и более непонятно, утвеpждать, что в пpогpамме 1 пpедставляемый интеpвал есть [low; high + 0.1111. ) по той пpичине, что пpи масштабитовании гpаниц для увеличения точности, нули смещаются к младшим битам low, а единицы смещаются в high. Хотя можно писать пpогpамму на основе pазных договоpенностей, данная имеет некотоpые пpеимущества в упpощении кода пpогpаммы.

    По меpе сужения кодового интеpвала, стаpшие биты low и high становятся одинаковыми, и поэтому могут быть пеpеданы немедленно, т.к. на них будущие сужения интеpвала все pавно уже не будут влиять. Поскольку мы знаем, что low for (;;) < if (high = Half) < output_bit(1); low = 2 * (low - Half); high = 2 * (high - Half) + 1; >else break; >

    гаpантиpующую, что после ее завеpшения будет спpеведливо неpавенство: low Пpиpащаемый ввод исходных данных выполняется с помощью числа, названного value. В пpогpамме 1, обpаботанные биты пеpемещаются в веpхнюю часть, а заново получаемые поступают в нижнюю. Вначале, start_decoding() (стpоки 168-176) заполняет value полученными битами. После опpеделения следующего входного символа пpоцедуpой decode_symbol(), пpоисходит вынос ненужных, одинаковых в low и в high, битов стаpшего поpядка сдвигом value на это количество pазpядов (выведенные биты восполняются введением новый с нижнего конца). Назад | Содержание | Дальше

    Теория информации

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

    Алгоритмы Шеннона-Фено и Хаффмена в лучшем случае не могут кодировать каждый символ сообщения менее чем 1 битом информации. Предположим, в сообщении, состоящем из 0 и 1, единицы встречаются 10 раз чаще. Энтропия такого сообщения HX0,469 (бит/сим). В таком случае желательно иметь схему кодирования, позволяющую кодировать символы сообщения менее чем 1 битом информации. Одним из лучших алгоритмов такого кодирования информации является арифметическое кодирование.

    По исходному распределению вероятностей д.с.в. строится таблица, состоящая из пересекающихся в граничных точках отрезков для каждого из значений д.с.в. Объединение этих отрезков должно образовывать интервал [0;1], а их длины пропорциональны вероятностям кодируемых значений.

    Алгоритм кодирования заключается в построении отрезка, однозначно определяющего конкретную последовательность символов сообщения. По мере поступления входных символов отрезок сообщения сужается. Отрезки строятся следующим образом. Если имеется отрезок сообщения длиной n-1, то для построения отрезка сообщения длиной n символов, предыдущий интервал разбивается на столько частей, сколько значений включает алфавит источника. Начало и конец каждого нового интервала сообщения определяется путем прибавления к началу предыдущего интервала произведения его ширины на значения границ отрезка, соответствующего текущему новому символу (по исходной таблице вероятностей символов и назначенных им интервалов). Затем из полученных отрезков выбирается тот, который соответствует конкретной последовательности символов сообщения длиной n.

    Для построенного отрезка сообщения находится число, принадлежащее этому отрезку, обычно, это целое число, делённому на минимально возможную степень 2. Это вещественное число и будет кодом для рассматриваемой последовательности. Все возможные коды – числа строго больше 0 и меньше 1, поэтому лидирующий 0 и десятичная точка не учитываются.

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

    Принципиальное отличие арифметического кодирования от методов сжатия Шеннона-Фено и Хаффмена в его непрерывности, т.е. в отсутствии необходимости блокирования сообщения. Эффективность арифметического кодирования растёт с ростом длины сжимаемого сообщения, однако требует больших вычислительных ресурсов.

    Поясним идею арифметического кодирования на конкретных примерах.

    Пример 1 Закодируем текстовую строку «МАТЕМАТИКА» по алгоритму арифметического кодирования.


    Определим частоту каждого из символов в сообщении и назначим каждому из них отрезок, длина которого пропорциональна вероятности соответствующего символа (табл. 2.7).

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

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

    Алгоритм кодирования Хаффмена, в лучшем случае, не может передавать на каждый символ сообщения менее одного бита информации. Предположим, известно, что в сообщении, состоящем из нулей и единиц, единицы встречаются в 10 раз чаще нулей. При кодировании методом Хаффмена и на 0 и на 1 придется тратить не менее одного бита. Но энтропия д.с.в., генерирующей такие сообщения 0.469 бит /сим. Неблочный метод Хаффмена дает для минимального среднего количества бит на один символ сообщения значение 1 бит . Хотелось бы иметь такую схему кодирования, которая позволяла бы кодировать некоторые символы менее чем одним битом. Одной из лучших среди таких схем является арифметическое кодирование , разработанное в 70-х годах XX века.

    По исходному распределению вероятностей для выбранной для кодирования д.с.в. строится таблица , состоящая из пересекающихся только в граничных точках отрезков для каждого из значений этой д.с.в.; объединение этих отрезков должно образовывать отрезок , а их длины должны быть пропорциональны вероятностям соответствующих значений д.с.в. Алгоритм кодирования заключается в построении отрезка, однозначно определяющего данную последовательность значений д.с.в. Затем для построенного отрезка находится число, принадлежащее его внутренней части и равное целому числу, деленному на минимально возможную положительную целую степень двойки. Это число и будет кодом для рассматриваемой последовательности. Все возможные конкретные коды — это числа строго большие нуля и строго меньшие одного, поэтому можно отбрасывать лидирующий ноль и десятичную точку, но нужен еще один специальный код-маркер, сигнализирующий о конце сообщения. Отрезки строятся так. Если имеется отрезок для сообщения длины , то для построения отрезка для сообщения длины , разбиваем его на столько же частей, сколько значений имеет рассматриваемая д.с.в. Это разбиение делается совершенно также как и самое первое (с сохранением порядка). Затем выбирается из полученных отрезков тот, который соответствует заданной конкретной последовательности длины .

    Принципиальное отличие этого кодирования от рассмотренных ранее методов в его непрерывности, т.е. в ненужности блокирования. Код здесь строится не для отдельных значений д.с.в. или их групп фиксированного размера, а для всего предшествующего сообщения в целом. Эффективность арифметического кодирования растет с ростом длины сжимаемого сообщения (для кодирования Хаффмена или Шеннона-Фэно этого не происходит). Хотя арифметическое кодирование дает обычно лучшее сжатие, чем кодирование Хаффмена, оно пока используется на практике сравнительно редко, т.к. оно появилось гораздо позже и требует больших вычислительных ресурсов.

    При сжатии заданных данных, например, из файла все рассмотренные методы требуют двух проходов. Первый для сбора частот символов, используемых как приближенные значения вероятностей символов, и второй для собственно сжатия.

    Пример арифметического кодирования. Пусть д.с.в. может принимать только два значения 0 и 1 с вероятностями 2/3 и 1/3 соответственно. Сопоставим значению 0 отрезок , а 1 — . Тогда для д.с.в. ,

    Среднее количество бит на единицу сообщения для арифметического кодирования получилось меньше, чем энтропия . Это связано с тем, что в рассмотренной простейшей схеме кодирования, не описан код-маркер конца сообщения, введение которого неминуемо сделает это среднее количество бит большим энтропии.

    Получение исходного сообщения из его арифметического кода происходит по следующему алгоритму.

    Шаг 1. В таблице для кодирования значений д.с.в. определяется интервал , содержащий текущий код, — по этому интервалу однозначно определяется один символ исходного сообщения. Если этот символ — это маркер конца сообщения, то конец.

    Шаг 2. Из текущего кода вычитается нижняя граница содержащего его интервала, полученная разность делится на длину этого же интервала. Полученное число считается новым текущим значением кода. Переход к шагу 1.

    Рассмотрим, например, распаковку сообщения 111. Этому сообщению соответствует число , что означает, что первый знак декодируемого сообщения — это 1. Далее от 7/8 вычитается 2/3 и результат делится на 1/3, что дает , что означает, что следующий знак — 0. Теперь, вычислив , получим следующий знак — 1, т.е. все исходное сообщение 101 декодировано. Однако, из-за того, что условие остановки не определенно, алгоритм декодирования здесь не остановится и получит «следующий символ» 1 и т.д.

    Упражнение 20 Вычислить среднее количество бит на единицу сжатого сообщения о значении каждой из д.с.в., из заданных следующими распределениями вероятностей, при сжатии методами Шеннона-Фэно, Хаффмена и арифметическим. Арифметический код здесь и в следующих упражнениях составлять, располагая значения д.с.в. в заданном порядке слева-направо вдоль отрезка от 0 до 1.

    Упражнение 21 Вычислить длины кодов Хаффмена и арифметического для сообщения AAB, полученного от д.с.в. со следующим распределением вероятностей , .

    Упражнение 22 Декодировать арифметический код 011 для последовательности значений д.с.в. из предыдущего упражнения. Остановиться, после декодирования третьего символа.

    Упражнение 23 Составить арифметический код для сообщения BAABC , полученного от д.с.в. со следующим распределением вероятностей , , . Каков будет арифметический код для этого же сообщения, если распределена по закону , , ?

    Упражнение 24 д.с.в. может принимать три различных значения. При построении блочного кода с длиной блока 4 для необходимо будет рассмотреть д.с.в. — выборку четырех значений . Сколько различных значений может иметь ? Если считать сложность построения кода пропорциональной количеству различных значений кодируемой д.с.в., то во сколько раз сложнее строить блочный код для по сравнению с неблочным?

    Упражнение 25 Составить коды Хаффмена, блочный Хаффмена (для блоков длины 2 и 3) и арифметический для сообщения ABAAAB , вычислить их длины. Приблизительный закон распределения вероятностей д.с.в., сгенерировавшей сообщение, определить анализом сообщения.

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

    Арифметическое ирование — один из алгоритмов энтропийного сжатия.

    В отличие от алгоритма Хаффмана, не имеет жесткого постоянного соответствия входных символов группам бит выходного потока. Это даёт алгоритму большую гибкость в представлении дробных частот встречаемости символов.

    Как правило, превосходит алгоритм Хаффмана по эффективности сжатия, позволяет сжимать данные с энтропией, меньшей 1 бита на ируемый символ, но некоторые версии имеют патентные ограничения от компании IBM. [1]

    Содержание

    Характеристики [ | ]

    Обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки ирования Шеннона. На каждый символ требуется почти H <\displaystyle H>бит, где H <\displaystyle H>— информационная энтропия источника.

    В отличие от алгоритма Хаффмана, метод арифметического ирования показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей ируемых символов. Однако в случае равновероятного распределения символов, например, для строки бит 010101…0101 длины s метод арифметического ирования приближается к префиксному у Хаффмана и даже может занимать на один бит больше. [2]

    Принцип действия [ | ]

    Пусть имеется некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок от 0 до 1.

    Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок будет соответствовать одному символу.

    Теперь возьмём символ из потока и найдём для него отрезок среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического ирования использованных символов потока.

    Пример работы метода арифметического ирования [ | ]

    Вероятностная модель [ | ]

    Используя метод арифметического ирования, можно достичь почти оптимального представления для заданного набора символов и их вероятностей (согласно теории энтропийного ирования источника Шеннона оптимальное представление будет стремиться к числу −log2P бит на каждый символ, вероятность которого P). Алгоритмы сжатия данных, использующие в своей работе метод арифметического ирования, перед непосредственным ированием формируют модель входных данных на основании количественных или статистических характеристик, а также, найденных в ируемой последовательности повторений или паттернов — любой дополнительной информации, позволяющей уточнить вероятность появления символа P в процессе ирования. Очевидно, что чем точнее определена или предсказана вероятность символа, тем выше эффективность сжатия.

    Рассмотрим простейший случай статической модели для ирования информации, поступающей с системы обработки сигнала. Типы сигналов и соответствующие им вероятности распределены следующим образом:

    • 60 % вероятность нейтрального значения сигнала или NEUTRAL.
    • 20 % вероятность положительного значения сигнала или POSITIVE.
    • 10 % вероятность отрицательного значения сигнала или NEGATIVE.
    • 10 % вероятность признака конца ируемой последовательности или END-OF-DATA.

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

    Следует также отметить, что в качестве алфавита вероятностной модели метода можно рассматривать любой набор символов, исходя из особенностей решаемой задачи. Более эвристические подходы, использующие основную схему метода арифметического ирования, применяют динамические или адаптивные модели. Идея данных методов заключается в уточнении вероятности ируемого символа за счёт учёта вероятности предшествующего или будущего контекста (то есть, вероятность появления ируемого символа после определённого k-го числа символов слева или справа, где k — это порядок контекста).

    ирование сообщения [ | ]

    Возьмём для примера следующую последовательность:

    NEUTRAL POSITIVE NEGATIVE END-OF-DATA

    Сначала разобьём отрезок от 0 до 1 согласно частотам сигналов. Разбивать отрезок будем в порядке, указанном выше: NEUTRAL — от 0 до 0,6; POSITIVE — от 0,6 до 0,8; NEGATIVE — от 0,8 до 0,9; END-OF-DATA — от 0,9 до 1.

    Теперь начнём ировать с первого символа. Первому символу — NEUTRAL соответствует отрезок от 0 до 0,6. Разобьём этот отрезок аналогично отрезку от 0 до 1.

    Заируем второй символ — NEGATIVE. На отрезке от 0 до 0,6 ему соответствует отрезок от 0,48 до 0,54. Разобьём этот отрезок аналогично отрезку от 0 до 1.

    Заируем третий символ — END-OF-DATA. На отрезке от 0,48 до 0,54 ему соответствует отрезок от 0,534 до 0,54.

    Так как это был последний символ, то ирование завершено. Заированное сообщение — отрезок от 0,534 до 0,54 или любое число из него, например, 0,538.

    Деирование сообщения [ | ]

    Предположим, что нам необходимо расировать сообщение методом арифметического ирования согласно описанной выше модели. Сообщение в заированном виде представлено дробным значением 0,538 (для простоты используется десятичное представление дроби, вместо двоичного основания). Предполагается, что заированное сообщение содержит ровно столько знаков в рассматриваемом числе, сколько необходимо для однозначного восстановления первоначальных данных.

    Начальное состояние процесса деирования совпадает с процессом ирования и рассматривается интервал [0,1). На основании известной вероятностной модели дробное значение 0,538 попадает в интервал [0, 0,6). Это позволяет определить первый символ, который был выбран ировщиком, поэтому его значение выводится как первый символ деированного сообщения.

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

    Арифметическое кодирование — один из алгоритмов энтропийного сжатия.

    В отличие от алгоритма Хаффмана, не имеет жесткого постоянного соответствия входных символов группам бит выходного потока. Это даёт алгоритму большую гибкость в представлении дробных частот встречаемости символов.

    Как правило, превосходит алгоритм Хаффмана по эффективности сжатия, позволяет сжимать данные с энтропией, меньшей 1 бита на кодируемый символ, но некоторые версии имеют патентные ограничения от компании IBM. [1]

    Характеристики

    Обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти H <\displaystyle H>бит, где H <\displaystyle H>— информационная энтропия источника.

    В отличие от алгоритма Хаффмана, метод арифметического кодирования показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов. Однако в случае равновероятного распределения символов, например, для строки бит 010101…0101 длины s метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше. [2]

    Принцип действия

    Пусть имеется некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок от 0 до 1.

    Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок будет соответствовать одному символу.

    Теперь возьмём символ из потока и найдём для него отрезок среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.

    Пример работы метода арифметического кодирования

    Вероятностная модель

    Используя метод арифметического кодирования, можно достичь почти оптимального представления для заданного набора символов и их вероятностей (согласно теории энтропийного кодирования источника Шеннона оптимальное представление будет стремиться к числу −log2P бит на каждый символ, вероятность которого P). Алгоритмы сжатия данных, использующие в своей работе метод арифметического кодирования, перед непосредственным кодированием формируют модель входных данных на основании количественных или статистических характеристик, а также, найденных в кодируемой последовательности повторений или паттернов — любой дополнительной информации, позволяющей уточнить вероятность появления символа P в процессе кодирования. Очевидно, что чем точнее определена или предсказана вероятность символа, тем выше эффективность сжатия.

    Рассмотрим простейший случай статической модели для кодирования информации, поступающей с системы обработки сигнала. Типы сигналов и соответствующие им вероятности распределены следующим образом:

    • 60 % вероятность нейтрального значения сигнала или NEUTRAL.
    • 20 % вероятность положительного значения сигнала или POSITIVE.
    • 10 % вероятность отрицательного значения сигнала или NEGATIVE.
    • 10 % вероятность признака конца кодируемой последовательности или END-OF-DATA.

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

    Следует также отметить, что в качестве алфавита вероятностной модели метода можно рассматривать любой набор символов, исходя из особенностей решаемой задачи. Более эвристические подходы, использующие основную схему метода арифметического кодирования, применяют динамические или адаптивные модели. Идея данных методов заключается в уточнении вероятности кодируемого символа за счёт учёта вероятности предшествующего или будущего контекста (то есть, вероятность появления кодируемого символа после определённого k-го числа символов слева или справа, где k — это порядок контекста).

    Кодирование сообщения

    Возьмём для примера следующую последовательность:

    NEUTRAL POSITIVE NEGATIVE END-OF-DATA

    Сначала разобьём отрезок от 0 до 1 согласно частотам сигналов. Разбивать отрезок будем в порядке, указанном выше: NEUTRAL — от 0 до 0,6; POSITIVE — от 0,6 до 0,8; NEGATIVE — от 0,8 до 0,9; END-OF-DATA — от 0,9 до 1.

    Теперь начнём кодировать с первого символа. Первому символу — NEUTRAL соответствует отрезок от 0 до 0,6. Разобьём этот отрезок аналогично отрезку от 0 до 1.

    Закодируем второй символ — NEGATIVE. На отрезке от 0 до 0,6 ему соответствует отрезок от 0,48 до 0,54. Разобьём этот отрезок аналогично отрезку от 0 до 1.

    Закодируем третий символ — END-OF-DATA. На отрезке от 0,48 до 0,54 ему соответствует отрезок от 0,534 до 0,54.

    Так как это был последний символ, то кодирование завершено. Закодированное сообщение — отрезок от 0,534 до 0,54 или любое число из него, например, 0,538.

    Декодирование сообщения

    Предположим, что нам необходимо раскодировать сообщение методом арифметического кодирования согласно описанной выше модели. Сообщение в закодированном виде представлено дробным значением 0,538 (для простоты используется десятичное представление дроби, вместо двоичного основания). Предполагается, что закодированное сообщение содержит ровно столько знаков в рассматриваемом числе, сколько необходимо для однозначного восстановления первоначальных данных.

    Начальное состояние процесса декодирования совпадает с процессом кодирования и рассматривается интервал [0,1). На основании известной вероятностной модели дробное значение 0,538 попадает в интервал [0, 0,6). Это позволяет определить первый символ, который был выбран кодировщиком, поэтому его значение выводится как первый символ декодированного сообщения.

    Примечания

    1. ↑История развития теории сжатия информации / Compression.ru, Sarmin Alexey, 10 марта 2011
    2. ↑Dr. Dobb’s Data Compression Newsletter, August 13, 2001

    Ссылки

    Asymmetric numeral systems (ANS, от «асимметричные системы счисления») — семейство методов энтропийного кодирования, изобретённых Ярославом (Яреком) Дудой в 2006 на основе введённой им концепции асимметричных систем счисления. С 2014 года используется для сжатия данных в ряде программ, так как эти методы по степени сжатия дают примерно столь же хорошее аккуратное приближение к оптимальному энтропийному кодированию, как и арифметическое кодирование, но обладают более высоким быстродействием, не уступая по скорости распаковки алгоритмам кодированию Хаффмана; кроме того, существенным является то, что эти методы не защищены патентами и свободны к использованию, так как создание и распространение свободной альтернативы арифметическому кодированию являлось целью автора.

    Контекстно-адаптивное двоичное арифметическое кодирование (КАДАК; CABAC от англ. Context-adaptive binary arithmetic coding) — форма энтропийного (статистического) кодирования, которое используется в видеокодеках стандарта H.264/MPEG-4 AVC. Используется техника сжатия без потерь для получения более высокой степени сжатия, чем большинство алгоритмов, которые доступны в кодировании видео.

    Является одним из основных преимуществ кодека H.264/AVC. CABAC поддерживается только в основном (Main) и более высоких профилях кодека, а также требует затрачивать достаточно большое количество рабочих циклов процессора в чисто программной реализации, как с точки зрения циклов, так и с точки зрения мощности системы для декодирования (просмотра) видео, закодированного с использованием этой технологии. Также, труден в векторизации и распараллеливании. Стоит отметить, что существует контекстно-адаптивное неравномерное кодирование (англ. Context-adaptive variable-length coding, CAVLC), более низкоэффективная схема статистического кодирования, которая используется для повышения производительности на более слабых системах декодирования.

    H.264, MPEG-4 Part 10 или AVC (Advanced Video Coding) — лицензируемый стандарт сжатия видео, предназначенный для достижения высокой степени сжатия видеопотока при сохранении высокого качества.

    JPEG (произносится «джейпег», англ. Joint Photographic Experts Group, по названию организации-разработчика) — один из популярных растровых графических форматов, применяемый для хранения фотоизображений и подобных им изображений. Файлы, содержащие данные JPEG, обычно имеют расширения (суффиксы) .jpg, .jfif, .jpe или .jpeg. Однако из них .jpg является самым популярным на всех платформах. MIME-типом является image/jpeg.

    Алгоритм JPEG позволяет сжимать изображение как с потерями, так и без потерь (режим сжатия lossless JPEG).

    Поддерживаются изображения с линейным размером не более 65535 × 65535 пикселей.

    В 2010 году, с целью сохранения для потомков информации о популярных в начале XXI века цифровых форматах, учёные из проекта PLANETS заложили инструкции по чтению формата JPEG в специальную капсулу, которую поместили в специальное хранилище в швейцарских Альпах.

    PAQ — серия свободных архиваторов с текстовым интерфейсом, которые общими усилиями разработчиков поднялись в первые места рейтингов многих тестов сжатия данных (хотя и ценой процессорного времени и объёма памяти). Лучший результат в этой серии на большинстве тестов был получен архиватором PAQ8JD, созданным совместными усилиями Мэтта Махони (Matt Mahoney), Александра Ратушняка, Сергея Оснача, Пшемыслава Скибиньского (Przemysław Skibiński) и Билла Петтиса (Bill Pettis), и выпущенным 30 декабря 2006 года. Однако в некоторых тестах он отстаёт от WinRK (созданного Малькомом Тейлором в январе 2005 года) в режиме PWCM. PWCM (англ. PAQ weighted context mixing, «PAQ взвешенное смешивание контекстов») — сторонняя проприетарная реализация алгоритма PAQ. Специально настроенные версии алгоритма PAQ выиграли призы в Приз Хаттера и Калгари Корпус Челлендж.

    Snappy (ранее известный как Zippy) — библиотека для быстрого сжатия и распаковки данных, написанная на C++ в Google и основанная на LZ77; код был открыт в 2011 году. Целью разработки библиотеки не являлось достижение наибольшего сжатия или совместимость и другими библиотеками, важной частью стало достижение высокой скорости сжатия. В 2011 году скорость сжатия на одном ядре Core i7 (2.26 ГГц, 64 бита) достигала 250 МБ/с и 500 МБ/с для распаковки, однако при этом коэффициент сжатия оказался на 20 – 100 % ниже, чем у gzip.Snappy часто используется в проектах Google, например, таких как BigTable, MapReduce и во внутренней системе RPC. Библиотеку можно использовать в MariaDB ColumnStore, Cassandra, Hadoop, LevelDB, MongoDB, RocksDB и Lucene. По большей части, в Snappy не используются ассемблерные вставки, также, библиотека является переносимой.

    Unified Video Decoder (рус. Унифицированный видео декодер; ранее называемый Universal Video Decoder — рус. Универсальный видео декодер; сокращённо — UVD) — аппаратный компонент (блок) графических процессоров производства американской компании AMD, предназначенный для аппаратного декодирования битовых потоков видеоданных, сжатых видеокодеками H.264, VC-1 и MPEG-2. Изначально UVD был разработан канадской компанией ATI Technologies, а после её покупки компанией AMD последняя продолжила разработку, совершенствование и поддержку UVD. UVD является частью технологии ATI Avivo HD, которая включает программные компоненты для работы с UVD.На 2010 год спецификации UVD поддерживаются API DirectX Video Acceleration (DXVA) для операционных систем семейства Microsoft Windows и игровой консоли Microsoft Xbox 360. На этих двух аппаратно-программных платформах видео, закодированное при помощи кодеков H.264,VC-1 и MPEG-2, может быть аппаратно ускоренным при помощи UVD. Вместе с тем для аппаратного ускорения нужно, чтобы медиаплеер также поддерживал DXVA и UVD.

    Для UNIX-подобных операционных систем, включая Linux, поддержка UVD реализована через API X-Video Bitstream Acceleration (XvBA), используемое расширением X video extension (Xv) для X Window System.

    TrueMotion VP6 — это видеокодек, созданный компанией On2 Technologies в развитие кодеков VP3 (позднее выпущенный как Theora) и VP5. Прямой конкурент MPEG4-ASP кодеков (известными представителями которых являются DivX и Xvid), на малых битрейтах даёт заметно лучшую картинку, чем все кодеки семейства ASP. Был выпущен в свободное распространение в VfW (Video for Windows) интерфейсе, однако в данный момент на сайте компании On2 он отсутствует (тем не менее, в сети можно отыскать прежнюю версию кодека, а декодер доступен в свободно распространяемой библиотеке libavcodec). Некоторая доля фильмов в сети закодирована именно VP6.

    В настоящее время взамен него On2 предлагает усовершенствованную версию — VP7.

    Популярный в последнее время формат Flash Video использует в качестве одного из основных вариантов кодирования VP6. Также может использоваться в JavaFX.

    x264 — свободная библиотека программных компонентов для кодирования видеопотоков H.264. Код этой библиотеки был написан с нуля. В проекте участвуют/участвовали: Лорен Мерит (Loren Merritt), Лоран Аймар (Laurent Aimar), Эрик Петит (Eric Petit), Мин Чен (Min Chen), Джастин Клэй (Justin Clay), Манс Руллгард (Måns Rullgård), Радек Чиз (Radek Czyz), Алекс Изворски (Alex Izvorski), Алекс Райт (Alex Wright) и Кристиан Хайн (Christian Heine). Эта реализация основана на принципах GNU, однако эта лицензия может быть несовместима с патентной лицензией MPEG LA в отношении понимания патентов на программное обеспечение.

    Было разработано несколько графических интерфейсов пользователя для консольной версии, среди которых MeGUI, StaxRip, Leiming’s x264 GUI, AutoAC, .NET (1.1) based x264CLI GUI и AMVSimple GUI.

    PPM (англ. Prediction by Partial Matching — предсказание по частичному совпадению) — адаптивный статистический алгоритм сжатия данных без потерь, основанный на контекстном моделировании и предсказании. Модель PPM использует контекст — множество символов в несжатом потоке, предшествующих данному, чтобы предсказывать значение символа на основе статистических данных. Сама модель PPM лишь предсказывает значение символа, непосредственное сжатие осуществляется алгоритмами энтропийного кодирования, как например, алгоритм Хаффмана, арифметическое кодирование.

    Длина контекста, который используется при предсказании, обычно сильно ограничена. Эта длина обозначается n и определяет порядок модели PPM, что обозначается как PPM(n). Неограниченные модели также существуют и обозначаются просто PPM*. Если предсказание символа по контексту из n символов не может быть произведено, то происходит попытка предсказать его с помощью n-1 символов. Рекурсивный переход к моделям с меньшим порядком происходит, пока предсказание не произойдёт в одной из моделей, либо когда контекст станет нулевой длины (n=0). Модели степени 0 и −1 следует описать особо. Модель нулевого порядка эквивалента случаю контекстно-свободного моделирования, когда вероятность символа определяется исключительно из частоты его появления в сжимаемом потоке данных. Подобная модель обычно применяется вместе с кодированием по Хаффману. Модель порядка −1 представляют собой статическую модель, присваивающую вероятности символа определенное фиксированное значение; обычно все символы, которые могут встретиться в сжимаемом потоке данных, при этом считаются pавновероятными. Для получения хорошей оценки вероятности символа необходимо учитывать контексты pазных длин. PPM представляет собой вариант стратегии перемешивания, когда оценки вероятностей, сделанные на основании контекстов pазных длин, объединяются в одну общую вероятность. Полученная оценка кодируется любым энтропийным кодером (ЭК), обычно это некая pазновидность арифметического кодера. На этапе энтропийного кодирования и происходит собственно сжатие.

    Большое значение для алгоритма PPM имеет проблема обработки новых символов, ещё не встречавшихся во входном потоке. Это проблема носит название проблема нулевой частоты. Некоторые варианты реализаций PPM полагают счётчик нового символа равным фиксированной величине, например, единице. Другие реализации, как например, PPM-D, увеличивают псевдосчётчик нового символа каждый раз, когда, действительно, в потоке появляется новый символ (другими словами, PPM-D оценивает вероятность появления нового символа как отношение числа уникальных символов к общему числу используемых символов).

    Опубликованные исследования алгоритмов семейства PPM появились в середине 1980-х годов. Программные реализации не были популярны до 1990-х годов, потому как модели PPM требуют значительного количества оперативной памяти.

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

    Интервальное кодирование (диапазонное кодирование) — энтропийный метод кодирования, предложенный Г. Найджелом и Н. Мартином в 1979 году. Это разновидность арифметического кодирования.

    Код — взаимно однозначное отображение конечного упорядоченного множества символов, принадлежащих некоторому конечному алфавиту, на иное, не обязательно упорядоченное, как правило более обширное множество символов для кодирования передачи, хранения или преобразования информации.

    Например, код Морзе, в котором любая буква/символ кодируются последовательностями точек и тире. Иной пример — кодирование букв, чисел и символов последовательностями логических нулей и единиц в компьютерах. Последовательность элементарных закодированных символов принято называть кодовым сообщением или кодовой посылкой. Иногда последовательность закодированных символов известной длины называют кодовым словом, или кодовым кадром.

    Сжатие данных без потерь (англ. lossless data compression) — класс алгоритмов сжатия данных (видео, аудио, графики, документов, представленных в цифровом виде), при использовании которых закодированные данные однозначно могут быть восстановлены с точностью до бита, пикселя, вокселя и т.д. При этом оригинальные данные полностью восстанавливаются из сжатого состояния. Этот тип сжатия принципиально отличается от сжатия данных с потерями. Для каждого из типов цифровой информации, как правило, существуют свои оптимальные алгоритмы сжатия без потерь.

    Сжатие данных без потерь используется во многих приложениях. Например, оно используется во всех файловых архиваторах. Оно также используется как компонент в сжатии с потерями.

    Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример — исполняемые файлы и исходный код. Некоторые графические файловые форматы (например PNG) используют только сжатие без потерь, тогда как другие (TIFF, FLIF или GIF) могут использовать сжатие как с потерями, так и без потерь.

    Сжа́тие да́нных (англ. data compression) — алгоритмическое преобразование данных, производимое с целью уменьшения занимаемого ими объёма. Применяется для более рационального использования устройств хранения и передачи данных. Синонимы — упаковка данных, компрессия, сжимающее кодирование, кодирование источника. Обратная процедура называется восстановлением данных (распаковкой, декомпрессией).

    Сжатие основано на устранении избыточности, содержащейся в исходных данных. Простейшим примером избыточности является повторение в тексте фрагментов (например, слов естественного или машинного языка). Подобная избыточность обычно устраняется заменой повторяющейся последовательности ссылкой на уже закодированный фрагмент с указанием его длины. Другой вид избыточности связан с тем, что некоторые значения в сжимаемых данных встречаются чаще других. Сокращение объёма данных достигается за счёт замены часто встречающихся данных короткими кодовыми словами, а редких — длинными (энтропийное кодирование). Сжатие данных, не обладающих свойством избыточности (например, случайный сигнал или белый шум, зашифрованные сообщения), принципиально невозможно без потерь.

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

    Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и списке основных разделов теории алгоритмов

    Хронология событий, связанных с теорией информации, сжатием данных, кодами коррекции ошибок и смежных дисциплин:

    1872 — Людвиг Больцман представляет свою H-теорему, а вместе с этим формулу Σpi log pi для энтропии одной частицы газа.1878 — Джозайя Уиллард Гиббс, определяет энтропию Гиббса: вероятности в формуле энтропии теперь взяты как вероятности состояния целой системы.1924 — Гарри Найквист рассуждает о квантификации «Интеллекта» и скорости, на которой это может быть передано системой коммуникации.1927 — Джон фон Нейман определяет фон Неймановскую энтропию, расширяя Гиббсовскую энтропию в квантовой механике.1928 — Ральф Хартли представляет формулу Хартли как логарифм числа возможных сообщений, с информацией, передаваемой, когда приёмник (получатель, ресивер) может отличить одну последовательность символов от любой другой (независимо от любого связанного значения).1929 — Лео Силард анализирует демона Максвелла, показывают, как двигатель Szilard может иногда преобразовывать информацию в извлечение полезной работы.1940 — Алан Тьюринг представляет deciban как единицу измерения информации в немецкой машине Энигма с настройками, зашифрованными процессом Banburismus.1944 — теория информации Клода Шеннона в основном завершена.1947 — Ричард Хемминг изобретает Код Хемминга для обнаружения ошибок и их исправления, но не публикует их до 1950 года.1948 — Клод Шеннон публикует Математическую теорию связи1949 — Клод Шеннон публикует Передачу Информации в виде шумов, в которой описаны Теорема отсчётов и Теорема Шеннона — Хартли.1949 — Рассекречена Теория связи в секретных системах Клода Шеннона.1949 — Роберт Фано опубликовал отчет, в котором независимо от Клода Шеннона описан Алгоритм Шеннона — Фано.1949 — опубликовано Неравенство Крафта — Макмиллана.1949 — Марсель Голей вводит коды Голея для исправления ошибок методом упреждения.1950 — Ричард Хемминг публикует коды Хемминга для исправления ошибок методом упреждения.1951 — Соломон Кульбак и Ричард Лейблер вводят понятие расстояния Кульбака-Лейблера.1951 — Дэвид Хаффман изобретает кодирование Хаффмана, метод нахождения оптимальных префиксных кодов для сжатия данных без потерь.1953 — опубликован Sardinas–Patterson algorithm.1954 — Ирвинг С. Рид и Дэвид E. Мюллер вводит коды Рида-Мюллера.1955 — Питер Элиас вводит свёрточные коды.1957 — Юджин Прандж первый обсуждает циклический избыточный код.1959 — Алексис Хоквингем, и самостоятельно в следующем году Радж Чандра Боуз и Двайджендра Камар Рей-Чоудхури, представляют коды Боуза-Чоудхури-Хоквингема (БЧХ-коды).1960 — Ирвинг Рид и Густав Соломон вводят коды Рида-Соломона.1962 — Роберт Галлагер предлагает код с малой плотностью проверок на чётность; их не использовали в течение 30 лет из-за технических ограничений.1966 — опубликована статья Дэвида Форнея Concatenated error correction code.1967 — Эндрю Витерби открывает алгоритм Витерби, делающий возможным декодирование свёрточных кодов.1968 — Элвин Берлекэмп изобретает алгоритм Берлекэмпа — Мэсси; его применение к расшифровке БЧХ-кодов и кода Рида-Соломона, указанный Джеймсом Мэсси в последующем году.1968 — Крис Уоллис и Дэвид М. Бутон издают первый из многих докладов о Сообщениях минимальной длины (СМД) — их статистический и индуктивный вывод.1972 — опубликована статья о Justesen code.1973 — Дэвид Слепиан и Джек Волф открывают и доказывают Код Слепиана-Вольфа, кодирующего пределы распределённого источника кодирования.1976 — Готфрид Унгербоэк публикует первую статью о Треллис-модуляции.1976 — Йорма Риссанен разрабатывает и позднее патентует арифметическое кодирование для IBM.1977 — Абрахам Лемпель и Яаков Зив разрабатывают алгоритм сжатия Лемпеля-Зива (LZ77)1982 — Готфрид Унгербоэк публикует более подробное описание Треллис-модуляции, что приводит к увеличению скорости аналогового модема старой обычной телефонной службы от 9.6 кбит/сек до 36 кбит/сек.1989 — Фил Кац создаёт .zip формат, включая формат сжатия DEFLATE (LZ77 + Huffman кодирование); позже это становится наиболее широко используемым алгоритмом сжатия без потерь.1993 — Клод Берроу, Алэйн Главиукс и Punya Thitimajshima вводят понятие Турбо-кодов.1994 — Майкл Барроуз и Дэвид Уилер публикуют теорию преобразования Барроуза-Уилера, которая далее найдет своё применение в bzip2.1995 — Benjamin Schumacher предложил термин Кубит.1998 — предложен Fountain code.2001 — описан алгоритм Statistical Lempel–Ziv.2008 — Erdal Arıkan предложил Полярные коды.

    Эффективность алгоритма — это свойство алгоритма, которое связано с вычислительными ресурсами, используемыми алгоритмом. Алгоритм должен быть проанализирован с целью определения необходимых алгоритму ресурсов. Эффективность алгоритма можно рассматривать как аналог производственной производительности повторяющихся или непрерывных процессов.

    Для достижения максимальной эффективности мы желаем уменьшить использование ресурсов. Однако различные ресурсы (такие как время и память) нельзя сравнить напрямую, так что какой из двух алгоритмов считать более эффективным часто зависит от того, какой фактор более важен, например, требование высокой скорости, минимального использования памяти или другой меры эффективности.

    Заметим, что данная статья НЕ об оптимизации алгоритма, которая обсуждается в статьях оптимизация программы, оптимизирующий компилятор, оптимизация циклов, оптимизатор объектного кода, и так далее. Термин «оптимизация» сам по себе вводит в заблуждение, поскольку всё, что может быть сделано, попадает под определение «улучшение».

    Теория информации

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

    Алгоритмы Шеннона-Фено и Хаффмена в лучшем случае не могут кодировать каждый символ сообщения менее чем 1 битом информации. Предположим, в сообщении, состоящем из 0 и 1, единицы встречаются 10 раз чаще. Энтропия такого сообщения HX0,469 (бит/сим). В таком случае желательно иметь схему кодирования, позволяющую кодировать символы сообщения менее чем 1 битом информации. Одним из лучших алгоритмов такого кодирования информации является арифметическое кодирование.

    По исходному распределению вероятностей д.с.в. строится таблица, состоящая из пересекающихся в граничных точках отрезков для каждого из значений д.с.в. Объединение этих отрезков должно образовывать интервал [0;1], а их длины пропорциональны вероятностям кодируемых значений.

    Алгоритм кодирования заключается в построении отрезка, однозначно определяющего конкретную последовательность символов сообщения. По мере поступления входных символов отрезок сообщения сужается. Отрезки строятся следующим образом. Если имеется отрезок сообщения длиной n-1, то для построения отрезка сообщения длиной n символов, предыдущий интервал разбивается на столько частей, сколько значений включает алфавит источника. Начало и конец каждого нового интервала сообщения определяется путем прибавления к началу предыдущего интервала произведения его ширины на значения границ отрезка, соответствующего текущему новому символу (по исходной таблице вероятностей символов и назначенных им интервалов). Затем из полученных отрезков выбирается тот, который соответствует конкретной последовательности символов сообщения длиной n.

    Для построенного отрезка сообщения находится число, принадлежащее этому отрезку, обычно, это целое число, делённому на минимально возможную степень 2. Это вещественное число и будет кодом для рассматриваемой последовательности. Все возможные коды – числа строго больше 0 и меньше 1, поэтому лидирующий 0 и десятичная точка не учитываются.

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

    Принципиальное отличие арифметического кодирования от методов сжатия Шеннона-Фено и Хаффмена в его непрерывности, т.е. в отсутствии необходимости блокирования сообщения. Эффективность арифметического кодирования растёт с ростом длины сжимаемого сообщения, однако требует больших вычислительных ресурсов.

    Поясним идею арифметического кодирования на конкретных примерах.

    Пример 1 Закодируем текстовую строку «МАТЕМАТИКА» по алгоритму арифметического кодирования.

    Определим частоту каждого из символов в сообщении и назначим каждому из них отрезок, длина которого пропорциональна вероятности соответствующего символа (табл. 2.7).

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

    ru.knowledgr.com

    Арифметическое кодирование — форма кодирования энтропии, используемого в сжатии данных без потерь. Обычно, ряд знаков, таких как слова «привет там» представлен, используя постоянное число битов за характер, как в кодексе ASCII. Когда последовательность будет преобразована в кодирование арифметики, часто используемые знаки будут снабжены меньшим количеством битов и происходящих знаков «не, таким образом, часто» будет снабжен большим количеством битов, приводящих к меньшему количеству битов, используемых всего. Арифметическое кодирование отличается от других форм кодирования энтропии, таких как Хафман, кодирующий, в этом вместо того, чтобы разделить вход на составляющие символы и заменить каждого кодексом, арифметическое кодирование кодирует все сообщение в единственное число, часть n где (0,0 ≤ n

    Илон Маск рекомендует:  Что такое код ctime
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL