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


Содержание

Арифметическое кодирование. Кодирование длин повторений (стр. 1 из 2)

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Реферат на тему:

«Арифметическое кодирование. Кодирование длин повторений»

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

Поясним идею арифметического кодирования на простейшем примере. Пусть нам нужно закодировать следующую текстовую строку: РАДИОВИЗИР.

Пеpед началом pаботы кодера соответствующий кодируемому тексту исходный интеpвал составляет [0; 1).

Алфавит кодируемого сообщения содержит следующие символы (буквы): < Р, А, Д, И, О, В, З >.

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

Символ Веpоятность Интеpвал
А 0.1 0 – 0.1
Д 0.1 0.1 – 0.2
В 0.1 0.2 – 0.3
И 0.3 0.3 – 0.6
З 0.1 0.6 – 0.7
О 0.1 0.7 – 0.8
Р 0.2 0.8 – 1

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

Процедура кодировани я

Итак, перед началом кодирования исходный интервал составляет [0 – 1).

После пpосмотpа пеpвого символа сообщения Р кодер сужает исходный интеpвал до нового — [0.8; 1), котоpый модель выделяет этому символу. Таким образом, после кодирования первой буквы результат кодирования будет находиться в интервале чисел [ 0.8 — 1).

Следующим символом сообщения, поступающим в кодер, будет буква А . Если бы эта буква была первой в кодируемом сообщении, ей был бы отведен интервал [ 0 — 0.1 ), но она следует за Р и поэтому кодируется новым подынтервалом внутри уже выделенного для первой буквы , сужая его до величины [ 0.80 — 0.82 ). Другими словами, интервал [ 0 — 0.1 ), выделенный для буквы А , располагается теперь внутри интервала, занимаемого предыдущим символом (начало и конец нового интервала определяются путем прибавления к началу предыдущего интервала произведения ширины предыдущего интервала на значения интервала, отведенные текущему символу ). В pезультате получим новый pабочий интеpвал [0.80 — 0.82), т.к. пpедыдущий интеpвал имел шиpину в 0.2 единицы и одна десятая от него есть 0.02.

Следующему символу Д соответствует выделенный интервал [0.1 — 0.2), что пpименительно к уже имеющемуся рабочему интервалу [0.80 — 0.82) сужает его до величины [0.802 — 0.804).

Следующим символом, поступающим на вход кодера, будет буква И с выделенным для нее фиксированным интервалом [ 0,3 – 0,6). Применительно к уже имеющемуся рабочему интервалу получим [ 0,8026 — 0,8032 ).

Пpодолжая в том же духе, имеем:

после пpосмотpа Р [0.8 — 1.0)

З [0.80303488 — 0.80303506)

И [0.803034934 — 0.803034988)

Р [0.8030349772 — 0.8030349880)

Результат кодирования: интервал [0,8030349772 – 0,8030349880]. На самом деле, для однозначного декодирования теперь достаточно знать только одну границу интервала – нижнюю или верхнюю, то есть результатом кодирования может служить начало конечного интервала — 0,8030349772. Если быть еще более точным, то любое число, заключенное внутри этого интервала, однозначно декодируется в исходное сообщение. К примеру, это можно проверить с числом 0,80303498, удовлетворяющим этим условиям. При этом последнее число имеет меньшее число десятичных разрядов, чем числа, соответствующие нижней и верхней границам интервала, и, следовательно может быть представлено меньшим числом двоичных разрядов.

Нетрудно убедиться в том, что, чем шире конечный интервал, тем меньшим числом десятичных (и, следовательно, двоичных) разрядов он может быть представлен. Ширина же интервала зависит от распределения вероятностей кодируемых символов – более вероятные символы сужают интервал в меньшей степени и , следовательно, добавляют к результату кодирования меньше бит. Покажем это на простом примере.

Допустим, нам нужно закодировать следующую строку символов: A A A A A A A A A # , где вероятность буквы А составляет 0,9. Процедура кодирования этой строки и получаемый результат будут выглядеть в этом случае следующим образом:

Входной символ Нижняя граница Верхняя граница

Результатом кодирования теперь может быть, к примеру, число 0.35 , целиком попадающее внутрь конечного интервала 0.3486784401 – 0.387420489. Для двоичного представления этого числа нам понадобится 7 бит (два десятичных разряда соответствуют примерно семи двоичным ), тогда как для двоичного представления результатов кодирования из предыдущего примера – 0,80303498 – нужно 27 бит .

Декодирование

Пpедположим, что все что декодер знает о тексте, – это конечный интеpвал [0,8030349772 — 0,8030349880]. Декодеру, как и кодеру, известна также таблица распределения выделенных алфавиту интервалов. Он сpазу же понимает, что пеpвый закодиpованный символ есть Р , так как результат кодирования целиком лежит в интеpвале [0.8 — 1), выделенном моделью символу Р согласно таблице .

Тепеpь повтоpим действия кодера:

после пpосмотpа [0.8 — 1.0).

Исключим из результата кодирования влияние теперь уже известного первого символа Р , для этого вычтем из результата кодирования нижнюю границу диапазона, отведенного для Р, – 0,8030349772 – 0.8 = =0,0030349772 – и разделим полученный результат на ширину интервала, отведенного для Р, – 0.2. В результате получим 0,0030349772 / 0,2 = =0,015174886. Это число целиком вмещается в интервал, отведенный для буквы А, – [0 – 0,1) , следовательно, вторым символом декодированной последовательности будет А .

Поскольку теперь мы знаем уже две декодированные буквы — РА , исключим из итогового интервала влияние буквы А . Для этого вычтем из остатка 0,015174886 нижнюю границу для буквы А 0,015174886 – 0.0 = =0,015174886 и разделим результат на ширину интервала, отведенного для буквы А , то есть на 0,1. В результате получим 0,015174886/0,1=0,15174886. Результат лежит в диапазоне, отведенном для буквы Д , следовательно, очередная буква будет Д .

Исключим из результата кодирования влияние буквы Д . Получим (0,15174886 – 0,1)/0,1 = 0,5174886. Результат попадает в интервал, отведенный для буквы И , следовательно, очередной декодированный символ – И , и так далее, пока не декодируем все символы:

Декодируемое Символ Границы Ширина число на выходе нижняя верхняя интервала0,8030349772 Р 0.8 1.0 0.20,015174886 А 0.0 0.1 0.10,15174886 Д 0.1 0.2 0.10,5174886 И 0.3 0.6 0.30,724962 О 0,7 0,8 0,10,24962 В 0,2 0,2 0,10,4962 И 0,3 0,6 0,30,654 З 0,6 0,7 0,10,54 И 0,3 0,6 0,30,8 Р 0,6 0,8 0,20.0 Конец декодирования

Это основная идея арифметического кодирования, его практическая реализация несколько сложнее. Некоторые проблемы можно заметить непосредственно из приведенного примера.

Первая состоит в том, что декодеру нужно обязательно каким-либо образом дать знать об окончании процедуры декодирования, поскольку остаток 0,0 может означать букву а или последовательность аа, ааа, аааа и т.д. Решить эту проблему можно двумя способами.

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

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

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

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

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

Метод Хаффмана является простым, но эффективным только в том случае, когда вероятности появления символов равны числам , где — любое целое положительное число. Это связано с тем, что код Хаффмана присваивает каждому символу алфавита код с целым числом бит. Вместе с тем в теории информации известно, что, например, при вероятности появления символа равной 0,4, ему в идеале следует поставить код длиной бит. Понятно, что при построении кодов Хаффмана нельзя задать длину кода в 1,32 бита, а только лишь в 1 или 2 бита, что приведет в результате к ухудшению сжатия данных. Арифметическое кодирование решает эту проблему путем присвоения кода всему, обычно, большому передаваемому файлу вместо кодирования отдельных символов.

Идею арифметического кодирования лучше всего рассмотреть на простом примере. Предположим, что необходимо закодировать три символа входного потока, для определенности – это строка SWISS_MISS с заданными частотами появления символов: S – 0,5, W – 0,1, I – 0,2, M – 0,1 и _ — 0,1. В арифметическом кодере каждый символ представляется интервалом в диапазоне чисел [0, 1) в соответствии с частотой его появления. В данном примере, для символов нашего алфавита получим следующие наборы интервалов:

Рис. 2. Распределение интервалов представление символов

Процесс кодирования начинается со считывания первого символа входного потока и присвоения ему интервала из начального диапазона [0, 1). В данном случае для первого символа S получаем диапазон [0,5, 1). Затем, считывается второй символ – W, которому соответствует диапазон [0,4, 0,5). Но исходный диапазон [0, 1) уже сократился до [0,5, 1), поэтому символ W необходимо представить в этом новом диапазоне. Для этого достаточно вычислить новые нижнюю и верхнюю границы. Значение 0,4 будет соответствовать значению 0,7, а значение 0,5 – значению 0,75 (рис. 3).

Рис. 3. Схема представления новых границ символа W


Данные границы можно вычислить по формулам:

NewHigh = OldLow + (OldHigh-OldLow)*HighRange(X),

NewLow = OldLow + (OldHigh-OldLow)*LowRange(X),

где OldLow – нижняя граница интервала, в котором представляется текущий символ; OldHigh – верхняя граница интервала; HighRange(X) – исходная верхняя граница кодируемого символа; LowRange(X) – исходная нижняя граница кодируемого символа. Применяя данные формулы к вычислению границ символа W, получаем:

OldLow = 0,5, OldHigh = 1,

HighRange(W) = 0,5, LowRange(W) = 0,4,

NewHigh = 0,5 + (1-0,5)*0,5 = 0,75,

NewLow = 0,5 + (1-0,5)*0,4 = 0,7.

Аналогичным образом выполняется кодирование символа I, для которого новые интервалы также можно вычислить по приведенной формуле:

OldLow = 0,7, OldHigh = 0,75,

HighRange(I) = 0,4, LowRange(I) = 0,2,

NewHigh = 0,7 + (0,75-0,7)*0,4 = 0,72,

NewLow = 0,7 + (0,75-0,7)*0,2 = 0,71.

Ниже, в табл. 1 представлены значения границ при кодировании строки SWISS_MISS.

Символ Границы
S L H 0.0+(1.0-0.0)*0.5 = 0.5 0.0+(1.0-0.0)*1.0 = 1.0
W L H 0.5+(1.0-0.5)*0.4=0.70 0.5+(1.0-0.5)*0.5=0.75
I L H 0.7+(0.75-0.7)*0.2=0.71 0.7+(0.75-0.7)*0.4=0.72
S L H 0.71+(0.72-0.71)*0.5=0.715 0.71+(0.72-0.71)*1.0=0.72
S L H 0.715+(0.72-0.715)*0.5=0.7175 0.715+(0.72-0.715)*1.0=0.72
L H 0.7175+(0.72-0.7175)*0.0=0.7175 0.7175+(0.72-0.7175)*0.1=0.71775
М L H 0.7175+(0.71775-0.7175)*0.1=0.717525 0.7175+(0.71775-0.7175)*0.2=0.717550
I L H 0.717525+(0.717550-0.717525)*0.4=0.717530 0.717525+(0.717550-0.717525)*0.5=0.717535
S L H 0.717530+(0.717535-0.717530)*0.5=0.7175325 0.717530+(0.717535-0.717530)*1.0=0.717535
S L H 0.7175325+(0.717535-0.7175325)*0.5=0.71753375 0.7175325+(0.717535-0.7175325)*1.0=0.717535

Конечный выходной код – это последнее значение переменной Low, равное 0.71753375, из которого следует взять лишь восемь цифр 71753375 для записи в файл.

Теперь рассмотрим возможность восстановления закодированной информации по восьми цифрам 71753375 и известным интервалам символов. Первая из восьми цифр – это 7, т.е. 0,7. Она принадлежит одному из заданных интервалов [0.5, 1), который соответствует символу S. Поэтому первый декодированный символ – это S. Теперь вернемся к рис. 3 и заметим, что второй символ был представлен в интервале символа S, т.е. [0.5, 1). Но для удобства декодирования его лучше представить в исходном интервале [0, 1). Для этого достаточно интервал [0.5, 1) увеличить до начального, т.е. умножить на два и границы сдвинуть на величину 0.5*2=1 (рис. 4).

Рис. 4. Схема восстановления исходных интервалов символа W

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

Полученное значение принадлежит диапазону [0.4, 0.5), который соответствует символу W. Затем, также полученное число 0.4350675 следует нормировать, что в общем случае выполняется по формуле:

где Code – текущее значение кода. Например, пользуясь этой формулой применительно к коду 0.71753375, получаем значение

Code = (0.71753375-0.5)/(1-0.5)= 0.4350675,

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

Таблица 2. Вычисление кодов при декодировании

Символ Code-Low Область
S 0.71753375 – 0.5 = 0.21753375 / 0.5 = 0.4350675
W 0.4350675 – 0.4 = 0.0350675 / 0.1 = 0.350675
I 0.350675 – 0.2 = 0.150675 / 0.2 = 0.753375
S 0.753375 – 0.5 = 0.253375 / 0.5 = 0.50675
S 0.50675 – 0.5 = 0.00675 / 0.5 = 0.0135
_ 0.0135 – 0 = 0.0135 / 0.1 = 0.135
M 0.135 – 0.1 = 0.035 / 0.1 = 0.35
I 0.35 – 0.2 = 0.15 / 0.2 = 0.75
S 0.75 – 0.5 = 0.25 / 0.5 = 0.5
S 0.5 – 0.5 = 0 / 0.5 = 0

Однако это не всегда так. Бывают случаи, когда ноль содержит в себе код очередного символа, а не означает конец процедуры декодирования. Здесь возникает проблема завершения декодирования. Для этого используют специальный символ eof, говорящий о том, что он является последним и декодирование последовательности можно завершить. При этом частота этого символа очевидно должна быть маленькой по сравнению с частотой символов алфавита последовательности, например, [0,999999 1).

Описанный выше процесс кодирования невозможно реализовать на практике, т.к. в нем предполагается, что в переменных Low и High хранятся числа с неограниченной точностью. По существу, результат кодирования – это вещественное число с очень большой точностью. Например, файл объемом 1Мб будет сжиматься, скажем, до 500 КБ, в котором будет записано одно число. Арифметические операции с такими числами реализовать сложно и долго. Поэтому любая практическая реализация арифметического кодера должна основываться на операциях с целыми числами, которые не должны быть слишком длинными. Рассмотрим такую реализацию, в которой переменные Low и High будут целыми числами длиной 16 или 32 бита. Эти переменные будут хранить верхние и нижние концы текущего подинтервала, но мы не будем им позволять неограниченно расти. Анализ табл. 1 показывает, что как только самые левые цифры переменных Low и High становятся одинаковыми, они уже не меняются в дальнейшем. Следовательно, эти цифры можно выдвинуть за скобки и работать с оставшейся дробной частью. После сдвига цифр мы будем справа дописывать 0 в переменную Low, а в переменную High – цифру 9. Для того, чтобы лучше понять весь процесс, можно представлять себе эти переменные как левый конец бесконечно длинного числа. Число Low имеет вид xxxx00… а число High = yyyy99…

Проблема состоит в том, что переменная High в начале должна равняться 1, однако мы интерпретируем Low и High как десятичные дроби меньшие 1. Решение заключается в присвоении переменной High значения 9999…, которое соответствует бесконечной дроби 0,9999…, равной 1.

Как это все работает? Закодируем этим способом ту же строку SWISS_MISS. Первая буква S определена диапазоном [0,5 1) и формально границы равны

но в нашем случае данные формулы следует преобразовать, чтобы переменные Low и High были целыми. Поэтому запишем их в таком виде:

но по условию граница High является открытой, т.е. не включает число 10000, поэтому от конечного значения нужно отнять 1:

Таким образом, получили формулы для вычисления целочисленных границ Low и High, и процесс кодирования будет выглядеть так (табл. 3).

Табл. 3. Кодирование сообщения сдвигами

S L= H= 0+(10000-0)*0.5 0+(10000-0)*1.0-1 = =
W L= H= 5000+(10000-5000)*0.4 5000+(10000-5000)*0.5 = =
I L= H= 0+(5000-0)*0.2 0+(5000-0)*0.4-1 = =
S L= H= 0+(10000-0)*0.5 0+(10000-0)*1.0-1 = =
S L= H= 5000+(10000-5000)*0.5 5000+(10000-5000)*1.0-1 = =
_ L= H= 7500+(10000-7500)*0.0 7500+(10000-7500)*0.1-1 = =
M L= H= 5000+(7500-5000)*0.1 5000+(7500-5000)*0.2 = =
I L= H= 2500+(5000-2500)*0.2 2500+(5000-2500)*0.4-1 = =
S L= H= 0+(5000-0)*0.5 0+(5000-0)*1.0-1 = =
S L= H= 2500+(5000-2500)*0.5 2500+(5000-2500)*1.0-1 = =

На последнем шаге операции кодирования записываются все 4 цифры и полученная выходная последовательность имеет вид: 717533750.

Декодер работает в обратном порядке. В начале переменным Low и High присваиваются значения 0000 и 9999 соответственно, а переменной Code значение 7175. На основе этой информации требуется определить первый закодированный символ. Для этого число переменной Code нужно корректно представить в интервале от 0 до 1. В самом начале интервал такой и есть, поэтому частота символа, соответствующая значению Code будет равна

Эта частота попадает в диапазон [0,5 1) и соответствует символу S. Теперь границы Low и High пересчитываются, так как это делалось в кодере и принимают значения 5000 и 9999 соответственно. Так как значащие цифры этих переменных отличаются, то переменная Code остается прежней и величина

Это значение попадает в диапазон [0,4 0,5) и соответствует символу W. После этого величины Low и High принимают значения 7000 и 7499 и после отбрасывания значащей цифры переходят в 0000 и 4999 соответственно, а переменная Code преобразуется в 1753. Таким образом раскодируется вся последовательность.

На практике обычно значение index принимает целочисленные значения, которые вычисляются по формуле

и округляют до ближайшего целого.

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

можно выбрать любое число, выберем наименьшее для хранения – это 717534, которому соответствует битовое представление 10101111001011011110 и составляет 20 бит. И строка из 10 символов сжимается в 20 бит. Хорошее ли это сжатие? Для этого нужно найти энтропию кодируемой последовательности и она будет равна

и составит величину

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

  1. Алгоритмы сжатия.


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студентов недели бывают четные, нечетные и зачетные. 9438 — | 7438 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

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

Пpи аpифметическом кодиpовании, в отличие от рассмотренных нами методов, когда кодируемый символ (или группа символов) заменяется соответствующим им кодом, результат кодирования всего сообщения пpедставляется одним или парой вещественных чисел в интеpвале от 0 до 1. По меpе кодиpования исходного текста отобpажающий его интеpвал уменьшается, а количество десятичных (или двоичных) разрядов, служащих для его пpедставления, возpастает. Очеpедные символы входного текста сокpащают величину интеpвала исходя из значений их веpоятностей, определяемых моделью. Более веpоятные символы делают это в меньшей степени, чем менее веpоятные, и, следовательно, добавляют меньше разрядов к pезультату.Поясним идею арифметического кодирования на простейшем примере. Пусть нам нужно закодировать следующую текстовую строку: РАДИОВИЗИР.

Пеpед началом pаботы кодера соответствующий кодируемому тексту исходный интеpвал составляет [0; 1).

Алфавит кодируемого сообщения содержит следующие символы (буквы): < Р, А, Д, И, О, В, З >.

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

Вероятности появления символов

Символ Вероятность Интервал
А 0,1 0 – 0,1
Д 0,1 0,1 – 0,2
В 0,1 0,2 – 0,3
И 0,3 0,3 – 0,6
З 0,1 0,6 – 0,7
О 0,1 0,7 – 0,8
Р 0.2 0,8 – 1

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

Итак, перед началом кодирования исходный интервал составляет [0 – 1).

После пpосмотpа пеpвого символа сообщения Р кодер сужает исходный интеpвал до нового — [0.8; 1), котоpый модель выделяет этому символу. Таким образом, после кодирования первой буквы результат кодирования будет находиться в интервале чисел [0.8 — 1).

Следующим символом сообщения, поступающим в кодер, будет буква А. Если бы эта буква была первой в кодируемом сообщении, ей был бы отведен интервал [ 0 — 0.1 ), но она следует за Р и поэтому кодируется новым подынтервалом внутри уже выделенного для первой буквы, сужая его до величины [ 0.80 — 0.82 ). Другими словами, интервал [ 0 — 0.1 ), выделенный для буквы А, располагается теперь внутри интервала, занимаемого предыдущим символом (начало и конец нового интервала определяются путем прибавления к началу предыдущего интервала произведения ширины предыдущего интервала на значения интервала, отведенные текущему символу). В pезультате получим новый pабочий интеpвал [0.80 — 0.82), т.к. пpедыдущий интеpвал имел шиpину в 0.2 единицы и одна десятая от него есть 0.02.

Следующему символу Д соответствует выделенный интервал [0.1 — 0.2), что пpименительно к уже имеющемуся рабочему интервалу [0.80 — 0.82) сужает его до величины [0.802 — 0.804).

Следующим символом, поступающим на вход кодера, будет буква И с выделенным для нее фиксированным интервалом [ 0,3 – 0,6). Применительно к уже имеющемуся рабочему интервалу получим [ 0,8026 — 0,8032 ).

Пpодолжая в том же духе, имеем:

после пpосмотpа Р [0,8 — 1,0 )

А [0,80 — 0,82 )

Д [0,802 — 0,804 )

И [0,8026 — 0,8032 )

О [0,80302 — 0,80308 )

В [0,803032 — 0,803038 )

И [0,8030338 — 0,8030356 )

З [0,80303488 — 0,80303506 )

И [0,803034934 — 0,803034988 )

Р [0,8030349772 — 0,8030349880 )

Результат кодирования: интервал [0,8030349772 – 0,8030349880]. На самом деле, для однозначного декодирования теперь достаточно знать только одну границу интервала – нижнюю или верхнюю, то есть результатом кодирования может служить начало конечного интервала — 0,8030349772. Если быть еще более точным, то любое число, заключенное внутри этого интервала, однозначно декодируется в исходное сообщение. К примеру, это можно проверить с числом 0,80303498, удовлетворяющим этим условиям. При этом последнее число имеет меньшее число десятичных разрядов, чем числа, соответствующие нижней и верхней границам интервала, и, следовательно может быть представлено меньшим числом двоичных разрядов.

Нетрудно убедиться в том, что, чем шире конечный интервал, тем меньшим числом десятичных (и, следовательно, двоичных) разрядов он может быть представлен. Ширина же интервала зависит от распределения вероятностей кодируемых символов – более вероятные символы сужают интервал в меньшей степени и, следовательно, добавляют к результату кодирования меньше бит. Покажем это на простом примере.

Допустим, нам нужно закодировать следующую строку символов:
A A A A A A A A A #, где вероятность буквы А составляет 0,9. Процедура кодирования этой строки и получаемый результат будут выглядеть в этом случае следующим образом:

Входной символ Нижняя граница Верхняя граница

A 0,0 0,9

A 0,0 0,81

A 0,0 0,729

A 0,0 0,6561

A 0,0 0,59049

A 0,0 0,531441

A 0,0 0,4782969

А 0,0 0,43046721

А 0,0 0,387420489

# 0,3486784401 0,387420489

Результатом кодирования теперь может быть, к примеру, число 0.35 , целиком попадающее внутрь конечного интервала 0.3486784401 – 0.387420489. Для двоичного представления этого числа нам понадобится 7 бит ( два десятичных разряда соответствуют примерно семи двоичным ), тогда как для двоичного представления результатов кодирования из предыдущего примера – 0,80303498 – нужно 27 бит .

При декодировании пpедположим, что все что декодер знает о тексте, – это конечный интеpвал [0,8030349772 — 0,8030349880]. Декодеру, как и кодеру, известна также таблица распределения выделенных алфавиту интервалов. Он сpазу же понимает, что пеpвый закодиpованный символ есть Р, так как результат кодирования целиком лежит в интеpвале [0.8 — 1), выделенном моделью символу Р согласно таблице .

Илон Маск рекомендует:  Что такое код asp buffer

Тепеpь повтоpим действия кодера:

после пpосмотpа [0,8 — 1,0).


Исключим из результата кодирования влияние теперь уже известного первого символа Р, для этого вычтем из результата кодирования нижнюю границу диапазона, отведенного для Р, – 0,8030349772 – 0,8 = 0,0030349772 – и разделим полученный результат на ширину интервала, отведенного для Р, – 0,2. В результате получим 0,0030349772 / 0,2 = =0,015174886. Это число целиком вмещается в интервал, отведенный для буквы А, – [0 – 0,1) , следовательно, вторым символом декодированной последовательности будет А.

Поскольку теперь мы знаем уже две декодированные буквы — РА, исключим из итогового интервала влияние буквы А. Для этого вычтем из остатка 0,015174886 нижнюю границу для буквы А 0,015174886 – 0.0 = =0,015174886 и разделим результат на ширину интервала, отведенного для буквы А, то есть на 0,1. В результате получим 0,015174886/0,1=0,15174886. Результат лежит в диапазоне, отведенном для буквы Д, следовательно, очередная буква будет Д.

Исключим из результата кодирования влияние буквы Д. Получим (0,15174886 – 0,1)/0,1 = 0,5174886. Результат попадает в интервал, отведенный для буквы И, следовательно, очередной декодированный символ – И, и так далее, пока не декодируем все символы:

Декодируемое Символ Границы Ширина число на выходе нижняя верхняя интервала0,8030349772 Р 0,8 1,0 0,20,015174886 А 0,0 0,1 0,10,15174886 Д 0,1 0,2 0,10,5174886 И 0,3 0,6 0,30,724962 О 0,7 0,8 0,10,24962 В 0,2 0,2 0,10,4962 И 0,3 0,6 0,30,654 З 0,6 0,7 0,10,54 И 0,3 0,6 0,30,8 Р 0,6 0,8 0,20,0 Конец декодирования Это основная идея арифметического кодирования, его практическая реализация несколько сложнее. Некоторые проблемы можно заметить непосредственно из приведенного примера. Первая состоит в том, что декодеру нужно обязательно каким-либо образом дать знать об окончании процедуры декодирования, поскольку остаток 0,0 может означать букву а или последовательность аа, ааа, аааа и т.д. Решить эту проблему можно двумя способами. Во-первых, кроме кода данных можно сохранять число, представляющее собой размер кодируемого массива. Процесс декодирования в этом случае будет прекращен, как только массив на выходе декодера станет такого размера. Другой способ – включить в модель источника специальный символ конца блока, например #, и прекращать декодирование, когда этот символ появится на выходе декодера. Вторая проблема вытекает из самой идеи арифметического кодирования и состоит в том, что окончательный результат кодирования – конечный интервал – станет известен только по окончании процесса кодирования. Следовательно, нельзя начать передачу закодированного сообщения, пока не получена последняя буква исходного сообщения и не определен окончательный интервал? На самом деле в этой задержке нет необходимости. По мере того, как интервал, представляющий результат кодирования, сужается, старшие десятичные знаки его (или старшие биты, если число записывается в двоичной форме) перестают изменяться (посмотрите на приведенный пример кодирования). Следовательно, эти разряды (или биты) уже могут передаваться. Таким образом, передача закодированной последовательности осуществляется, хотя и с некоторой задержкой, но последняя незначительна и не зависит от размера кодируемого сообщения. И третья проблема – это вопрос точности представления. Из приведенного примера видно, что точность представления интервала (число десятичных разрядов, требуемое для его представления) неограниченно возрастает при увеличении длины кодируемого сообщения. Эта проблема обычно решается использованием арифметики с конечной разрядностью и отслеживанием переполнения разрядности регистров.

Дата добавления: 2020-02-04 ; просмотров: 1030 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Реферат: Алгоритмы сжатия данных 2

Алгоритмы сжатия данных

Энтропия и количество информации

Комбинаторная, вероятностная и алгоритмическая оценка количества информации

Моделирование и кодирование

Некоторые алгоритмы сжатия данных

BWT — преобразование и компрессор

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

Реализация алгоритма арифметического кодирования

Доказательство правильности декодирования

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

Переполнение и завершение

Адаптивная модель для арифметического кодирования

Приложение 1. Программный код

Приложение 2. Интерфейс программы

Основоположником науки о сжатии информации принято считать Клода Шеннона. Его теорема об оптимальном кодировании показывает, к чему нужно стремиться при кодировании информации и на сколько та или иная информация при этом сожмется. Кроме того, им были проведены опыты по эмпирической оценке избыточности английского текста. Он предлагал людям угадывать следующую букву и оценивал вероятность правильного угадывания. На основе ряда опытов он пришел к выводу, что количество информации в английском тексте колеблется в пределах 0.6 — 1.3 бита на символ. Несмотря на то, что результаты исследований Шеннона были по-настоящему востребованы лишь десятилетия спустя, трудно переоценить их значение.

Первые алгоритмы сжатия были примитивными в связи с тем, что была примитивной вычислительная техника. С развитием мощностей компьютеров стали возможными все более мощные алгоритмы. Настоящим прорывом было изобретение Лемпелем и Зивом в 1977 г. словарных алгоритмов. До этого момента сжатие сводилось к примитив­ному кодированию символов. Словарные алгоритмы позволяли кодир­овать повторяющиеся строки символов, что позволило резко повысить степень сжатия. Важную роль сыграло изобретение примерно в это же время арифметического кодирования, позволившего воплотить в жизнь идею Шеннона об оптимальном кодировании. Следующим прорывом было изобретение в 1984 г. алгоритма РРМ. Следует отметить, что это изобретение долго оставалось незамеченным. Дело в том, что алгоритм сложен и требует больших ресурсов, в первую очередь больших объемов памяти, что было серьезной проблемой в то время. Изобретенный в том же 1984 г. алгоритм LZW был чрезвычайно популярен благодаря своей простоте, хорошей рекламе и нетребовательности к ресурсам, несмотря на относительно низкую степень сжатия. На сегодняшний день алгоритм РРМ является наилучшим алгоритмом для сжатия текстовой информации, a LZW давно уже не встраивается в новые приложения (однако широко используется в старых).

Будущее алгоритмов сжатия тесно связано с будущим компью­терных технологий. Современные алгоритмы уже вплотную приблизи­лись к Шенноновской оценке 1.3 бита на символ, но ученые не видят причин, по которым компьютер не может предсказывать лучше, чем человек. Для достижения высоких степеней сжатия приходится использовать более сложные алгоритмы. Однако существовавшее одно время предубеждение, что сложные алгоритмы с более высокой степенью сжатия всегда более медленны, несостоятельно. Так, существуют крайне быстрые реализации алгоритмов РРМ для текстовой информации и SPIHT для графики, имеющие очень высокую степень сжатия.

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

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

Количество нужной человеку информации неуклонно растет. Объемы устройств для хранения данных и пропускная способность линий связи также растут. Однако количество информации растет быстрее. У этой проблемы есть три решения. Первое — ограничение количества информации. К сожалению, оно не всегда приемлемо. Например, для изображений это означает уменьшение разрешения, что приведет к потере мелких деталей и может сделать изображения вообще бесполезными (например, для медицинских или космических изображений). Второе — увеличение объема носителей информации и пропускной способности каналов связи. Это решение связано с материальными затратами, причем иногда весьма значительными. Третье решение — использование сжатия информации. Это решение позволяет в несколько раз сократить требования к объему устройств хранения данных и пропускной способности каналов связи без дополнительных издержек (за исключением издержек на реализацию алгоритмов сжатия). Условиями его применимости является избы­точность информации и возможность установки специального програм­много обеспечения либо аппаратуры как вблизи источника, так и вблизи приемника информации. Как правило, оба эти условия удовлетворяются.

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

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

При реализации алгоритма арифметического кодирования использовался язык C# и визуальная среда программирования Microsoft Visual Studio 2005. Язык C# имеет следующие преимущества: простота, объектная ориентированность, типовая защищенность, “сборка мусора”, поддержка совместимости версий, упрощение отладки программ.

Энтропия и количество информации

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

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

Комбинаторная, вероятностная и алгоритмическая оценка количества информации

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

Таким образом, для передачи состояния объекта достаточно I=log2N бит информации. Заметим, что количество информации может быть дробным. Разумеется, дробное количество информации невозможно сохранить на носителе или передать по каналам связи. В то же время, если необходимо передать либо сохранить большое количество блоков информации дробной длины, их всегда можно сгруппировать таким образом, чтобы полностью исключить потери (например, посредством арифметического кодирования).

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

Обозначим через р(у|х) условную вероятность того, что наступит событие у если событие х уже наступило. В таком случае условная энтропия для переменной Y, которая может принимать М значений yi с условными вероятностями р(уi|х) будет

Приведенные формулы показывают, что вне зависимости от того, как были получены вероятности наступления следующих событий, для кодирования события с вероятностью р достаточно — log2 p бит (в полном соответствии с теоремой Шеннона об оптимальном кодировании).

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

Моделирование и кодирование

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

Моделирование обеспечивает предсказание вероятности наступ­ления возможных событий, кодирование обеспечивает представление события в виде -log2p бит, где р — предсказанная вероятность наступ­ления события. Задача моделирования, как правило, более сложная. Это обусловлено высокой сложностью современных моделей данных. В то же время кодирование не является серьезной проблемой. Существует большое количество стандартных кодеров, различающихся по степени сжатия и быстродействию. Как правило, в системах сжатия исполь­зуемый кодер при необходимости может быть легко заменен другим.

Некоторые алгоритмы сжатия данных

Этот словарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977 г., но сам алгоритм разработан не позднее 1975 г.

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

Скользящее окно имеет длину N, т. е. в него помещается N символов, и состоит из двух частей:


■ последовательности длины W=N-n уже закодированных символов, которая и является словарем;

■ упреждающего буфера, или буфера предварительного просмотра, длины n; обычно и на порядки меньше W.

Пусть к текущему моменту времени мы уже закодировали t символов S1, S2, . St. Тогда словарем будут являться W предшествующих символов St-(W-1), St-(W-1)+1, …, St. Соответственно, в буфере находятся ожидающие кодирования символы St+1, St+2, …, St+n. Очевидно, что если W≥ t, то словарем будет являться вся уже обработанная часть входной последовательности.

Идея алгоритма заключается в поиске самого длинного совпадения между строкой буфера, начинающейся с символа St+1, и всеми фразами словаря. Эти фразы могут начинаться с любого символа St-(W-1), St-(W-1)+1,…, St выходить за пределы словаря, вторгаясь в область буфера, но должны лежать в окне. Следовательно, фразы не могут начинаться с St+1. поэтому буфер не может сравниваться сам с собой. Длина совпадения не должна превышать размера буфера. Полученная в результате поиска фраза St-(i-1), St-(i-1)+1, …, St-(i-1)+(j-1) кодируется с помощью двух чисел:

1) смещения (offset) от начала буфера, i;

2) длины соответствия, или совпадения (match length), j;

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

Таким образом, на каждом шаге кодер выдает описание трех объектов: смещения и длины соответствия, образующих код фразы, равной обработанной строке буфера, и одного символа s (литерала). Затем окно смещается на j+1 символов вправо и осуществляется переход к новому циклу кодирования. Величина сдвига объясняется тем, что мы реально закодировали именно j+1 символов: j с помощью указателя на фразу в словаре и 1(? i) с помощью тривиального копирования. Передача одного символа в явном виде позволяет разрешить проблему обработки еще ни разу не виденных символов, но существенно увеличивает размер сжатого блока.

Алгоритм LZ78, предложенный в 1978 г. Лемпелом и Зивом, нашел свое практическое применение только после реализации LZW84, предложенной Велчем в 1984 г.

Словарь является расширяющимся (expanding). Первоначально в нем содержится только 256 строк длиной в одну букву-все коды ASCII. В процессе работы словарь разрастается до своего максимального объема |Vmax| строк (слов). Обычно, объем словаря достигает нескольких десятков тысяч слов. Каждая строка в словаре имеет свою известную длину и этим похожа на привычные нам книжные словари и отличается от строк LZ77, которые допускали использование подстрок. Таким образом, количество слов в словаре точно равно его текущему объему. В процессе работы словарь пополняется по следующему закону:

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позиции pos исходного текста. Так как словарь первоначально не пустой, такое слово всегда найдется;

2. В выходной файл помещается номер найденного слова в словаре position и следующий символ из входного текста В (на котором обнаружилось различие) —

. Длина кода равна |position|+|B||=[logVmax]+8 (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте pos смещается на |strB|=|str|+l байт дальше к символу, следующему за В.

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

Птак как словарь увеличивается постепенно и одинаково для кодировщика и декодировщика, для кодирования позиции нет необходимости использовать [logVmax] бит, а можно брать лишь [logV] бит, где V-текущий объем словаря.

Самая серьезная проблема LZ78-переполнение словаря: если словарь полностью заполнен, прекращается его обновление и процесс сжатия может быть заметно ухудшен (метод FREEZE). Отсюда следует вывод-словарь нужно иногда обновлять. Самый простой способ как только словарь заполнился его полностью обновляют. Недостаток очевиден кодирование начинается на пустом месте, как бы с начала, и пока словарь не накопится сжатие будет незначительным, а дальше-замкнутый цикл опять очистка словаря. Поэтому предлагается словарь обновлять не сразу после его заполнения, а только после того, как степень сжатия начала падать (метод FLUSH). Более сложные алгоритмы используют два словаря, которые заполняются синхронно, но с задержкой на |V|/2 слов один относительно другого. После заполнения одного словаря, он очищается, а работа переключается на другой (метод SWAP). Еще более сложными являются эвристические методы обновления словарей в зависимости от частоты использования тех или иных слов (LRU, TAG).

Выходной код также формируется несколько иначе (сравните с предыдущим описанием):

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позицииpos исходного текста;

2. В выходной файл помещается номер найденного слова в словаре

. Длина кода равна |position|=[logV] (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте pos смещается на |str| байт дальше к символу В.

Алгоритм PPM (prediction by partial matching) — это метод контекстно-ограниченного моделирования, позволяющий оценить вероятность символа в зависимости от предыдущих символов. Строку символов, непосредственно предшествующую текущему символу, будем называть контекстом. Модели, в которых для оценки вероятности используются контексты длиной не более чем N, принято называть моделями порядка N.

Вероятность символа может быть оценена в контекстах разных порядков. Например, символ «о» в контексте «to be or not t» может быть оценен в контексте первого порядка «t», в контексте второго порядка «_t», в контексте третьего порядка «t_t» и т.д. Он также может быть оценен в контексте нулевого порядка, где вероятности символов не зависят от контекста, и в контексте минус первого порядка, где все символы равновероятны. Контекст минус первого порядка используется для того, чтобы исключить ситуацию, когда символ будет иметь нулевую вероятность и не сможет быть закодирован. Это может случиться, если вероятность символа не будет оценена ни в одном из контекстов (что возможно, если символ в них ранее не встречался).

Существуют два основных подхода к вычислению распределения вероятностей следующего символа на основе вероятностей символов в контекстах. Первый подход называется «полное перемешивание». Он предполагает назначение весов контекстам разных порядков и получение суммарных вероятностей сложением вероятностей символов в контекстах, умноженных на веса этих контекстов. Применение такого подхода ограничено двумя факторами. Во-первых, не существует быстрой реализации данного алгоритма. Во-вторых, не разработан эффективный алгоритм вычисления весов контекстов. Примитивные же подходы не обеспечивают достаточно высокой точности оценки и, как следствие, степени сжатия.

Второй подход называется «методом исключений». При этом подходе сначала делается попытка оценить символ в контексте самого высокого порядка. Если символ кодируется, алгоритм переходит к кодированию следующего символа. В противном случае кодируется «уход» и предпринимается попытка закодировать символ в контексте меньшего порядка. И так далее, пока символ не будет закодирован.

BWT — преобразование и компрессор

BWT-компрессор (Преобразование Барроуза – Уиллера) — сравнительно новая и революционная техника для сжатия информации (в особенности-текстов), основанная на преобразовании, открытом в 1983 г. и описанная в 1994 г… BWT является удивительным алгоритмом. Во-первых, необычно само преобразование, открытое в научной области, далекой от архиваторов. Во-вторых, даже зная BWT, не совсем ясно, как его применить к сжатию информации. В-третьих, BW преобразование чрезвычайно просто. И, наконец, сам BWT компрессор состоит из «магической» последовательности нескольких рассмотренных ранее алгоритмов и требует, поэтому, для своей реализации самых разнообразных программных навыков.

BWT не сжимает данные, но преобразует блок данных в формат, исключительно подходящий для компрессии. Рассмотрим его работу на упрощенном примере. Пусть имеется словарь V из N символов. Циклически переставляя символы в словаре влево, можно получить N различных строк длиной N каждая. В нашем примере словарь-это слово V=«БАРАБАН» и N=7. Отсортируем эти строки лексикографически и запишем одну под другой:

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

Фактический «выход» преобразования состоит из строки L=«РББАНАА» и первичного индекса I, показывающего, какой символ из L является действительным первым символом словаря V (в нашем случае I=2). Зная L и I можно восстановить строку V.

Этот алгоритм кодиро­вания информации был предложен Д.А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.

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

2. Выбираются два свободных узла дерева с наименьшими весами.

3. Создается их родитель с весом, равным их суммарному весу.

4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

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

Допустим, у нас есть следующая таблица частот:

На первом шаге из листьев дерева выбираются два с наименьшими весами — Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавливается в 5+6 = 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д — ветви 1.

На следующем шаге то же происходит с узлами Б и В, так как теперь эта пара имеет самый меньший вес в дереве. Создается новый узел с весом 13, а узлы Б и В удаляются из списка свободных. После всего этого дерево кодирования выглядит так, как показано на рис. 2.

Рис. 2. Дерево кодирования Хаффмана после второго шага

На следующем шаге «наилегчайшей» парой оказываются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д—ветви 1.


На последнем шаге в списке свободных осталось только два узла — это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям.

Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Н-дерево представлено на рис. 3.

Рис. 3. Окончательное дерево кодирования Хаффмана

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

Дня данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

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

Классический алгоритм Хаффмана имеет один существенный недостаток. Дня восстановления содер­жимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Н-дерева), другого для собственно кодирования.

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

Арифметическое сжатие — достаточно изящный метод, в основе которого лежит очень простая идея. Мы представляем кодируемый текст в виде дроби, при этом строим дробь таким образом, чтобы наш текст был представлен как можно компактнее. Для примера рассмотрим построение такой дроби на интервале [0, 1) (0 — включается, 1 — нет). Интервал [0, 1) выбран потому, что он удобен для объяснений. Мы разбиваем его на подынтервалы с длинами, равными вероятностям появления символов в потоке. В дальнейшем будем называть их диапазонами соответствующих символов.

Илон Маск рекомендует:  Что такое код swffill &#62;skewyto

Пусть мы сжимаем текст «КОВ.КОРОВА» (что, очевидно, означает «коварная корова»). Распишем вероятности появления каждого символа в тексте (в порядке убывания) и соответствующие этим символам диапазоны:

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

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

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

Примечания

Ссылки

  • (August 13, 2001) Dr. Dobb’s Data Compression Newsletter
Методы сжатия
Теория
Информация Собственная · Взаимная · Энтропия · Условная энтропия · Сложность · Избыточность
Единицы измерения Бит · Нат · Ниббл · Хартли · Формула Хартли
Без потерь
Энтропийное сжатие Алгоритм Хаффмана · Адаптивный алгоритм Хаффмана · Алгоритм Шеннона — Фано · Арифметическое кодирование (Интервальное) · Коды Голомба · Дельта · Универсальный код (Элиаса · Фибоначчи)
Словарные методы RLE · Deflate · LZ (LZ77/LZ78 · LZSS · LZW · LZWL · LZO · LZMA · LZX · LZRW · LZJB · LZT)
Прочее RLE · CTW · BWT · MTF · PPM · DMC
Аудио
Теория Свёртка · PCM · Алиасинг · Дискретизация · Теорема Котельникова
Методы LPC (LAR · LSP) · WLPC · CELP · ACELP · A-закон · μ-закон · MDCT · Преобразование Фурье · Психоакустическая модель
Прочее Компрессор аудиосигнала · Сжатие речи · Полосное кодирование
Изображения
Термины Цветовое пространство · Пиксель · Субдискретизация насыщенности · Артефакты сжатия
Методы RLE · DPCM · Фрактальный · Вейвлетный · EZW · SPIHT · LP · ДКП · ПКЛ
Прочее Битрейт · Test images · PSNR · Квантование
Видео
Термины Характеристики видео · Кадр · Типы кадров · Качество видео
Методы Компенсация движения · ДКП · Квантование · Вейвлетный
Прочее Видеокодек · Rate distortion theory (CBR · ABR · VBR)

Wikimedia Foundation . 2010 .

Смотреть что такое «Арифметическое кодирование» в других словарях:

Адаптивное арифметическое кодирование — Содержание 1 Введение 2 Алгоритм 3 Пример 4 Реализация кодера … Википедия

Кодирование энтропии — кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных коды, длины которых… … Википедия

Кодирование с минимальной избыточностью — Кодирование энтропии кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных… … Википедия

Кодирование длин серий — (англ. Run length encoding, RLE) или Кодирование повторов простой алгоритм сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании… … Википедия

Кодирование Шеннона-Фано — Алгоритм Шеннона Фано один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм… … Википедия

Кодирование Хаффмана — Алгоритм Хаффмана (англ. Huffman) адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. В настоящее… … Википедия

Кодирование Голомба — Коды Голомба это семейство энтропийных кодеров, являющихся общим случаем унарного кода. Также под кодом Голомба может подразумеваться один из представителей этого семейства. Код Голомба позволяет представить последовательность символов в виде… … Википедия

Дельта-кодирование — Для термина «Кодирование» см. другие значения. Дельта кодирование (англ. Delta encoding) способ представления данных в виде разницы (дельты) между последовательными данными вместо самих данных. Пожалуй, наиболее простой пример… … Википедия

Энтропийное кодирование — Для термина «Кодирование» см. другие значения. Энтропийное кодирование кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных (длины последовательности) с помощью усреднения… … Википедия

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

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

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

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

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

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

    Кодировщик переделывает символ на входе в код на выходе, используя вероятности символов, которые поставляет ему моделировщик. В данной статье речь пойдет о двух самых распространенных и известных методах кодирования информации во время сжатия: кодирование Хаффмана (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 г.

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

    Основные тенденции статистического метода арифметического кодирования текстовой информации и последовательностей дискретных данных Текст научной статьи по специальности « Автоматика. Вычислительная техника»

    Аннотация научной статьи по автоматике и вычислительной технике, автор научной работы — Журавка Андрей Викторович, Шевченко Людмила Петровна

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

    Похожие темы научных работ по автоматике и вычислительной технике , автор научной работы — Журавка Андрей Викторович, Шевченко Людмила Петровна,

    An introduction to the statatistical method of arithmetic coding of text’s compression and signals

    Up-to-day, it’s particulary important to provide computer resources computer according to the compressed data represantation. Rapidly increasing data transmission and space reduction of data’s storage considerably improve computer’s features and meaningfully save costs.

    Текст научной работы на тему «Основные тенденции статистического метода арифметического кодирования текстовой информации и последовательностей дискретных данных»

    ОСНОВНЫЕ ТЕНДЕНЦИИ СТАТИСТИЧЕСКОГО МЕТОДА АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ ТЕКСТОВОЙ ИНФОРМАЦИИ И ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДИСКРЕТНЫХ ДАННЫХ

    ЖУРАВКА А. В, ШЕВЧЕНКО Л. П.___________

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

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

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

    Решаемые задачи. Допустим, необходимо закодировать методом арифметического сжатия такую последовательность дискретных данных: ‘sail!’ алфавита (a,

    Символ Вероятность Интервал

    s, l, o, y, !) модель с постоянными вероятностями, заданными в табл. 1.

    Описание алгоритма и его реализация. Кодировщику и декодировщику известно, что в самом начале интервал соответствует [0; 1). После просмотра первого символа ‘s’ кодировщик сужает интервал до [0,2; 0,5), который модель выделяет этому символу. Второй символ ‘а’ сузит этот новый интервал до первой его пятой части, поскольку для ‘а’ выделен фиксированный интервал [0,0; 0,2). В результате получим рабочий интервал [0,2;

    0,26), так как предыдущий интервал имел ширину в 0,3 единицы

    — одна пятая от него 0,06. Следующему символу ‘l’ соответствует фиксированный интервал [0,5; 0,6), что применительно к рабочему интервалу [0,2; 0,26) суживает его до интервала [0,23; 0,236). Следуя алгоритму, получим табл. 2.

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

    Для фиксированной модели, задаваемой алфавитом, приведенным в табл. 1, энтропия исследуемого текста вычисляется по известной формуле:

    — lg 0.3 — lg 0.2 — lg 0.1 — lg 0.1 — ig 0.1= — ig 0.00006

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

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

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

    /* С каждым символом текста обращаться к процедуре encode_symbol() */

    /* Проверить, что “завершающий” символ закодирован последним */

    /* Вывести полученное значение интервала [low; high) */

    encode_symbol(symbol,cum_freq) range = high — low

    high = low + range*cum_freq[symbol-1] low = low + range*cum_freq[symbol]

    /* Value — это поступившее на вход число */

    /* Обращение к процедуре decode_symbol() пока она не возвратит */

    decode_symbol(cum_freq) поиск такого символа, что

    cum_freq[symbol] i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

    По мере сужения кодового интервала старшие биты low и high становятся одинаковыми, поэтому могут быть переданы немедленно, так как на них будущие сужения интервала все равно уже не будут влиять. Поскольку мы знаем, что low = Half) <

    low = 2 * (low — Half);

    high = 2 * (high — Half) + 1;

    гарантирующую, что после ее завершения будет спреведливо неравенство: low i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

    value = 2 * (value — Half) + шр^^кО;

    low = 2 * (low — Half);

    high = 2 * (high — Half) + 1;

    Доказательство правильности декодирования

    Проверим верность определения процедурой decode_symbol() следующего символа. Из псевдокода в программе 1 видно, что decode_symbol() должна использовать value для поиска символа, сократившего при кодировании рабочий интервал так, что он продолжает включать в себя value. Строки в decode_symbol() определяют символ, таким образом, что value лежит внутри нового интервала, вычисляемого процедурой decode_symbol() в строках. Это определенно гарантирует корректность определения каждого символа операцией декодирования.

    Отрицательное переполнение. Как показано в псевдокоде, арифметическое кодирование работает при помощи масштабирования накопленных вероятностей, поставляемых моделью в интервале [low; high] для каждого передаваемого символа. Предположим, что low и high настолько близки друг к другу, что

    операция масштабирования приводит полученные от модели разные символы к одному целому числу, входящему в [low; high]. В этом случае дальнейшее кодирование продолжать невозможно. Следовательно, кодировщик должен следить за тем, чтобы интервал [low; high] всегда был достаточно широк. Простейшим способом для этого является обеспечение ширины интервала не меньшей Max_frequency— максимального значения суммы всех накапливаемых частот.

    Как можно сделать это условие менее строгим? Объясненная выше операция битового сдвига гарантирует, что low и high могут только тогда становиться опасно близкими, когда заключают между собой Half. Предположим, они становятся настолько близки, что

    First_qtr i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

    Ограниченность реализации. Ограничения, связанные с длиной слова и вызванные возможностью переполнения, можно обобщить, полагая, что счетчики частот представляются f битами, а code_va1ues — c битами. Программа будет работать корректно при f = cum_freq[i];

    . никогда не делается попытка кодировать символ i, для которого

    . cum_freq[0] i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

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

    Адаптивная модель. Адаптивная модель изменяет частоты уже найденных в тексте символов. В начале все счетчики могут быть равны, что отражает отсутствие начальных данных, но по мере просмотра каждого входного символа они изменяются, приближаясь к наблюдаемым частотам. И кодировщик, и декодировщик используют одинаковые начальные значения (например, равные счетчики) и один и тот же алгоритм обновления, что позволяет их моделям всегда оставаться на одном уровне. Кодировщик получает очередной символ, кодирует его и изменяет модель. Декодировщик определяет очередной символ на основании своей текущей модели, а затем обновляет ее.

    Вторая часть Программы 2 демонстрирует такую адаптивную модель, рекомендуемую для использования в Программе 1, поскольку на практике она превосходит фиксированную модель по эффективности сжатия. Инициализация проводится так же, как для фиксированной модели, за исключением того, что все частоты устанавливаются в 0. Процедура ^date_mode1 (symbol) вызывается из encode_symbol() и decode_symbo1() (Программа 1) после обработки каждого символа.

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

    2). Затем, если необходимо, update_mode1() переупорядочивает символы для того, чтобы разместить текущий в его правильной категории относительно частотного порядка, чередуя для отражения изменений перекодировочные таблицы. В итоге процедура увеличивает значение соответствующего счетчика частоты и приводит в порядок соответствующие накопленные частоты.

    2. Основные характеристики и сравнительный анализ

    Рассмотрим показатели эффективности сжатия и времени выполнения известного программного обеспечения, реализующего практическое примененение арифметического кодирования (программы 1).

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

    относительно использованной для кодирования модели. Три фактора вызывают ухудшение этой характеристики:

    (1) расходы на завершение текста;

    (2) использование арифметики небесконечной точности;

    (3) такое масштабирование счетчиков, что их сумма не превышает Max_frequency.

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

    Арифметическое кодирование должно досылать дополнительные биты в конец каждого текста, совершая такимобразом дополнительные усилия на завершение текста. Для ликвидации неясности с последним символом процедура done_encoding() (Программа 1) посылает два бита.

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

    Дополнительные затраты на масштабирование счетчиков отчасти больше, но все равно очень малы. Для коротких текстов (меньших 2Л14 байт) их нет. Но даже с текстами в 10л5 — 10л6 байтов накладные расходы, подсчитанные экспериментально, составляют менее 0,25% от кодируемой строки.

    Адаптивная модель в Программе 2, при угрозе превышения общей суммой накопленных частот значение Max_frequency, уменьшает все счетчики. Это приводит к тому, что взвешивать последние события тяжелее, чем более ранние. Таким образом, показатели имеют тенденцию прослеживать изменения во входной последовательности, которые могут быть очень полезными. (Мы сталкивались со случаями, когда ограничение счетчиков до 6-7 битов давало лучшие результаты, чем повышение точности арифметики). Это зависит от источника, к которому применяется модель.

    Время выполнения. Программа 1 была написана скорее для ясности, чем для скорости. При выполнении ее вместе с адаптивной моделью из Программы 2 потребовалось около 420 мкс на байт исходного текста на ЭВМ VAX-11/780 для кодирования и почти столько же для декодирования. Однако легко устраняемые расходы, такие как вызовы некоторых процедур, создающие многие из них, и простая оптимизация увеличивают скорость в 2 раза. В приведенной версии программы на языке Си были сделаны следующие изменения:

    (1) процедуры шри1_Ьк(), output_bit() и bit_p1us_fo11ow() были переведены в макросы, устранившие расходы по вызову процедур;

    (2) часто используемые величины были помещены в регистровые переменные;

    (3) умножения на 2 были заменены добавлениями (“+=”);

    (4) индексный доступ к массиву в циклах Программ 1 и 2 адаптивной модели был заменен операциями с указателями.

    Эта среднеоптимизированная реализация на Си имела время выполнения 214/252 мкс на входной байт, для кодирования/декодирования 100.000 байтов английского текста на VAX-11/780. Кодирование программы на Си одной и той же длины везде осуществляется несколько дольше, исключая только лишь двоичные объектные файлы. В тестовый набор были включены два искусственных файла, чтобы позволить читателям повторять результаты. 100000-байтный “алфавит” состоит из повторяемого 26-буквенного алфавита. “Асимметричные показатели” содержит 10000 копий строки “aaaabaaaac”. Эти примеры показывают, что файлы могут быть сжаты плотнее, чем 1 бит/символ (12092-байтный выход равен 93736 битам). Все приведенные результаты получены с использованием адаптивной модели из Программы 2.

    Дальнейшее снижение в 2 раза временных затрат может быть достигнуто перепрограммированием приведенной программы на язык ассемблера. Тщательно оптимизированная версия Программ 1 и 2 (адаптивная модель) была реализована для VAX.

    Временные характеристики ассемблерной реализации на VAX-11/780 даны в табл. 3. Они были получены при использовании возможности профиля UNIX и точны только в пределах 10%. (Этот механизм создает гистограмму значений программного счетчика прерываний часов реального времени и страдает от статистической вариантности также, как и некоторые системные ошибки). “Вычисление границ” относится к начальным частям encode_symbol() и decode_symbol() (программа 1), которые содержат операции умножения и деления. “Сдвиг битов” — это главный цикл в процедурах кодирования и декодирования. Требующее умножения и деления вычисление cum в decode_symbol(), а также последующий цикл для определения следующего символа есть “декодирование символа”. А “обновление модели” относится к адаптивной процедуре update_model() из Программы 2.

    Как и предполагалось, вычисление границ и обновление модели требуют одинакового количества времени и для кодирования, и для декодирования в пределах ошибки эксперимента. Сдвиг битов осуществляется быстрее для текстовых файлов, чем для Си-программ и объектных файлов из-за лучшего его сжатия. Дополнительное время для декодирования по сравнению с кодированием возникает из-за шага “декодирование символа” — цикла в строке, выполняемого чаще (в среднем 9, 13 и 35 раз соответственно). Это также влияет на время обновления модели, так как связано с количеством накапливающих

    Тип последовательностей данных Время кодирования, мкс Время декодирования, мкс

    Текстовые файлы 104 135

    Вычисление границ 32 31

    Сдвиг битов 39 30

    Обновление модели 29 29

    Си-программы 109 151

    Вычисление границ 30 28

    Сдвиг битов 42 35

    Обновление модели 33 36

    Объектный файл 158 241

    Вычисление границ 34 31

    Сдвиг битов 46 40

    Обновление модели 75 75

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

    Адаптивное сжатие текстов. Результаты сжатия, достигнутые Программами 1 и 2, варьируются от 4,8-5,3 битов/символ для коротких английских текстов (10л3 -10л4 байтов) до 4,5-4,7 битов/символ для длинных (10Л5-10Л6 байтов). Хотя существуют и адаптивные техники Хаффмана, они все же испытывают недостаток концептуальной простоты, свойственной арифметическому кодированию. При сравнении они оказываются более медленными. Небрежная проверка compact показывает, что внимание к оптимизации для обеих систем сравнимо при том, что арифметическое кодирование выполняется в 2 раза быстрее. Показатели сжатия в некоторой степени лучше у арифметического кодирования для всех тестовых файлов. Различие будет заметным в случае применения более сложных моделей, предсказывающих символы с вероятностями, зависящими от определенных обстоятельств (например, следования за буквой q буквы u).

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

    равной степени двойки, чтобы операции деления при вычислении границ (Программа 1) выполнялись через сдвиги. Для реализации на ассемблере VAX-11/ 780 время кодирования/декодирования составило 60-90 мкс. Аккуратно написанная реализация кодирования Хаффмана с использованием таблиц просмотра для кодирования и декодирования будет выполняться немного быстрее.

    Кодирование черно-белых изображений. Применение для этих целей арифметического кодирования было рассмотрено Лангдоном и Риссаненом, получившим при этом блестящие результаты с помощью модели, использующей оценку вероятности цвета точки относительно окружающего ее некоторого шаблона. Он представляет собой совокупность из 10 точек, лежа-ших сверху и спереди от текущей, поэтому при сканировании растра они ей предшествуют. Это создает 1024 возможных контекста, относительно которых вероятность черного цвета у данной точки оценивается адаптивно по мере просмотра изображения. После этого каждая полярность точки кодировалась арифметическим методом в соответствии с данной вероятностью. Такой подход улучшил сжатие на 2030% по сравнению с более ранними методами. Для увеличения скорости кодирования Лангдон и Рисса-нен применили приблизительный метод арифметического кодирования, который избежал операций умножения путем представления вероятностей в виде целых степеней дроби 1/2. Кодирование Хаффмана для этого случая не может быть использовано прямо, поскольку оно никогда не выполняет сжатия двухсимвольного алфавита. Другую возможность для арифметического кодирования представляет применяемый к такому алфавиту популярный метод кодирования длин тиражей (run-length method). Модель здесь приводит данные к последовательности длин серий одинаковых символов (например, изображения представляются длинами последовательностей черных точек, идущих за белыми, следующих за черными, которым пре-дшествуют белые, и т.д.). В итоге должна быть передана последовательность длин. Стандарт факсимильных аппаратов CCITT строит код Хаффмана на основе частот, с которыми черные и белые последовательности разных длин появляются в образцахдокументов. Фиксированное арифметическое кодирование, которое будет использовать те же частоты, будет иметь лучшие характеристики, а адаптация таких частот для каждого отдельного документа будет работать еще лучше.

    Кодирование произвольно распределенных целых чисел

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

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

    Литература: 1. Langdon G.G. An introduction to arithmetic coding. IBM Res. Беуек>р. 1984. Vol. 28, № 2. Р.135-149. 2. Rubin F. ЕхрєпшєП^ in text file compression. C^to^ia, 1997. Vol. 3.

    Поступила в редколлегию 19.01.2000

    Рецензент:д-р физ.-мат. наук, проф. Слесаренко А.П.

    Журавка Андрей Викторович, аспирант кафедры информатики ХГТУСА ведущий инженер кафедры страхового, биржевого и банковского дела. Научные интересы: проблемы архивации текстовой информации и последовательностей дискретных данных. Увлечения и хобби: компьютерная техника, иностранные языки, туризм. Адрес: Украина, 61002, Харьков, ул. Сумская, 40, тел. 40-29-46.

    Шевченко Людмила Петровна, д-р физ.-мат. наук, профессор, зав. кафедрой информатики ХГТУСА. Научные интересы: математическое моделирование, объектно-ориентированное программирование. Увлечения и хобби: компьютерная техника, иностранные языки, туризм. Адрес: Украина, 61002, Харьков, ул. Сумская, 40, тел. 40-29-25.

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

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

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

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

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

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

      Кодировщик переделывает символ на входе в код на выходе, используя вероятности символов, которые поставляет ему моделировщик. В данной статье речь пойдет о двух самых распространенных и известных методах кодирования информации во время сжатия: кодирование Хаффмана (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 г.

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

      Матричное кодирование

      Читайте также:

      1. Адаптивное арифметическое кодирование
      2. Адаптивные алгоритмы сжатия. Кодирование Хаффмена
      3. Арифметическое кодирование
      4. Внутреннее кодирование
      5. Двоичное кодирование звуковой информации в компьютере
      6. Двоичное кодирование чисел
      7. Декодирование по LZW
      8. Декодирование циклических кодов
      9. Кодирование
      10. Кодирование графической информации
      11. Кодирование графической информации.
      12. Кодирование данных

      Ранее каждая схема кодирования описывалась таблицами, задающими кодовое слово длины n для каждого исходного слова длины m. Для блоков большой длины этот способ требует большого объема памяти и поэтому непрактичен. Например, для (16, 33)-кода потребуется 33 * 2 16 = 2 162 688 бит.

      Гораздо меньшего объема памяти требует матричное кодирование. Пусть E матрица размерности m × n, состоящая из элементов eij, где i — это номер строки, а j — номер столбца. Каждый из элементов матрицы eij может быть либо 0, либо 1. Кодирование реализуется операцией b = аЕ или где кодовые слова рассматриваются как векторы, т.е как матрицы-строки
      размера 1 × n.

      Пример. Рассмотрим следующую 3 × 6-матрицу:

      Тогда кодирование задается такими отображениями: 000 → 000000, 001 → 001111, 010 → 010011, 011 → 011100, 100 → 100110, 101 → 101001, 110 → 110101, 111 → 111010.

      Рассмотренный пример показывает преимущества матричного кодирования: достаточно запомнить m кодовых слов вместо 2 m слов. Это общий факт.

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

      Матричные коды называют также линейными кодами. Для линейных (n − r, n)-кодов с минимальным расстоянием Хэмминга d существует нижняя граница Плоткина (Plotkin) для минимального количества контрольных разрядов r
      при n³ 2d − 1,

      | следующая лекция ==>
      Математическая модель системы связи | Групповые коды

      Дата добавления: 2014-01-04 ; Просмотров: 1079 ; Нарушение авторских прав? ;

      Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

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

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

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

      Как правило, превосходит алгоритм Хаффмана по эффективности сжатия, позволяет сжимать данные с энтропией, меньшей 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). Это позволяет определить первый символ, который был выбран кодировщиком, поэтому его значение выводится как первый символ декодированного сообщения.

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