Алгоритм LZMA

LZMA (англ. Lempel-Ziv-Markov chain-Algorithm) — алгоритм сжатия данных без потерь. Он разрабатывался с 1996-1998 гг и впервые был использован в формате 7z архиватора 7-Zip. Алгоритм использует схему сжатия данных по словарю, сходную с алгоритмом LZ77, опубликованным Авраамом Лемпелем (Abraham Lempel) и Якобом Зивом (Jacob Ziv) в 1977 году, и отличается высокой степенью сжатия, произвольным размером словаря, тогда как скорость распаковки сходна с другими алгоритмами сжатия.

Описание

LZMA использует алгоритм сжатия данных по словарю, чей результат закодирован интервальным кодированием, используя сложную модель вычисления вероятности появления каждого бита. Система сжатия ищет совпадения, используя словарь структур данных, и создает поток символов и ссылок на фразы, который закодирован 1 битом интервальным кодировщиком, в то же время динамическое программирование используется, чтобы выбрать оптимальный код под некоторой аппроксимацией.