Сегодня перед многими разработчиками программного обеспечения встает вопрос, каким образом обеспечить приличное сжатие информации в базах данных. Очевидна необходимость хранить всю базу в компактном, сжатом варианте, ведь она очень часто имеет довольно приличный объем, измеряемый в сотнях мегабайт. При этом нужно обеспечить оперативный доступ к данным и наибольший коэффициент сжатия. Ясно, что оптимальный выход - разработать собственную систему архивации. В таком случае необходимо учитывать некоторые важные особенности программных продуктов, для которых система разрабатывается, и заранее продумывать все аспекты проблемы.

В этой статье рассматриваются плюсы и минусы реализации классических методов архивации (таких, как алгоритмы Хаффмана и LZW) в аспекте нашей задачи - сжатия больших объемов информации в базах данных. Проводится также сравнение с готовой технологией корпорации "СофтИнформ".

Вообще, при создании крупных баз данных должны приниматься во внимание следующие основные факторы:

1. Большой размер базы данных.
2. Состав базы данных исключительно из текстовых данных с одинаковым в большинстве своем набором символов (кириллица), т. е. на одном языке.
3. Необходимость обеспечить высокую скорость разархивации, что, с учетом фактора 1, невозможно, используя распространенные рекурсивные методы сжатия (например, алгоритм Хаффмана).

Этими требованиями руководствовалась и корпорация "СофтИнформ", которая разработала эффективную технологию сжатия данных. Технология обеспечивает быстрое сжатие текста в 6-8 раз, использует линейный метод архивации, т.е. составляется большой словарь, единый для всей базы, а вместо слов в документах фактически хранятся только индексы, ссылающиеся на соответствующие слова из словаря. Это позволяет оперативно прочитать любой фрагмент архива в любой момент времени, т.к. архив не связан древовидной структурой. Кроме того, из вышеописанной характеристики линейного метода следует еще одно важное свойство - высокая надежность хранения информации по сравнению с базой, сжатой рекурсивным методом. Ведь если повредится какая-то часть базы (даже несколько байт), то при рекурсивном сжатии вся информация из файла будет потеряна. Линейный метод лишен этого недостатка. В данном смысле система сжатия текста напоминает алгоритм LZW (Lempel-Ziv-Welch), изобретенный Дж. Зивом и А. Лемпелем и окончательно доработанный Терри А. Велчем в 1984 году.

Напомню, что алгоритм LZW представляет собой алгоритм кодирования последовательностей неодинаковых символов. Возьмем для примера строку "Функция XParameter происходит от "SummaryXParameter". Анализируя эту строку, мы можем видеть, что слово "XParameter" повторяется дважды. В этом слове 10 символов - 80 бит. И если мы сможем заменить это слово в выходном файле, во втором его включении, на ссылку на первое включение, то получим сжатие информации. Если рассматривать входной блок информации размером не более 64К и ограничиться длиной кодируемой строки в 256 символов, то, учитывая байт "флаг", получим, что строка из 80 бит заменяется на 32 бита (8+16+8). Алгоритм LZW как бы "обучается" в процессе сжатия файла. Если существуют повторяющиеся строки в файле, то они будут закодированы в таблицу. Очевидным преимуществом алгоритма является то, что нет необходимости включать таблицу кодировки в сжатый файл.

В то же время алгоритм Хаффмана требует создания дерева кодирования. Первым делом нужно подсчитать частоту вхождения в файл символов из расширенного набора ASCII. Затем создается мнимая компоновка между кодами по убыванию. После этого символы с наименьшей частотой вхождения образуют между собой некое подобие "веток", при этом их частоты складываются и новые ветки образуются уже от следующих двух наименьших частот. Так постепенно дерево "сверху вниз" доходит до корня, при этом получившаяся в корне сумма от частот вхождений двух последних веток равна количеству символов в файле. В получившемся дереве, если двигаться от "корня", на узлах нужно "отмечать" повороты. Поворот налево - это 0. Направо - 1. Так для каждого символа получаем некое битовое обозначение, которое заведомо меньше 8 бит, "занимаемых" символом изначально. Все отлично, но недостаток этого метода заключается в том, что для восстановления первоначального файла мы должны иметь декодирующее дерево, так как деревья будут различными для разных файлов. Следовательно, нужно сохранять дерево вместе с файлом. Для раскодирования отдельного участка файла придется сначала прочитать дерево этого файла, т. е. прочитать файл целиком. Для нашей ситуации это неприемлемо.

Можно сказать, что имеет смысл продумать морфологический механизм архивации, когда, например, однокоренные слова, различающиеся только окончаниями, будут ссылаться на одно и то же слово в словаре, и одновременно существует ссылка на базу данных "Окончания". Данная технология увеличивает степень сжатия, уменьшая размеры словаря. Этот алгоритм сжатия, подобно алгоритму LZW, со временем "обучается", приспосабливаясь к особенностям определенного языка, стиля. Лингвистическая система может с одинаковым успехом применяться на любом языке.

Данная система архивации наиболее эффективна при работе с большими объемами текстовой информации, при базе данных свыше 100 мегабайт она просто незаменима. Тогда достигается коэффициент сжатия в 6-8 раз, что можно назвать просто выдающимся результатом. В то же время система абсолютно бесполезна для сжатия небольших файлов. В этом смысле она, можно сказать, специализирована.

Еще одна важная (и необходимая) особенность рассматриваемой системы - линейный метод архивации, то есть можно прочитать только одну небольшую часть архива, чтобы распознать ее содержание. Это чрезвычайно важно при обновлении базы данных (как известно, обновление БД - довольно частая процедура). Файл обновления очень удобно отправлять по модемной связи. В этом случае мы получаем файл в несколько раз меньший, чем это могло быть, не используй компания свою собственную систему сжатия. В файле хранятся только небольшие кусочки для обновления базы данных и (главное!) самого словаря архива, то есть мы получаем обновление не только без перечитывания (а, значит, и переписывания) всего большого архива, но и даже без перечитывания словаря.

Понятно, что сжатие информации в крупных базах данных - довольно сложная проблема. Однако и ее важности нельзя недооценивать. Общепризнанной технологии еще не изобретено, и вполне возможно, что успех принесут новые, оригинальные подходы.

Вадим МИРКО