Как работает алгоритм LZ77?

Пользователь

от janiya , в категории: Общие вопросы , 2 года назад

Как работает алгоритм LZ77?

Facebook Vk Ok Twitter LinkedIn Telegram Whatsapp Pocket

2 ответа

Пользователь

от francisca.kertzmann , год назад

@janiya 

Алгоритм LZ77 используется для сжатия данных без потерь. Он основан на поиске и замене повторяющихся фрагментов данных.


Работа алгоритма LZ77 происходит следующим образом:

  1. Алгоритм просматривает входные данные последовательно, считывая символ за символом.
  2. Когда алгоритм обнаруживает повторяющийся фрагмент данных, он создает словарь, состоящий из сдвига (offset) и длины (length) повторяющегося фрагмента.
  3. Сдвиг (offset) указывает на позицию начала повторяющегося фрагмента относительно текущей позиции чтения.
  4. Длина (length) указывает на количество символов повторяющегося фрагмента.
  5. Словарь сдвигов и длин запоминается и используется для декодирования сжатых данных.
  6. Алгоритм продолжает просматривать входные данные до тех пор, пока не достигнет конца строки или установленного ограничения сжатия.
  7. Затем алгоритм осуществляет кодировку данных с помощью сдвигов и длин, создавая сжатую последовательность.
  8. Распаковка данных осуществляется путем восстановления повторяющихся фрагментов с помощью словаря сдвигов и длин.


Алгоритм LZ77 достаточно эффективен для сжатия текстовых данных и других типов файлов, содержащих повторяющиеся фрагменты. Он широко используется в архиваторах, сжатии данных в сетевых протоколах и других приложениях сжатия данных.

Пользователь

от regan.gerhold , год назад

@janiya 

Алгоритм LZ77 работает следующим образом:

  1. Инициализация: Алгоритм начинает с пустого словаря сдвигов и длин.
  2. Просмотр данных: Алгоритм последовательно просматривает входные данные и считывает символы один за другим.
  3. Поиск повторяющихся фрагментов: Алгоритм ищет самое длинное повторение текущего фрагмента данных в словаре. Если находит такое повторение, то определяет его сдвиг и длину.
  4. Кодирование: Алгоритм кодирует найденное повторение, записывая пару (сдвиг, длина) в выходной поток данных.
  5. Обновление словаря: Алгоритм добавляет новый фрагмент данных в словарь. Этот фрагмент состоит из текущего символа и следующих символов, взятых из входных данных.
  6. Повторение шагов 2-5: Алгоритм повторяет шаги 2-5 для оставшихся символов входных данных.
  7. Завершение: Алгоритм завершается, когда все символы входных данных обработаны. Полученная сжатая последовательность данных записывается в выходной файл или передаётся по сети.


В процессе декодирования алгоритм использует словарь сдвигов и длин для восстановления оригинальных данных. Он перебирает записанные пары (сдвиг, длина) и восстанавливает повторяющиеся фрагменты, добавляя их в выходной поток данных.


Весь процесс работы алгоритма LZ77 основан на нахождении и использовании повторяющихся фрагментов в исходных данных для сокращения их объема и достижения сжатия.