Алгори́тм Ле́мпеля — Зи́ва — Уэлча (Lempel-Ziv-Welch, LZW) — это универсальный алгоритм сжатия данных без потерь, созданный Авраамом Лемпелем, Яаковом Зивом и Терри Велчем. Он был опубликован Велчем в 1984 году в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм разработан так, чтобы его было достаточно просто реализовать как программно, так и аппаратно.
Акроним «LZW» указывает на фамилии изобретателей алгоритма: Лемпель, Зив и Велч, но многие утверждают, что, поскольку патент принадлежал Зиву, то метод должен называться алгоритмом Зива — Лемпеля — Велча.
Описание Данный алгоритм при кодировании (сжатии) сообщения динамически создаёт словарь фраз: определённым последовательностям символов (фразам) ставятся в соответствие группы битов (коды) фиксированной длины (например, 12-битные, как предлагается в исходной статье Велча). Словарь инициализируется всеми 1-символьными фразами (в случае 8-битных символов — это 256 фраз). По мере кодирования алгоритм просматривает текст символ за символом слева направо. При чтении алгоритмом очередного символа в данной позиции находится строка максимальной длины, совпадающая с какой-то фразой из словаря. Затем код этой фразы подаётся на выход, а строка , где — это символ, следующий за во входном сообщении, вносится в словарь в качестве новой фразы и ей присваивается какой-то код (так как выбрана жадно, ещё не содержится в словаре). Символ используется в качестве начала следующей фразы. Более формально данный алгоритм можно описать следующей последовательностью шагов:
Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы первым символом сообщения. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для и завершить алгоритм. Считать очередной символ из кодируемого сообщения. Если фраза уже есть в словаре, то присвоить входной фразе значение WK и перейти к шагу 2. Иначе выдать код , добавить в словарь, присвоить входной фразе значение и перейти к шагу 2.
Алгоритму декодирования на входе требуется только закодированный текст: соответствующий словарь фраз легко воссоздаётся посредством имитации работы алгоритма кодирования (но есть неочевидные нюансы, обсуждаемые в примере ниже).
Реализация Примечательной особенностью алгоритма LZW является простота реализации, благодаря которой он до сих пор очень популярен, несмотря на зачастую худшую степень сжатия по сравнению с такими аналогами, как LZ77. Обычно LZW реализуется с помощью префиксного дерева, содержащего фразы из словаря: для нахождения нужно просто прочитать как можно более длинную строку из корня дерева, затем для добавления новой фразы нужно присоединить к найденному узлу нового сына по символу , а кодом фразы W может выступать индекс узла в массиве, содержащем все узлы.
Кодирование фраз Использование для фраз кодов фиксированной длины (12 битов в описании Велча) может негативно сказаться на эффективности сжатия, так как, во-первых, для начальных кодируемых символов этот подход скорее будет раздувать данные, а не сжимать (если символ занимает 8 битов), и во-вторых, общий размер словаря () получается не так велик. Первая проблема решается кодированием выходной последовательности алгоритмом Хаффмана (возможно, адаптивным) или арифметическим кодированием. Для решения второй используют другие подходы.
Первый простой вариант — применить какой-нибудь оптимальный универсальный код типа кода Левенштейна или кода Элиаса. В таком случае теоретически словарь может расти неограниченно.
Другой более распространённый вариант — изменять максимальный возможный размер словаря с ростом числа фраз. Изначально, например, максимальный размер словаря полагается 29 (28 кодов при этом уже заняты фразами для кодирования 8-битовых одиночных символов) и на код фразы отводится 9 битов. Когда число фраз становится 29, максимальный размер становится 210 и на коды отводится 10 битов. И так далее. Таким образом, теоретически словарь может быть сколь угодно большим. Этот метод продемонстрирован в примере ниже (обычно, тем не менее, максимальный размер словаря ограничивается; например в LZC — популярной модификации LZW, рассматриваемой ниже — длины кодов растут от 9 до 16 битов).
В большинстве реализаций последнего метода число битов, выделяемых на код фразы, увеличивается до добавления новой фразы , переполняющей словарь, но после записи на выход кода . Например, пусть в данный момент в процессе работы алгоритма длина кода — битов, и алгоритм собирается выдать код фразы и добавить новую фразу в словарь; если код равен (то есть переполняет словарь), то сначала выдаётся -битовый код W и только после этого увеличивается на один, чтобы последующие коды занимали битов. Среди ранних реализаций LZW существуют такие, которые увеличивают до выдачи кода , то есть код , выдаваемый перед добавлением в словарь, уже занимает битов (что не является необходимым, так как код меньше ). Такое поведение называется «ранним изменением» (early change). Эта путаница в реализациях побудила Adobe поддерживать оба варианта LZW в PDF (используются ли «ранние изменения», указывается с помощью специального флага в заголовке сжимаемых данных).
Переполнение словаря Так как коды в алгоритме LZW имеют фиксированную длину, размер словаря ограничен (при использовании кодов нефиксированной длины размер словаря ограничен объёмом доступной памяти). Возникает вопрос: что делать в случае переполнения словаря? Используют несколько стратегий: Самый очевидный вариант — просто использовать построенный словарь без дальнейших модификаций. Ясно, что часто это плохая стратегия. Авторы некогда популярной утилиты просто используют построенный словарь, пока степень сжатия остаётся приемлемой, а затем очищают его в случае ухудшения качества сжатия. Такая модификация LZW называется LZC (Lempel-Ziv-Compress, см. ниже). П. Тисчер предложил перед вставкой в переполненный словарь новой фразы на очередном шаге алгоритма удалять из словаря фразу, которая дольше всего не использовалась (LRU, Least Recently Used). Такая модификация иногда называется LZT (Lempel-Ziv-Tischer, см. ниже).
Пример Данный пример показывает алгоритм LZW в действии, показывая состояние выходных данных и словаря на каждой стадии, как при кодировании, так и при раскодировании сообщения. С тем чтобы сделать изложение проще, мы ограничимся простым алфавитом — только заглавные буквы, без знаков препинания и пробелов. Сообщение, которое нужно сжать, выглядит следующим образом: TOBEORNOTTOBEORTOBEORNOT# Маркер # используется для обозначения конца сообщения. Тем самым, в нашем алфавите 27 символов (26 заглавных букв от A до Z и символ #). Компьютер представляет это в виде групп бит, для представления каждого символа алфавита нам достаточно группы из 5 бит на символ. По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. 5-битные группы дают возможных комбинации бит, поэтому, когда в словаре появится 33-е слово, алгоритм должен перейти к 6-битным группам. Заметим, что, поскольку используется группа из всех нулей 00000, то 33-я группа имеет код 32. Начальный словарь будет содержать: # = 00000 A = 00001 B = 00010 C = 00011 . . . Z = 11010
Кодирование Без использования алгоритма LZW, при передаче сообщения, как оно есть — 25 символов по 5 бит на каждый — оно займёт 125 бит. Сравним это с тем, что получается при использовании LZW:
Символ: Битовый код: Новая запись словаря: (на выходе)
T 20 = 10100 O 15 = 01111 27: TO B 2 = 00010 28: OB E 5 = 00101 29: BE O 15 = 01111 30: EO R 18 = 10010 31: OR <--- со следующего символа начинаем использовать 6-битные группы N 14 = 01110 32: RN O 15 = 01111 33: NO T 20 = 10100 34: OT TO 27 = 11011 35: TT BE 29 = 11101 36: TOB OR 31 = 11111 37: BEO TOB 36 = 100100 38: ORT EO 30 = 11110 39: TOBE RN 32 = 100000 40: EOR OT 34 = 100010 41: RNO # 0 = 00000 42: OT#
Общая длина = 13*5 + 3*6 = 83 бит.
Таким образом, используя LZW, мы сократили сообщение на 29 бит из 125 — это почти 22 %. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно.
Декодирование Теперь представим, что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего, нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей.
Данные: На выходе: Новая запись: Полная: Частичная: 10100 = 20 T 27: T? 01111 = 15 O 27: TO 28: O? 00010 = 2 B 28: OB 29: B? 00101 = 5 E 29: BE 30: E? 01111 = 15 O 30: EO 31: O? 10010 = 18 R 31: OR 32: R? <---- начинаем использовать 6-битные группы 01110 = 14 N 32: RN 33: N? 01111 = 15 O 33: NO 34: O? 10100 = 20 T 34: OT 35: T? 11011 = 27 TO 35: TT 36: TO? <---- для 37, добавляем только первый элемент 11101 = 29 BE 36: TOB 37: BE? следующего слова словаря 11111 = 31 OR 37: BEO 38: OR? 100100 = 36 TOB 38: ORT 39: TOB? 11110 = 30 EO 39: TOBE 40: EO? 100000 = 32 RN 40: EOR 41: RN? 100010 = 34 OT 41: RNO 42: OT? 00000 = 0 #
Единственная небольшая трудность может возникнуть, если новое слово словаря пересылается немедленно. В приведённом выше примере декодирования, когда декодер встречает первый символ, T, он знает, что слово 27 начинается с T, но чем оно заканчивается? Проиллюстрируем проблему следующим примером. Мы декодируем сообщение ABABA: Данные: На выходе: Новая запись: Полная: Частичная: . . . 011101 = 29 AB 46: (word) 47: AB? 101111 = 47 AB? <--- что нам с этим делать?
На первый взгляд, для декодера это неразрешимая ситуация. Мы знаем наперёд, что словом 47 должно быть ABA, но как декодер узнает об этом? Заметим, что слово 47 состоит из слова 29 плюс символ, идущий следующим. Таким образом, слово 47 заканчивается на «символ, идущий следующим». Но, поскольку это слово посылается немедленно, то оно должно начинаться с «символа, идущего следующим», и поэтому оно заканчивается тем же символом, что и начинается, в данном случае — A. Этот трюк позволяет декодеру определить, что слово 47 — это ABA.
В общем случае, такая ситуация появляется, когда кодируется последовательность вида , где — это один символ, а — строка, причём слово уже есть в словаре.
Теоретическая оценка эффективности Теоретические свойства LZW с неограниченным словарём в целом такие же, как и у LZ78, и анализ этих двух методов сжатия аналогичен. При рассмотрении неограниченного словаря естественно предполагать, что выходные фразы кодируются кодами переменной длины, например, каким-нибудь универсальным кодом или фиксированным кодом, размер которого растёт вместе с максимальным размером словаря (см. раздел о реализации).
Асимптотическая оптимальность Для теоретической оценки эффективности данный метод сжатия сравнивают с некоторой эталонной метрикой. К сожалению, идеальная эталонная метрика сжатия данных — Колмогоровская сложность — невычислима даже приблизительно, и поэтому любой алгоритм сжатия заведомо проигрывает в сравнении с ней. Лемпель и Зив предложили ослабленную версию Колмогоровской сложности — сжатие конечными автоматами. По техническим причинам данная метрика определяется для бесконечных строк. Зафиксируем конечный алфавит . Пусть дана бесконечная строка над . Обозначим через число битов в кодировке LZW с неограниченным словарём для строки . Отсюда имеем:
где — это число фраз в LZW кодировке для . Зив показал, что
где — это метрика сжатия конечными автоматами, определённая далее. Таким образом, коэффициент сжатия LZW (отношение к — числу битов, занимаемых несжатой строкой) асимптотически ограничен и в этом смысле LZW оптимален. Более того, если размер словаря ограничен и при переполнении используется стратегия удаления наименее используемых фраз, LZW также асимптотически оптимален в следующем смысле: