Реализация LZW алгоритма сжатия с использованием возможностей современных GPU
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?чен входному потоку алгоритма сжатия. Отметим, что первые 256 кодов уже определены для перевода одиночных символов, также как и в алгоритме сжатия.
В алгоритме сжатия существуют некоторые исключительные ситуации, которые создают проблемы при распаковке. Если существует строка, представляющая пару (СТРОКА СИМВОЛ) и уже определенную в таблице, а просматриваемый входной поток содержит последовательность СТРОКА СИМВОЛ СТРОКА СИМВОЛ СТРОКА, алгоритм сжатия выведет код прежде, чем распаковщик получит возможность определить его.
Простой пример иллюстрирует это. Предположим, строка "JOEYN" определена в таблице с кодом 300. Когда последовательность "JOEYNJOEYNJOEY" появляется в таблице, выходной поток алгоритма сжатия выглядит подобно тому, как показано на рис. 5.
Входная строка: тАжJOEYNJOEYNJOEYтАж
Вход(символы)Выход(коды)Новые коды и соотв. СтрокиJOEYN288 = JOEY300 = JOEYNAN301 = NA.........JOEYNJ300 = JOEYN400 = JOEYNJJOEYNJO400401 = JOEYNJO
Когда распаковщик просматривает входной поток, он сначала декодирует код 300, затем выводит строку "JOEYN" и добавляет определение для, скажем, кода 399 в таблицу, хотя он уже мог там быть. Затем читает следующий входной код, 400, и обнаруживает, что его нет в таблице. Это уже проблема. К счастью, это произойдет только в том случае, если распаковщик встретит неизвестный код. Так как это фактически единственная коллизия, то можно без труда усовершенствовать алгоритм.
Модифицированный алгоритм предусматривает специальные действия для еще неопределенных кодов. В примере на рис. 6 распаковщик обнаруживает код 400, который еще не определен. Так как этот код не известен, то декодируется значение СТАРОГО_КОДА, равное 300. Затем распаковщик добавляет значение СИМВОЛА, равное "J", к строке. Результатом является правильный перевод кода 400 в строку "JOEYNJ".
Процедура LZW-распаковки:
читать СТАРЫЙ_КОД
вывести СТАРЫЙ_КОД
СИМВОЛ = СТАРЫЙ_КОДвходной поток не пуст DO
читать НОВЫЙ_КОДNOT в таблице перевода НОВЫЙ_КОД THEN
СТРОКА = перевести СТАРЫЙ_КОД
СТРОКА = СТРОКА+СИМВОЛ
СТРОКА = перевести НОВЫЙ_КОДof IF
вывести СТРОКУ
СИМВОЛ = первый символ СТРОКИ
добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ
СТАРЫЙ_КОД = НОВЫЙ_КОДof WHILE
Рис. 6 Модифицированный алгоритм распаковки
.3 Реализация
Алгоритм реализован как приложение Windows 95/98 на языке программирования C++. Структурная схема реализации приведена на рисунке. Данный вариант имеет семь логически независимых блоков, отвечающих за инициализацию хэшей и стеков, передачу, чтение, запись и буферизацию байтов данных, дополнение, очистку стеков и динамически выделяемой памяти, рекурсивный поиск по хэшу и рекурсивное кодирование повторяющихся данных хэш-таблицы (т.е. сжатие второго уровня, происходящее одновременно со сжатием основного потока, благодаря чему объем используемой памяти не только сокращается, но и становится заведомо известным). Передача кодируемых байтов между блоками осуществляется как с помощью простого вызова соответствующих функций, так и с помощью классов-интерфейсов, преобразующих восьмибитовые байты в N-битовые.
Проведенное тестирование разработанного модуля показало, что практическая реализация алгоритма LZW по качеству сопоставима с самыми современными программами сжатия информации.
Концепции, использованные в алгоритме сжатия, настолько просты, что весь алгоритм может быть записан в несколько строк. Но так как управление построением таблицы требует некоторых специальных действий, реализация несколько более сложна. В демонстрационной программе, приведенной ниже, использовались коды длиной 12, 13 и 14 бит. При длине кода 12 бит потенциально возможно хранить до 4096 строк в таблице. Каждый раз, когда читается новый символ, таблица строк должна просматриваться для сопоставления. Если сопоставление не найдено, новая строка должна быть добавлена в таблицу. Здесь возникают две проблемы. Во-первых, таблица строк может достаточно быстро стать очень большой. Даже если длина строк в среднем ограничивается 3 или 4 символами каждая, верхний предел длин строк может легко превысить 7 или 8 байт на код. К тому же количество памяти, необходимой для хранения строк, заранее не известно, так как оно зависит от общей длины строк.
Вторая проблема заключается в организации поиска строк. Каждый раз, когда читается новый символ, необходимо организовать поиск для новой строки вида СТРОКА+СИМВОЛ. Это означает поддержку отсортированного списка строк. В этом случае поиск для каждой строки включает число сравнений порядка log2 от общего числа строк. Использование 12-битных слов потенциально позволяет выполнять не более 12 сравнений для каждого кода.
Первая проблема может быть решена хранением строк как комбинаций код/символ. Так как каждая строка в действительности является представлением комбинации уже существующего кода и добавочного символа, можно хранить каждую строку как отдельный код плюс символ. Например, в разобранном выше примере строка "/WEE" хранится как код 260 и символ "E". Это позволяет использовать для хранения только 3 байта вместо 5 (включающих дополнительный байт для конца строки). Идя назад, можно определить, что код 260 хранится как код 256 плюс добавочный символ "E". Наконец, код 256 хранится как "/" плюс "W".
Выполнение сравнения строк является немного более трудным. Новый метод хранения увеличивает время, необходимое для сравнения строк, но он не влияет на число сравнений. Эта проблема решается ис