Алгоритмы совпадения строк

Такие алгоритмы, как метод Хаффмана и арифметическое кодирование, основаны на знании оценки статистики сжимаемых данных. Эти алгоритмы не адаптируются к изменениям в представлении данных. Кроме того, ограничения памяти ставят предел их способности фиксировать взаимосвязи высокого порядка между слова­ми и фразами текста. Другой подход, доказавший свою эффективность, использу­ется в семействе методов, известных под названием алгоритмов совпадения строк.

В то время как в методе Хаффмана и при арифметическом кодировании вход­ные последовательности фиксированной длины преобразуются в коды переменной длины, алгоритмы совпадения строк преобразуют входные последовательности переменной длины в коды фиксированной длины. Кроме того, алгоритмы совпа­дения строк не выдвигают априорных предположений о статистике данных, а адап­тируются к изменениям в характере входных данных по мере их обработки.

Все алгоритмы данной категории обязаны своим происхождением израильс­ким исследователям Якову Зива (Jacob Zib) и Аврааму Лемпелю (Abraham Lempel). В 1977 г. они описали метод, основанный на буфере скользящего окна, в котором содержится только что обработанный текст. Этот алгоритм обычно называ­ют LZ77. Разновидность этого алгоритма используется в популярной в Интернете схеме сжатия zip (PKZIP, gzip, zipit и т. д.). В следующем году те же авторы опи­сали улучшенную версию этого алгоритма, основанного на структурированном в виде дерева словаре. Этот алгоритм называется LZ78. Затем алгоритм LZ78 был усовершенствован и назван LZW. Многие программы сжатия основаны на алгоритмах LZ78 и LZW, включая стандарт V.42bis сектора ITU-T, предназначен­ный для голосовых модемов, популярный формат сжатия изображений GIF, а так­же программу сжатия данных в операционной системе UNIX. В алгоритмах LZ77, LZ78 и их вариантах используется тот факт, что слова и фразы в потоке текста (элементы изображения в случае GIF) повторяются с боль­шой вероятностью. Когда встречается повторяющаяся последовательность, она может быть заменена коротким кодом. Программа сжатия ищет подобные повто­ряющиеся участки текста и «на лету» формирует коды, которыми заменяет их на выходе. Те же коды могут использоваться для обозначения новых последователь­ностей. Алгоритм должен быть определен таким образом, чтобы программа распа­ковки могла найти текущее соответствие между кодами и последовательностями исходных данных.

Другой способ повышения эффективности алгоритмов совпадения строк состо­ит в том, чтобы учитывать энтропию входных данных, рассматриваемых в виде последовательности строк. Вспомним, что чем выше уровень агрегации входных символов, тем ниже энтропия. Поэтому следует ожидать, что, используя совпаде­ния строк, можно добиться высоких коэффициентов сжатия.