LZ77 и LZ78

LZ77 и LZ78 — два сжатия данных без потерь, алгоритма опубликованные в статьях Авраама Лемпеля и Джейкоба Зива в 1977 году. ^[1] и 1978 год. ^[2] Они также известны как LZ1 и LZ2 соответственно. ^[3]Эти два алгоритма составляют основу для многих вариантов, включая LZW , LZSS , LZMA и другие. Помимо своего академического влияния, эти алгоритмы легли в основу нескольких распространенных схем сжатия, включая GIF и алгоритм DEFLATE , используемый в PNG и ZIP .

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

Поскольку LZ77 кодирует и декодирует из скользящего окна по ранее увиденным символам, распаковка всегда должна начинаться с начала ввода. Концептуально декомпрессия LZ78 могла бы обеспечить произвольный доступ к входным данным, если бы весь словарь был известен заранее. Однако на практике словарь создается во время кодирования и декодирования путем создания новой фразы при каждом выводе токена. ^[4]

Алгоритмы были названы вехой IEEE в 2004 году. ^[5] В 2021 году Джейкоб Зив был награжден Почетной медалью IEEE за участие в их разработке. ^[6]

эффективность Теоретическая

Во второй из двух статей, в которых были представлены эти алгоритмы, они анализируются как кодеры, определяемые конечными автоматами. мера, аналогичная информационной энтропии Для отдельных последовательностей (в отличие от вероятностных ансамблей) разрабатывается . Эта мера дает ограничение на степень сжатия данных , которая может быть достигнута. Затем показано, что существуют конечные кодеры без потерь для каждой последовательности, которые достигают этой границы при увеличении длины последовательности до бесконечности. В этом смысле алгоритм, основанный на этой схеме, дает асимптотически оптимальные кодировки. Этот результат можно доказать более непосредственно, как, например, в заметках Питера Шора . ^[7]

Формально (теорема 13.5.2 ^[8]).

LZ78 универсален и энтропичен — если ${\textstyle X}$ является двоичным источником, который является стационарным и эргодическим, то

\limsup _{n}{\frac {1}{n}}l_{LZ78}(X_{1:n})\leq h(X)

с вероятностью 1. Здесь

{\textstyle h(X)}

- уровень энтропии источника.

Аналогичные теоремы применимы и к другим версиям алгоритма LZ.

LZ77 [ править ]

Алгоритмы LZ77 обеспечивают сжатие путем замены повторяющихся вхождений данных ссылками на одну копию этих данных, существовавшую ранее в потоке несжатых данных. Соответствие кодируется парой чисел, называемой парой длина-расстояние , что эквивалентно утверждению «каждый из следующих символов длины равен символам, расположенным точно на расстоянии символов позади него в несжатом потоке». ( Вместо этого расстояние иногда называют смещением .)

Чтобы обнаружить совпадения, кодировщик должен отслеживать некоторый объем самых последних данных, например последние 2 КБ , 4 КБ или 32 КБ. Структура, в которой хранятся эти данные, называется скользящим окном , поэтому LZ77 иногда называют сжатием скользящего окна . Кодировщику необходимо хранить эти данные для поиска совпадений, а декодеру необходимо хранить эти данные для интерпретации совпадений, на которые ссылается кодер. Чем больше скользящее окно, тем дольше назад кодер может искать создание ссылок.

Не только приемлемо, но и часто полезно разрешить парам длина-расстояние указывать длину, которая фактически превышает это расстояние. В качестве команды копирования это вызывает недоумение: «Вернитесь на четыре символа назад и скопируйте десять символов из этой позиции в текущую позицию». Как можно скопировать десять символов, если на самом деле в буфере находятся только четыре из них? При обработке одного байта за раз нет проблем с обслуживанием этого запроса, поскольку при копировании байта он может быть снова подан в качестве входных данных для команды копирования. Когда позиция копирования достигает исходной позиции назначения, в нее, следовательно, передаются данные, которые были вставлены из начала позиции копирования. Таким образом, эта операция эквивалентна утверждению «копировать данные, которые вам предоставили, и многократно вставлять их, пока они не поместятся». Поскольку этот тип пары повторяет одну копию данных несколько раз, ее можно использовать для включения гибкой и простой формы кодирования длин серий .

Другой способ увидеть ситуацию заключается в следующем: во время кодирования, чтобы указатель поиска продолжал находить совпадающие пары после конца окна поиска, все символы из первого совпадения со смещением D и далее до конца окна поиска должны совпадать. входные данные, и это (видимые ранее) символы, составляющие одну единицу длины L _R , которая должна равняться D . Затем, когда указатель поиска проходит мимо окна поиска и вперед, пока шаблон выполнения повторяется во входных данных, указатели поиска и ввода будут синхронизированы и совпадут с символами до тех пор, пока шаблон выполнения не будет прерван. Тогда L всего было сопоставлено символов, L > D , и код — [ D , L , c ].

При декодировании [ D , L , c снова D = L _R. ] Когда первые символы L _R считываются на выход, это соответствует одной единице выполнения, добавленной в выходной буфер. На этом этапе указатель чтения можно рассматривать как нуждающийся только в возврате int( L / L _R ) + (1, если L mod L _R ≠ 0) раз в начало этого единственного буферизованного модуля выполнения, чтения LR _{символов} ( или, возможно, меньше при последнем возврате) и повторяйте, пока не будет прочитано всего L символов. Но, отражая процесс кодирования, поскольку шаблон повторяется, указатель чтения должен следовать синхронно с указателем записи только на фиксированное расстояние, равное длине серии L _R , пока L символов не будут скопированы для вывода в общей сложности.

Учитывая вышеизложенное, особенно если ожидается, что будет преобладать сжатие прогонов данных, поиск окна должен начинаться в конце окна и продолжаться в обратном направлении, поскольку шаблоны прогона, если они существуют, будут найдены первыми и позволят завершить поиск. абсолютно, если достигнута текущая максимальная длина совпадающей последовательности, или разумно, если достигнута достаточная длина, и, наконец, для простой возможности того, что данные являются более свежими и могут лучше коррелировать со следующим вводом.

Псевдокод [ править ]

Следующий псевдокод представляет собой воспроизведение скользящего окна алгоритма сжатия LZ77.

пока  ввод не пуст,  сделайте 
      match := самое длинное повторяющееся появление ввода, которое начинается в окне 
    
      если  совпадение существует  , то 
          d := расстояние до начала матча 
          l := длина совпадения 
          c := символ, следующий за совпадением во входных данных 
      еще 
          д := 0 
          л := 0 
          c := первый символ ввода 
      конец, если 
    
     вывод  (d, l, c) 
    
      отбросить  l  + 1 символ перед окном 
      s := pop  l  + 1 символ перед вводом 
      добавить s в конец окна 
  повторить

Реализации [ править ]

Несмотря на то, что все алгоритмы LZ77 работают по определению на одном и том же базовом принципе, они могут сильно различаться в том, как они кодируют сжатые данные, чтобы изменять числовые диапазоны пары длина-расстояние, изменять количество битов, потребляемых для пары длина-расстояние, и отличать их пары длина-расстояние от литералов (необработанные данные, закодированные как сами по себе, а не как часть пары длина-расстояние). Несколько примеров:

Алгоритм, проиллюстрированный в оригинальной статье Лемпеля и Зива 1977 года, выводит все данные по три значения одновременно: длину и расстояние самого длинного совпадения, найденного в буфере, и литерал, следующий за этим совпадением. Если бы два последовательных символа во входном потоке можно было закодировать только как литералы, длина пары длина-расстояние была бы равна 0.
LZSS совершенствует LZ77, используя 1-битный флаг, указывающий, является ли следующий фрагмент данных литералом или парой длина-расстояние, а также использует литералы, если пара длина-расстояние будет длиннее.
В формате PalmDoc пара длина-расстояние всегда кодируется двухбайтовой последовательностью. Из 16 бит, составляющих эти два байта, 11 бит идут на кодирование расстояния, 3 — на кодирование длины, а оставшиеся два используются для того, чтобы декодер мог идентифицировать первый байт как начало такого двухбайта. последовательность байтов.
В реализации используется во многих играх Electronic Arts . ^[9]размер пары длина-расстояние в байтах может быть указан внутри первого байта самой пары длина-расстояние; в зависимости от того, начинается ли первый байт с 0, 10, 110 или 111 (при чтении с обратным порядком битов), длина всей пары длина-расстояние может составлять от 1 до 4 байтов.
По состоянию на 2008 год ^[update], самый популярный метод сжатия на основе LZ77 — DEFLATE ; он сочетает в себе LZSS с кодированием Хаффмана . ^[10]Литералы, длины и символ, обозначающий конец текущего блока данных, помещаются вместе в один алфавит. Расстояния можно смело вынести в отдельный алфавит; поскольку расстояние встречается только сразу после длины, его нельзя спутать с символом другого типа или наоборот.

LZ78 [ править ]

Алгоритмы LZ78 сжимают последовательные данные, создавая словарь последовательностей токенов из входных данных, а затем заменяя второе и последующие вхождения последовательности в потоке данных ссылкой на запись словаря. Наблюдение состоит в том, что количество повторяющихся последовательностей является хорошей мерой неслучайного характера последовательности. Алгоритмы представляют словарь в виде n-арного дерева, где n — количество токенов, используемых для формирования последовательностей токенов. Каждая словарная статья имеет вид dictionary[...] = {index, token}, где индекс — это индекс словарной записи, представляющей ранее увиденную последовательность, а токен — это следующий токен из входных данных, который делает эту запись уникальной в словаре. Обратите внимание, насколько жадным является алгоритм: в таблицу ничего не добавляется, пока не будет найден уникальный токен создания. Алгоритм заключается в инициализации последнего индекса соответствия = 0 и следующего доступного индекса = 1, а затем для каждого токена входного потока словарь ищет совпадение: {last matching index, token}. Если совпадение найдено, то индекс последнего соответствия устанавливается равным индексу соответствующей записи, ничего не выводится, и остается последний индекс соответствия, представляющий входные данные на данный момент. Ввод обрабатывается до тех пор, пока совпадение не будет найдено. Затем создается новая словарная запись, dictionary[next available index] = {last matching index, token}, и алгоритм выводит последний индекс соответствия, за которым следует токен, затем сбрасывает последний индекс соответствия = 0 и увеличивает следующий доступный индекс. В качестве примера рассмотрим последовательность токенов ОТЕЦ который бы собрал словарь;

0 {0,_}
 1 {0,А}
 2 {1,Б}
 3 {0,Б}

и выходная последовательность сжатых данных будет 0A1B0B . Обратите внимание, что последний A еще не представлен, поскольку алгоритм не может знать, что будет дальше. На практике ко входу добавляется маркер EOF — ОТЕЦ $ например. Также обратите внимание, что в этом случае вывод 0A1B0B1$ длиннее исходного ввода, но степень сжатия значительно улучшается по мере роста словаря, а в двоичном формате индексы не обязательно должны быть представлены более чем минимальным числом битов. ^[11]

Декомпрессия заключается в восстановлении словаря из сжатой последовательности. Из последовательности 0A1B0B1$ первая запись всегда является терминатором 0 {...} , и первым из последовательности будет 1 {0,А} . А добавляется к выводу. Вторая пара из входа: 1Б и приводит к записи номер 2 в словаре, {1,Б} . Выводится токен «B», которому предшествует последовательность, представленная словарной записью 1. Запись 1 — это «A» (за которой следует «запись 0» — ничего), поэтому АБ добавляется к выводу. Следующий 0Б добавляется в словарь в качестве следующей записи, 3 {0,Б} , и B (перед которым ничего не указано) добавляется к выводу. Наконец-то словарная статья для 1$ создается и А$ выводится в результате AB BA$ или ОТЕЦ удаление пробелов и маркера EOF.

ЛЗВ [ править ]

LZW — это алгоритм на основе LZ78, который использует словарь, предварительно инициализированный всеми возможными символами (символами), или эмуляцию предварительно инициализированного словаря. Основное улучшение LZW заключается в том, что, если совпадение не найдено, текущий символ входного потока считается первым символом существующей строки в словаре (поскольку словарь инициализируется всеми возможными символами), поэтому только последнее совпадение на выходе выводится индекс (который может быть предварительно инициализированным индексом словаря, соответствующим предыдущему (или начальному) входному символу). см. в статье LZW. Подробности реализации

BTLZ — это алгоритм на основе LZ78, который был разработан для использования в системах связи реального времени (первоначально модемах) и стандартизирован CCITT/ITU как V.42bis . Когда словарь с древовидной структурой заполнен, используется простой алгоритм повторного использования/восстановления, чтобы гарантировать, что словарь может продолжать адаптироваться к изменяющимся данным. Счетчик циклически просматривает словарь. Когда необходима новая запись, счетчик проходит по словарю, пока не будет найден листовой узел (узел без зависимых элементов). Оно удаляется, а пространство повторно используется для новой записи. Это проще реализовать, чем LRU или LFU, и достигается эквивалентная производительность.

См. также [ править ]

Лемпель – Зив – Стац (ЛЗС)

Ссылки [ править ]

^ Зив, Джейкоб ; Лемпель, Авраам (май 1977 г.). «Универсальный алгоритм последовательного сжатия данных». Транзакции IEEE по теории информации . 23 (3): 337–343. CiteSeerX 10.1.1.118.8921 . дои : 10.1109/TIT.1977.1055714 . S2CID 9267632 .
^ Зив, Джейкоб ; Лемпель, Авраам (сентябрь 1978 г.). «Сжатие отдельных последовательностей посредством кодирования с переменной скоростью». Транзакции IEEE по теории информации . 24 (5): 530–536. CiteSeerX 10.1.1.14.2892 . дои : 10.1109/TIT.1978.1055934 .
^ Патент США № 5532693 Адаптивная система сжатия данных с логикой сопоставления систолической строки.
^ «Сжатие данных без потерь: LZ78» . cs.stanford.edu .
^ «Вехи: алгоритм сжатия данных Лемпеля-Зива, 1977 г.» . Сеть глобальной истории IEEE . Институт инженеров электротехники и электроники . 22 июля 2014 года . Проверено 9 ноября 2014 г.
^ Джоанна, Гудрич. «Почетная медаль IEEE вручена пионеру сжатия данных Джейкобу Зиву» . IEEE Spectrum: Новости технологий, техники и науки . Проверено 18 января 2021 г.
^ Питер Шор (14 октября 2005 г.). «Записки Лемпеля-Зива» (PDF) . Архивировано из оригинала (PDF) 28 мая 2021 года . Проверено 9 ноября 2014 г.
^ Обложка, Томас М.; Томас, Джой А. (2006). Элементы теории информации (2-е изд.). Хобокен, Нью-Джерси: Wiley-Interscience. ISBN 978-0-471-24195-9 .
^ «Сжатие QFS (RefPack)» . Ниотсо Вики . Проверено 9 ноября 2014 г.
^ Фельдшпат, Антей (23 августа 1997 г.). «Объяснение алгоритма дефлирования» . comp.compression Группа новостей . zlib.net . Проверено 9 ноября 2014 г.
^ https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf ^{[ пустой URL PDF ]}

Внешние ссылки [ править ]

СМИ, связанные с алгоритмом LZ77, на Викискладе?
СМИ, связанные с алгоритмом LZ78, на Викискладе?
«Алгоритм LZ77» . Справочный центр по сжатию данных: рабочая группа RASIP . Факультет электротехники и вычислительной техники Загребского университета . 1997. Архивировано из оригинала 7 января 2013 года . Проверено 22 июня 2012 г.

«Алгоритм LZ78» . Справочный центр по сжатию данных: рабочая группа RASIP . Факультет электротехники и вычислительной техники Загребского университета. 1997. Архивировано из оригинала 7 января 2013 года . Проверено 22 июня 2012 г.

«Алгоритм LZW» . Справочный центр по сжатию данных: рабочая группа RASIP . Факультет электротехники и вычислительной техники Загребского университета. 1997. Архивировано из оригинала 7 января 2013 года . Проверено 22 июня 2012 г.

[1] Зив, Джейкоб ; Лемпель, Авраам (май 1977 г.). «Универсальный алгоритм последовательного сжатия данных». Транзакции IEEE по теории информации . 23 (3): 337–343. CiteSeerX 10.1.1.118.8921 . дои : 10.1109/TIT.1977.1055714 . S2CID 9267632 .

[2] Зив, Джейкоб ; Лемпель, Авраам (сентябрь 1978 г.). «Сжатие отдельных последовательностей посредством кодирования с переменной скоростью». Транзакции IEEE по теории информации . 24 (5): 530–536. CiteSeerX 10.1.1.14.2892 . дои : 10.1109/TIT.1978.1055934 .

[3] Патент США № 5532693 Адаптивная система сжатия данных с логикой сопоставления систолической строки.

[4] «Сжатие данных без потерь: LZ78» . cs.stanford.edu .

[5] «Вехи: алгоритм сжатия данных Лемпеля-Зива, 1977 г.» . Сеть глобальной истории IEEE . Институт инженеров электротехники и электроники . 22 июля 2014 года . Проверено 9 ноября 2014 г.

[6] Джоанна, Гудрич. «Почетная медаль IEEE вручена пионеру сжатия данных Джейкобу Зиву» . IEEE Spectrum: Новости технологий, техники и науки . Проверено 18 января 2021 г.

[7] Питер Шор (14 октября 2005 г.). «Записки Лемпеля-Зива» (PDF) . Архивировано из оригинала (PDF) 28 мая 2021 года . Проверено 9 ноября 2014 г.

[8] Обложка, Томас М.; Томас, Джой А. (2006). Элементы теории информации (2-е изд.). Хобокен, Нью-Джерси: Wiley-Interscience. ISBN 978-0-471-24195-9 .

[9] «Сжатие QFS (RefPack)» . Ниотсо Вики . Проверено 9 ноября 2014 г.

[10] Фельдшпат, Антей (23 августа 1997 г.). «Объяснение алгоритма дефлирования» . comp.compression Группа новостей . zlib.net . Проверено 9 ноября 2014 г.

[11] ttps://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf ^{[ пустой URL PDF ]}

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

эффективность Теоретическая ​ ​