Вопрос по algorithm, decompression, lzw, compression – LZW алгоритм декомпрессии

4

Я пишу программу для назначения, которая должна реализовывать сжатие / декомпрессию LZW. Для этого я использую следующие алгоритмы:

-compression

<code>w = NIL;
   while ( read a character k )
       {
         if wk exists in the dictionary
         w = wk;
         else
         add wk to the dictionary;
         output the code for w;
         w = k;
       }
</code>

-decompression

<code>read a character k;
   output k;
   w = k;
   while ( read a character k )    
  /* k could be a character or a code. */
        {
         entry = dictionary entry for k;
         output entry;
         add w + entry[0] to dictionary;
         w = entry;
        }
</code>

Для стадии сжатия я просто выводю целые числа, представляющие индекс для словарная статья, также начальный словарь состоит из символов ASCII (0 - 255). Но когда я прихожу на стадию декомпрессии, я получаю эту ошибку например, если я сжимаю текстовый файл, состоящий только из «booop» он пройдет через эти шаги для создания выходного файла:

<code>w       k       Dictionary          Output

-       b       -                   -
b       o       bo (256)            98 (b)
o       o       oo (257)            111 (o)
o       o       -                   -
oo      p       oop (258)           257 (oo)
p       -       -                   112 (p)
</code>

output.txt: 98 111 257 112

Затем, когда я прихожу, чтобы распаковать файл

<code>w       k          entry        output       Dictionary
        98 (b)                  b   
b       111 (o)    o            o             bo (256)
o       257 (error)
</code>

257 (oo) еще не добавлено. Может ли кто-нибудь увидеть, где я здесь не так, потому что я озадачен. Алгоритм неверен?

Да, я применил внесенные вами изменения в алгоритм, и он работает. clintbeastwood
Проблема решена? dragon66
Можете ли вы показать нам реальный код, потому что псевдокод всегда неоднозначен. Thomash

Ваш Ответ

2   ответа
7

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

-decompression

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, вы обнаружите, что его нет в словаре. Но вы знаете, что предыдущая запись - "o" и первым его символом является «o»; тоже, сложив их вместе, вы получите "oo". Теперь выведите oo и добавьте его в словарь. Затем вы получаете код 112 и уверены, что знаете его с. СДЕЛАННЫЙ!

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

Увидеть:этот объяснение Стива Блэкстока для получения дополнительной информации.лучшая страница с блок-схемой для фактической реализации декодера и кодера, на котором& Quot; icafe & Quot; Библиотека изображений Java GIF кодировщик и декодер на основе.

Работает как шарм спасибо. clintbeastwood
1

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

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

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) add (oo) к таблице как 257. Я просто продолжаю то, что я прочитал в Википедии, дайте нам знать, как это получается если это не решение.

Спасибо, я лучше понимаю, как это на самом деле работает сейчас. clintbeastwood

Похожие вопросы