LZ77 - это обратная ссылка на строки в буфере распаковки по их длине и расстоянию от текущей позиции. Но как кодировать эти обратные ссылки, остается вам. Многие реализации LZ77 делают это по-разному.
Но вы правы в том, что должен быть какой-то способ отличать «литералы» (несжатые части данных, предназначенные для копирования «как есть» с ввода на вывод) от «обратных ссылок» (которые копируются из уже несжатой части) .
Один из способов сделать это - зарезервировать некоторые символы как «специальные» (так называемые «escape-последовательности»). Вы можете сделать это так же, как и вы, то есть с помощью <, чтобы отметить начало обратной ссылки. Но тогда вам также понадобится способ вывода <, если это литерал. Вы можете сделать это, например, установив, что когда после < идет еще один <, это означает литерал, и вы просто выводите один <. Или вы можете установить, что если после < сразу идёт >, без чего-либо между ними, то это не обратная ссылка, поэтому вы просто выводите <.
Кроме того, это не самый эффективный способ кодирования этих обратных ссылок, потому что он использует несколько байтов для кодирования обратной ссылки, поэтому он станет эффективным только для ссылок на строки, длина которых превышает эти несколько байтов. Для более коротких обратных ссылок он будет раздувать данные вместо их сжатия, если вы не установите, что совпадения короче нескольких байтов остаются как есть, вместо генерации обратных ссылок. Но опять же, это означает меньшее усиление компрессии.
Если вы сжимаете только простые старые тексты ASCII, вы можете использовать лучшую схему кодирования, потому что ASCII использует только 7 из 8 бит в байте. Таким образом, вы можете использовать самый старший бит для сигнализации обратной ссылки, а затем использовать оставшиеся 7 бит как длину, а следующий байт (или два) как расстояние обратной ссылки. Таким образом, вы всегда можете точно определить, является ли следующий байт буквальным символом ASCII или обратной ссылкой, проверив его старший бит. Если это 0, просто выведите символ как есть. Если он равен 1, используйте следующие 7 бит в качестве длины и считайте следующие 2 байта, чтобы использовать их в качестве расстояния. Таким образом, каждая обратная ссылка занимает 3 байта, поэтому вы можете эффективно сжимать текстовые файлы с повторяющимися последовательностями длиной более 3 символов.
Но есть еще лучший способ сделать это, который дает еще большее сжатие: вы можете заменить свои символы битовыми кодами переменной длины, созданными таким образом, чтобы символы, появляющиеся чаще, имели самые короткие коды, а те, которые встречаются редко, - иметь более длинные коды. Для этого эти коды должны быть так называемыми «префиксными кодами», чтобы никакой код не был префиксом какого-либо другого кода. Если у ваших кодов есть это свойство, вы всегда можете различать их, считывая эти биты последовательно, пока вы не расшифруете некоторые из них. Тогда вы можете быть уверены, что не получите никакого другого действительного элемента, прочитав дополнительные биты. Следующий бит всегда запускает новую последовательность. Чтобы получить такие коды, вам нужно использовать деревья Хаффмана. Затем вы можете объединить все свои байты и ссылки разной длины в одно такое дерево и сгенерировать для них разные битовые коды в зависимости от их частоты. Когда вы пытаетесь их декодировать, вы просто читаете биты, пока не дойдете до кода некоторых из этих элементов, и тогда вы точно узнаете, является ли это кодом некоторого буквального символа или кодом длины обратной ссылки. Во втором случае вы затем считываете некоторые дополнительные биты для расстояния обратной ссылки (также закодированные с помощью префиксного кода). Это то, что делает схема сжатия DEFLATE. Но это совсем другая история, и подробности вы найдете в RFC, предоставленном @MarkAdler.
person
SasQ
schedule
13.07.2014
