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.

while input is not empty do
    match := longest repeated occurrence of input that begins in window
    
    if match exists then
        d := distance to start of match
        l := length of match
        c := char following match in input
    else
        d := 0
        l := 0
        c := first char of input
    end if
    
    output (d, l, c)
    
    discard l + 1 chars from front of window
    s := pop l + 1 chars from front of input
    append s to back of window
repeat

Реализации

Несмотря на то, что все алгоритмы 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,A}
2 {1,B}
3 {0,B}

и выходная последовательность сжатых данных будет 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 ]