96
правок
Изменения
Нет описания правки
Для етого используют метод скользящего окна.
Метод кодирования согласно принципу скользящего окна учитывает уже ранее встречавшуюся информацию, то есть информацию, которая уже известна для кодировщика и декодировщика (второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на ее первое вхождение).
Скользящее окно можно представить в виде буфера (или более сложной динамической видединамической структуры данных), который организован так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ.
Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне».
Размер скользящего окна может динамически изменяться и составлять 2, 4 или 32 килобайта. Следует также отметить, что размер окна кодировщика может быть менее или равен размеру окна декодировщика, но не наоборот.
* длина совпадения (match length)
* смещение (offset) или дистанция (distance)
Кодируемая пара трактуется именно как команда копирования символов из скользящего окна с определенной позиции, или дословно как: «Вернуться в буфере символов словаре на ''значение смещения'' символов и скопировать ''значение длины'' символов, начиная с текущей позиции».
Особенность данного алгоритма сжатия заключается в том, что использование кодируемой пары ''длина-смещение'' является не только приемлемым, но и эффективным в тех случаях, когда значение длины превышает значение смещения.
Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад в буфере и скопировать 7 символов, начиная с текущей позиции». Каким образом можно скопировать 7 символов из буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентны) с 1 символом перед ними.
Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары ''длина-смещение''.
=== Описания алгоритма===
LZ77 использует "скользящее" по сообщению окно, разделенное на две неравные части. Первая, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, является буфером, содержащим еще незакодированные символы входного потока. Обычно размер буфера составляет не более ста байт. Алгоритм пытается найти в словаре (большей части окна) скользящем окне фрагмент, совпадающий с содержимым буфера.Алгоритм LZ77 выдает коды, состоящие из трех элементов: * смещение в словаре относительно его начала подстроки, совпадающей с началом содержимого буфера; * длина этой подстроки; * первый символ буфера, следующий за подстрокой.=== Пример "abracadabramississippi" ===
Поз. Длина Симв.
''abracadabramississippi '' 0 0 a
a ''bracadabra'' 0 0 b
ab ''racadabra'' 0 0 r
