stringtranslate.com

LZ77 и LZ78

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.

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 := первый символ ввода конец, если  выход (д, л, в)  отбросить l + 1 символ перед окном s := pop l + 1 символ перед вводом добавить s в конец окнаповторить

Реализации

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

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, и достигается эквивалентная производительность.

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

Рекомендации

  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. ^ https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf [ пустой URL-адрес PDF ]

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