LZW (Limpel-Ziv-Welch) Словарь разделитель кодирования проблема

Question

Этот вопрос не может быть строго ограничен алгоритмом LZW и может охватывать другие реализации LZ77 и LZ78:

Я пытался написать утилиту сжатия / распаковки, включающую схему кодирования словаря LZW.Проблема в том, что я счел необходимым включать символ-разделитель (пробел) после того, как каждое кодовое слово (или «код») записывается на этапе кодирования.Я делаю это, потому что не могу предположить, что вывод передается прямо в декодер и может быть сохранен в сжатом файле для последующего декодирования (в этом случае декодеру потребуется какой-то способ обнаружить то, что разделяеткодовые слова - разделитель).

Мне недавно сказали, что в этом нет необходимости, и что декодер должен иметь возможность динамически «вычислять», сколько сжатого файла нужно прочитать в каждый раз, предположительно на основена ранее прочитанный код (ы).Это предположительно исключило бы (дорогостоящую) необходимость вставлять дополнительный байт после каждого кода.

Я просто не уверен, как декодер может понять это.Может быть, кто-то, кто понимает, как это работает, мог бы объяснить это мне?Спасибо.

РЕДАКТИРОВАТЬ:

Словарь представляет собой хэш-таблицу, отображающую "входные строки" в целые числа (коды), и строится обычным способом, когда в исходные данные читаетсяКоды записываются в сжатый файл.Декодер считывает каждый код (целое число) из сжатого файла и либо ищет в своем словаре соответствующую строку для вывода, либо, если для этого кода нет записи, то он выясняет, какой должна быть строка обычным способом, и обновляетего словарь.

"Почему это имеет значение, если файл передается в потоковом режиме или хранится?"Если выходные данные кодера передаются декодеру по одному за раз, то декодер может работать с каждым кодом, когда он их получает.Но если кодер записывает все коды в файл (сжатый файл), а затем этот файл подается в декодер, то как декодер узнает, где один код начинается, а другой начинается.Файл представляет собой последовательность цифр с разбивкой.

Например: сжатый файл с разделителями: 127 32 45 22 228 122 209 .... сжатый файл без разделителей: 127324522228122209 ...

* 1017 Роб *

Answer 1

В LZW словарь не сохраняется со сжатым файлом. (Или словарь - это файл, в зависимости от вашей перспективы.) Каждое значение, записываемое в файл, имеет предопределенную битовую ширину в соответствии с его местоположением. Например, он может начинаться как пары 9-битных индексов словаря, за которыми следуют 8-битные данные, до тех пор, пока индексы не будут исчерпаны (что происходит в точном месте), когда он переключается на 10-битные индексы.

Детали зависели от того, как вы реализуете сжатие. Некоторые делают постоянные 12-битные индексы. Но ни в коем случае не требуются дополнительные разделители.

Кроме того, поскольку данные не выровнены по 8-битным границам, невозможно определить разделители, если вы еще не правильно читаете данные!

Edit:

Если вы надеетесь, что алгоритм сжатия LZW действительно сгенерирует меньшие данные, чем входные данные, то вам следует сделать несколько вещей.

Во-первых, вы должны записать файл как двоичный файл, а не как текст. Запись в виде текста будет расширять, а не сокращать размер файла. Значение 127 может храниться в одном байте в двоичном виде (01111111), но для него требуется четыре байта UTF-8 с пробелом-разделителем («127» = 00110001 00110010 00110111 00100000).

Во-вторых, LZW предназначен для работы со значениями кода, которые больше, чем один байт, но меньше, чем два байта, поэтому для правильной выдачи данных вы должны выполнить некоторую перестановку битов. Одного байта достаточно только для кодирования первых 256 неявно определенных записей таблицы. Еще один бит даст вам еще 256 записей для работы, но записи в 9-битной индексированной таблице быстро исчерпываются. С 12 битами вы можете получить 4096 записей таблицы, что является разумным размером таблицы. Если бы вы использовали два полных байта, то у вас была бы довольно большая таблица с 65 тыс. Записей. Проблема в том, что если вы не используете всю емкость своего табличного пространства, вы теряете биты. Вывод будет содержать много битов, которые всегда равны нулю, и это будет очень плохо для ваших коэффициентов сжатия.

В-третьих, потоковый кодер / декодер не может принимать отдельные значения за раз, потому что закодированные данные перекрывают границы байтов. Если используется постоянный размер 12-битного кода, то одновременно может быть обработано несколько кратных двух кодированных значений. Но в целом алгоритм предназначен для работы с полными файлами.

Answer 2

С LZW кодовая книга генерируется при чтении файла, что устраняет необходимость в разделителе.Когда каждый символ добавляется к выходу LZW, он преобразуется из 8 бит в нечто большее (обычно 10 или 12 бит), чтобы освободить место для кодовой книги.Например:

banana

В LZW b уже находится в кодовой книге (ссылка 2), поэтому перейдите на ba.ba отсутствует в кодовой книге, поэтому добавьте его.

в данный момент вывод

ba с кодовой книгой

27 = ba

(1-26 - индексы для az)

Далее он сохраняет a и читает n -> an.Этого также нет в кодовой книге, поэтому он добавляется.

в настоящее время вывод

ban с кодовой книгой

27 = ba 28 = an

повторить до конца.Результат:

bana29 с кодовой книгой, которая

27 = ba 28 = an 29 = na

Нет необходимостидобавьте разделители, потому что, поскольку слово bana29 декодируется, поиск для 29 уже существует в кодовой книге.

Я надеюсь, что это помогает объяснить, почему нет необходимости удалять с LZW