Сжатие данных

Равномерное кодирование при передаче текстов неэкономично – например, ASCII код имеет 256 кодовых слов, что излишне для кодирования букв и знаков препинания в любом языке. Можно задаться символами языка и частотами их появления в тексте (они известны для любого естественного языка), затем оптимизировать коды алгоритмом Хаффмана. Выигрыш при этом получается порядка 25% и выше.

Замечание. Распространённые программы–упаковщики сжимают текст до 80% – это показывает, что принцип сжатия в этих программах не алфавитный.

Другой принцип сжатия текстов был упомянут в начале настоящего раздела.

1. Исходный текст, скажем, «Война и мiр», разбивается по некоторому принципу на слова. В обычном тексте это могут быть обычные слова, можно применять и к объектам не числовой природы). Слова могут иметь одно или несколько вхождений в сообщение.

2. Полученное множество слов считается буквами нового алфавита. Для этого алфавита строится разделимая схема алфавитного кодирования (равномерного или оптимального, если подсчитать число вхождений слова в текст). Полученную схему называют словарём.

3. Код сообщения состоит из словаря и последовательности кодов, соответствующих исходному сообщению.

4. Декодирование – восстановление текста по приложенному словарю.

Пример. Как правило, любой текст на естественном языке содержит меньше, чем 2¹⁶ различных слов. Таким образом, любому слову в тексте можно сопоставить номер – целое число из двух байт (равномерное кодирование). Поскольку в среднем слова состоят более чем из двух букв, такое кодирование даёт существенное сжатие текста – порядка 75% для русского текста. Если текст велик, то затраты на хранение словаря будут относительно невелики.

Замечание. Попутно решается задача полнотекстового поиска по словам.