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

  • Почти всё

    Так как одиннадцатая винда фичами пока не радует, попробовал заменить на рабочем компе всё на Убунту 20.04 И оно, знаете, практически взлетело.…

  • Не всё так плохо

    Моя гневная телега по поводу национальных особенностей преподавания математики в начальной школе получила довольно простой ответ: дети всё же умеют…

  • Как в Америке преподают математику

    Извиняюсь за матюги, но выбесило. Очередная чушь-бредятина от местной системы преподавания основ математики и горячий привет от Common, блядь,…

  • 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