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

Простая строка, использованная для демонстрации алгоритма, приведена в таблице 2.1. Входная строка является кратким списком английских слов, разделенных символом "/". Как вы можете заметить, анализируя алгоритм, его работа начинается с того, что на первом шаге цикла он выполняет проверку на наличие строки "/W" в таблице. Когда он не находит эту строку, то генерирует код для "/" и добавляет в таблицу строку "/W". Т.к. 256 символов уже определены для кодов 0 - 255, то первой определенной строке может быть поставлен в соответствие код 256. После этого система читает следующую букву ("E"), добавляет вторую подстроку ("WE") в таблицу и выводит код для буквы "W".

Этот процесс повторяется до тех пор, пока вторая подстрока, состоящая из прочитанных символов "/" и "W", не сопоставится со строковым номером 256. В этом случае система выводит код 256 и добавляет трехсимвольную подстроку в таблицу. Этот процесс продолжается до тех пор, пока не исчерпается входной поток и все коды не будут выведены.

Входная строка: /WED/WE/WEE/WEB/WET

Таблица 2.1. Процесс сжатия.

Выходной поток для заданной строки показан в таблице 2.1, также как и полученная в результате таблица строк. Как вы можете заметить, эта таблица быстро заполняется, т.к. новая строка добавляется в таблицу каждый раз, когда генерируется код. В этом явно вырожденном примере было выведено пять закодированных подстрок и семь символов. Если использовать 9-битные коды для вывода, то 19-символьная входная строка будет преобразована в 13.5-символьная выходную строку. Конечно, этот пример был выбран только для демонстрации. В действительности сжатие обычно не начинается до тех пор, пока не будет построена достаточно большая таблица, обычно после прочтения порядка 100 входных байт.

2.3.2 Краткое описание алгоритма декодирования.

Алгоритму сжатия соответствует свой алгоритм распаковки. Он получает выходной поток кодов от алгоритма сжатия и использует его для точного восстановления входного потока. Одной из причин эффективности LZW-алгоритма является то, что он не нуждается в хранении таблицы строк, полученной при сжатии. Таблица может быть точно восстановлена при распаковке на основе выходного потока алгоритма сжатия. Это возможно потому, что алгоритм сжатия выводит СТРОКОВУЮ и СИМВОЛЬНУЮ компоненты кода прежде чем он поместит этот код в выходной поток. Это означает, что сжатые данные не обременены необходимостью тянуть за собой большую таблицу перевода.

Алгоритм распаковки представлен ниже:

Процедура LZW-распаковки:

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

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

В таблице 2.2 приведена схема работы алгоритма на основе сжатых данных, полученных в выше приведенном примере. Важно отметить, что построение таблицы строк алгоритмом распаковки заканчивается как раз тогда, когда построена таблица строк алгоритма сжатия.

Входные коды: / W E D 256 E 260 261 257 B 260 T