Информатика и выч. техника \ Микропроцессорные системы

Разработка системы для сжатия информации (объём памяти данных не должен превышать 64 килобайт) (Проектная часть дипломного проекта), страница 3

Таблица 2.2. Процесс распаковки.

Вход

СТАРЫЙ КОД

СТРОКА

СИМВОЛ

Новый вход таблицы

НОВЫЙ КОД

Выход

/

/

/

W

/

W

W

256 = /W

E

W

E

E

257 = WE

D

E

D

D

258 = ED

256

D

/W

/

259 = D/

E

256

E

E

260 = /WE

260

E

/WE

/

261 = E/

261

260

E/

E

262 = /WEE

257

261

WE

W

263 = E/W

B

257

B

B

264 = WEB

260

B

/WE

/

265 = B/

T

260

T

T

266 = /WET

Выходной поток идентичен входному потоку алгоритма сжатия. Надо отметить, что первые 256 кодов уже определены для перевода одиночных символов, также как и в алгоритме сжатия.

2.3.3 Особый случай при декодировании данных.

К сожалению, простой алгоритм распаковки, приведенный в таблице 2.2, является все же слишком простым. В алгоритме сжатия существуют некоторые исключительные ситуации, которые создают проблемы при распаковке. Если существует строка, представляющая пару (СТРОКА СИМВОЛ) и уже определенную в таблице, а просматриваемый входной поток содержит последовательность СТРОКА СИМВОЛ СТРОКА СИМВОЛ СТРОКА, алгоритм сжатия выведет код прежде, чем распаковщик получит возможность определить его.

Простой пример иллюстрирует это. Предположим, строка "JOEYN" определена в таблице с кодом 300. Когда последовательность "JOEYNJOEYNJOEY" появляется в таблице, выходной поток алгоритма сжатия выглядит подобно тому, как показано в таблице 2.3.

Входная строка: ...JOEYNJOEYNJOEY...

Таблица 2.3. Проблемы декодирования.

Вход(символы)

Выход(коды)

Новые коды и соответствующие строки

JOEYN

288 = JOEY

300 = JOEYN

A

N

301 = NA

–

–

–

–

–

–

–

–

–

JOEYNJ

300 = JOEYN

400 = JOEYNJ

JOEYNJO

400

401 = JOEYNJO

Когда распаковщик просматривает входной поток, он сначала декодирует код 300, затем выводит строку "JOEYN" и добавляет определение для, скажем, кода 399 в таблицу, хотя он уже мог там быть. Затем читает следующий входной код, 400, и обнаруживает, что его нет в таблице. Это уже проблема. К счастью, это произойдет только в том случае, если распаковщик встретит неизвестный код. Так как это фактически единственная коллизия, то можно без труда усовершенствовать алгоритм.

Модифицированный алгоритм предусматривает специальные действия для еще неопределенных кодов. Распаковщик обнаруживает код 400, который еще не определен. Так как этот код не известен, то декодируется значение СТАРОГО_КОДА, равное 300. Затем распаковщик добавляет значение СИМВОЛА, равное "J", к строке. Результатом является правильный перевод кода 400 в строку "JOEYNJ".

Модифицированная процедура LZW-распаковки:

читать СТАРЫЙ_КОД вывести СТАРЫЙ_КОД СИМВОЛ = СТАРЫЙ_КОД WHILE входной поток не пуст DO читать НОВЫЙ_КОД IF NOT в таблице перевода НОВЫЙ_КОД THEN СТРОКА = перевести СТАРЫЙ_КОД СТРОКА = СТРОКА+СИМВОЛ ELSE СТРОКА = перевести НОВЫЙ_КОД END of IF вывести СТРОКУ СИМВОЛ = первый символ СТРОКИ добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ СТАРЫЙ_КОД = НОВЫЙ_КОД END of WHILE

2.4 Особенности реализации алгоритма LZW

Скачать файл