| арифметическое сжатие |
| 1 | Метод арифметического сжатия. АРХИВАЦИЯ. Пусть у нас есть некий алфавит, а также данные о частотности использования символов в порядке убывания частоты. Тогда рассмотрим на координатной прямой отрезок от 0 до 1. Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа и каждый такой отрезок будет соответствовать одному символу. Теперь возьмём символ из файла и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Будем выполнять это операцию до конца файла. Затем выберем любое число из рабочего отрезка. Это число и количество символов в файле и будет конечный архив. |
| 2 | |
| 3 | ПРИМЕР. Дан текстовый файл: «АБВБА». Частоты символов: «А» - 0.4 «Б» - 0.4 «В» - 0.2 Отрезок от 0 до 1 разобьем на отрезки от 0 до 0.4 для «А», от 0.4 до 0.8 для «Б» и от 0.8 до 1 для «В». Первый символ «А» поэтому берем отрезок от 0 до 0.4. Отрезок от 0 до 0.4 разобьем на отрезки от 0 до 0.16 для «А», от 0.16 до 0.32 для «Б» и от 0.32 до 0.4 для «В». Второй символ «Б» поэтому берем отрезок от 0.16 до 0.32. Отрезок от 0.16 до 0.32 разобьем на отрезки от 0.16 до 0.224 для «А», от 0.224 до 0.288 для «Б» и от 0.288 до 0.32 для «В». Третий символ «В» поэтому берем отрезок от 0.288 до 0.32. Отрезок от 0.288 до 0.32 разобьем на отрезки от 0.288 до 0.3008 для «А», от 0.3008 до 0.3136 для «Б» и от 0.3136 до 0.32 для «В». Четвертый символ «Б» поэтому берем отрезок от 0.3008 до 0.3136. Отрезок от 0.3008 до 0.3136 разобьем на отрезки от 0.3008 до 0.30592 для «А», от 0.30592 до 0.31104 для «Б» и от 0.31104 до 0.3136 для «В». Пятый символ «А» поэтому берем отрезок от 0.3008 до 0.30592 и из него берем число, например 0.304. |
Комментарии