Изменения
Нет описания правки
Основная суть алгоритма - ето замена повторно вхождения строки ссылкою на одну из предыдущих позиций вхождения.
Для етого используют метод скользящего окна.
Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне».
В стандартном алгоритме LZ77 совпадения строки кодируются парой:
* длина совпадения (match length)
Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары ''длина-смещение''.
=== Описания алгоритма===
LZ77 использует "скользящее" по сообщению окно, разделенное . Допустим на две неравные частитекущей итерации окно зафиксировано. Первая, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, является буфером, содержащим еще незакодированные символы входного потока. Обычно размер буфера составляет не более ста байт. Алгоритм пытается найти С правой стороны окна наращиваем подстроку пока она есть в строке скользящее окно+наращиваемая строка и начинается в скользящем окне фрагмент, совпадающий с содержимым буфера. Алгоритм LZ77 После наращивания алгоритм выдает коды, состоящие код состоящий из трех элементов:
* смещение в окне;
* длина подстроки;
* первый символ буфера, следующий за подстрокой.
В конце итерации алгоритм сдвигает окно на длину подстроки+1.=== Пример "КРАСНАЯ КРАСКАkabababk" ==={| border="21"
!Содержымое окна
!Содержимое буфераНаращиваемая строка
!КОД
|-
