К несчастью прекрасный , простой алгоритм
распаковки, приведенный на рис. 4, является все таким слишком
простым. В алгоритме сжатия существуют некоторые исключительные
ситуации, которые создают проблемы при распаковке. Если существует
строка, представляющая пару (СТРОКА СИМВОЛ) и уже определенную в
таблице, а просматриваемый входной поток содержит последовательность
СТРОКА СИМВОЛ СТРОКА СИМВОЛ СТРОКА, алгоритм сжатия выведет код
прежде, чем распаковщик получит возможность определить его.
Простой пример иллюстрирует это. Предположим, строка "JOEYN"
определена в таблице с кодом 300. Когда последовательность
"JOEYNJOEYNJOEY" появляется в таблице, выходной поток алгоритма
сжатия выглядит подобно тому, как показано на рис. 5.
Входная строка : ...JOEYNJOEYNJOEY...
| Вход(символы) |
Выход(коды) |
Новые коды и
соотв. строки |
| JOEYN |
288 = JOEY |
300 = JOEYN |
| A |
N |
301 = NA |
| . |
. |
. |
| . |
. |
. |
| . |
. |
. |
| JOEYNJ |
300 = JOEYN |
400 = JOEYNJ |
| JOEYNJO |
400 |
401 =
JOEYNJO |
Рис. 5 Некоторые проблемы
Когда распаковщик просматривает входной поток,
он сначала декодирует код 300, затем выводит строку "JOEYN" и
добавляет определение для, скажем, кода 399 в таблицу, хотя он уже
мог там быть. Затем читает следующий входной код, 400, и
обнаруживает, что его нет в таблице. Это уже проблема. К счастью,
это произойдет только в том случае, если распаковщик встретит
неизвестный код. Так как это фактически единственная коллизия, то
можно без труда усовершенствовать алгоритм.
Модифицированный алгоритм предусматривает специальные действия
для еще неопределенных кодов. В примере на рис. 6 распаковщик
обнаруживает код 400, который еще не определен. Так как этот код не
известен, то декодируется значение СТАРОГО_КОДА, равное 300. Затем
распаковщик добавляет значение СИМВОЛА, равное "J", к строке.
Результатом является правильный перевод кода 400 в строку
"JOEYNJ".
Процедура LZW-распаковки:
читать СТАРЫЙ_КОД
вывести СТАРЫЙ_КОД
СИМВОЛ =
СТАРЫЙ_КОД
WHILE входной поток не пуст DO
читать
НОВЫЙ_КОД
IF NOT в таблице перевода НОВЫЙ_КОД THEN
СТРОКА =
перевести СТАРЫЙ_КОД
СТРОКА = СТРОКА+СИМВОЛ
ELSE
СТРОКА =
перевести НОВЫЙ_КОД
END of IF
вывести СТРОКУ
СИМВОЛ =
первый символ СТРОКИ
добавить в таблицу перевода
СТАРЫЙ_КОД+СИМВОЛ
СТАРЫЙ_КОД = НОВЫЙ_КОД
END of WHILE
Рис. 6 Модифицированный алгоритм распаковки
Назад
