Наиболее распространены в настоящее времямодификации алгоритма LZ (по имени их авторов - Лемпела и Зива). По сравнению с RLE сделан шаг вперед - будем искать в исходном материале не последовательности одинаковых видов, а повторяющихся цепочек символов. Повторяющие цепочки в кодированном сообщении хранятся как ссылка на первое появление данной цепочки. Например, в цепочке КЗСЗБСКЗСЗБ начиная с 7 символа, идет цепочка КЗСЗ, которую мы можем заменить ссылкой на 1-ый символ. Рассмотрим наиболее распространенные реализации алгоритма LZ:
LZ77 - при работе выдает тройки вида (A, B, C), где A - смещение (адрес предыдущей цепочки B байтов которой совпадают с кодируемой цепочкой), B - длина цепочки, C - первый символ в кодируемом массиве, следующий за цепочкой. Если совпадение не обнаружено то создается тройка вида (0, 0, С), где C - первый символ кодируемой цепочки. Недостаток такого подхода очевиден - при кодировании “редких” байтов мы “сжимаем” один байт в три. Преимущество - простота реализации, большая скорость декодирования.
LZSS - создает при работе вектора вида (флаг, C) и (флаг, A, B). Если битовый флаг=0, то следующий за ним C трактуется, как единичный байт и выдается в декодируемый массив. Иначе, когда флаг=1, то в декодируемый массив выдается цепочка длиною B по смещению A. LZSS кодирует намного более эффективно, по сравнению с LZ77, так как использует битовые флаги и мало проигрывает при кодировании одиночных символов. При кодировании строится словарь встречающихся цепочек в виде двоичного упорядоченного дерева. Скорость и простота алгоритма декодирования массива у LZSS также высока.
LZMX (упрощенный LZM) - данный алгоритм предназначен для скоростного кодирования и по эффективности уступает LZSS, заметно обгоняя его по скорости работы. При работе кодер LZMX формирует несколько векторов вида:
(0, A, несжатый поток) - где 00 -2х битовый флаг признака данного блока, A (7 битов с диапазоном в [1..127]) - длина следующего за ним несжатого потока в байтах..
(0, 0000000, A, B) - где, A - количество повторяющего байта B. То есть код RLE.
(1, A, B) - где A(7 битов с диапазоном в [1..127]) - длина декодируемой цепочки, B - ее смещение.
Для быстрого поиска повторяющихся цепочек используется хеш. Индекс - 12 битовый, вычисляется как [ (a*4) xor (b*2) ] xor c, где a, b, c - первые символы цепочки. Индекс дает смещение в массиве ранее встреченной цепочки с теми же первыми символами. Использование хеша и дает высокую скорость кодирования.
Декодирование также имеет большую скорость - читается бит - флаг, если он есть 0 и следующие за ним 7 битов также ноль, читаем следующие два байта - A и B и копируем в выходной массив байт B A - раз: если при флаге=0 следующие 7 битов=A больше нуля, то в выходной массив копируем A байтов следующих за A. И, наконец, если флаг установлен в единицу, то читаем A иследующий за ним байт B и копируем в выходной массив цепочку длиною A байт со смещения B.
Существуют и другие модификации алгоритма LZ (LZW, LZS, LZ78 ...). Общее свойство LZ - высокая скорость декодирования. Общая проблема - эффективность поиска кодируемых цепочек. Модификация данного алгоритма используется в графическом формате GIF.
Энтропийное сжатие в отличие от последовательного, в качестве информации о входном массиве использует только частоты встречаемости в нем отдельных байтов. Эту информацию он использует как при кодировании, так и при декодировании массива. Ее представляют в виде 256 компонентного вектора, координата i которого представляет собой сколько раз байт со значением i встречается в исходном массиве. Данный вектор занимает небольшое пространство и почти не влияет на степень компрессии. Многие методы энтропийного кодирования видоизменяют данный вектор в соответствии с используемым алгоритмом. Рассмотрим два наиболее часто используемых методов:
Метод Хаффмана. Данный метод сокращает избыточность массива, создавая при кодировании переменную битовую длину его элементов. Основной принцип таков: наиболее часто встречающемуся байту - наименьшую длину, самому редкому - наибольшую. Рассмотрим простейший пример кодирования методом Хаффмана - способ конечного нуля. Любой элемент кодируется цепочкой битов, состоящей из одних единиц и кончающийся нулем. Таким образом, самый частый закодируем одним битом - 0, следующий за ним по частоте как 10, далее - 110, 1110, 11110 и т.д. Процедура декодирования также очевидна.
Рассмотрим вышесказанное на примере. Пусть дана часть изображения длиной 80 бит - десять цветов и каждый из них закодирован одним байтом (индексированное 256 цветами изображение): КЗСГКСКБСК (где К - красный, З - зеленый и т.д.). Закодируем его. Построим таблицу частоты встречаемости цветаи кода ему соответствующего:
| Цвет | Частота | Код |
| К | 4 | 0 |
| З | 1 | 110 |
| С | 3 | 10 |
| Г | 1 | 1110 |
| Б | 1 | 11110 |
Таким образом, мы закодировали исходный массив как 0 110 10 1110 0 10 0 11110 10 0. Итого: длина выходного сообщения - 22 бита. Степень компрессии ~4.
Метод арифметического кодирования. Данный метод появился позднее. Его принцип - кодирование исходного массива одним числом. Часто входной массив разбивают на одинаковые небольшие участки и кодируют их по отдельности, получая в результате последовательность кодовых чисел. Закодируем предыдущий пример числом, лежащим в единичном диапазоне. Схема кодировки следующая. Строим таблицу частот, каждому элементу таблицы ставим в соответствие диапазон, равный его частоте поделенной на длину входного массива. Устанавливаем верхнюю границу ВГ в 1, нижнюю НГ в 1. Далее N раз выполняем следующую последовательность действий (где N - длина кодируемого участка или всего массива):
Читаем из массива очередной символ.
Установка текущего интервала. Интервал И = ВГ - НГ.
ВГ = НГ + И*ВГ символа (берем из таблицы).
НГ = НГ + И*НГ символа (берем из таблицы).
Рассмотрим на примере: КЗСГКСКБСК. Построим необходимую таблицу:
| Цвет | Частота | Нижняя граница НГ | Верхняя граница ВГ |
| К | 4 | 0 | 0.4 |
| З | 1 | 0.4 | 0.5 |
| С | 3 | 0.5 | 0.8 |
| Г | 1 | 0.8 | 0.9 |
| Б | 1 | 0.9 | 1 |
Теперь, собственно, сама процедура кодирования:
| Шаг | Символ | НГ | ВГ | Интервал |
| 0 | 0 | 1 | 1 | |
| 1 | К | 0 | 0.4 | 0.4 |
| 2 | З | 0.16 | 0.2 | 0.04 |
| 3 | С | 0.18 | 0.192 | 0.012 |
| 4 | Г | 0.1896 | 0.1908 | 0.0012 |
| 5 | К | 0.1896 | 0.19008 | 0.00048 |
| 6 | С | 0.18984 | 0.189984 | 0.000144 |
| 7 | К | 0.18984 | 0.1898976 | 0.0000576 |
| 8 | Б | 0.18989184 | 0.1898976 | 0.00000576 |
| 9 | С | 0.18989472 | 0.189896448 | 0.000001728 |
| 10 | К | 0.18989472 | 0.1898954112 | 0.0000006912 |
Таким образом, любое число в диапазоне [0.18989472 .. 0.1898954112] однозначно кодирует исходный массив. В двоичном дробном виде как 0.XXXXXXXX...Для хранения такого числа хватит n бит (размерность XXXXXXXX....), где n ближайшее целое, удовлетворяющее неравенству: 2n > Интервал-1=0.0000006912-1. Искомое n равно 21. То есть мы можем закодировать исходный массив 21 битом. В данном примере - 001100001001110111111. Процедура декодирования обратная и состоит в выполнении n раз следующего:
Ищем в таблице интервал, в который попадает наше число Ч, и выдаем символ в него входящий в декодируемый массив.
Интервал И = ВГ символа - НГ символа (оба значения - из таблицы).
Ч = (Ч - НГ) / И.
| Шаг | Число | Символ | НГ | ВГ | Интервал |
| 1 | 0.18989472 | К | 0 | 0.4 | 0.4 |
| 2 | 0.4747368 | З | 0.4 | 0.5 | 0.1 |
| 3 | 0.747368 | С | 0.5 | 0.8 | 0.3 |
| 4 | 0.82456 | Г | 0.8 | 0.9 | 0.1 |
| 5 | 0.2456 | К | 0 | 0.4 | 0.4 |
| 6 | 0.614 | С | 0.5 | 0.8 | 0.3 |
| 7 | 0.38 | К | 0 | 0.4 | 0.4 |
| 8 | 0.95 | Б | 0.9 | 1 | 0.1 |
| 9 | 0.5 | С | 0.5 | 0.8 | 0.3 |
| 10 | 0 | К | 0 | 0.4 | 0.4 |
В данном примере арифметический кодер “обогнал” метод Хаффмана на 1 бит. В отличие от метода Хаффмана трудоемкость алгоритма значительна. В чем же тогда “полезность” алгоритма? Рассмотрим последовательность КККККККС. При кодировании методом Хаффмана получим выходную последовательность длиной в 9 бит (можно и в 8, так как массив состоит из 2 разных байт). При арифметическом кодировании данную последовательность можно закодировать числом 0.4375 или в двоичном виде как 0111, занимающей 4 бита. То есть при арифметическом кодировании возможно получать плотность кодирования меньше бита на символ. Это свойство проявляется, когда во входном массиве частоты некоторых символов значительно выше остальных.