Принцип работы алгоритма LZMA
Долгое время на рынке использовались уже изученные и апробированные алгоритмы, каждый из которых имел своих противников и почитателей: LZx, метод Хаффмана (Шеннона-Фано), метод арифметической компрессии и т.д. Для невероятно плотной упаковки графики уже давно обещали внедрить фрактальный метод компрессии, но что-то с этим не заладилось. Прежде чем рассказывать о сравнительно новом алгоритме LZMA, хотелось бы рассказать о принципе упаковки данных вообще.
Проблема кодирования информации восходит к тем временам, когда сигналы передавались по сетям, имеющим массу помех. Для этого придумывали разнообразные алгоритмы, чтобы по искажениям уметь восстанавливать переданную информацию в исходящий вид. Это было избыточное кодирование, что понятно. С тех пор сети обросли более интеллектуальной обвязкой, и надобность в избыточном кодировании исчезла. Даже в жестких дисках ошибки чтения отлавливаются на уровне контроллера. Получив такие «нешумные» каналы передачи, возникла обратная идея – можно ли уменьшить энтропию кода? Оказалось, что во многих случаях вполне можно. Более того, в той же графике стала возможной упаковка кода с потерями (видеоформаты, JPEG, варианты TIFF), но для традиционных данных упаковка кода требовала сжатия без потерь. Некоторая информация имела свою специфику, которая разрешала использовать специальные компрессоры: для обработки текста, графики, музыки, технических данных. Другие алгоритмы пытались обрабатывать входные потоки информации, не зная заранее их сущность. Общая идея была такова: входной код анализировался сканером, после чего каждому коду, по возможности, присваивался временный код, имеющий переменное число битов. Чем чаще попадалось одно и то же сообщение, тем короче ему присваивался код. Затем это бинарное дерево кодов сохранялось вместе с упакованным текстом. Затем декодер восстанавливал этот поток данных, следуя по таблице, так как код получался префиксным (любые коды не имели пересечения друг с другом). Были и другие алгоритмы, более сложные, или, наоборот, довольно простые.
К таким относится и алгоритм сжатия LZMA, реализованный в архиваторе 7-Zip, FreeArc. В настоящее время это открытый проект, доступный любому, поэтому информация о нем часто попадается в контексте архиваторов Linux и Unix: bzip2 и подобных. Алгоритм по принципу работы напоминает известный LZ77, где данные упаковываются с помощью словаря и скользящего (или фиксированного) окна. Входной поток рассматривается побайтно и сравнивается со словарем. Если часть данных уже есть в словаре, то поток читается дальше, и при этом вместо него будет записана ссылка на имеющееся совпадение, иначе в словарь заносится накопленная часть информации и ее длина. При этом сообщения в словаре могут иметь разное число битов. Для большей эффективности размер словаря приходилось увеличивать от 2 до 32 Кб, рос и размер скользящего окна. Тем не менее, увеличивать размер словаря было неэффективно. Алгоритм LZMA внес изменения в эту модель, добавив в него интервальное кодирование, а также новые способы обработки бинарных файлов и поисковых алгоритмов работы с двоичными деревьями. При этом размер словаря перестал быть жестко фиксированным, увеличиваясь вплоть до 4 Гб. Тем не менее, споры об эффективности работы алгоритма на реальных данных все еще ведутся. |