96
правок
Изменения
→LZ77
== LZ77 ==
Можно сказать, что алгоритмы семейства LZ* представляют собой более сложное обобщение простого и интуитивного способа сжатия данных, используемого в [[RLE]].
=== Принципы работи работы алгоритма ===Основная суть алгоритма - ето это замена повторно вхождения строки ссылкою на одну из предыдущих позиций вхождения.Для етого этого используют метод скользящего окна.
Скользящее окно можно представить в виде динамической структуры данных который организован так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ.
Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне».
Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары ''длина-смещение''.
=== Описания алгоритма===
LZ77 использует "скользящее" по сообщению окно. Допустим на текущей итерации окно зафиксировано. С правой стороны окна наращиваем подстроку пока она есть в строке скользящее окно+наращиваемая строка и начинается в скользящем окне. Назовем наращиваемую строку буфером. После наращивания алгоритм выдает код состоящий из трех элементов:
* смещение в окне;
* длина буфера;
