nlothik (nlothik) wrote,
nlothik
nlothik

Categories:

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

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

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

Конечно, вместе с упакованными таким образом данными, надо включать и построенное дерево, которое так же занимает место. Поэтому для таких коротких фраз реальный выхлоп, конечно, маловат. Чем более длинный и однообразный (выражаясь научно, чем меньше его энтропия) текст, тем лучше сжатие.
Tags: компьютерное, учёба
Subscribe

  • Хочу эту гитару

    Очень интересный продукт. Ультракомпактная гитара, которую легко брать с собой в дорогу, и при этом гриф у неё полноразмерный: на неё можно ставить…

  • Любимая ария

    Случайно наткнулся на арию Lascia ch’io pianga (“Дай мне слезами выплакать горе”) из оперы “Ринальдо” Георга нашего…

  • Вдогонку

    Японская поп-музыка является, по большей частью, диким поревом. В этих песнях всё какое-то жутко гротескное, всё доводится до каких-то диких…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 9 comments