- •Арифметическое кодирование
- •3 Шаг: Далее нужно закодировать следующий символ исходной последовательности «вас» - это символ «а».
- •Раскодирование сообщения зашифрованного с помощью арифметического кода. Считается что алфавит и вероятности его символов известны.
- •Адаптивный алгоритм Хафмана
- •Адаптивное арифметическое кодирование
- •Раскодирование сообщения зашифрованного с помощью адаптивного арифметического кода
Раскодирование сообщения зашифрованного с помощью адаптивного арифметического кода
Пример 7: Пусть нам пришло сообщение 010010101.
Этому сообщению соответствует число 149/512.
Мы знаем состав алфавита: А, В, С и Е-символ конца, веса символов на первом шаге по 1, вероятность каждого из символов = его вес / на суммарный вес всех символов (т.е. одинаковые и по 1/4).
Шаг 1: Смотрим, в какой из отрезков это число попадает: 149/512 = 0,291016
1/4 = 0,25 2/4 =0,5 3/4 = 0,75 это число попадает в интервал [1/4, 2/4].
Получается что первый символ закодированного сообщения «В».
Увеличиваем вес символа «В», теперь он =2. Суммарный вес всех символов теперь 5.
Шаг 2: Получаем новый (текущий) код, для этого
от текущего кода, т.е. числа 9/32 вычитаем левую (нижнюю границу) содержащего его интервала, т.е. число 1/4 и делим все на длину этого интервала, т.е. на 1/4.
это новый текущий код.
Шаг 3: Перестраиваем разбиение единичного отрезка согласно новому распределению весов символов.
Считаем вероятности А= 1/5, В=2/5, С=1/5, Е=1/5.
Шаг 4: Смотрим, в какой из отрезков попадает текущий код: 21/128 = 0,164063
1/5 = 0,2 3/5 =0,6 4/5 = 0,8 это число попадает в интервал [0, 1/5].
Получается что второй символ закодированного сообщения «А».
Увеличиваем вес символа «А», теперь он =2. Суммарный вес всех символов теперь 6.
Шаг 5: Получаем новый (текущий) код, для этого
от текущего кода, т.е. числа 1/8 вычитаем левую (нижнюю границу) содержащего его интервала, т.е. число 0 и делим все на длину этого интервала, т.е. на 1/5.
это новый текущий код.
Шаг 6: Перестраиваем разбиение единичного отрезка согласно новому распределению весов символов.
Считаем вероятности А= 2/6, В=2/6, С=1/6, Е=1/6.
Шаг 7: Смотрим, в какой из отрезков попадает текущий код: 105/128 = 0,820313
2/6 = 0,3333 4/6 =0,66667 5/6 = 0,83333 это число попадает в интервал [4/6, 5/6]..
Получается что третий символ закодированного сообщения «С».
Увеличиваем вес символа «С», теперь он =2. Суммарный вес всех символов теперь 7.
Шаг 8: Получаем новый (текущий) код, для этого
от текущего кода, т.е. числа 105/128 вычитаем левую (нижнюю границу) содержащего его интервала, т.е. число 4/6 и делим все на длину этого интервала, т.е. на 1/6.
это новый текущий код.
Шаг 9: Перестраиваем разбиение единичного отрезка согласно новому распределению весов символов.
Считаем вероятности А= 2/7, В=2/7, С=2/7, Е=1/7.
Шаг 10: Смотрим, в какой из отрезков попадает текущий код: 708/768 = 0,921875
2/7 = 0,285714 4/7 =0,571429 6/7 = 0,857143 это число попадает в интервал [6/7, 1]
Получается что четвертый символ закодированного сообщения «Е», который означает окончание процесса раскодирования.
Получили раскодированное сообщение кода 010010101 => «ВАСЕ» !!!