stringtranslate.com

ЛЗ77 и ЛЗ78

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

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

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

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

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

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

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

LZ78 универсален и энтропичен  —  Если — двоичный источник, который является стационарным и эргодическим, то с вероятностью 1. Здесь — скорость энтропии источника.

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

ЛЗ77

Алгоритмы 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) раз к началу этого одного буферизованного блока выполнения, считывания L R символов (или, может быть, меньшего количества при последнем возврате) и повторения, пока не будет считано L символов. Но, отражая процесс кодирования, поскольку шаблон повторяется, указатель чтения должен только синхронизироваться с указателем записи на фиксированное расстояние, равное длине цикла L R, пока L символов не будут скопированы на выход в общей сложности.

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

Псевдокод

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

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

Реализации

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

ЛЗ78

Алгоритмы LZ78 сжимают последовательные данные, создавая словарь последовательностей токенов из входных данных, а затем заменяя второе и последующее вхождение последовательности в потоке данных ссылкой на запись словаря. Наблюдение заключается в том, что количество повторяющихся последовательностей является хорошей мерой неслучайной природы последовательности. Алгоритмы представляют словарь как n-арное дерево, где n — количество токенов, используемых для формирования последовательностей токенов. Каждая запись словаря имеет вид dictionary[...] = {index, token}, где 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$создан иА$выводится в результатеА АБ БА$илиААББАудаление пробелов и маркера EOF.

ЛЗВ

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

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

Смотрите также

Ссылки

  1. ^ Зив, Якоб ; Лемпель, Абрахам (май 1977). «Универсальный алгоритм последовательного сжатия данных». Труды IEEE по теории информации . 23 (3): 337–343. CiteSeerX  10.1.1.118.8921 . doi :10.1109/TIT.1977.1055714. S2CID  9267632.
  2. ^ Зив, Якоб ; Лемпель, Абрахам (сентябрь 1978 г.). «Сжатие отдельных последовательностей с помощью кодирования с переменной скоростью». Труды IEEE по теории информации . 24 (5): 530–536. CiteSeerX 10.1.1.14.2892 . doi :10.1109/TIT.1978.1055934. 
  3. ^ Патент США № 5532693 Адаптивная система сжатия данных с логикой сопоставления систолических строк
  4. ^ "Сжатие данных без потерь: LZ78". cs.stanford.edu .
  5. ^ "Milestones: Lempel–Ziv Data Compression Algorithm, 1977". IEEE Global History Network . Institute of Electrical and Electronics Engineers . 22 июля 2014 г. Получено 9 ноября 2014 г.
  6. ^ Джоанна, Гудрич. «IEEE Medal of Honor Goes to Data Compression Pioneer Jacob Ziv». IEEE Spectrum: Technology, Engineering, and Science News . Получено 18 января 2021 г.
  7. ^ Питер Шор (14 октября 2005 г.). «Заметки Лемпеля–Зива» (PDF) . Архивировано из оригинала (PDF) 28 мая 2021 г. . Получено 9 ноября 2014 г. .
  8. ^ Обложка, Томас М.; Томас, Джой А. (2006). Элементы теории информации (2-е изд.). Хобокен, Нью-Джерси: Wiley-Interscience. ISBN 978-0-471-24195-9.
  9. ^ "QFS Compression (RefPack)". Niotso Wiki . Получено 9 ноября 2014 г.
  10. ^ Feldspar, Antaeus (23 августа 1997 г.). "Объяснение алгоритма Deflate". comp.compression newsgroup . zlib.net . Получено 9 ноября 2014 г. .
  11. ^ https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf [ пустой URL-адрес PDF ]

Внешние ссылки