Реализация LZW алгоритма сжатия с использованием возможностей современных GPU
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Оглавление
Введение
. Метод LZW алгоритма
.1 Сжатие
.2 Распаковка
.3 Реализация
.4 Графический формат GIF
.5 Формат TIFF
. Возможности использования современных GPU
.1 Алгоритм
.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 строк. Ядро кода сжатия занимает не более сотни строк, а код декомпрессии не намного больше. Программисты считают, что это облегчает чтение и понимание алгоритма, а также позволяет адаптировать его для самых разных целей.
1.Метод LZW алгоритма
Собственно исходный Lempel/Ziv подход к сжатию данных был впервые обнародован в 1977г., а усовершенствованный (Terry Welch) вариант был опубликован в 1984г. Алгоритм на удивление прост. Если в двух словах, то LZW-сжатие заменяет строки символов некоторыми кодами. Это делается без какого-либо анализа входного текста. Вместо этого при добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда код заменяет строку символов. Коды, генерируемые LZW-алгоритмом, могут быть любой длины, но они должны содержать больше бит, чем единичный символ. Первые 256 кодов (когда используются 8-битные символы) по умолчанию соответствуют стандартному набору символов. Остальные коды соответствуют обрабатываемым алгоритмом строкам. Ядром LZW-алгоритма является словарь, содержащий все символы входного алфавита и некоторые строки из этих символов. До начала работы алгоритма в словарь входят элементы, в качестве строк содержащие каждый из символов входного алфавита. По мере работы алгоритма, встречающиеся во входном потоке цепочки символов заносятся в словарь. При этом в выходной поток заносится номер элемента словаря, содержащий строку максимальной длины, совпадающую со строкой входного потока. Словарь организован как совокупность двоичных деревьев и содержит по одному двоичному дереву на каждый символ входного алфавита. Каждый элемент словаря является в то же время вершиной одного из двоичных деревьев. Вершины деревьев являются элементами словаря, соответствующими символам входного алфавита. Каждая вершина соответствует некоторой строке, имеет одну входящую дугу и до двух выходящих. Первая из них указывает на вершину, которая соответствует стр