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

Алгоритм:

• Каждому символу сопоставляется его вес: вначале он для всех равен 1.

• Все символы располагаются в естественном порядке, например, по возрастанию.

• Вероятность каждого символа устанавливается равной его весу, деленному на суммарный вес всех символов.

• После получения очередного символа и постройки интервала для него, вес этого символа увеличивается на 1 (можно увеличивать вес любым регулярным способом).

Пример 6: Пусть заданное множество - это символы A, B, C. Сжимаемое сообщение – «ВАС». Введем маркер конца сообщения - E.

Нам потребуется закодировать сообщение «ВАСЕ».

1 шаг: Располагаем на интервале [0,1] граничные точки отрезков соответствующих символов алфавита сначала равные по величине. Указываем их веса пока, так же одинаковые.

2 шаг: Первый символ в кодируемом сообщении это символ «В», поэтому увеличиваем вес символа «В», теперь он =2. Суммарный вес всех символов 5.

3 шаг: Располагаем на интервале [1/4,2/4] граничные точки отрезков пропорциональные вероятностям соответствующих символов алфавита.

Пересчитываем значения граничных точек символов алфавита на новом интервале [1/4,2/4]  [0.25, 0.5].

Правая граница символа «А» 1/4+(1/4*1/5)=6/20 = 0,3

а теперь словами озвучим эту формулу – к началу нового интервала (1/4) прибавляем длину пропорционального отрезка «А» (это длина отрезка с которым работаем {В} на текущем шаге умноженная на вес символа А на текущем шаге/суммарный вес).

Правая граница символа «В» 6/20+(1/4*2/5)=8/20=0.4,

а теперь словами озвучим эту формулу – к началу нового интервала (6/20) прибавляем длину пропорционального отрезка «В» (это длина В на предыдущем (1/4) шаге умноженное на его вес на текущем шаге/суммарный вес=2/5).

Левой граница символа «Е»= правой границе «С» = 8/20+(1/4*1/5)=9/20=0.45.

4 шаг: Далее нужно закодировать следующий символ исходной последовательности «ВАСЕ» - это символ «А».

Увеличиваем вес символа «А», теперь он =2. Суммарный вес всех символов 6.

5 шаг: Располагаем на интервале [1/4,6/20] граничные точки отрезков пропорциональные вероятностям соответствующих символов алфавита.

Пересчитываем значения граничных точек символов алфавита на новом интервале [1/4,6/20]  [0.25, 0.3].

Правая граница символа «А» 1/4+(1/20*2/6)=15/60+1/60=16/60=0,26667

а теперь словами озвучим эту формулу – к началу нового интервала (1/4) прибавляем длину пропорционального отрезка «А» (это длина отрезка в котором работаем =6/20-1/4=6/20-5/20=1/20 умноженная на его вес А на текущем шаге /суммарный вес=2/6).

Правая граница символа «В» 16/60+(1/20*2/6)=17/60= 0,283333,

а теперь словами озвучим эту формулу – к началу нового интервала (5/16) прибавляем длину пропорционального отрезка «В» (это длина отрезка в котором работаем =6/20-1/4=6/20-5/20=1/20 умноженное на вес В на текущем шаге /суммарный вес =2/6).

Левой граница символа «Е»= правой границе символа «С» = 17/60+(1/20*1/6)=34/120+1/120=35/120=7/24=0,291667

6 шаг: Далее нужно закодировать следующий символ исходной последовательности «ВАСЕ» - это символ «С».

Увеличиваем вес символа «С», теперь он =2. Суммарный вес всех символов 7.

7 шаг: Располагаем на интервале [17/60, 7/24] граничные точки отрезков пропорциональные вероятностям соответствующих символов алфавита.

Пересчитываем значения граничных точек символов алфавита на новом интервале [17/60, 7/24]  [0.28333, 0.291667].

Правая граница символа «А» 17/60+(1/120*2/7)=119/420+1/420=120/420=0,285714

а теперь словами озвучим эту формулу – к началу нового интервала (17/60) прибавляем длину пропорционального отрезка «А» (это длина отрезка в котором работаем =7/24-17/60=(35-34)/120=1/120 умноженная на его вес А на текущем шаге /суммарный вес=2/7).

Правая граница символа «В» 120/420+(1/120*2/7)= 120/420+1/420= 121/420=0,288095,

а теперь словами озвучим эту формулу – к началу нового интервала (120/420) прибавляем длину пропорционального отрезка «В» (это длина отрезка в котором работаем =7/24-17/60=(35-34)/120=1/120 умноженное на вес В на текущем шаге /суммарный вес =2/7).

Левой граница символа «Е»= правой границе символа «С» = 121/420+(1/120*2/7)= 120/420+1/420= 122/420=0,290476,

8 шаг: Далее нужно закодировать последний символ исходной последовательности «ВАСЕ» - это символ «Е».

То есть нужно найти число равное целому числу, деленному на минимально возможную положительную целую степень двойки попадающее в интервал [122/420, 122,5/420] => [0,290476, 0,291667]

1/2= 0,5 не подходит 1/4 = 0,25 не подходит 3/4= 0,75 не подходит

1/8 = 0,125 не подходит 3/8 = 0,375 не подходит 7/8= 0,875 не подходит

1/16= 0,0625 не подходит 3/16 = 0,1875 не подходит 5/16 = 0,3125 не подходит

9/32 = 0,28125 не подходит 11/32 = 0,34375 не подходит

18/64 = 0,28125 не подходит 19/64 = 2,96875 не подходит

37/128 = 0,289063 не подходит 38/128 = 0,296875 не подходит

74/256 = 0,289063 не подходит 75/256 = 0,292969 не подходит

149/512 = 0,291016 ЭТО ПОДХОДИТ

Значит код сообщения «ВАСЕ» будет соответствовать числу 149/512, для кодирования достаточно будет 9 разрядов.

256	128	64	32	16	8	4	2	1
0	1	0	0	1	0	1	0	1