Введение к работе
Актуальность темы. Методы сжатия данных применяются для уменьшения объемов информации, хранимой на ЭВМ и передаваемой по линиям связи, т. к. достоверно известно, что подавляющая часть такой информации высокоизбыточна. Особый интерес представляют неискажающис методы сжатия (гарантирующие, что восстановление из сжатого представления данные в точности совпадут с исходными), т. к. обычно — при сжатии текстов, образов исполняемых программ, объектных файлов и других типичных видов данных — искажения недопустимы.
Основные параметры метода сжатия - качество сжатия (отношение длин сжатых и исходных данных), скорость сжатия (объем исходных данных, обрабатываемых в единицу времени) и объем требуемой памяти. При практической реализации имеются жесткие ограничения на объем доступной памяти (не более 20 Мб, для встроенных систем — не более 1 Мб ввиду ограниченного объема ОЗУ) и скорость сжатия (не менее 50 Кб/с). Скорость особенно важна, т. к. пропускная способность даже обычных телефонных линий —- 3-10 Кб/с сжатых данных, по-чтому (с учеїчш коэффициента сжатия) необходимо обрабатывать не менее 10-30 Кб/с исходных данных; типичный объем жесткого диска — 2-ї) Гб, поэтому при скорости сжатия менее 50 Кб/с (180 Мб/с) время резервного копирования превысит 12-24 часов, что не приемлемо.
Наличие таких ограничений на время сжатия и объем памяти существенно сужает круг используемых на практике методов сжатия; в частности, теоретически оптимальные методы сжатия статистическим моделированием цепей Маркова не пригодны для практического использования. С другой стороны, качество метода сжатия должно быть достаточно высоким, чтобы оправдать свое применение, поэтому чересчур простые методы также не используются.
Поскольку быстродействие и объем памяти современных ЭВМ достаточно ограничены по сравнению с объемами хранимой информации и пропускными способностями линий связи, особенно остро стоит проблема построения высокоскоростных систем сжатия данных, обладающих высоким качеством сжатия и требующих небольшого объема оперативной памяти.
Цель диссертационной работы заключается в построении систем неискажающего сжатия данных, обладающих высокой скоростью сжатия при хорошем качестве, как при наличии жестких ограничений на объем требуемой памяти, так и без таковых, допускающих эффективную программную реализацию на традиционных однопроцессорных ЭВМ с побайтовым или пословным доступом к памяти (параллельные и векторные ЭВМ встречаются редко, а область применения аппаратных решений очень узкая).
Научная новизна работы состоит в том, что были предложены, изучены и обоснованы новые методы и алгоритмы сжатия, способы их реализации, новые решения известных проблем:
предложены и исследованы новые методы построения и декодирования канонических кодов Хаффмана; доказано, что эти методы почти оптимальны по скорости и на порядок эффективнее известных при таком же объеме требуемой памяти;
разработаны и изучены новый методы сжатия текстов и гипертекстов на естественных языках (английском, русском, немецком и т. д.); доказано, что они близки к оптимальным;
предложены и изучены новые алгоритмы поиска подстрок в алгоритмах словарного сжатия семейства LZ77 (обладающих высокой скоростью сжатия, приемлемым качеством и требующих мало — 300-500 Кб — оперативной памяти), разработаны новые эффективные варианты таких методов сжатия и предложены новые однопроходные алгоритмы построения оптимальной последовательности кодирования; доказано, что большинство вышеперечисленных методов сжатия близки к оптимальным по всем или почти по всем параметрам, и показано, что при таком же качестве сжатия и меньшем объеме требуемой памяти предложенные методы в несколько раз быстрее известных;
разработана новая методика построения алгоритмов сжатия сортировкой блоков (обладающих высокой скоростью и очень хорошим качеством сжатия, но требующих достаточно больших — 5-20 Мб — объемов оперативной памяти):
- предложены и исследованы новые эффективные методы реализации полной сортировки блоков; доказано, что
они оптимальны в своем классе, и показано, что при
таком же объеме требуемой памяти по скорости1 (130-
150 Кб/с) они-превосходят (иногда в тысячи раз) ис
пользуемые и настоящее время эвристические методы;
— разработан и изучен новый класс алгоритмов сжатия
частичной сортировкой блоков и доказано, что скорость
таким методов сжатия (250 300 Кб/с) вдвое выше, чем
при полной сортировке, и не зависит от сжимаемых дан
ных (что является достаточно редким и очень важным
свойством), а качество сжатия незначительно хуже сжа
тия полной сортировкой блоков;
-- разработаны и исследованы новые методы кодирования
выхода преобразования сортировкой блока (полной или
частичной) и предложены эффективные методы их ре
ализации; доказано, что по скорости такие методы ко
дирования оптимальны, и показано, что [в сочетании с
преобразованием сортировкой блоков] по качеству сжа
тия они не уступают наилучшим известным методам
сжатия (будучи в 5-20 раз быстрее), а по скорости —
алгоритмам семейства LZ77 (превосходя последние по
качеству в 1.3 1.7 раза).
Практическая ценность работы подтверждается фактом их
использования рядом коммерческих компаний, занимающихся
созданием программного обеспечения самого различного про
филя от систем автоматизации машиностроения до разра
ботки сильно оптимизирующих компиляторов для встроенных
систем (ProPro Group Inc., XDS Ltd., АЇР NL и др.).
Разработанные и реализованные А.В. Калачом системы сжатия исполняемых файлов (PRSEXE и UXECE) получили широкое международное признание; согласно регулярно проводимым канадской группой ACT тестам, они уверенно занимают лидирующее положение среди более десяти аналогичных продуктов, разработанных известными производителями программного обеспечения Microsoft, Symantec и др.
Апробация работы и публикации. Результаты работы неоднократно докладывались и обсуждались на объединенном се-
Скорость сжатия указана для процессора, исполняющего 100 млн. команд типа регистр-регистр в секунду.
минаре ИСИ СО РАН и НГУ «Системное программирование», семинарах Новосибирского института связи (СибГАТИ) и Института математики СО РАН с участием ведущих специалистов. По теме диссертации опубликовано семь печатных работ (все — без соавторов).
Структура и объем работы. Диссертационная работа состоит из пяти частей (12 глав) и списка литературы из 203 наименований. Общий объем работы — 184 страницы. К работе прилагаются акты внедрения разработанных и реализованным автором систем сжатия.
