Наверняка, каждый пользовался архиватором, но при этом даже не задумывался, как он работает. Лично у меня всегда возникал вопрос, куда же девается информация, и почему она занимает меньше места. Никакого волшебства нет, информация перекодируется так, чтобы быть менее объёмной.
Избыточность
Избыточность означает, что мы можем закодировать слово меньшим количеством символов. Почти любой естественный язык избыточен с точки зрения теории информации. Например, слово перелесок можно закодировать как прелесок или даже пелесок. Ведь слов, в которых на местах выброшенных букв стоят другие буквы нет в русском языке. Если рассматривать не слова по отдельности, а целый текст, то можно перекодировать и более длинные последовательности символов. Каждый новый символ в тексте должен нести в себе как можно больше информации и задачей архиваторов как раз и является избавление текста от избыточности.
Конечно, можно просто отбросить какую-то часть информации, тем самым уменьшив её объём. Но тогда мы не сможем восстановить эту часть и утратим её, что непозволительно для текстов или бинарных файлов. Этот метод борьбы с избыточностью используется для сжатия изображений или видеофайлов, однако это повлечет за собой уменьшение качества материала.
Типы алгоритмов архивации
Статистические (энтропийные)
Пусть нам задан некоторый текст и частоты каждого символа в этом тексте. Тогда нетрудно заметить, что наиболее часто встречаемые элементы нужно закодировать более короткими словами, тогда у нас получится сжать текст. Минус такого подхода в том, что нужно пройтись по тексту и посчитать эти частоты, что увеличит время архивации. Кроме того, одни символы встречаются в начале текста чаще, а в конце реже. То есть часть информации будет сжата не совсем эффективно.
Адаптивные
Этот тип алгоритмов подстраивается под новое распределение частот в тексте, то есть всегда сжимает информацию наиболее эффективным способом. Самым известным и широко используемым является семейство алгоритмов LZ.
Первый способ архивации из этого класса был придуман в 1977 году и называется LZ-77. Он основывается на буфере, который хранит встречавшиеся ранее подпоследовательности. Если подпоследовательность есть в буфере, он ссылается на неё вместо того, чтобы заново кодировать, что позволяет экономить память. Добавление последовательности происходит следующим образом. Берется символ текста и ищется в буфере. Если он есть, то производим поиск последовательности из этого символа и следующего. Если есть и он, то добавляем ещё один символ из кодируемой последовательности, иначе добавляем в буфер новую последовательность и кодируем её.
Основным недостатком является то, что этот буфер является частью последовательности на выходе кодера, поэтому для поиска в нём последовательности нужно много времени. Этот недостаток был устранён в следующих версиях алгоритма. Стал использоваться отдельный словарь для сопоставления кодов и последовательностей, которые им соответствуют. Обычно он инициализируется со значениями одиночных символов, а затем добавляет новые последовательности и коды для них.
Применение алгоритмов на практике
Современные программы-архиваторы комбинируют адаптивные и статистические методы между друг другом для получение наиболее эффективных методов сжатия.
Сначала могут пройтись адаптивным методом, а затем энтропийным. Это поможет дважды сжать информацию и использовать преимущества каждого из типов архивации данных.
Заключение
В современном мире появляется все больше и больше информации и для её хранения и передачи используются разобранные выше алгоритмы. Их роль сложно недооценить, потому что используются архиваторы повсеместно и знать принципы их работы будет полезно каждому человеку.
Не забудьте подписаться на канал)