Арифметическое сжатие/кодирование?

Question

[AndreySlimus]

Здравствуйте!
С помощью арифметического сжатия/кодирования требуется закодировать сообщение "информационный", а затем представить сообщение в двоичном виде.
Метод вроде бы не является сложным, но у меня возникли определенные проблемы. Во всех примерах, что можно отыскать в интернете, используется интервал [0;1) И во всех примерах сообщение хорошо "впихивается" в этот интервал. С сообщением "информационный" так не выходит, так как только три символа в нем повторяются: это "н" - 3, "и" - 2, "о" - 2.
Как быть в таком случае?

Answer 1

[Rsa97]

А в чём проблема?
Определяем алфавит: (а, и, й, м, н, о, р, ф, ц, ы).
Считаем символы (распределение вероятности).

а | и | й | м | н | о | р | ф | ц | ы
1 | 2 | 1 | 1 | 3 | 2 | 1 | 1 | 1 | 1

Строим накопительную сумму

а | и | й | м | н | о  | р  | ф  | ц  | ы
1 | 3 | 4 | 5 | 8 | 10 | 11 | 12 | 13 | 14

Приводим в отрезок [0,1) делением на общую сумму (14)

а     | и     | й     | м     | н     | о     | р     | ф     | ц     |  ы
0.071 | 0.214 | 0.286 | 0.357 | 0.571 | 0.714 | 0.786 | 0.857 | 0.929 | 1

Кодируем сообщение

старт - [0, 1)
и - [0.071, 0.214)
н - [0.122, 0,153)
ф - [0.1465, 0.1486)
...
й - [0.147980532221506, 0.147980532221545)

Берём середину интервала, получаем кодированное сообщение 0.147980532221526

Comments

[AndreySlimus]

Спасибо!

Answer 2

[maaGames]

Интервал [0;1) это число не float и не double. А в длинное число "впихнётся" любое сообщение. Только качество сжатия будет плохое.
Можно сжимать не символами, а по 4 бита, например. Или вообще побитово. Может лучше результат получится. А может и хуже.

Comments

[AndreySlimus]

Мне эту задачку нужно решить на бумаге. Т.е. мне можно увеличить интервал, например, до [0;1.4), что бы определить диапазон абсолютно всех символов в моем сообщении?