Алгоритмы сжатия

GPcH (admin@dotfix.net)

Спецвыпуск: Хакер, номер #062, стр. 062-062-1

Теория и практика сжатия данных без потерь

давным-давно, когда в мире не существовало компьютеров, об экономии носителей информации (папирусов и камней :)) никто не задумывалсЯ. более того, все надежды возлагали на криптографию, и основные исследованиЯ в области данных велись в направлении их шифрованиЯ

Многое изменилось тогда, когда были созданы первые ЭВМ, размеры которых вне всякой критики, а объемы жестких дисков — меньше, чем ПЗУ в первых мобильных телефонах. Тут-то весь прогрессивный мир и задумался о том, как поместить в такой маленький объем памяти как можно больше полезных документов. И вот ученые стали предлагать свои наработки, но большинство из этих теорем лишь доказывали возможность сжатия тех или иных данных. Идей о сжатии же и, тем более, о последующем разжатии было немного. Постепенно родился энтропийный анализ данных, позволяющий оценить компактность хранения информации и возможность ее сжатия — благодаря этому событию идеи начали воплощаться в реальность. Была предложена идея сжатия в результате подсчета частоты появления тех или иных байт в тексте: текст первоначально оценивается упаковщиком, подсчитывается частота появления в тексте каждой буквы, присутствующей в нем, частота повторения участков текста и т.д.; составляется таблица этих самых частот, по которой уже вторым проходом происходит упаковка/распаковка. Метод надолго засел в умах разработчиков. Его идеальной реализацией можно считать алгоритм Хаффмана и последующие доработки. Рассмотрим данный метод вкратце.

Метод Хаффмана

Как известно, текстовый файл состоит из фиксированного набора символов. Для примера возьмем эту статью. В ней используются строчные и заглавные буквы русского алфавита, знаки препинания — количество используемых символов меньше, чем 256 (Ascii-таблица). Однако компьютер сохранит текстовый файл в восьмибитной кодировке (2^8=256). Соответственно, больше половины символов Ascii-таблицы совсем не используются. Наша задача — сделать так, чтобы использовалось как можно больше символов. К примеру, Ascii-таблица состоит из десяти символов (0,1,2,3,4,5,6,7,8,9). У нас есть текст «00112233011223322113». Как видишь, символы 4,5,6,7,8,9 не используются. Можно ввести следующее обозначение:

00 - 0

11 - 1

22 - 2

33 - 3

01 - 4

12 - 5

23 - 6

32 - 7

21 - 8

13 - 9

Таким образом наш текст можно записать в виде: «0123456789». После подобного преобразования текст стал занимать в два раза меньше объема. Все допустимые символы присутствуют в тексте. Чтобы получить исходный текст, необходимо, согласно обозначению, вновь заменить символы на их комбинацию. Теперь ты знаешь смысл метода Хаффмана. Поехали!

Сначала в тексте подсчитывается количество повторяющихся символов. К примеру, символ «А» повторяется 100 раз, символ «В» — 300 раз и т.д. Затем символы сортируются по убыванию или возрастанию согласно количеству их появлений в тексте. Потом составляется дерево Хаффмана, наподобие наших символов, которые обозначали их комбинацию("00" — 0,"11" — 1 и т.д.). Только дерево Хаффмана призвано максимально уменьшить количество символов в заархивированном тексте, поэтому оно составляется несколько иначе. Мы уже отсортировали символы согласно их количеству. Теперь берем символ с наименьшей частотой появления и объединяем его с символом, стоящим на втором месте. Получаем новый символ с частотой появления, которая равна сумме частот символов, входящих в него. Проделываем то же самое с другими символами (объединенные символы со счетов не сбрасывай). В конце концов у нас получится один символ с частотой появления, равной размеру файла. Теперь посмотрим, что получилось.