Реализация LZW алгоритма сжатия с использованием возможностей современных GPU
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ным 12 битам, что означает возможность запоминания 0FFF, или 4096, элементов в нашей таблице цепочек. Давайте также предположим, что мы имеем 32 возможных различных символа. (Это соответствует, например, картинке с 32 возможными цветами для каждого пиксела.) Чтобы инициализировать таблицу, мы установим соответствие кода #0 символу #0, кода #1 символу #1, и т.д., до кода #31 и символа #31. На самом деле мы указали, что каждый код от 0 до 31 является корневым. Больше в таблице не будет других кодов, обладающих этим свойством.
Особенность LZW заключается в том, что для декомпрессии нам не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.
Мы знаем, что для каждого кода надо добавлять в таблицу строку, состоящую из уже присутствующей там строки и символа, с которого начинается следующая строка в потоке.
Следует отметить, что в целях экономии памяти ЭВМ таблицу цепочек можно эффективно представлять, учитывая следующую ее особенность: если, например, цепочка ASDFK входит в таблицу цепочек, то ASDF тоже входит в нее. Это обстоятельство наводит на мысль, что вместо запоминания в таблице всей цепочки, достаточно запомнить код для ASDF, за которым следует замыкающий символ K.
Для повышения степени сжатия изображений данным методом часто используется одна "хитрость" реализации этого алгоритма. Некоторые изображения, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых значений, например 12 12 12 тАж или 32 32 32 тАж и т. П. Их непосредственное сжатие будет генерировать выходной код 12 12 258 и т.д.
Кодирование таких цепочек будем осуществлять следующим образом. Первый цвет 12 записывает с его же кодом из таблицы 12. Следующий цвет тоже 12, тогда добавляем в таблицу строку 12 12 с кодом 258 и в выходной поток сразу заносим этот код, т.е. 258. Смотрим входной поток дальше. Если на вход опять поступает цвет 12, он есть в таблице, смотрим следующий - 12, последовательность 12 12 тоже есть в таблице, смотрим дальше - 12, последовательности 12 12 12 присваиваем код 259 и заносим его в выходной поток. В результате на выходе получаем последовательность 12 258 259 тАж, которая гораздо короче прямого кодирования стандартным методом LZW.
Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код - это 12, которому соответствует цвет 12. Затем читает код 258, но этого кода в его таблице нет. Такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, т.е. 12. Поэтому он добавит в свою таблицу строку 12 12 с кодом 258, а в выходной поток поместит 12 12. И так может быть раскодирована вся цепочка кодов.
Описанное выше правило кодирования можно применять в общем случае не только к подряд идущим одинаковым цветам точек, но и к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки.
Работа LZW декодирования.
Характеристики алгоритма LZW:
Коэффициенты компрессии: Примерно 1000, 4, 5/7 (Лучший, средний, худший коэффициенты). Сжатие в 1000 раз достигается только на одноцветных изображениях размером кратным примерно 7 Мб.
Класс изображений: Ориентирован LZW на 8-битные изображения, построенные на компьютере. Сжимает за счет одинаковых подцепочек в потоке.
Симметричность: Почти симметричен, при условии оптимальной реализации операции поиска строки в таблице.
Характерные особенности: Ситуация, когда алгоритм увеличивает изображение, встречается крайне редко. LZW универсален - именно его варианты используются в обычных архиваторах.
1.2 Распаковка
Алгоритму сжатия соответствует свой алгоритм распаковки. Он получает выходной поток кодов от алгоритма сжатия и использует его для точного восстановления входного потока. Одной из причин эффективности LZW-алгоритма является то, что он не нуждается в хранении таблицы строк, полученной при сжатии. Таблица может быть точно восстановлена при распаковке на основе выходного потока алгоритма сжатия. Это возможно потому, что алгоритм сжатия выводит СТРОКОВУЮ и СИМВОЛЬНУЮ компоненты кода прежде чем он поместит этот код в выходной поток. Это означает, что сжатые данные не обременены необходимостью тянуть за собой большую таблицу перевода.
Алгоритм распаковки представлен на рис. 3. В соответствии с алгоритмом сжатия, он добавляет новую строку в таблицу строк каждый раз, когда читает из входного потока новый код. Все, что ему необходимо сделать в добавок - это перевести каждый входной код в строку и переслать ее в выходной поток.
Процедура LZW-распаковки:
читать СТАРЫЙ_КОД
вывести СТАРЫЙ_КОДвходной поток не пуст DO
читать НОВЫЙ_КОД
СТРОКА = перевести НОВЫЙ_КОД
вывести СТРОКУ
СИМВОЛ = первый символ СТРОКИ
добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ
СТАРЫЙ_КОД = НОВЫЙ_КОДof WHILE
На рис. 4 приведена схема работы алгоритма на основе сжатых данных, полученных в выше приведенном примере. Важно отметить, что построение таблицы строк алгоритмом распаковки заканчивается как раз тогда, когда построена таблица строк алгоритма сжатия.
Входные коды: / W E D 256 E 260 261 257 B 260 T
ВходСТАРЫЙ КОДСТРОКАСИМВОЛНовый вход таблицыНОВЫЙ КОДВыход///W/WW256 = /WEWEE257 = WEDEDD258 = ED256D/W/259 = D/E256EE260 = /WE260E/WE/261 = E/261260E/E262 = /WEE257261WEW263 = E/WB257BB264 = WEB260B/WE/265 = B/T260TT266 = /WETРис. 4 Процесс распаковки
Выходной поток идент