Концепции, использованные в алгоритме сжатия, достаточно просты, настолько, что весь алгоритм может быть записан в несколько строк. Но так как управление построением словаря требует некоторых специальных действий, реализация несколько более сложна. В программе, реализованной в дипломном проекте, используются коды длиной 9, 10, 11 и 12 бит. Программа следит за параметром next_code, который отвечает за длину выводимого кода и всегда выводит именно то число битов кода, которое необходимо для его корректного представления. Для этого зарезервировано три кода, которые вставляются в выходной поток перед каждым увеличением длины кода. Убытки при добавлении в выходной поток 5 байтов очень малы по сравнению с выигрышем в степени сжатия. При длине кода 12 бит потенциально возможно хранить до 4096 строк в таблице словаря, так что потеря 3 строк не повлияет существенно на степень сжатия информации. Каждый раз, когда читается новый символ, таблица строк должна просматриваться для сопоставления. Если сопоставление не найдено, новая строка должна быть добавлена в таблицу. Здесь возникают две проблемы. Во-первых, таблица строк может достаточно быстро стать очень большой. Даже если длина строк в среднем ограничивается 3 или 4 символами каждая, верхний предел длин строк может легко превысить 7 или 8 байт на код. К тому же количество памяти, необходимой для хранения строк, заранее не известно, так как оно зависит от общей длины строк.
Вторая проблема заключается в организации поиска строк. Каждый раз, когда читается новый символ, необходимо организовать поиск для новой строки вида СТРОКА+СИМВОЛ. Это означает поддержку отсортированного списка строк. В этом случае поиск для каждой строки включает число сравнений порядка log2 от общего числа строк. Использование 12-битных слов потенциально позволяет выполнять не более 12 сравнений для каждого кода.
Первая проблема может быть решена хранением строк как комбинаций код/символ. Так как каждая строка в действительности является представлением комбинации уже существующего кода и добавочного символа, можно хранить каждую строку как отдельный код плюс символ. Например в разобранном выше примере строка "/WEE" хранится как код 260 и символ "E". Это позволяет использовать для хранения только 3 байта вместо 5 (включающих дополнительный байт для конца строки). Идя назад, можно определить, что код 260 хранится как код 256 плюс добавочный символ "E". Наконец, код 256 хранится как "/" плюс "W". Данное решение позволяет заранее ограничить используемую память и хранить в словаре последовательность практически любой длины (в реальной ситуации строка не может быть длиннее количества строк в словаре).
Выполнение сравнения строк является немного более трудным. Новый метод хранения увеличивает время, необходимое для сравнения строк, но он не влияет на число сравнений. Эта проблема решается использованием алгоритма хэширования для хранения строк. Это означает, что код 256 не хранится в каком-либо массиве по адресу 256, а хранится в массиве по адресу, сформированному на основе самой строки. При определении места хранения данной строки можно использовать тестовую строку для генерации хэш-адреса и затем найти целевую строку однократным сравнением. Так как код для любой данной строки нельзя узнать в дальнейшем иначе как по его позиции в массиве, необходимо хранить код для данной строки совместно с данными строки. В программе для этого используются элементы трёх массивов: code_value[i], prefix_code[i] и append_character[i].
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.