Программы
ВХОД
Логин:    

Пароль:  

   Запомнить меня
Вам нужно авторизоваться.
Забыли пароль? / Регистрация
Статьи


   Статьи
   Soft
   Программирование
   Алгоритм сжатия данных LZMA

Алгоритм сжатия данных LZMA

Добавлено: 01.04.2012

Прочитано: 3178

Принцип работы алгоритма LZMA

Долгое время на рынке использовались уже изученные и апробированные алгоритмы, каждый из которых имел своих противников и почитателей: LZx, метод Хаффмана (Шеннона-Фано), метод арифметической компрессии и т.д. Для невероятно плотной упаковки графики уже давно обещали внедрить фрактальный метод компрессии, но что-то с этим не заладилось. Прежде чем рассказывать о сравнительно новом алгоритме LZMA, хотелось бы рассказать о принципе упаковки данных вообще.

Проблема кодирования информации восходит к тем временам, когда сигналы передавались по сетям, имеющим массу помех. Для этого придумывали разнообразные алгоритмы, чтобы по искажениям уметь восстанавливать переданную информацию в исходящий вид. Это было избыточное кодирование, что понятно. С тех пор сети обросли более интеллектуальной обвязкой, и надобность в избыточном кодировании исчезла. Даже в жестких дисках ошибки чтения отлавливаются на уровне контроллера. Получив такие «нешумные» каналы передачи, возникла обратная идея – можно ли уменьшить энтропию кода? Оказалось, что во многих случаях вполне можно. Более того, в той же графике стала возможной упаковка кода с потерями (видеоформаты, JPEG, варианты TIFF), но для традиционных данных упаковка кода требовала сжатия без потерь. Некоторая информация имела свою специфику, которая разрешала использовать специальные компрессоры: для обработки текста, графики, музыки, технических данных. Другие алгоритмы пытались обрабатывать входные потоки информации, не зная заранее их сущность. Общая идея была такова: входной код анализировался сканером, после чего каждому коду, по возможности, присваивался временный код, имеющий переменное число битов. Чем чаще попадалось одно и то же сообщение, тем короче ему присваивался код. Затем это бинарное дерево кодов сохранялось вместе с упакованным текстом. Затем декодер восстанавливал этот поток данных, следуя по таблице, так как код получался префиксным (любые коды не имели пересечения друг с другом). Были и другие алгоритмы, более сложные, или, наоборот, довольно простые.

К таким относится и алгоритм сжатия LZMA, реализованный в архиваторе 7-Zip, FreeArc. В настоящее время это открытый проект, доступный любому, поэтому информация о нем часто попадается в контексте архиваторов Linux и Unix: bzip2 и подобных. Алгоритм по принципу работы напоминает известный LZ77, где данные упаковываются с помощью словаря и скользящего (или фиксированного) окна. Входной поток рассматривается побайтно и сравнивается со словарем. Если часть данных уже есть в словаре, то поток читается дальше, и при этом вместо него будет записана ссылка на имеющееся совпадение, иначе в словарь заносится накопленная часть информации и ее длина. При этом сообщения в словаре могут иметь разное число битов. Для большей эффективности размер словаря приходилось увеличивать от 2 до 32 Кб, рос и размер скользящего окна. Тем не менее, увеличивать размер словаря было неэффективно. Алгоритм LZMA внес изменения в эту модель, добавив в него интервальное кодирование, а также новые способы обработки бинарных файлов и поисковых алгоритмов работы с двоичными деревьями. При этом размер словаря перестал быть жестко фиксированным, увеличиваясь вплоть до 4 Гб. Тем не менее, споры об эффективности работы алгоритма на реальных данных все еще ведутся.



обновить программы бесплатно

<<  Язык программирования Форт Язык программирования PHP  >>


Добавить Комментарий

Скачать программу для проверки на ошибки
Скачать программу автоматического обновления программ
Статьи
Новые Программы
Новые статьи
Популярные Программы
Самые читаемые статьи
Copyright © Дай Прогу 2011 Контакты ¤ Статистика