Энтропия набора данных, а значит и максимально возможная степень сжатия, зависит от модели. Чем адекватнее модель (чем качественнее мы можем предсказать распределение вероятности значений следующего элемента), тем ниже энтропия и тем лучше максимально достижимая степень сжатия. Таким образом, сжатие данных разбивается на две самостоятельные задачи - моделирование и кодирование.
Моделирование обеспечивает предсказание вероятности наступления возможных событий, кодирование обеспечивает представление события в виде -log2pбит, где р - предсказанная вероятность наступления события. Задача моделирования, как правило, более сложная. Это обусловлено высокой сложностью современных моделей данных. В то же время кодирование не является серьезной проблемой. Существует большое количество стандартных кодеров, различающихся по степени сжатия и быстродействию. Как правило, в системах сжатия используемый кодер при необходимости может быть легко заменен другим.
Некоторые алгоритмы сжатия данных
Алгоритм LZ77
Этот словарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977 г., но сам алгоритм разработан не позднее 1975 г.
Алгоритм LZ77 является родоначальником целого семейства словарных схем - так называемых алгоритмов со скользящим словарем, или скользящим окном. Действительно, в LZ77 в качестве словаря используется блок уже закодированной последовательности. Как правило, по мере выполнения обработки положение этого блока относительно начала последовательности постоянно меняется, словарь "скользит" по входному потоку данных.
Скользящее окно имеет длину N, т. е. в него помещается N символов, и состоит из двух частей:
■ последовательности длины W=N-nуже закодированных символов, которая и является словарем;
■ упреждающего буфера, или буфера предварительного просмотра, длины n; обычно и на порядки меньше W.
Пусть к текущему моменту времени мы уже закодировали tсимволов S1, S2, ...,St. Тогда словарем будут являться Wпредшествующих символов St-(W-1), St-(W-1)+1, …, St. Соответственно, в буфере находятся ожидающие кодирования символы St+1, St+2, …, St+n. Очевидно, что если W≥ t, то словарем будет являться вся уже обработанная часть входной последовательности.
Идея алгоритма заключается в поиске самого длинного совпадения между строкой буфера, начинающейся с символа St+1, и всеми фразами словаря. Эти фразы могут начинаться с любого символа St-(W-1), St-(W-1)+1,…, Stвыходить за пределы словаря, вторгаясь в область буфера, но должны лежать в окне. Следовательно, фразы не могут начинаться с St+1. поэтому буфер не может сравниваться сам с собой. Длина совпадения не должна превышать размера буфера. Полученная в результате поиска фраза St-(i-1), St-(i-1)+1, …, St-(i-1)+(j-1) кодируется с помощью двух чисел:
1) смещения (offset) от начала буфера, i;
2) длины соответствия, или совпадения (matchlength), j;
Смещение и длина соответствия играют роль указателя (ссылки), однозначно определяющего фразу. Дополнительно в выходной поток записывается символ s, непосредственно следующий за совпавшей строкой буфера.
Таким образом, на каждом шаге кодер выдает описание трех объектов: смещения и длины соответствия, образующих код фразы, равной обработанной строке буфера, и одного символа s(литерала). Затем окно смещается на j+1 символов вправо и осуществляется переход к новому циклу кодирования. Величина сдвига объясняется тем, что мы реально закодировали именно j+1 символов: j с помощью указателя на фразу в словаре и 1(? i) с помощью тривиального копирования. Передача одного символа в явном виде позволяет разрешить проблему обработки еще ни разу не виденных символов, но существенно увеличивает размер сжатого блока.
Алгоритм LZ78-LZW84
Алгоритм LZ78, предложенный в 1978 г. Лемпелом и Зивом, нашел свое практическое применение только после реализации LZW84, предложенной Велчем в 1984 г.
Словарь является расширяющимся (expanding). Первоначально в нем содержится только 256 строк длиной в одну букву-все коды ASCII. В процессе работы словарь разрастается до своего максимального объема |Vmax| строк (слов). Обычно, объем словаря достигает нескольких десятков тысяч слов. Каждая строка в словаре имеет свою известную длину и этим похожа на привычные нам книжные словари и отличается от строк LZ77, которые допускали использование подстрок. Таким образом, количество слов в словаре точно равно его текущему объему. В процессе работы словарь пополняется по следующему закону:
1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позиции posисходного текста. Так как словарь первоначально не пустой, такое слово всегда найдется;
2. В выходной файл помещается номер найденного слова в словаре positionи следующий символ из входного текста В (на котором обнаружилось различие) - <position,B>. Длина кода равна |position|+|B||=[logVmax]+8 (бит);
3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;
4. Указатель в исходном тексте posсмещается на |strB|=|str|+l байт дальше к символу, следующему за В.
В таком варианте алгоритм почти не нашел практического применения и был значительно модернизирован. Изменения коснулись принципов управления словарем (его расширения и обновления) и способа формирования выходного кода:
Птак как словарь увеличивается постепенно и одинаково для кодировщика и декодировщика, для кодирования позиции нет необходимости использовать [logVmax] бит, а можно брать лишь [logV] бит, где V-текущий объем словаря.
Самая серьезная проблема LZ78-переполнение словаря: если словарь полностью заполнен, прекращается его обновление и процесс сжатия может быть заметно ухудшен (метод FREEZE). Отсюда следует вывод-словарь нужно иногда обновлять. Самый простой способ как только словарь заполнился его полностью обновляют. Недостаток очевиден кодирование начинается на пустом месте, как бы с начала, и пока словарь не накопится сжатие будет незначительным, а дальше-замкнутый цикл опять очистка словаря!.. Поэтому предлагается словарь обновлять не сразу после его заполнения, а только после того, как степень сжатия начала падать (метод FLUSH). Более сложные алгоритмы используют два словаря, которые заполняются синхронно, но с задержкой на |V|/2 слов один относительно другого. После заполнения одного словаря, он очищается, а работа переключается на другой (метод SWAP). Еще более сложными являются эвристические методы обновления словарей в зависимости от частоты использования тех или иных слов (LRU, TAG).
Выходной код также формируется несколько иначе (сравните с предыдущим описанием):
1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позицииposисходного текста;
2. В выходной файл помещается номер найденного слова в словаре <positior>. Длина кода равна |position|=[logV] (бит);
3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;
4. Указатель в исходном тексте posсмещается на |str| байт дальше к символу В.
Алгоритм PPM
Алгоритм PPM (predictionbypartialmatching) - это метод контекстно-ограниченного моделирования, позволяющий оценить вероятность символа в зависимости от предыдущих символов. Строку символов, непосредственно предшествующую текущему символу, будем называть контекстом. Модели, в которых для оценки вероятности используются контексты длиной не более чем N, принято называть моделями порядка N.
Вероятность символа может быть оценена в контекстах разных порядков. Например, символ "о" в контексте "tobeornott" может быть оценен в контексте первого порядка «t», в контексте второго порядка «_t», в контексте третьего порядка «t_t» и т.д. Он также может быть оценен в контексте нулевого порядка, где вероятности символов не зависят от контекста, и в контексте минус первого порядка, где все символы равновероятны. Контекст минус первого порядка используется для того, чтобы исключить ситуацию, когда символ будет иметь нулевую вероятность и не сможет быть закодирован. Это может случиться, если вероятность символа не будет оценена ни в одном из контекстов (что возможно, если символ в них ранее не встречался).
Существуют два основных подхода к вычислению распределения вероятностей следующего символа на основе вероятностей символов в контекстах. Первый подход называется «полное перемешивание». Он предполагает назначение весов контекстам разных порядков и получение суммарных вероятностей сложением вероятностей символов в контекстах, умноженных на веса этих контекстов. Применение такого подхода ограничено двумя факторами. Во-первых, не существует быстрой реализации данного алгоритма. Во-вторых, не разработан эффективный алгоритм вычисления весов контекстов. Примитивные же подходы не обеспечивают достаточно высокой точности оценки и, как следствие, степени сжатия.
Второй подход называется «методом исключений». При этом подходе сначала делается попытка оценить символ в контексте самого высокого порядка. Если символ кодируется, алгоритм переходит к кодированию следующего символа. В противном случае кодируется «уход» и предпринимается попытка закодировать символ в контексте меньшего порядка. И так далее, пока символ не будет закодирован.