Сложно понять декомпрессию с помощью алгоритма LZW.

Я сжал следующее сообщение: ababcbababaaaaaaa, используя алгоритм сжатия LZW.

С a=1;b=2;c=3 я получаю следующее сообщение: 1 2 4 3 5 8 1 10 11 1, что соответствует результату, который мой профессор получил в наших конспектах упражнений.

Однако, когда я пытаюсь распаковать сообщение, я получаю следующую последовательность событий:

Current: a  ; Next: b  ; Output: a  ; AddToDict: ab=4;

Current: b  ; Next: a  ; Output: b  ; AddToDict: ba=5;

Current: ab ; Next: c  ; Output: ab ; AddToDict: abc=6;

Current: c  ; Next: ba ; Output: c  ; AddToDict: cb=7;

Current: ba ; Next: 8? ; Output: ?  ; AddToDict: ?;

Как видите, моя проблема в том, что у меня еще нет 8 (которое должно быть bab) в словаре.

Что я делаю не так?

Полный словарь, полученный в результате сжатия,

(1=a;2=b;3=c;4=ab;5=ba;6=abc;7=cb;8=bab;9=baba;10=aa;11=aaa;12=aaaa)


compression algorithm information-theory lzw
person user569685    schedule 19.08.2020    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Тебе следует быть осторожным! Первый столбец — это текущая последовательность, а второй — следующий символ (не следующая последовательность). Следовательно, вы допустили ошибку, написав следующее: ba. Кстати, до последней строки правильно:

Current: ba  ; Next: b   ; Output: ba   ; AddToDict: bab = 8;   // here is 5
Current: bab ; Next: a   ; Output: bab  ; AddToDict: baba = 9;  // here you can find 8
Current: a   ; Next: a   ; Output: a    ; AddToDict: aa = 10;   // here is 1 
Current: aa  ; Next: a   ; Output: aa   ; AddToDict: aaa = 11;  // here is 10
Current: aaa ; Next: a   ; Output: aaa  ; AddToDict: aaaa = 12; // here is 11
Current: a   ; Next: #   ; Output: a    ; #                     // here is 1
person OmG    schedule 19.08.2020

arrow_upward
1
arrow_downward

Вы думаете о Current Next. Я рассматриваю расшифровку с точки зрения Previous Current. Поэтому при чтении этого ответа имейте в виду, что Current — это текущий номер из сообщения (см. столбец с меткой Current в таблице ниже и обратите внимание, что он содержит сообщение, которое нужно декодировать).

Обратите внимание, что по моему определению первый код сообщения следует рассматривать как особый случай, поскольку Previous кода нет. Первый код в сообщении всегда представляет собой однобуквенный код, и при обработке этого кода словарная запись не создается.

Для всех остальных кодов в сообщении есть две возможности:

  • Типично: код Current имеет словарную запись. В этом случае выходом является строка словаря для кода Current. Новая строка словаря формируется путем взятия строки для кода Previous и добавления первой буквы строки для кода Current.

  • Причудливо: код Current еще не имеет словарной статьи. В этом случае на выходе будет строка для кода Previous плюс первая буква строки для кода Previous. Новая строка словаря формируется путем взятия строки для кода Previous и добавления первой буквы строки для кода Previous.

Имея это в виду, вот как расшифровывается сообщение:

Previous  Current  Output    Dictionary  Type
    -        1       a        -          special
    1        2       b        4: ab      typical
    2        4       ab       5: ba      typical
    4        3       c        6: abc     typical
    3        5       ba       7: cb      typical
    5        8       bab      8: bab     quirky: dict[5] is "ba" plus first letter of dict[5] is "b" means dict[8] is "bab"
    8        1       a        9: baba    typical
    1       10       aa      10: aa      quirky
   10       11       aaa     11: aaa     quirky
   11        1       a       12: aaaa    typical

Обратите внимание, что в необычном случае вывод и новая запись в словаре совпадают. Они генерируются с использованием информации исключительно из кода Previous. Код Current игнорируется при расшифровке причудливого случая, а новая запись в словаре является записью для кода Current.

person user3386109    schedule 19.08.2020