55
правок
Изменения
Нет описания правки
'''Алгори́тм Ле́мпеля — Зи́ва — Ве́лча''' ('''Lempel-Ziv-Welch''', '''LZW''') — это универсальный алгоритм сжатия данных без потерь, созданный Абрахамом Лемпелем(''Abraham Lempel''), Якобом Зивом (''Jacob Ziv'') и Терри Велчем (''Terry Welch''). Он был опубликован Велчем в 1984 году, в качестве улучшенной реализации [[Алгоритм LZ78|алгоритма LZ78]], опубликованного Лемпелем и Зивом в 1978 году.
Алгоритм разработан так, чтобы его можно было быстро реализовать, но он не обязательно оптимален, поскольку он не проводит никакого анализа входных данных.
== Применение ==
В настоящее время, алгоритм содержится в стандарте PDF.
== Описание ==
Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов — это 256 записей). По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.
Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту.
== Алгоритм ==
