Закодировать сообщение JGJGY при помощи арифметического кодирования
Решение
Подсчитаем количество букв и выделим частотные интервалы для них на промежутке [0; 1].
В первой строке – буква, во второй – частота символа, в третьей – вероятность возникновения (частота деленная на количество символов в слове), в четвертой – правая граница интервала.
G J Y
2 2 1
0,4 0,4 0,2
0,4 0,8 1
Кодируем слово:
Возьмем первый символ «J» и принимаем его границы [0,4; 0,8] за начало отсчета
. Для кодирования следующего символа «G» нужно пересчитать границы по формулам:
где - новый рабочий интервал
- старый рабочий интервал
- оценка символа из таблицы
Получаем следующие результаты:
Символ Граница слева Граница справа
J 0,4 0,8
G 0,4 0,56
J 0,464 0,528
G 0,464 0,4896
Y 0,48448 0,4896
0,4+(0,8-0,4)*0=0,40,4+(0,8-0,4)*0,4=0,56
0,4+(0,56-0,4)*0,4=0,4640,4+(0,56-0,4)*0,8=0,528
0,464+(0,528-0,464)*0=0,4640,464+(0,528-0,464)*0,4=0,4896
0,464+(0,4896-0,464)*0,8=0,484480,464+(0,4896-0,464)*1=0,4896
Результатом кодирования будет любое число из полуинтервала [0,48448; 0,4896), например левая граница, т.е