Закодировать сообщение LKJDD при помощи арифметического кодирования
Решение
Подсчитаем количество букв и выделим частотные интервалы для них на промежутке [0; 1].
В первой строке – буква, во второй – частота символа, в третьей – вероятность возникновения (частота деленная на количество символов в слове), в четвертой – правая граница интервала.
D J K L
2 1 1 1
0,4 0,2 0,2 0,2
0,4 0,6 0,8 1
Кодируем слово:
Возьмем первый символ «L» и принимаем его границы [0,8; 1] за начало отсчета
. Для кодирования следующего символа «К» нужно пересчитать границы по формулам:
где - новый рабочий интервал
- старый рабочий интервал
- оценка символа из таблицы
Получаем следующие результаты:
Символ Граница слева Граница справа
L 0,8 1
K 0,92 0,96
J 0,936 0,944
D 0,936 0,9392
D 0,936 0,93728
0,8+(1-0,8)*0,6=0,920,8+(1-0,8)*0,8=0,96
0,92+(0,96-0,92)*0,4=0,9360,92+(0,96-0,92)*0,6=0,944
0,936+(0,944-0,936)*0=0,9360,936+(0,944-0,936)*0,4=0,9392
0,936+(0,9392-0,936)*0=0,9360,936+(0,9392-0,936)*0,4=0,93728
Результатом кодирования будет любое число из полуинтервала [0,936; 0,93728), например левая граница, т.е