Реализация LZW алгоритма сжатия с использованием возможностей современных GPU - Дипломная работа

Актуальность данной работы обусловлена большим интересом к теме "Реализация LZW алгоритма сжатия с использованием возможностей современных GPU" в современной науке. Задачи: 1) рассмотреть теоретические подходы к LZW алгоритму; 2) выявить основную проблему LZW алгоритма сжатия. В основе представленного алгоритма лежит предположение о том, что информация, поступающая на вход кодирующего устройства заведомо избыточна, а содержание полезной информации не равно нулю. В этой ситуации добиться идеального сжатия можно лишь в случае, если предварительно известны энтропия - мера содержания информации, выраженная в битах, множество символов входного алфавита и вероятность появления каждого символа во входном потоке. В числе достоинств алгоритма LZW - использование целочисленной арифметики, возможность автоматической адаптации к качественному составу входного потока, возможность разделения и инициализации последовательностей, имеющих заранее известную структуру, использование плавающей длины байта (от 9 до N битов), экономное использование динамической памяти, и файловая независимость от таблицы соответствий между кодами и символами алфавита.Вместо этого при добавлении каждой новой строки символов просматривается таблица строк. Ядром LZW-алгоритма является словарь, содержащий все символы входного алфавита и некоторые строки из этих символов. До начала работы алгоритма в словарь входят элементы, в качестве строк содержащие каждый из символов входного алфавита. По мере работы алгоритма, встречающиеся во входном потоке цепочки символов заносятся в словарь. Первая из них указывает на вершину, которая соответствует строке, такой же, как данная, но на один символ длиннее (связь ), вторая - на вершину, соответствующую строке, имеющей такую же длину, как данная, но отличающуюся последним символом (связь ).· Если в таблице содержится комбинации "текущая строка символ (под " " имеется в виду конкатенация строк)", то выполняется: o Проверка на наличие в таблице более крупной цепочки, начинающаяся с данной, поэтому присоединяем символ к строке. · иначе (если текущая строка символ не содержится в таблице но текущая строка при этом таблице.) · Текущая строка теперь - последний считанный из потока символ (все, что было считано до него, уже выведено в выходной файл). Если строка есть, то мы считываем следующий символ, а если строки нет, то мы заносим в поток код для предыдущей найденной строки, заносим строку в таблицу и начинаем поиск снова. (Это соответствует, например, картинке с 32 возможными цветами для каждого пиксела.) Чтобы инициализировать таблицу, мы установим соответствие кода #0 символу #0, кода #1 символу #1, и т.д., до кода #31 и символа #31.Одной из причин эффективности LZW-алгоритма является то, что он не нуждается в хранении таблицы строк, полученной при сжатии. Это возможно потому, что алгоритм сжатия выводит СТРОКОВУЮ и СИМВОЛЬНУЮ компоненты кода прежде чем он поместит этот код в выходной поток. Процедура LZW-распаковки: читать СТАРЫЙ_КОД вывести СТАРЫЙ_КОД СТРОКА = перевести НОВЫЙ_КОД вывести СТРОКУ Если существует строка, представляющая пару (СТРОКА СИМВОЛ) и уже определенную в таблице, а просматриваемый входной поток содержит последовательность СТРОКА СИМВОЛ СТРОКА СИМВОЛ СТРОКА, алгоритм сжатия выведет код прежде, чем распаковщик получит возможность определить его.Даже если длина строк в среднем ограничивается 3 или 4 символами каждая, верхний предел длин строк может легко превысить 7 или 8 байт на код. Так как каждая строка в действительности является представлением комбинации уже существующего кода и добавочного символа, можно хранить каждую строку как отдельный код плюс символ. Например, в разобранном выше примере строка "/WEE" хранится как код 260 и символ "E". Это означает, что код 256 не хранится в каком-либо массиве по адресу 256, а хранится в массиве по адресу, сформированному на основе самой строки. Так как код для любой данной строки нельзя узнать в дальнейшем иначе как по его позиции в массиве, необходимо хранить код для данной строки совместно с данными строки.Боб Берри (Bob Berry), взял LZW в качестве основы для созданного им в 1987 году принципиально нового графического формата GIF (Graphic Interchange Format). Следует отметить, что созданная Терри Уэлчем компания Unisys, которой и принадлежали авторские права на алгоритм LZW, взимала плату за его использование только с производителей аппаратного обеспечения для компьютеров, в котором применялся данный стандарт, например с изготовителей модемов. Однако зимой 1994 года компания Unisys, начавшая испытывать финансовые проблемы, объявила LZW коммерческим стандартом, потребовав оплаты за его использование. Тем не менее GIF чрезвычайно широко используется в Интернете и сейчас, причем пользователи не обязаны оплачивать кому бы то ни было возможность опубликовать во Всемирной сети изображение в данном формате, так как упомянутые выше финансовые претензии касаются в первую очередь, производителей работающего

Оглавление

Введение

1. Метод LZW алгоритма

1.1 Сжатие

1.2 Распаковка

1.3 Реализация

1.4 Графический формат GIF

1.5 Формат TIFF

2. Возможности использования современных GPU

2.1 Алгоритм

2.2 Исполнительные точки отсчета

Заключение

Список используемой литературы

Приложение

Актуальность данной работы обусловлена большим интересом к теме "Реализация LZW алгоритма сжатия с использованием возможностей современных GPU" в современной науке. Рассмотрение вопросов связанных с данной тематикой носит как теоретическую, так и практическую значимость.

Цель работы - изучение темы "Реализация LZW алгоритма сжатия с использование возможностей современных GPU".

Задачи: 1) рассмотреть теоретические подходы к LZW алгоритму; 2) выявить основную проблему LZW алгоритма сжатия.

С каждым годом мощность и производительность вычислительных систем постоянно растет, проблемы сжатия, и кодирования информации остаются актуальными для разработчиков программного обеспечения. Одним из эффективных и распространенных решений данной проблемы является применение алгоритма сжатия LZW.

В основе представленного алгоритма лежит предположение о том, что информация, поступающая на вход кодирующего устройства заведомо избыточна, а содержание полезной информации не равно нулю. В этой ситуации добиться идеального сжатия можно лишь в случае, если предварительно известны энтропия - мера содержания информации, выраженная в битах, множество символов входного алфавита и вероятность появления каждого символа во входном потоке. Альтернативным решением задачи является метод LZW, который по мере поступления информации динамически вычисляет целочисленные признаки частоты появления входных символов. Этими признаками являются: · положение повторяющейся цепочки символов в промежуточной таблице соответствий между исходным фиксированным алфавитом и кодирующими последовательностями;

· длина сжатого кода, соответствующего набору символов во входном потоке;

· битовый диапазон длин кодов, значения которого колеблются от 9 до 16 бит;

· размер хэш-таблицы, а также разбиение ячеек этой таблицы на жестко фиксированные и имеющие переменные значения.

В числе достоинств алгоритма LZW - использование целочисленной арифметики, возможность автоматической адаптации к качественному составу входного потока, возможность разделения и инициализации последовательностей, имеющих заранее известную структуру, использование плавающей длины байта (от 9 до N битов), экономное использование динамической памяти, и файловая независимость от таблицы соответствий между кодами и символами алфавита. Все это позволяет использовать алгоритм LZW в разных приложениях не только обособленно в качестве архиватора данных, но и в составе более сложных методов, таких как, например, методы шифрования или любые другие методы побайтовой обработки информации. Метод сжатия LZW (Lempel-Ziv-Welch) разработан в 1978 году израильтянами Лемпелом и Зивом и доработан позднее в США. Название алгоритм получил по первым буквам фамилий его разработчиков - Lempel, Ziv и Welch. Сжатие в нем, в отличие от RLE, осуществляется уже за счет одинаковых цепочек байт. LZW - это способ сжатия данных, который извлекает преимущества при повторяющихся цепочках данных.

Популярность алгоритма LZW в значительной степени связана с успехом программы compress. Исходный текст последней версии программы, осуществляющей как сжатие, так и декомпрессию, занимает всего 1200 строк. Ядро кода сжатия занимает не более сотни строк, а код декомпрессии не намного больше. Программисты считают, что это облегчает чтение и понимание алгоритма, а также позволяет адаптировать его для самых разных целей.