Упаковка данных
Данные многих форматов имеют значительный объем, поэтому их хранение и передача зачастую требуют значительных ресурсов.
Научной основой всех методов упаковки является теория информации: данные, в которых имеются статистические автокорреляций, называются избыточными. Устранив эти автокорреляции, объем данных можно уменьшить без потери смысла, а зачастую и с возможностью однозначно восстановить исходные данные.
Методы, которые не позволяют по упакованному потоку восстановить исходный, называются необратимыми, приблизительными или сжимающими с потерями (losing compression). Соответственно, методы, которые позволяют это сделать, называются обратимыми, точными, или сжимающими без потерь (losless compression).
Один из первых методов упаковки был предложен задолго до разработки современной теории информации; в 1844 году Сэмюэл Морзе построил первую линию проволочного телеграфа. Система кодировки букв, известная как Азбука Морзе использовала для представления различных букв алфавита посылки различной длины, при этом длина посылки зависела от частоты использования соответствующего символа. Часто встречающиеся символы кодировались более короткими последовательностями.
В конце сороковых годов XX века основателем современной теории информации Шенноном был разработан универсальный алгоритм построения оптимальных кодов. Более известый аналог этого алгоритма был предложен несколько позже Дэвидом Хаффманом. Принцип построения этих кодов соответствует логике, которой руководствовался Морзе, - кодировать значения, которые часто повторяются в потоке, более короткими последовательностями битов.
Для упаковки данных такого рода в конце 70-х Лемпелем и Зиффом было предложено семейство алгоритмов, наиболее известные из которых - LZ77 и LZW.
предыдущаяследующая