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

Введение Актуальность данной работы обусловлена большим интересом к теме «Реализация LZW алгоритма сжатия с использованием возможностей современных GPU» в современной науке. Рассмотрение вопросов связанных с данной тематикой носит как теоретическую, так и практическую значимость. Цель работы – изучение темы «Реализация LZW алгоритма сжатия с использование возможностей современных GPU». Задачи: 1) рассмотреть теоретические подходы к LZW алгоритму; 2) выявить основную проблему LZW алгоритма сжатия. С каждым годом мощность и производительность вычислительных систем постоянно растет, проблемы сжатия, и кодирования информации остаются актуальными для разработчиков программного обеспечения. Одним из эффективных и распространенных решений данной проблемы является применение алгоритма сжатия LZW. В основе представленного алгоритма лежит предположение о том, что информация, поступающая на вход кодирующего устройства заведомо избыточна, а содержание полезной информации не равно нулю. В этой ситуации добиться идеального сжатия можно лишь в случае, если предварительно известны энтропия – мера содержания информации, выраженная в битах, множество символов входного алфавита и вероятность появления каждого символа во входном потоке.

---

Не бойтесь заказать реферат в Краснодаре , у нас работают профессионалы

---

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

Достаточно трудно охарактеризовать результативность какой-либо техники сжатия данных. Степень сжатия определяется различными факторами. LZW-сжатие выделяется среди прочих, когда встречается с потоком данных, содержащим повторяющиеся строки любой структуры. По этой причине он работает весьма эффективно, когда встречает английский текст. Уровень сжатия может достигать 50% и выше. Соответственно, сжатие видеоформ и копий экранов показывает еще большие результаты. Трудности при сжатии файлов данных несколько больше. В зависимости от данных, результат сжатия может быть как хорошим, так и не очень удовлетворительным. В некоторых случаях "сжатый" файл может превосходить по своим размерам исходный текст. Программа, приведенная в данной работе, является рабочей. Процедуры, организующие входные и выходные потоки, невелики по размерам и легки для понимания, но увеличивают накладные расходы. Вы можете попробовать увеличить скорость программы, совершенно переписав эти процедуры с использованием кодов фиксированной длины, скажем 12 бит. Одной из проблем является то, что приведенная программа не адаптируется к различной длине файлов. Использование 14- или 15-битных кодов дает лучшую степень сжатия на больших файлах (это объясняется тем, что для них строятся большие таблицы строк), но хуже работает с маленькими файлами. Такие программы, как "ARC", решают эту проблему использованием кодов переменной длины. Например, когда величина next_code находится между 256 и 511, "ARC" читает и выводит 9-битные коды. Когда величина next_code становится настолько большой, что необходимы 10-битные коды, процедуры сжатия и распаковки увеличивают размер кода. Это значит, что 12- и 15-битные варианты программы работают хорошо и на маленьких файлах.

Ватолин Д.С., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2002. 2. Романов В.Ю. Популярные форматы файлов для хранения графических изображений на IBM PC.- М.:Унитех, 1992. 3. Семенюк В. В. Экономное кодирование дискретной информации. – СПб.: СПбГИТМО (ТУ), 2001. 4. http://library.mephi.ru/data/scientific-sessions/2001/13/2146.html 5. http://algolist.manual.ru/compress/standard/lzw.php