0голос

Имеется псевдокод, необходимо составить программу, реализующую арифметическое кодирование информации
Арифметическое кодирование

Input: Объем алфавита M
вероятности букв pi, i = 1, ..., M
длина последовательности n
последовательность на выходе источника (x1, ..., xn),
Output : Кодовое слово арифметического кода
Кумулятивные вероятности :
q1 = 0;
for i = 2 to M do
qi = qi?1 + pi?1;
end
Кодирование :
for i = 1 to n do
F ? F + q(xi)G;
G ? p(xi)G; .
end
Формирование кодового слова :
c ? первые [? log G] + 1 разрядов после запятой в двоичной записи числа F + G/2.

Принцип кодирования:
Пусть даны числа 0, 1, 2 и распределение вероятности P(0)=2/3, P(1/6), P(2)=1/6
Берешь отрезок [0, 1]. Разбиваем на части в соответствии с распределением.
Теперь на вход подается последовательность: 0102
первая цифра 0 => выбираем отрезок первый [0, 2/3] и разбиваем его в соответствии с распределением
вторая цифра 1 => выбираем в новом отрезке второй отрезок [4/9, 5/9] и разбиваем его на части в соответствии с распределением
и так далее.

В итоге получим какой-то отрезок. [x, y]. Надо найти двоичную дробь, например 0.01101, которая имеет минимальное число цифр и принадлежит этому отрезку. Тогда ответ: 01101 (это закодированное сообщение)

Ваш ответ

Яндекс.Метрика
...

Вопрософ.нет Задавайте любые вопросы и получайте быстрые ответы на них. Задать вопрос и получить ответ легко! Поделись своими знаниями с другими участниками сервиса!

Задайте ваш вопрос::