Реализация LZW алгоритма сжатия с использованием возможностей современных GPU
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ользованием алгоритма хэширования для хранения строк. Это означает, что код 256 не хранится в каком-либо массиве по адресу 256, а хранится в массиве по адресу, сформированному на основе самой строки. При определении места хранения данной строки можно использовать тестовую строку для генерации хэш-адреса и затем найти целевую строку однократным сравнением. Так как код для любой данной строки нельзя узнать в дальнейшем иначе как по его позиции в массиве, необходимо хранить код для данной строки совместно с данными строки. В демонстрационной программе для этого используются элементы трех массивов: code_value[i], prefix_code[i] и append_character[i].
Когда необходимо добавить новый код в таблицу, используется хэш-функция в процедуре find_match для генерации корректного i. Процедура find_match генерирует адрес и затем проверяет, не использовался ли он уже. Если это так, то find_match выполняет вторую пробу и так до тех пор, пока не найдется свободное место.
Хэш-функция, использованная в этой программе - простая "xor"-типа кэш-функция. Префикс кода и добавочный символ комбинируются для формирования адреса массива. Если содержимое префикса кода и символ в массиве сопоставляются им, то возвращается корректный адрес. Если элемент массива по этому адресу уже использован, выполняется фиксированное смещение для поиска нового места. Это выполняется до тех пор, пока не будет найдено свободное место или не произойдет сопоставление. Среднее число поисков в такой таблице - меньше 3, если используется таблица на 25% большего размера, чем необходимо. Оно может быть улучшено путем увеличения размера таблицы. Необходимо отметить, что для того, чтобы порядок вторичных проб работал, размер таблицы должен быть простым числом. Это объясняется тем, что проба может быть любым целым между 1 и размером таблицы. Если проба и размер таблицы не являются взаимно простыми, поиск свободных мест может закончиться неудачей, даже если они есть.
Реализация алгоритма распаковки имеет свой набор проблем. Одна из проблем алгоритма сжатия здесь исчезает. Когда выполняется сжатие, необходимо организовать поиск в таблице для данной строки. При распаковке необходимо организовать просмотр для отдельного кода. Это означает, что можно хранить префиксы кодов и добавочные символы, индексируясь по их строковому коду. Это устраняет необходимость в хэш-функции и освобождает массив, использовавшийся для хранения значений кодов.
К сожалению метод, использованный для хранения строковых величин, приводит к тому, что декодировка строк должна выполняться в инверсном порядке. Это значит, что все символы для данной строки при декодировании должны помещаться в стековый буфер, а затем выводиться в обратном порядке. В приведенной программе это выполняется функцией decode_string.
Проблема появляется, когда чтение входного потока прерывается при достижении конца потока. Для этого частного случая в программе зарезервирован последний определяемый код MAX_VALUE как признак конца данных. Это не является необходимым при чтении файла, но может помочь при чтении буфера сжатых данных из памяти. Затраты на потерю одного определяемого кода весьма малы сравнительно со всем процессом.
Алгоритм LZW имеет несколько особенностей своей реализации в формате сжатия изображений gif. Первая особенность - это переменный размер кода таблицы цепочек, который не может превышать 12 бит, т.е. не превышать числа 4095. Вторая особенность состоит в использовании двух специальных кодов - это код обновления (реинициализации) таблицы цепочек, и код завершения потока символов.
В самом начале своей работы алгоритм определяет количество цветов, используемых в изображении. В случае GIF их максимум может быть 256, т.к. любое изображение, даже с большим набором цветов преобразуется в 256 цветовое пространство. Минимум может быть 2 цвета. Если используется только два цвета, то начальный размер кодов в таблице равен 3 битам. Причем коду 0 ставится цвет 0, а коду 1 - цвет 1. Коды 4 и 5 соответствуют коду очистки таблицы и коду. При большем количестве цветов размер кода таблицы равен числу бит N, приходящихся на один пиксел. При этом специальные коды равны и. Начальный размер кодов в таблице записывается в заголовок GIF файла.
Кодирование пикселей изображения начинается кодами размером бит. По мере накопления таблицы будут увеличиваться значения кодов и как только очередной код достигает значения, то это значит, что значение необходимо увеличить на 1, иначе значение кода превысит прежний размер в бит.
Разработчики формата GIF ограничили максимальный размер кодов в таблице 12 битами. Это значит, что когда код достигает значения, то размер увеличивать уже нельзя. Но в то же время и размер кодов становится больше 12 бит.
Отметим самые главные варианты LZ-метода. Данная таблица содержит сведения об основных отличиях в разных реализациях этого метода. Все они произошли от одного из двух разных подходов.
Таблица: Основные варианты LZ-схемы.
ИмяАвторыОтличияLZ77Ziv and Lempel [1977]Указатели и символы чередуются. Указатели адресуют подстроку среди предыдущих N символов.LZRRoden et al [1981]Указатели и символы чередуются. Указатели адресуют подстроку среди всех предыдущих символов.LZSSBell [1986]Указатели и символы различаются флажком-битом. Указатели адресуют подстроку среди предыдущих N символов.LZBBell [1987]Аналогично LZSS, но для указателей применяется разное кодирование.LZHBrent [1987]Аналогично LZSS, но на втором шаге для указателей применяется кодирование Хаффмана.LZ78Ziv and Lempel [1978]Указатели и символы чередуются. Указат