Алгоритм сжатия

В алгоритме сжатия LZ77 и его вариантах используются два буфера. В скользя­щем буфере предыстории хранятся N только что обработанных символов источника, а в упреждающем буфере содержатся следующие L символов, ожидающих обработки. Алгоритм пытается найти соответствие между двумя и более символами из начала упреждающего буфера и строкой в скользящем буфе­ре предыстории. Если соответствие не обнаружено, первый символ упреждающе­го буфера выводится как 9-битовый символ, а также сдвигается в скользящее окно, при этом самый старый символ выбрасывается из скользящего окна. Если совпа­дение обнаруживается, алгоритм продолжает искать самое длинное совпадение. Затем строка, для которой найдено соответствие, выводится в виде триплета (инди­катор, указатель, длина). Затем из скользящего окна выдвигаются столько символов, сколько содержится в кодированной триплетом последовательности, и столько же новых символов исходного текста помещаются в скользящее окно.

На нижней части рисунка показана работа данной схемы с последовательностью из на­шего примера. В иллюстрации предполагается использование 39-символьного скользящего окна и 13-символьного упреждающего буфера. В верхней части примера первые 40 символов были обработаны, и несжатая версия последних 39 символов находится в скользящем окне. Остальная часть сообщения нахо­дится в упреждающем буфере. Алгоритм сжатия находит следующее совпадение, сдвигает 5 символов из упреждающего буфера в скользящее окно и формирует код для этой строки. Состояние буфера после этих операций показано в нижней части примера.

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