"Сжатие" данных
                               
Трудно найти область, в которой было бы написано больше глупостей - начиная с
классификации.

Возможно, вы имели несчастье читать статью или книгу, в которой
классифицировались методы сжатия данных - обычно их делят на "статистические"
и всякие прочие - насколько хватает фантазии автора. Скажем, на некоторых
русскоязычных форумах мне даже встретилось новенькое словечко -
"координатные".

Так вот - нестатистических методов сжатия - чтобы вам не пришлось встретить на
эту тему - НЕ существует.

Каким же образом вообще можно осуществить сжатие данных?

Для ответа на этот вопрос, представим, что Сообщение является Текстом,
состоящим из Букв некоторого Алфавита. Разумеется, и размер (мощность)
Алфавита и размер (длина) Текста конечны. Непрерывность и Бесконечность
существуют только в теориях.

Сейчас неважно, как именно Текст поделен на Буквы. Необходимо только
подсчитать их количество - для каждой из Букв отдельно. Результат подсчета и
есть Статистика.

Фундаментальный результат заключается в следующем:

Если некоторые Буквы встречаются чаще других, то Текст может быть сжат.

Если частоты всех Букв равны, то сжатие в данном Алфавите невозможно.

Заметьте, что невозможность сжатия в данном Алфавите вовсе не означает
невозможности сжатия в некотором другом. Точно также если Текст может быть
сжат в данном Алфавите, это никак не связано с возможностью/степенью его
сжатия в других.

Иными словами, для заданного Текста существуют некоторые алфавиты, в которых
он сжимается лучше, чем в других.

И еще одно очень сильное утверждение:

Существует такой Текст (будем называть его однородным), что он не может
быть сжат ни в каком алфавите.

Каким же образом сжимается (если возможно) текст в заданном алфавите?

Вариантов ровно два:

Первый используется, если все буквы алфавита имеют одинаковый (битовый)
размер.

Второй, соответственно, если буквы алфавита различаются по (битовому) размеру.

Итак, пусть имеется два равномощных алфавита (с одинаковым количеством букв),
таких что в одном (равномерном) все буквы имеют одинаковый (битовый) размер, а
во втором (неравномерном) буквы различаются по (битовому) размеру.

Поскольку количество букв в обоих алфавитах одинаково, то можно
взаимооднозначно сопоставить каждой букве одного алфавита некоторую букву
другого алфавита.

Такое сопоставление будем называть Кодированием.

Само сопоставление можно выполнить различными способами, но некоторые из них
"равнее других".

Итак,

Способ Первый: все буквы исходного алфавита имеют одинаковый (битовый) размер.

Иными словами, исходный алфавит является равномерным.

В этом случае, достаточно записать (закодировать) самые частые буквы исходного
равномерного алфавита самыми короткими буквами неравномерного, оставив самые
длинные буквы неравномерного алфавита для самых редких (в идеале - не
встречающихся в тексте вовсе) букв исходного.

Впервые, в промышленном масштабе, эта идея была реализована Самуэлем Морзе в
изобретенной им в 1838 году системе кодов для созданного им же годом раньше
телеграфного аппарата ("Азбука Морзе"), где самым частым буквам английского
алфавита были назначены самые короткие комбинации точек и тире.

Но прошло более ста лет, прежде чем американский математик Давид Хаффмен
предложил в 1952 году алгоритм (и доказательство) построения оптимальных
неравномерных кодов.

Таким образом, Источник и Приемник просто договариваются о кодировании
(таблице соответствия букв равномерного и неравномерного алфавитов), после
чего Источник использует эту таблицу (Контекст) для кодирования Сообщения, а
Приемник использует эту же самую таблицу для декодирования.

Способ Второй: буквы алфавита различаются по (битовому) размеру.

Иными словами, исходный алфавит является неравномерным.

В этом случае все еще проще, так как не требуется явное вычисление статистики
- частот отдельных букв. (На самом деле, это просто "заметание мусора под
коврик" - взамен неравенства частот, используется неравенство длин (битовых
размеров). И если в первом способе отыскивалась "самая частая" буква, то во
втором отыскивается "самая длинная").

Кодирование выглядит зеркально: если в первом способе равномерный алфавит
кодировался неравномерным, то во втором, наоборот, неравномерный алфавит
кодируется равномерным.

Также, как и раньше, Источник и Приемник договариваются о кодировании (таблице
соответствия букв равномерного и неравномерного алфавитов), после чего
Источник использует эту таблицу (Контекст) для кодирования Сообщения, а
Приемник использует эту же самую таблицу для декодирования.

Гм. Я, кажется, сказал ДВА способа ?

На самом деле, их ТРИ. Третий является комбинацией первых двух - неравномерный
алфавит кодируется другим неравномерным алфавитом. Для простоты, обычно, два
кодера ставят каскадно - один за другим. Тогда первый кодирует неравномерный
алфавит равномерным, а второй - равномерный алфавит (выходной поток первого
кодера) неравномерным.

Вся оставшаяся практика сжатия данных занята, во-первых, отысканием способов
построения "оптимального" исходного алфавита и, во-вторых, минимизацией
трафика на передачу кодовых таблиц.

О построении алфавита будет сказано позднее, а что касается кодовых таблиц, то
основных вариантов три:

-  Использовать заранее созданные (фиксированные) кодовые таблицы на обоих
   концах Канала передачи

-  Передавать кодовые таблицы в упакованном (сжатом) виде

-  Независимо вычислять кодовые таблицы на обоих концах Канала передачи
   (Адаптивное кодирование)