LZ77 и спасающийся персонаж

Question

Я пытаюсь реализовать алгоритм сжатия LZ77 и столкнулся с этой проблемой.

Я сжимаю ввод (может быть любой двоичный файл, не только текстовые файлы) на байтовой основе, и я использую 3байты для представления указателя / ссылки на ранее подстроку.Первый байт указателя всегда является escape-символом, b "\ xCC", чтобы упростить задачу, скажем, это C.

"Стандартный" способ, который я знаю при работе с escape-символом, это то, что выобычно кодируйте все другие символы и экранируйте литерал, который имеет то же значение, что и escape-символ.Так что «ABCDE» закодировано в «ABCCDE».

Проблема в том, что значение указателя может быть «CCx», где второй байт может быть «C» и делает указатель неотличимым от экранированного литерала «CC», и это вызывает проблемы.

Как это исправить?Или какой правильный / стандартный способ сделать LZ77?Спасибо!

Answer 1

Для того чтобы LZ77 был полезен, за ним должен следовать энтропийный кодер.Именно на этом этапе вы кодируете свои символы в биты, которые входят в сжатые данные.

Один из подходов заключается в определении 258 символов, 256 для буквенных байтов, один из которых указывает, что длина и расстояние дляза ним следует соответствие, которое указывает на конец потока.

Или вы можете делать то, что делает deflate, то есть кодировать длины и литералы вместе, чтобы этот символ декодировался либо в литеральный байт, либо в длину, гдедлина означает, что следует код расстояния.

Или вы можете делать то, что делает brotli, то есть определять «вставлять и копировать» коды, которые дают количество литералов, за которыми следует столько литеральных кодов, а затемдлина копии и расстояние.

Или вы можете изобрести свой собственный.