Из Википедии, бесплатной энциклопедии
  (Перенаправлено из Лемпель-Зив )
Перейти к навигации Перейти к поиску

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]

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

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

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

Псевдокод является воспроизведением скользящего окна алгоритма сжатия LZ77.

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

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

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

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

LZ78 [ править ]

Алгоритмы LZ78 достигают сжатия, заменяя повторяющиеся вхождения данных ссылками на словарь, построенный на основе входного потока данных. Каждая словарная запись имеет форму dictionary[...] = {index, character}, где index - это указатель предыдущей словарной статьи, а символ добавляется к строке, представленной dictionary[index]. Например, «abc» будет сохраняться (в обратном порядке) следующим образом:, dictionary[k] = {j, 'c'}, dictionary[j] = {i, 'b'}, dictionary[i] = {0, 'a'}где индекс 0 указывает первый символ строки. Алгоритм инициализирует последний совпадающий индекс = 0 и следующий доступный индекс = 1. Для каждого символа входящего потока в словаре выполняется поиск совпадения: {последний соответствующий индекс, символ}. Если совпадение найдено, то последний соответствующий индексустанавливается на индекс соответствующей записи, и ничего не выводится. Если совпадение не найдено, создается новая запись словаря: словарь [следующий доступный индекс] = {последний соответствующий индекс, символ}, и алгоритм выводит последний совпадающий индекс , за которым следует символ , затем сбрасывает последний совпадающий индекс = 0 и увеличивает следующий доступный индекс . Как только словарь заполнится, записи больше не будут добавляться. Когда достигается конец входного потока, алгоритм выводит последний соответствующий индекс . Обратите внимание, что строки хранятся в словаре в обратном порядке, с которым декодеру LZ78 придется иметь дело.

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

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

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

  • Лемпель – Зив – Стац (LZS)
  • Дискретное косинусное преобразование (DCT), алгоритм сжатия с потерями , используемый в стандартах кодирования JPEG и MPEG.

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

  1. ^ Зив, Джейкоб ; Лемпель, Авраам (май 1977 г.). «Универсальный алгоритм последовательного сжатия данных». IEEE Transactions по теории информации . 23 (3): 337–343. CiteSeerX  10.1.1.118.8921 . DOI : 10.1109 / TIT.1977.1055714 .
  2. ^ Зив, Джейкоб ; Лемпель, Авраам (сентябрь 1978 г.). «Сжатие отдельных последовательностей с помощью кодирования с переменной скоростью». IEEE Transactions по теории информации . 24 (5): 530–536. CiteSeerX 10.1.1.14.2892 . DOI : 10.1109 / TIT.1978.1055934 . 
  3. ^ Патент США № 5532693 Адаптивная система сжатия данных с логикой сопоставления систолической строки.
  4. ^ "Сжатие данных" Концепция " " .
  5. ^ "Вехи: алгоритм сжатия данных Lempel-Ziv, 1977" . Сеть глобальной истории IEEE . Институт инженеров по электротехнике и радиоэлектронике . 22 июля 2014 . Проверено 9 ноября 2014 .
  6. ↑ Джоанна, Гудрич. «Почетная медаль IEEE досталась первопроходцу в области сжатия данных Якову Зиву» . IEEE Spectrum: Новости технологий, инженерии и науки . Проверено 18 января 2021 года .
  7. ↑ Питер Шор (14 октября 2005 г.). «Записки Лемпель-Зива» (PDF) . Проверено 9 ноября 2014 .
  8. ^ "Сжатие QFS (RefPack)" . Niotso Wiki . Проверено 9 ноября 2014 .
  9. ^ Шпат, Антей (23 августа 1997). «Объяснение алгоритма Deflate» . группа новостей comp.compression . zlib.net . Проверено 9 ноября 2014 .

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

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