Закодировать сообщение ATADA при помощи арифметического кодирования
Решение
Подсчитаем количество букв и выделим частотные интервалы для них на промежутке [0; 1].
В первой строке – буква, во второй – частота символа, в третьей – вероятность возникновения (частота деленная на количество символов в слове), в четвертой – правая граница интервала.
A D T
3 2 1
0,6 0,2 0,2
0,6 0,8 1
Кодируем слово:
Возьмем первый символ «A» и принимаем его границы [0; 0,6] за начало отсчета
. Для кодирования следующего символа «T» нужно пересчитать границы по формулам:
где - новый рабочий интервал
- старый рабочий интервал
- оценка символа из таблицы
Получаем следующие результаты:
Символ Граница слева Граница справа
A 0 0,6
T 0,48 0,6
A 0,48 0,552
D 0,5232 0,5376
A 0,5232 0,53184
0+(0,6-0)*0,8=0,480+(0,6-0)*1=0,6
0,48+(0,6-0,48)*0=0,480,48+(0,6-0,48)*0,6=0,552
0,48+(0,552-0,48)*0,6=0,52320,48+(0,552-0,48)*0,8=0,5376
0,5232+(0,5376-0,5232)*0=0,52320,5232+(0,5376-0,5232)*0,6=0,53184
Результатом кодирования будет любое число из полуинтервала [0,5232; 0,53184), например левая граница, т.е