Упаковка данных
Данные многих форматов имеют значительный объем, поэтому их хранение и передача зачастую требуют значительных ресурсов. Одним из способов решения этой проблемы является повышение емкости запоминающих устройств и пропускной способности каналов связи. Однако во многих случаях применима и более дешевая альтернатива этим методам – упаковка данных.
Научной основой всех методов упаковки является теория информации: данные, в которых имеются статистические автокорреляции, называются избыточными или имеющими низкую энтропию. Устранив эти автокорреляции, т. е. повысив энтропию, объем данных можно уменьшить без потери смысла, а зачастую и с возможностью однозначно восстановить исходные данные. Методы повышения энтропии, которые не позволяют по упакованному потоку восстановить исходный, называются необратимыми, приблизительными или сжимающими с потерями (losing compression). Соответственно, методы, которые позволяют это сделать, называются обратимыми, точными, или сжимающими без потерь (losless compression).
Один из первых методов упаковки был предложен задолго до разработки современной теории информации; в 1844 году Сэмюэл Морзе построил первую линию проволочного телеграфа. Система кодировки букв, известная как Азбука Морзе (табл. 1.4), использовала для представления различных букв алфавита посылки различной длины, при этом длина посылки зависела от частоты использования соответствующего символа в английском языке. Часто встречающиеся символы кодировались более короткими последовательностями.
Таблица 1.4. Русская азбука Морзе.
| Буква | Символы Морзе | Слово | Буква | Символы Морзе | Слово |
|---|---|---|---|---|---|
| А | .- | а-том | Р | .-. | ра-ду-га |
| Б | -… | бес-са-раб-ка | С | - | са-ма-ра |
| В | .-- | ва-ви-лон | Т | - | Ток |
| Г | --. | го-ло-ва | У | ..- | |
| Д | -.. | до-бав-ка | ф | ..-. | фа-на-тич-ка |
| Е | - | X | - | ха-на-ан-ка | |
| Ж | …- | жат-ва-зла-ков | ц | -.-. | цы-га-ноч-ка |
| 3 | --.. | звон-бу-ла-та | ч | - | че-ре-му-ха |
| И | - | ш | ше-ре-ме-тев | ||
| К | -.- | конс-тан-тин | Щ | --.- | щу-ро-гла-зый |
| Л | .-.. | ла-до-жан-ка | ю | ..-- | |
| М | -- | ми-иин | я | .-.- | |
| Н | -. | но – га | ы | -.-- | ы-ка-ни-е |
| 0 | о-ло-во | ь-ъ | -..- | ||
| П | .--. | па-ни-хи-да | - |
Примечание
Во вспомогательных словах для запоминания слоги, содержащие букву "а", обозначают точкой, не содержащие – тире.
В конце сороковых годов XX века основателем современной теории информации Шенноном, и независимо от него, Фано был разработан универсальный алгоритм построения оптимальных кодов. Более известный аналог этого алгоритма был предложен несколько позже Дэвидом Хаффманом [Huffman 1952]. Принцип построения этих кодов в целом соответствует логике, которой руководствовался Морзе, – кодировать значения, которые часто повторяются в потоке, более короткими последовательностями битов.
Коды Хаффмана и Шеннона-Фано устраняют автокорреляции, соответствующие неравномерности встречаемости символов, но сохраняют без изменений часто встречающиеся последовательности символов, а они ответственны за значительную часть избыточности текстов на естественных и синтетических языках. Для упаковки данных такого рода в конце 70-х Лемпелем и Зиффом было предложено семейство алгоритмов, наиболее известные из которых – LZ77 и LZW [Lempel-Ziv 1978].
Все эти алгоритмы сводятся к поиску в потоке повторяющихся последовательностей и замене этих последовательностей на их номер в динамически формируемом словаре. Различие состоит в способах кодирования номера и формирования словаря. Номер последовательности в словаре должен содержать больше битов, чем символы исходного потока, хотя бы уже для того, чтобы его можно было отличить от символа, поэтому алгоритмы Лемпеля-Зиффа предполагают дальнейшее перекодирование преобразованного потока кодом Хаффмана. Большинство современных архиваторов, такие, как PkZip, GNU Zip, RAR, основаны на вариациях и аналогах алгоритмов Лемпеля-Зиффа.
При упаковке нетекстовых данных могут применяться и другие способы удаления повторений. Например, при упаковке растровых изображений широко используется метод RLE (Run-Length Encoding), когда повторяющиеся пикселы заменяются счетчиком повторений и значением пиксела.