Алгоритм декомпрессии LZW

Ваша часть сжатия верна и завершена, но часть декомпрессии не завершена. Вы включаете только случай, когда код находится в словаре. Поскольку процесс распаковки всегда на один шаг отстает от процесса сжатия, существует вероятность того, что декодер найдет код, которого нет в словаре. Но поскольку он отстает всего на один шаг, он может понять, что процесс кодирования добавит дальше, и правильно вывести декодированную строку, а затем добавить ее в словарь. Чтобы продолжить процесс декомпрессии следующим образом:

-декомпрессия

read a character k;
   output k;
   w = k;
   while ( read a character k )    
  /* k could be a character or a code. */
        {
         if k exists in the dictionary
         entry = dictionary entry for k;
         output entry;
         add w + entry[0] to dictionary;
         w = entry;
         else
         output entry = w + firstCharacterOf(w);
         add entry to dictionary;
         w = entry;
        }

Затем, когда вы распаковываете файл и видите 257, вы обнаруживаете, что его нет в словаре. Но вы знаете, что предыдущая запись — «о», и ее первый символ тоже «о», сложите их вместе, вы получите «оо». Теперь выведите oo и добавьте его в словарь. Затем вы получаете код 112 и уверены, что знаете, что это p. ВЫПОЛНЕНО!

w       k          entry        output       Dictionary
        98 (b)                  b   
b       111 (o)    o            o             bo (256)
o       257 (oo)                oo            oo(257)
oo      112(p)                  p

См. это объяснение Стива Блэкстока для получения дополнительной информации. улучшенная страница с блок-схемой фактической реализации декодера и кодировщика, на которой < кодировщик и декодер GIF основан на href="https://github.com/dragon66/icafe/wiki" rel="nofollow">"icafe" Java-библиотеке изображений.

Из http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch ты попадаешь в это дело?

Что произойдет, если декодер получит код Z, которого еще нет в его словаре? Поскольку декодер всегда отстает от кодера всего на один код, Z может находиться в словаре кодировщика только в том случае, если кодировщик только что сгенерировал его при выдаче предыдущего кода X для χ. Таким образом, Z кодирует некоторый ω, равный χ + ?, и декодер может определить неизвестный символ следующим образом:

1) The decoder sees X and then Z.
2) It knows X codes the sequence χ and Z codes some unknown sequence ω.
3) It knows the encoder just added Z to code χ + some unknown character,
4) and it knows that the unknown character is the first letter z of ω.
5) But the first letter of ω (= χ + ?) must then also be the first letter of χ.
6) So ω must be χ + x, where x is the first letter of χ.
7) So the decoder figures out what Z codes even though it's not in the table,
8) and upon receiving Z, the decoder decodes it as χ + x, and adds χ + x to the table as the value of Z.

Эта ситуация возникает всякий раз, когда кодировщик встречает ввод формы cScSc, где c — одиночный символ, S — строка, а cS уже есть в словаре, а cSc — нет. Кодер выдает код для cS, помещая в словарь новый код для cSc. Затем он видит cSc на входе (начиная со второго c в cScSc) и выдает только что вставленный новый код. Приведенный выше аргумент показывает, что всякий раз, когда декодер получает код, которого нет в его словаре, ситуация должна выглядеть следующим образом.

Хотя ввод формы cScSc может показаться маловероятным, этот шаблон довольно распространен, когда входной поток характеризуется значительным повторением. В частности, длинные строки из одного символа (которые часто встречаются в изображениях, которые LZW часто использует для кодирования) многократно генерируют шаблоны такого рода.

Для этого конкретного случая подходит википедия, у вас есть X+? где X — это (o), Z пока неизвестна, поэтому первая буква — это X, дающая (oo) добавить (oo) к таблице как 257. Я просто исхожу из того, что прочитал в википедии, дайте нам знать, как это получается если это не решение.