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

При ответе на данный вопрос необходимо дать понятие «адаптивное арифметическое кодирование» и рассказать об алгоритме построения такого кода.

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

Рассмотрим на примере алгоритм адаптивного арифметического кодирования. Пусть требуется закодировать сообщение S = «bab!». Известен первичный алфавит символов {a, b, !}, но неизвестны вероятности их использования.

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

Итак, на первом этапе вес символов «a», «b» и «!» одинаков и равен 1. Соответственно, вероятности использования каждого символа также одинаковы и равны 1/3. Разделим рабочий отрезок [0; 1) на три равные части длиной 1/3:

Первая часть соответствует букве «a», вторая букве «b», третья — символу «!». Первый символ сообщения S — буква «b». Ей соответствует отрезок [1/3; 2/3). Теперь он будет новым рабочим отрезком.

Вес буквы «b» увеличивается на единицу, веса остальных символов не изменяются. Суммарный вес всех символов меняется (сейчас он равен 1 + 2 + 1 = 4). Соответственно изменяются и вероятности использования символов: символ «а» имеет вероятность 1/4, символ «b» - вероятность 2/4 или 1/2, символ «!» - вероятность 1/4. Отношение вероятностей 1:2:1. Именно в этом отношении необходимо разделить новый рабочий отрезок (т. е. отрезок нужно разделить на 4 части длиной 1/12 каждая, по одной части отдать символам «а» и «!», две части отдать символу «b», сохранив при этом первоначальный порядок следования букв):

Следующая буква в сообщении S — буква «а». Ее рабочий отрезок [1/3; 5/12). Вес буквы «а» увеличивается на единицу. Суммарный вес всех символов теперь равен 2 + 2 + 1 = 5. Вероятности использования символов: Р_а =2/5, Р_b =2/5, Р_! =1/5. Отношение вероятностей 2:2:1. Отрезок [1/3; 5/12) делим следующим образом:

В сообщении S появляется новый символ: «b». Ей соответствовал отрезок [11/30; 12/30). Переходим к этому новому рабочему отрезку. Делим его на 6 равных частей, ведь суммарный вес символов увеличился на единицу, вследствие увеличения на единицу веса символа «b». Букве «а» соответствует две части из полученных шести, букве «b» - три части, символу «!» - одна часть:

Последний символ сообщения S — признак конца строки «!». Его рабочий отрезок на данном этапе кодирования [71/180; 12/30). Любое число из этого отрезка может быть выбрано в качестве кода сообщения S. Например 71/180 ≈ 0,394.

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

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