Как работают архиваторы
Готовлюсь к экзамену, попутно делаю заметки. Дай, думаю, поделюсь, вдруг кто не знает.
Способов сжатия данных существует несколько. Один из наиболее известных -- алгоритм Хаффмана, используемый, например, в архиваторах, сжимающих данные в формат 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). То-есть, компрессия данных налицо.
Конечно, вместе с упакованными таким образом данными, надо включать и построенное дерево, которое так же занимает место. Поэтому для таких коротких фраз реальный выхлоп, конечно, маловат. Чем более длинный и однообразный (выражаясь научно, чем меньше его энтропия) текст, тем лучше сжатие.
Способов сжатия данных существует несколько. Один из наиболее известных -- алгоритм Хаффмана, используемый, например, в архиваторах, сжимающих данные в формат 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). То-есть, компрессия данных налицо.
Конечно, вместе с упакованными таким образом данными, надо включать и построенное дерево, которое так же занимает место. Поэтому для таких коротких фраз реальный выхлоп, конечно, маловат. Чем более длинный и однообразный (выражаясь научно, чем меньше его энтропия) текст, тем лучше сжатие.