Адские тиски правосудия

Косякин Антон

Xakep, номер #066, стр. 066-112-3

Берем в руки молот и топор

Перейдем к более интересным вещам - самой реализации. Как я уже говорил, LZW-сжатие относится к словарным методам кодирования. Поэтому главной частью нашей программы будет именно словарь. Можно пойти двумя путями - простым и очень простым :). Можно либо честно хранить в памяти все строки, содержащиеся в словаре (что, кстати, займет достаточно много памяти), либо поступить по-хитрому. Я выбираю второй путь. Будем хранить словарь как набор пар - префикс, т.е. предшествующий номер строки, и символ, который в сочетании с префиксом образует новую строку. И памяти это будет "кушать" меньше, и в реализации попроще.

Определившись с "типом" словаря, снова встаем на перепутье - как его реализовывать. Наш словарь можно представить в виде списка, тогда нам не нужно будет особо заботиться о количестве элементов, выходе за пределы массива - мы будем ограничены только размерами доступной оперативной памяти. Возможен и другой вариант – массив. Да-да, старый добрый статический массив. С четко фиксированным числом элементов. Хорошо это или плохо - решать тебе, но я выбрал именно его. По двум причинам. Во-первых - простота реализации. Во-вторых - номер каждого элемента массива будет совпадать с номером строки в словаре, из-за чего не нужно будет пробегаться по всему словарю в поисках нужной строки. Кстати, здесь возникает один нюанс - при обработке входного файла мы последовательно строим словарь, с помощью которого кодируем данные. Но в один прекрасный момент, особенно если используем массив, свободные ячейки в словаре могут закончиться (или кончится память для списка). Вообще, в таких случаях советуют остановиться с дополнением словаря и кодировать данные по существующему, пока степень сжатия не начнет убывать. А затем - добавить в выходной поток специальный символ (например, с кодом 256), означающий очистку словаря. Однако это тоже приводит к падению степени сжатия. Поэтому, наверное, стоит очищать только половину.

С началом определились. Теперь давай сразу перейдем к концу, а потом уже - к середине :). Как я уже говорил, получив на вход некоторый набор данных, алгоритм LZW перемалывает их, строит некоторый словарь и на выход подает некие коды, которые являются номерами "фраз" в словаре. Поэтому нужно научиться эффективно эти коды записывать. В большинстве реализаций LZ-алгоритмов используются 12-битные коды, т.е. числа от 0 до 4095, по полтора байта на код. Такая запись достаточно компактна, но в этом случае на словарь тоже накладывается ограничение в 4095 фраз, из-за чего на больших файлах возникает проблема. Некоторые реализации используют 16 бит на код, т.е. 2 байта. Но на достаточно маленьких файлах такой способ записи выдает малую степень сжатия. А вот создатели архиватора ARC (если не вру) пошли дальше - изначально используются коды в 9 бит, затем в 10, 12, 15. В зависимости от текущего размера словаря. Советую и тебе идти тем же путем :).