Декодирование по LZW
Кодирование
Итак, пусть мы сжимаем последовательность «abacabadabacabae».
· Шаг 1: Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке “a” и проверим, есть ли строка “a” в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка “a” есть в таблице.
· Шаг 2: Далее мы читаем следующий символ «b» из входного потока и проверяем, есть ли строка “ab” в таблице. Такой строки в таблице пока нет.
· Добавляем в таблицу <5> “ab”. В выход: <0>;
· Шаг 3: “ba” — нет. В словарь: <6> “ba”. В выход: <1>;
· Шаг 4: “ac” — нет. В словарь: <7> “ac”. В выход: <0>;
· Шаг 5: “ca” — нет. В словарь: <8> “ca”. В выход: <2>;
· Шаг 6: “ab” — есть в словаре; “aba” — нет. В словарь: <9> “aba”. В выход: <5>;
· Шаг 7: “ad” — нет. В словарь: <10> “ad”. В выход: <0>;
· Шаг 8: “da” — нет. В словарь: <11> “da”. В выход: <3>;
· Шаг 9: “aba” — есть в словаре; “abac” — нет. В словарь: <12> “abac”. В выход: <9>;
· Шаг 10: “ca” — есть в таблице; “cab” — нет. В словарь: <13> “cab”. В выход: <8>;
· Шаг 11: “ba” — есть в таблице; “bae” — нет. В словарь: <14> “bae”. В выход: <6>;
· Шаг 12: И, наконец последняя строка “e”, за ней идет конец сообщения, поэтому мы просто выводим <4>.
Итак, мы получаем закодированное сообщение «0 1 0 2 5 0 3 9 8 6 4», что на 11 бит короче. При этом для расшифровки необходимо дополнительно хранить начальный словарь : 0-a, 1-b, 2-c, 3-d, 4-e.
Особенность алгоритма LZW заключается в том, что для декомпрессии нам не надо сохранять всютаблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только имеющейся сжатой последовательностью и начальным словарем, или ASCII таблицей.
Теперь представим, что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего, нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто соединением-объединением предыдущих записей.
Итак, декодирование.
