Войти
LZ77 и LZ78 - это два сжатия данных без потерь алгоритмы, опубликованные в статьях Абрахама Лемпеля и Джейкоба Зива в 1977 и 1978 годах. Они также известны как LZ1 и LZ2 <41.>соответственно. Эти два алгоритма составляют основу для многих вариантов, включая LZW, LZSS, LZMA и другие. Помимо академического влияния, эти алгоритмы легли в основу нескольких широко распространенных схем сжатия, включая GIF и алгоритм DEFLATE, используемый в PNG и ZIP <165.>Они оба теоретически кодировщики словаря. LZ77 поддерживает скользящее окно во время сжатия. Позже было показано, что это эквивалентно явному словарю, созданному LZ78, однако они эквивалентны только тогда, когда все данные предназначены для распаковки.
Поскольку LZ77 кодирует и декодирует из скользящего окна ранее увиденные символы, декомпрессия всегда должна начинаться с начала ввода. По идее, декомпрессия LZ78 могла бы позволить произвольный доступ к входным данным, если бы весь словарь был известен заранее. Однако на практике словарь создается во время кодирования и декодирования путем создания новой фразы всякий раз, когда выводится токен.
В 2004 году алгоритмы были названы IEEE Milestone.
Во второй из двух статей, в которых представлены эти алгоритмы, они анализируются как кодеры, определяемые конечными автоматами. Мера, аналогичная информационной энтропии, разработана для отдельных последовательностей (в отличие от вероятностных ансамблей). Эта мера дает предел степени сжатия данных, которая может быть достигнута. Затем показано, что существуют конечные кодеры без потерь для каждой последовательности, которые достигают этой границы, когда длина последовательности увеличивается до бесконечности. В этом смысле алгоритм, основанный на этой схеме, производит асимптотически оптимальные кодировки. Этот результат может быть подтвержден более прямо, например, в примечаниях Питера Шора.
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.
в то время как ввод не пуст do prefix: = самый длинный префикс ввода, который начинается в окне если существует префикс, то i: = расстояние до начало префикса l: = длина префикса c: = символ после префикса на входе else i: = 0 l: = 0 c: = первый символ ввода конец, если output (i, l, c) s: = вытолкнуть l + 1 символов с начала ввода отменить l + 1 символов от передней части окна добавить s к задней части окна повторить
Несмотря на то, что все алгоритмы LZ77 по определению работают по одному и тому же основному принципу, они могут широко варьироваться в том, как они кодируют свои сжатые данные, чтобы варьировать числовые диапазоны пары длина-расстояние, изменять количество бит, потребляемых для длины-расстояния. пара и отличать их пары длина – расстояние от литералов (необработанные данные, закодированные как сами по себе, а не как часть пары длина – расстояние). Несколько примеров:
Алгоритмы LZ78 достигают сжатия, заменяя повторяющиеся вхождения данных ссылками на словарь, который является построен на основе входного потока данных. Каждая словарная запись имеет форму dictionary [...] = {index, character}, где index - это указатель предыдущей словарной статьи, а символ добавляется к строке, представленной dictionary [указатель]. Например, «abc» будет сохраняться (в обратном порядке) следующим образом: dictionary [k] = {j, 'c'}, dictionary [j] = {i, 'b'}, dictionary [i] = {0, 'a'}, где индекс 0 указывает первый символ строки. Алгоритм инициализирует последний совпадающий индекс = 0 и следующий доступный индекс = 1. Для каждого символа входного потока в словаре выполняется поиск совпадения: {последний соответствующий индекс, символ}. Если соответствие найдено, то последний соответствующий индекс устанавливается равным индексу соответствующей записи, и ничего не выводится. Если совпадение не найдено, создается новая запись словаря: словарь [следующий доступный индекс] = {последний соответствующий индекс, символ}, и алгоритм выводит последний совпадающий индекс, за которым следует символ, затем сбрасывает последний совпадающий индекс = 0 и увеличивает следующий доступный индекс. Как только словарь заполнится, записи больше не будут добавляться. Когда достигается конец входного потока, алгоритм выводит последний соответствующий индекс. Обратите внимание, что строки хранятся в словаре в обратном порядке, с которым декодеру LZ78 придется иметь дело.
LZW - это алгоритм на основе LZ78, который использует словарь, предварительно инициализированный всеми возможными символами (символами), или эмуляцию предварительно инициализированного словаря. Основное улучшение LZW заключается в том, что, когда совпадение не найдено, предполагается, что текущий символ входного потока является первым символом существующей строки в словаре (поскольку словарь инициализируется всеми возможными символами), поэтому выводится только последний соответствующий индекс (который может быть предварительно инициализированным индексом словаря, соответствующим предыдущему (или начальному) входному символу). Обратитесь к статье LZW за подробностями реализации.
- это алгоритм на основе LZ78, который был разработан для использования в системах связи в реальном времени (изначально модемах) и стандартизирован CCITT / ITU как V.42bis. Когда trie -структурированный словарь заполнен, используется простой алгоритм повторного использования / восстановления, чтобы гарантировать, что словарь может продолжать адаптироваться к изменяющимся данным. Счетчик просматривает словарь. Когда требуется новая запись, счетчик просматривает словарь, пока не будет найден листовой узел (узел без зависимых). Он удаляется, а пространство повторно используется для новой записи. Это проще реализовать, чем LRU или LFU, и обеспечивает эквивалентную производительность.
