Изменения

Можно сказать, что алгоритмы семейства LZ* представляют собой более сложное обобщение простого и интуитивно понятного способа сжатия данных, используемого в [[RLE]].=== Принципы работы Описание алгоритма ===Основная идея алгоритма <tex>-</tex> это замена повторного вхождения строки ссылкой LZ77 использует уже просмотренную часть сообщения как словарь. Чтобы достигнуть сжатия, алгоритм пытается заменить очередной фрагмент сообщения на одну из предыдущих позиций вхожденияуказатель в содержимое словаря.Для этого используют метод скользящего окна.Скользящее В качестве модели данных LZ77 использует "скользящее" по сообщению окно можно представить в виде динамической структуры данных, которая организована такразделенное на две неравных части. Первая часть, большая по размеру, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступвключает уже просмотренную часть сообщения.Таким образомВторая, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программынамного меньшая, команды которой позволяют обращаться к элементам скользящего окна- буфер, и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в скользящем окнесодержащий еще не закодированные символы.В стандартном алгоритме LZ77 совпадения строки кодируются парой:* длина совпадения (match length)* смещение (offset) или дистанция (distance)Кодируемая пара трактуется именно как команда копирования символов из скользящего Как правило, размер окна с определенной позиции, или дословно как: «Вернуться в словаре на ''значение смещения'' символов и скопировать ''значение длины'' символов, начиная с текущей позиции»- несколько килобайтов.Особенность данного алгоритма сжатия заключается в томБуфер намного меньше, что использование кодируемой пары ''длина-смещение'' является обычно не только приемлемымбольше, но и эффективным в тех случаях, когда значение длины превышает значение смещениячем сто байтов.Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад Алгоритм пытается найти фрагмент в буфере и скопировать 7 символовсловаре, начиная который совпадает с текущей позиции». Каким образом можно скопировать 7 символов из содержанием буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентны) с 1 символом перед ними.Это означает, что каждый символ можно однозначно определить переместившись назад в буфере, даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары ''длина-смещение''.=== Описания алгоритма===Алгоритм LZ77 использует скользящее по сообщению окно. Допустимвыдает коды, на текущей итерации окно зафиксировано. С правой стороны окна наращиваем подстроку, пока она есть в строке <скользящее окно + наращиваемая строка> и начинается в скользящем окне. Назовем наращиваемую строку буфером. После наращивания алгоритм выдает код состоящий состоящие из трех элементов: * смещение в окнесловаре относительно его начала подстроки, которая соответствует содержанию буфера;* длина буфераподстроки;* последний первый символ буферав буфере после подстроки.В конце итерации После этого алгоритм сдвигает перемещает окно на длину равную длине буферасовпадающей подстроки +1символ влево. Если совпадение не найдено, алгоритм выдает код ''<0, 0, первый символ в буфере>'' и продолжает свою работу. Хотя такое решение неэффективно, оно гарантирует, что алгоритм сможет закодировать любое сообщение.=== Пример <tex>kabababababz</tex> ===

!Содержимое окнаСообщение !Содержимое буфераПодстрока !КОДКод

|<tex>kabababababz\fbox{kababa}bababz</tex> |<tex>k</tex>

|<tex>kabababababzk\fbox{ababab}ababz</tex> |<tex>a</tex>

|<tex>kabababababzka\fbox{bababa}babz</tex> |<tex>b</tex>

|<tex>kkab\fbox{abababab}ababababzabz</tex> |<tex>abaab</tex>

|<tex>kabakababa\fbox{bababbababz}abz</tex> |<tex>bababzbabab</tex>