96
правок
Изменения
→Принципы работи алгоритма
Можно сказать, что алгоритмы семейства LZ* представляют собой более сложное обобщение простого и интуитивного способа сжатия данных, используемого в [[RLE]].
=== Принципы работи алгоритма ===
Основная суть алгоритма заключается - ето замена повторно вхождения строки ссылкою на одну из предыдущих позиций вхождения.
Для етого используют метод скользящего окна.
Метод кодирования согласно принципу скользящего окна учитывает уже ранее встречавшуюся информацию, то есть информацию, которая уже известна для кодировщика и декодировщика (второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на ее первое вхождение).
Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне».
Размер скользящего окна может динамически изменяться и составлять 2, 4 или 32 килобайта. Следует также отметить, что размер окна кодировщика может быть менее или равен размеру окна декодировщика, но не наоборот.
Рассмотрим последовательность из N элементов. Если все элементы последовательности уникальны, то такая последовательность не будет содержать ни одного повторяющегося элемента, или, иначе говоря, в последовательности не найдется хотя бы двух равных друг другу или совпадающих элементов.
В стандартном алгоритме LZ77 совпадения строки кодируются парой:
Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад в буфере и скопировать 7 символов, начиная с текущей позиции». Каким образом можно скопировать 7 символов из буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентны) с 1 символом перед ними.
Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары ''длина-смещение''.
=== Пример "abracadabra" ===
Поз. Длина Симв.
