техника

Как работают архиваторы

Готовлюсь к экзамену, попутно делаю заметки. Дай, думаю, поделюсь, вдруг кто не знает.

Способов сжатия данных существует несколько. Один из наиболее известных -- алгоритм Хаффмана, используемый, например, в архиваторах, сжимающих данные в формат zip.

Возьмём, например, фразу "мама мыла раму". Не считая пробелов, в этой фразе 12 символов. Сколько требуется бит для записи этой информации?

Если у нас 8-битная таблица символов, то 8*12 = 96 бит.

Если берём жесткий минимум и кодируем только 33 символов (число букв в алфавите), то нам понадобится 6 бит на букву или 6*12 = 72 бита.

Но можно использовать ещё меньше. Как -- вот про это и алгоритм Хаффмана.

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

Получим: м:3, а:3, ы:1, л:1, р:1, у:1

Теперь строим бинарное дерево таким образом, чтобы сумма частот для каждого поддерева была минимальной. Листьями дерева являются символы, а корнем -- сколько раз в тексте символы встречаются, суммарно.

То-есть, берём две буквы, которые встречаются реже всего, и делаем поддерево. Начнём слева направо, с букв ы и л. Они встречаются 1 раз каждая, и у нас получится вот что:



Дальше берём буквы р и у, они тоже встречаются по одному разу.



Делаем слияние этих двух деревьев (так как сумма будет = 4, что меньше, чем если бы мы добавили бы к любому из деревьев буквы м или а).



Теперь добавляем к получившемуся букву м, и потом букву а.



А теперь каждому переходу налево присваиваем 0, а переходу направо -- 1 (можно и наоборот, результат не изменится), и получаем готовое дерево Хаффмана:



Теперь, записывая переходы нулями и единичками, мы можем записать эту фразу в битах. Так, букве а соответствует 1, букве м -- 01, букве у -- 0011, и так далее.

Вы понимаете, что происходит? Наиболее часто используемые буквы записываются наименьшим количеством бит. Это ключевое.

Что у нас теперь получится, если фразу записать (без пробелов)?

0110110100000001100101010011

Это -- всего лишь 28 бит или в среднем 2.3 бита на символ (вместо 6). То-есть, компрессия данных налицо.

Конечно, вместе с упакованными таким образом данными, надо включать и построенное дерево, которое так же занимает место. Поэтому для таких коротких фраз реальный выхлоп, конечно, маловат. Чем более длинный и однообразный (выражаясь научно, чем меньше его энтропия) текст, тем лучше сжатие.
Лайк. Не знал и никогда не понимал как архиваторы работают.
мне относительно недавно сын, заканчивающий MIT на пальцах объяснил как работает RAID-5 и как он ухитряется восстанавливать информацию в конфигурации например 7 дисков +1, когда казалось бы куда там и как оно возможно. Оказалось, что идея настолько проста, что просто офигеть.