техника

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

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

Способов сжатия данных существует несколько. Один из наиболее известных -- алгоритм Хаффмана, используемый, например, в архиваторах, сжимающих данные в формат 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, когда казалось бы куда там и как оно возможно. Оказалось, что идея настолько проста, что просто офигеть.
Хаффман использовался в архиваторе HA, еще активно используется в линиях передачи. Морзе, кстати, на той же идее базируется - чем чаще используется символ - тем короче цепочка.

В ZIP же основа архивации - сворачивание цепочек алгоритмом на основе Lempel-Zive.

На самом деле Хаффман не очень для файловой архивации - цепочка нулей, скажем, длинной в 1 мегабайт всё равно будет 1/8 мегабайта, не меньше. В том время как LZ превратит это в 5 байт грубо говоря - (dword: 1024*1024) byte: 0
> В ZIP же основа архивации - сворачивание цепочек алгоритмом на основе Lempel-Zive.

Емнип, там Deflate -- сочетание LZ и Huffman.

> На самом деле Хаффман не очень для файловой архивации - цепочка нулей, скажем, длинной в 1 мегабайт всё равно будет 1/8 мегабайта, не меньше.

Да, бывает намного лучше, безусловно. Но -- очень простой алгоритм зато, учебный.
> В том время как LZ превратит это в 5 байт грубо говоря

Это не LZ, это RLE. LZ вроде ж по словарю работает и в такие фокусы просто не умеет.
> Не считая пробелов, в этой фразе 12 символов

Сразу вспомнился алгоритм архивации "sort-drop-RLE".
Сортируем биты в файле по возрастанию: нули вперёд, единицы назад.
Лидирующие нули ничего не значат, поэтому их отбрасываем.
А единицы архивируем, просто пересчитав их, и записав в архив общее количество.
Разархивация - в обратном порядке.

Это я к тому, что дидактичнее было бы пробелы тоже включить в дерево. Ну, и упомянуть про LZ, а то может создаться впечатление, что zip - это только Хаффман.
> Разархивация - в обратном порядке.

Чего-то я не вкурил, а откуда возьмётся информация о том, где стояла какая-то единица?

Или это шутка такая?

> Это я к тому, что дидактичнее было бы пробелы тоже включить в дерево.

Думаешь? Ну, дерево было бы немного посложнее, после добавления м к дереву со стоимостью 4 оказалось бы дешевле создать отдельное поддерево с листьями а и пробелом, а потом уже слить их. Не знаю, насколько это прибавляет наглядности.
> откуда возьмётся информация о том, где стояла какая-то единица?

Оттуда же, откуда возьмётся информация о расположении пробелов в фразе про маму и Раму, то есть - ниоткуда.
То есть, это шутка конечно, но строго в тему.

> Не знаю, насколько это прибавляет наглядности.

Ну, как бы, выкидывание пробелов наглядность несколько убавляет, потому что либо создаёт обманчивое впечатление, что пробелы (или нули, как у меня) можно просто выкинуть, "они же ничего не значат", либо вызывает законные вопросы "а как их потом восстановить-то, в примере об этом ничего не сказано". И вообще, в качестве учебных примеров как-то обычно используют примеры удобные и при этом корректные, а не просто удобные :-)