2
правки
Изменения
Правка пунктационных и речевых ошибок.
'''LZ77''' и '''LZ78''' — алгоритмы сжатие сжатия без потерь, опубликованные в статьях Абрахама Лемпеля и Якоба Зива в 1977 и 1978 годах. Эти алгоритмы наиболее известные варианты известны в семействе LZ*, которое включает в себя также [[Алгоритм LZW|LZW]], LZSS, LZMA и другие алгоритмы.Оба алгоритма относятся к алгоритмам со словарным методамподходом. LZ77 является алгоритмом со «скользящим окном»использует, так называемое, «скользящее окно», что эквивалентно неявному использованию словарного подхода, впервые предложенного в LZ78.
== LZ77 ==
Можно сказать, что алгоритмы семейства LZ* представляют собой более сложное обобщение простого и интуитивного интуитивно понятного способа сжатия данных, используемого в [[RLE]].
=== Принципы работы алгоритма ===
Основная суть алгоритма - это замена повторно повторного вхождения строки ссылкою ссылкой на одну из предыдущих позиций вхождения.
Для этого используют метод скользящего окна.
Скользящее окно можно представить в виде динамической структуры данных который организован , которая организована так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ.Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна»скользящего окна, и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне»скользящем окне.
В стандартном алгоритме LZ77 совпадения строки кодируются парой:
* длина совпадения (match length)
Особенность данного алгоритма сжатия заключается в том, что использование кодируемой пары ''длина-смещение'' является не только приемлемым, но и эффективным в тех случаях, когда значение длины превышает значение смещения.
Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад в буфере и скопировать 7 символов, начиная с текущей позиции». Каким образом можно скопировать 7 символов из буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентны) с 1 символом перед ними.
Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — , даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары ''длина-смещение''.
=== Описания алгоритма===
LZ77 использует "скользящее" по сообщению окно. Допустим , на текущей итерации окно зафиксировано. С правой стороны окна наращиваем подстроку , пока она есть в строке <скользящее окно + наращиваемая строка > и начинается в скользящем окне. Назовем наращиваемую строку буфером. После наращивания алгоритм выдает код состоящий из трех элементов:
* смещение в окне;
* длина буфера;
== LZ78 ==
=== Описание алгоритма ===
В отличие от LZ77, работающего с уже полученными данными, LZ78 ориентируется на данные, которые только будут получены (LZ78 не использует «скользящее» скользящее окно, он хранит словарь из уже просмотренных фраз). Алгоритм считывает символы сообщения до тех пор, пока накапливаемая подстрока входит целиком в одну из фраз словаря. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, алгоритм генерирует код, состоящий из индекса строки в словаре, которая до последнего введенного символа содержала входную строку, и символа, нарушившего совпадение. Затем в словарь добавляется введенная подстрока. Если словарь уже заполнен, то из него предварительно удаляют менее всех используемую в сравнениях фразу. Если в конце алгоритма мы не находим мы не находим символ , нарушивший совпадения , то тогда мы выдаем код в виде <индекс строки в словаре без последнего символа, последний символ>.
=== Пример "kabababababz" ===
