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

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

Обозначим:

l_i - нижняя граница отрезка, соответствующего i- той букве исходного      

сообщения;

h_i - верхняя граница этого отрезка;

r_i - длина отрезка [l_i, h_i);

m - порядковый номер кодируемой буквы в алфавите источника;

Q – массив для величин Q_i.

 

    l₀:=0; h₀:=1; r₀:=1; i:=0

    DO (not EOF)

    C:=Read() (читаем следующий символ из файла)

    i:=i+1

    DO (j=1,…,n)

              IF (C=a_j) m:=j FI

    OD

    l_i = l_i-1 + r_i-1·Q [m-1]

    h_i = l_i-1 + r_i-1·Q [m]

    r_i = h_i - l_i

    OD

 

В начале декодирования известен конечный интервал, например, [0.56112; 0.5616) или любое число из этого интервала, например, 0.56112. Сразу можно определить, что первым закодированным символом был а ₃, так как число 0.56112 лежит в интервале [0.5; 0.7), выделенном символу а ₃. Затем в качестве интервала берется [0.5; 0.7) и в нем определяется диапазон, соответствующий числу 0.56112. Это интервал [0.52, 0.6), выделенный символу а ₂ и т.д. Для декодирования необходимо знать количество закодированных символов и исходные вероятности символов.

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

Обозначим:

l_i - нижняя граница отрезка, соответствующего i- той букве исходного

сообщения;

h_i - верхняя граница этого отрезка;

r_i - длина отрезка [l_i, h_i);

Q – массив для величин Q_i;

length – количество закодированных символов;

value – значение из входного файла.

 

    l₀:=0; h₀:=1; r₀:=1;

    value:=ReadCode();  (читаем код из файла)

    DO (i=1,…,length)

    DO (j=1,…,n)

              l_i = l_i-1 + r_i-1·Q [j-1]

              h_i = l_i-1 + r_i-1·Q [j]

              r_i = h_i - l_i

                       IF ((l_i <= value) и (value< h_i ) OD FI

              OD

              Write(a[i])  (пишем символ в выходной файл)

    OD

 

При реализации арифметического кодирования возникают две проблемы:

− необходима арифметика с плавающей точкой теоретически неограниченной точности;

− результат кодирования становится известен только после окончания входного потока.

Для решения этих проблем реальные алгоритмы работают с целыми числами и оперируют с дробями, числитель и знаменатель которых являются целыми числами (например, знаменатель равен 10000h = 65536, l ₀ = 0, h ₀=65535). При этом с потерей точности можно бороться, отслеживая сближение l_i и h_i и умножая числитель и знаменатель представляющей их дроби на одно и то же число, например на 2. С переполнением сверху можно бороться, записывая старшие биты l_i и h_i в файл только тогда, когда они перестают меняться (т.е. уже не участвуют в дальнейшем уточнении интервала), когда l_i и h_i одновременно находятся в верхней или нижней половине интервала.

Порядок выполнения работы

1. Изучить теоретический материал.

2. Закодировать арифметическим кодом текст на английском языке, использовать файл не менее 1 Кб.

3. Вычислить коэффициент сжатия данных как процентное отношение длины закодированного файла к длине исходного файла.

4. Определить зависимость коэффициента сжатия данных от длины блока при арифметическом кодировании.

5. Декодировать файл, закодированный арифметическим кодом, и сравнить полученный файл с исходным текстом на английском языке.

Контрольные вопросы

1. Как зависит средняя длина кодового слова от длины блока при арифметическом кодировании?

2. Как формируется кодовое слово для последовательности символов при арифметическом кодировании?

3. Сколько двоичных разрядов необходимо взять для арифметического кодирования k исходных символов, чтобы декодирование было возможным?

4. Как осуществляется арифметическое декодирование?

5. Какие проблемы возникают при реализации арифметического кодирования?

 

 

Лабораторная работа № 3

Тема: Код Шеннона.