Алгоритмы сжатия данных без потерь LZ77 и LZ78

Введение

Алгоритмы сжатия данных без потерь LZ77 и LZ78 — это два алгоритма сжатия данных без потерь, опубликованные в статьях Авраама Лемпеля и Джейкоба Зива в 1977 и 1978 годах. Они также известны как LZ1 и LZ2 соответственно. Эти два алгоритма являются основой для множества вариаций, включая LZW, LZSS, LZMA и другие. Помимо их академического влияния, эти алгоритмы легли в основу нескольких широко используемых схем сжатия, включая GIF и алгоритм DEFLATE, применяемый в PNG и ZIP. Теоретически, оба алгоритма являются кодировщиками на основе словаря. LZ77 поддерживает скользящее окно в процессе сжатия. Позже было показано, что это эквивалентно явному словарю, создаваемому LZ78, однако такое равенство выполняется только при условии декомпрессии всего объема данных. Поскольку LZ77 кодирует и декодирует, используя скользящее окно по ранее встреченным символам, декомпрессия всегда должна начинаться с начала входных данных. Концептуально, декомпрессия LZ78 могла бы обеспечить произвольный доступ к входным данным, если бы весь словарь был известен заранее. Однако на практике словарь создается в процессе кодирования и декодирования путем добавления новой фразы при каждом выводе токена. В 2004 году эти алгоритмы были признаны IEEE Milestone. В 2021 году Джейкоб Зив был удостоен медали IEEE Medal of Honor за вклад в их разработку.

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

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

LZ77

Алгоритмы LZ77 достигают сжатия путем замены повторяющихся последовательностей данных ссылками на единственную копию этих данных, существующую ранее в несжатом потоке. Совпадение кодируется парой чисел, называемой парой «длина-расстояние», что эквивалентно утверждению: «каждый из следующих `длина` символов равен символам, находящимся ровно на `расстояние` символов позади текущей позиции в несжатом потоке». (Расстояние иногда называют смещением.) Для обнаружения совпадений кодировщик должен отслеживать некоторое количество самых последних данных, например, последние 2 КБ, 4 КБ или 32 КБ. Структура, в которой хранятся эти данные, называется скользящим окном, поэтому LZ77 иногда называют сжатием со скользящим окном. Кодировщик должен хранить эти данные для поиска совпадений, а декодер — для интерпретации ссылок, сделанных кодировщиком. Чем больше скользящее окно, тем дальше в прошлое кодировщик может искать для создания ссылок. Не только допустимо, но и часто полезно разрешать парам «длина-расстояние» указывать длину, которая фактически превышает расстояние. Как команда копирования, это выглядит парадоксально: «Вернитесь на четыре символа назад и скопируйте десять символов из этой позиции в текущую». Как можно скопировать десять символов, если в буфере фактически есть только четыре? Если обрабатывать по одному байту за раз, то нет проблем с выполнением этого запроса, поскольку при копировании байта он может быть снова подан на вход команде копирования. Когда копирование из исходной позиции достигает конечной позиции назначения, в него поступают данные, которые были вставлены с начала копируемой области. Таким образом, операция эквивалентна утверждению: «копируйте предоставленные данные и повторяйте их вставку, пока они не поместятся». Поскольку этот тип пары повторяет одну копию данных несколько раз, его можно использовать для реализации гибкой и простой формы кодирования длин серий. Другой взгляд на это следующий: во время кодирования, чтобы указатель поиска продолжал находить совпадающие пары за пределами окна поиска, все символы от первого совпадения со смещением D и до конца окна поиска должны соответствовать входным данным, и это (ранее встреченные) символы составляют единицу серии длиной LR, которая должна быть равна D. Затем, по мере продвижения указателя поиска за пределы окна поиска, если шаблон серии повторяется во входных данных, указатели поиска и ввода будут синхронизированы и соответствовать символам до тех пор, пока шаблон серии не будет прерван. Тогда всего будет сопоставлено L символов, L > D, и код будет [D, L, c]. При декодировании [D, L, c], опять же, D = LR. Когда первые LR символов считываются в выходной буфер, это соответствует единице серии, добавленной к выходному буферу. В этот момент указатель чтения можно рассматривать как нуждающийся только в возврате int(L/LR) + (1, если L mod LR ≠ 0) раз к началу этой единицы серии, чтении LR символов (или, возможно, меньше при последнем возврате) и повторении до тех пор, пока не будет прочитано всего L символов. Но, повторяя процесс кодирования, поскольку шаблон повторяется, указателю чтения нужно лишь отставать от указателя записи на фиксированное расстояние, равное длине серии LR, пока в выходной буфер не будет скопировано всего L символов. Учитывая вышесказанное, особенно если ожидается преобладание сжатия серий данных, поиск в окне следует начинать с конца окна и двигаться назад, поскольку шаблоны серий, если они существуют, будут найдены первыми и позволят завершить поиск, либо абсолютно, если достигнута текущая максимальная длина совпадающей последовательности, либо разумно, если достигнута достаточная длина, и, наконец, просто потому, что данные более свежие и могут лучше коррелировать со следующим входом.

LZ77 algorithms achieve compression by replacing repeated occurrences of data with references to a single copy of that data existing earlier in the uncompressed data stream. A match is encoded by a pair of numbers called a length distance pair, which is equivalent to the statement "each of the next length characters is equal to the characters exactly distance characters behind it in the uncompressed stream". (The distance is sometimes called the offset instead.) To spot matches, the encoder must keep track of some amount of the most recent data, such as the last 2 KB, 4 KB, or 32 KB. The structure in which this data is held is called a sliding window, which is why LZ77 is sometimes called sliding window compression. The encoder needs to keep this data to look for matches, and the decoder needs to keep this data to interpret the matches the encoder refers to. The larger the sliding window is, the longer back the encoder may search for creating references. It is not only acceptable but frequently useful to allow length distance pairs to specify a length that actually exceeds the distance. As a copy command, this is puzzling: "Go back four characters and copy ten characters from that position into the current position". How can ten characters be copied over when only four of them are actually in the buffer? Tackling one byte at a time, there is no problem serving this request, because as a byte is copied over, it may be fed again as input to the copy command. When the copy from position makes it to the initial destination position, it is consequently fed data that was pasted from the beginning of the copy from position. The operation is thus equivalent to the statement "copy the data you were given and repetitively paste it until it fits". As this type of pair repeats a single copy of data multiple times, it can be used to incorporate a flexible and easy form of run length encoding. Another way to see things is as follows: While encoding, for the search pointer to continue finding matched pairs past the end of the search window, all characters from the first match at offset D and forward to the end of the search window must have matched input, and these are the (previously seen) characters that comprise a single run unit of length LR, which must equal D. Then as the search pointer proceeds past the search window and forward, as far as the run pattern repeats in the input, the search and input pointers will be in sync and match characters until the run pattern is interrupted. Then L characters have been matched in total, L > D, and the code is [D, L, c]. Upon decoding [D, L, c], again, D = LR. When the first LR characters are read to the output, this corresponds to a single run unit appended to the output buffer. At this point, the read pointer could be thought of as only needing to return int(L/LR) + (1 if L mod LR ≠ 0) times to the start of that single buffered run unit, read LR characters (or maybe fewer on the last return), and repeat until a total of L characters are read. But mirroring the encoding process, since the pattern is repetitive, the read pointer need only trail in sync with the write pointer by a fixed distance equal to the run length LR until L characters have been copied to output in total. Considering the above, especially if the compression of data runs is expected to predominate, the window search should begin at the end of the window and proceed backwards, since run patterns, if they exist, will be found first and allow the search to terminate, absolutely if the current maximal matching sequence length is met, or judiciously, if a sufficient length is met, and finally for the simple possibility that the data is more recent and may correlate better with the next input.

Реализация

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

Even though all LZ77 algorithms work by definition on the same basic principle, they can vary widely in how they encode their compressed data to vary the numerical ranges of a length–distance pair, alter the number of bits consumed for a length–distance pair, and distinguish their length–distance pairs from literals (raw data encoded as itself, rather than as part of a length–distance pair). A few examples:
The algorithm illustrated in Lempel and Ziv's original 1977 article outputs all its data three values at a time: the length and distance of the longest match found in the buffer, and the literal that followed that match. If two successive characters in the input stream could be encoded only as literals, the length of the length–distance pair would be 0. LZSS improves on LZ77 by using a 1 bit flag to indicate whether the next chunk of data is a literal or a length–distance pair, and using literals if a length–distance pair would be longer. In the PalmDoc format, a length–distance pair is always encoded by a two byte sequence. Of the 16 bits that make up these two bytes, 11 bits go to encoding the distance, 3 go to encoding the length, and the remaining two are used to make sure the decoder can identify the first byte as the beginning of such a two byte sequence. In the implementation used for many games by Electronic Arts, the size in bytes of a length–distance pair can be specified inside the first byte of the length–distance pair itself; depending on whether the first byte begins with a 0, 10, 110, or 111 (when read in big endian bit orientation), the length of the entire length–distance pair can be 1 to 4 bytes. as of 2008, the most popular LZ77 based compression method is DEFLATE; it combines LZSS with Huffman coding. Literals, lengths, and a symbol to indicate the end of the current block of data are all placed together into one alphabet. Distances can be safely placed into a separate alphabet; because a distance only occurs just after a length, it cannot be mistaken for another kind of symbol or vice versa.

LZ78

Алгоритмы LZ78 сжимают последовательные данные, создавая словарь последовательностей токенов из входных данных, а затем заменяя второе и последующие вхождения последовательности в потоке данных ссылкой на запись словаря. Наблюдение состоит в том, что количество повторяющихся последовательностей является хорошей мерой неслучайности последовательности. Алгоритмы представляют словарь в виде n-арного дерева, где n — количество токенов, используемых для формирования последовательностей токенов. Каждая запись словаря имеет вид (индекс, токен), где индекс — это индекс записи словаря, представляющей ранее встреченную последовательность, а токен — следующий токен из входных данных, который делает эту запись уникальной в словаре. Обратите внимание, что алгоритм является жадным, поэтому ничего не добавляется в таблицу, пока не будет найден уникальный токен. Алгоритм заключается в инициализации последнего совпавшего индекса = 0 и следующего доступного индекса = 1, а затем, для каждого токена входного потока, поиск совпадения в словаре: если совпадение найдено, то последний совпавший индекс устанавливается на индекс совпадающей записи, ничего не выводится, и последний совпавший индекс остается представлять входные данные до этого момента. Вход обрабатывается до тех пор, пока не будет найдено несовпадение. Затем создается новая запись словаря (индекс, токен), и алгоритм выводит последний совпавший индекс, за которым следует токен, затем сбрасывает последний совпавший индекс = 0 и увеличивает следующий доступный индекс. В качестве примера рассмотрим последовательность токенов AABABBABA, которая сформирует следующий словарь:

и выходная последовательность сжатых данных будет (1, A), (2, B), (1, A), (3, B), (1, A). Обратите внимание, что последнее A еще не представлено, поскольку алгоритм не может знать, что будет дальше. На практике, например, к вводу добавляется маркер EOF. Также обратите внимание, что в этом случае выход длиннее исходного ввода, но степень сжатия значительно улучшается по мере роста словаря, и в двоичном представлении индексы не требуют больше, чем минимальное количество бит. Декомпрессия заключается в восстановлении словаря из сжатой последовательности. Из последовательности (1, A), (2, B), (1, A), (3, B), (1, A) первая запись всегда является терминатором, а первая запись из последовательности будет A, которая добавляется к выводу. Вторая пара из входных данных — (2, B), что приводит к созданию записи номер 2 в словаре. Токен "B" выводится, предваряемый последовательностью, представленной записью словаря 1. Запись 1 — это "A" (за которой следует "запись 0" — ничего), поэтому "A" добавляется к выводу. Далее AB добавляется в словарь как следующая запись (3, AB), а "B" (предваряемый ничем) добавляется к выводу. Наконец, создается запись словаря для AABA, и выводится AABA, в результате чего получается AABABBABA или, удалив пробелы и маркер EOF.

ЛЗВ

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