автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Эффективные алгоритмы неискажающего сжатия текстовой информации

российская академия наук

СИБИРСКОЕ ОТДЕЛЕНИЕ

Р ИНСТИТУТ СИСТЕМ ИНФОРМАТИКИ П 0 иЦ им. А. II. Ершова

Иа правах рукописи

Кадач Андрей Викторович

Эффективные алгоритмы неискажающего сжатия текстовой информации

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ

диссертации иа соискание ученой степени кандидата физико-математических наук

Новосибирск 1998

Работа выполнена в Институте систем информатики имени А.П. Ершова Сибирского отделения Российской академии наук (ИСИ СО РАН).

Научный руководитель: доктор физико-математических наук,

профессор И.В. Поттосин

Официальные оппоненты: академик МАИ, доктор технических нау

профессор Б.Я. Рябко

кандидат физико-математических наук, старший научный сотрудник П.А. Ким

Ведущая организация: Институт математики СО РАН

Защита состоится «» февраля 1998 г. в 14 час. 30 мин. на заседании специализированного совета К0003.93.01 в Институте систем информатики им. А.II. Ершова Сибирского отделения РАН по адресу: 630090, Новосибирск, пр. ак. Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале библиотеки ВЦ СО РАН (пр. ак. Лаврентьева, 6).

Автореферат разослан « » января 1998 г.

Ученый секретарь специализированного совета К0003.93.01

к.ф.-м.н. А ' М.А. Бульонков

Общая характеристика работы

Актуальность- темы.- Методы сжатия данных применяются для уменьшения объемов информации, хранимой на ЭВМ и передаваемой по линиям связи, т. к. достоверно известно, что подавляющая часть такой информации высокоизбыточна. Особый интерес представляют неискажающис методы сжатия (гарантирующие, что восстановление из сжатого представления данные в т очности совпадут с исходными), т. к. обычно — при сжатии текстов, образов исполняемых программ, объектных файлов и других типичных видов данных — искажения недопустимы.

Основные параметры метода сжатия - качество сжатия (отношение длин сжатых и исходных данных), скорость сжатия (объем исходных данных, обрабатываемых в единицу времени) и объем требуемой памяти. При практической реализации имеются жесткие ограничения на объем доступной памяти (не более 20 Мб, для встроенных систем — не более 1 Мб ввиду ограниченного объема ОЗУ) и скорость сжатия (не менее 50 Кб/с). Скорость особенно важна, т. к. пропускная способность даже обычных телефонных линий — 3-10 Кб/с сжатых данных, поэтому (с уче том коэффициента сжатия) необходимо обрабатывать не менее 10-30 Кб/с исходных данных; типичный объем жесткого диска — 2-5 Гб. поэтому при скорости сжатия менее 50 Кб/с (180 Мб/с) время резервного копирования превысит 1224 часов, что не приемлемо.

Наличие таких ограничений на время сжатия и объем памяти существенно сужает круг используемых на практике методов сжатия; в частности, теоретически оптимальные методы сжатия статистическим моделированием цепей Маркова не пригодны для практического использования. С другой стороны, качество метода сжатия должно быть достаточно высоким, чтобы оправдать свое применение, поэтому чересчур простые методы также не используются.

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

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

Научная новизна работы состоит в том, что были предложены, изучены и обоснованы новые методы и алгоритмы сжатия, способы их реализации, новые решения известных проблем:

• предложены и исследованы новые методы построения и декодирования канонических кодов Хаффмана; доказано, что эти методы почти оптимальны по скорости и на порядок эффективнее известных при таком же объеме требуемой памяти;

• разработаны и изучены новый методы сжатия текстов и гипертекстов на естественных языках (английском, русском, немецком и т. д.); доказано, что они близки к оптимальным;

• предложены и изучены новые алгоритмы поиска подстрок в алгоритмах словарного сжатия семейства 1^77 (обладающих высокой скоростью сжатия, приемлемым качеством и требующих мало — 300-500 Кб — оперативной памяти), разработаны новые эффективные варианты таких методов сжатия и предложены новые однопроходные алгоритмы построения оптимальной последовательности кодирования; доказано, что большинство вышеперечисленных методов сжатия близки к оптимальным по всем или почти по всем параметрам, и показано, что при таком же качестве сжатия и меньшем объеме требуемой памяти предложенные методы в несколько раз быстрее известных;

• разработана новая методика построения алгоритмов сжатия сортировкой блоков (обладающих высокой скоростью и очень хорошим качеством сжатия, но требующих достаточно больших — 5-20 Мб — объемов оперативной памяти):

- предложены и исследованы новые эффективные методы реализации полной сортировки блоков; доказано, что

они оптимальны в своем классе, и показано, что при таком же объеме требуемой памяти по скорости1 (ISOISO Кб/с) они-превосходят (иногда в тысячи раз) используемые в настоящее время эвристические методы; — разработан и изучен новый класс алгоритмов сжатия частичной сортировкой блоков и доказано, что скорость таким методов сжатия ('250 300 Кб/с) вдвое выше, чем при полной сортировке, и не зависит от сжимаемых данных (что является достаточно редким и очень важным свойством), а качество сжатия незначительно хуже сжатия полной сортировкой блоков; ~ разработаны и исследованы новые методы кодирования выхода преобразования сортировкой блока (полной или частичной) и предложены эффективные методы их реализации; доказано, что по скорости такие методы кодирования оптимальны, и показано, что [в сочетании с преобразованием сортировкой блоков] по качеству сжатия они не уступают наилучшим известным методам сжатия (будучи в 5-20 раз быстрее), а по скорости — алгоритмам семейства LZ77 (превосходя последние по качеству в 1.3 1.7 раза).

Практическая ценность работы подтверждается фактом их использования рядом коммерческих компаний, занимающихся созданием программного обеспечения самого различного профиля от систем автоматизации машиностроения до разработки сильно оптимизирующих компиляторов для встроенных систем (ProPro Group inc., XDS Ltd., AIP NL и др.).

Разработанные и реализованные A.B. Кадачом системы сжатия исполняемых файлов (PRSEXE и UXECE) получили широкое международное признание; согласно регулярно проводимым канадской группой ACT тестам, они уверенно занимают лидирующее положение среди более десяти аналогичных продуктов, разработанных известными производителями программного обеспечения .Microsoft, Symantec и др.

Апробация работы и публикации. Результаты работы неоднократно докладывались и обсуждались на объединенном се-

1 Скорость сжатия указана для процессора, исполняющего 100 млн. команд типа регистр-регистр в секунду.

минаре ИСИ СО РАН и НГУ «Системное программирование», семинарах Новосибирского института связи (СибГАТИ) и Института математики СО РАН с участием ведущих специалистов. По теме диссертации опубликовано семь печатных работ (все — без соавторов).

Структура и объем работы. Диссертационная работа состоит из пяти частей (12 глав) и списка литературы из 203 наименований. Общий объем работы — 184 страницы. К работе прилагаются акты внедрения разработанных и реализованным автором систем сжатия.

Содержание работы

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

Вторая часть работы состоит из главы 3 и посвящена префиксным кодам, которые лидируют по скорости кодирования и декодирования (но не являются наилучшими по качеству); особое внимание уделено кодам Хаффмана, оптимальным по качеству сжатия среди префиксных кодов.

Кодом называется отображение / : £ —» {0,1}*, а кодовым словом символа2 а £ Е — значение /(о). Код называется префиксным, если ни одно кодовое слово не является префиксом (полным началом) какого-либо другого кодового слова. Код называется полным, если из того, что битовая строка 5 € {0,1}* — префикс некоторого кодового слова, отличный от него, следует, что строки «0 и «1 — также префиксы некоторых кодовых слов. Можно показать, что для каждого однозначно-декодируемого кода /' существует псудлиняющий полный префиксный код /, т. е.

2 В дальнейшем предполагается, что £ — алфавит конечной мощности, что позволяет занумеровать все символы алфавита и задать на них полный порядок, который индуцирует естественный полный порядок на строках символов алфавита

такой, что |/(а)| < |/'(а)1 £ поэтому можно ограничиться изучением только полных префиксных кодов, каждому из которых однозначно соответствует полное кодовое дерево — двоичное дерево, левые дуги которого помечены нулями, правые — единицами, листья символами S, а каждая промежуточная вершина имеет ровно двух потомков, причем код символа о является конкатенацией (слева направо) пометок дуг на пути от корня к листу, помеченному а.

Если известны вероятности р(а) > 0 появления символов Е, то возникает задача построение оптимального кода /, средняя стоимость кодирования которого минимальна:

C(P,f) = £>(«№)! -min; »es

известно, что С(р, /) не меньше энтропии

£(Р) = log2p(a);

«es

'R(p) = C(]>. f) — £(;■>) > 0 называется избыточностью кода /.

Задача построения оптимального кода была решена Хафф-маном в 1952 г. следующим образом: создадим ¡ü¡ деревьев, состоящих из одной вершины, помеченной очередным символом, и припишем каждому дереву вес, равный вероятности появления соответствующего символа. Пока существует более одного дерева, будем сливать два дерева с минимальным весом в одно (в качестве потомков новой вершины), которому припишем вес, равный сумме весов его поддеревьев. Оставшееся дерево и будет деревом Хаффмана. По построению, соответствующий ему код будет полним и префиксным; можно показать, что его избыточность меньше единицы, а средняя стоимость кодирования — минимальна.

Поскольку на практике вероятности появления символов заранее не известны, требуется предварительно просмотреть сообщение длины .V и подсчитать п(а) количество появлений символа гу в сообщении:

понятно, что при таком подходе закодированное сообщение необходимо предварить информацией об использованном коде.

Заметим, что на практике длина кодируемого сообщения N заведомо ограничена сверху (хотя бы потому, что суммарный объем всех существующих носителей информации не превышает 2128 битов, так что N < 2128); это позволяет существенно упростить и ускорить ряд алгоритмов.

В п. 3.1 приводятся малоизвестные оценки максимальной избыточности кода Хаффмана, показывающие, что при соблюдении определенных условий избыточность кода Хаффмана не превышает 1-2%, чего вполне достаточно для практических целей. Там же приводятся полученные автором доказательства некоторых специфических свойств кодов Хаффмана (соотношение максимальной длины кодового слова и длины кодируемого сообщения, длины кодового слова и вероятности появления символа и т. д.), которые используются в дальнейшем.

В п. 3.2 описан способ вычисления стоимости кодирования ^п(а)|/(а)| не более чем за 3|£| сложений3 и не требующий умножений вообще, что существенно при реализации для процессоров, не имеющих команды умножения (например, младших моделях ШЯС-процессоров); вычисление стоимости кодирования необходимо, чтобы определить, является ли кодирование сжимающим (с учетом стоимости передачи собственно кода).

В п. 3.3 доказано, что если символы отсортированы по количеству появлений, то код Хаффмана может быть построен за линейное время, тогда как традиционным методам требуется 0(|Е|^|Е|) операций. Таким образом, задача построения кода Хаффмана сводится к задаче сортировки целых ключей 7г(а), где п(а) — количество появлений символа а в кодируемом тексте. В 1994-1996 гг. Андерссоном и Нильссоном был предложен ряд алгоритмов целочисленной сортировки ключей к, £ N таких, что ¿1 6 [0,2Ш), где ад — ширина машинного слова в битах, за О(п^^п) операций, где п — количество ключей; это заметно лучше, чем 0(п1о§?г) в общем случае. Их алгоритм чересчур сложен и на практике мало эффективен; автором был предложен алгоритм сортировки за 0(|£|)+0(1) операций при условии, что п(а) £ [О, 2Ш). Таким образом, построение кода Хаф-

3 Отметим, что все предложенные автором алгоритмы не используют ни умножений, ни делений.

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

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

Третья часть работы посвящена словарным методам сжатия данных семейства Лемпела Зива, которые заменяют подстроки кодируемой строки ссылками в словарь на идентичные вхождения. Наиболее эффективны алгоритмы семейства LZ77 со «скользящим» окном ширины Ц\ заменяющие подстроки парой < (\р >, где ( — длина предыдущего идентичного вхождения подстроки, а р < 11' - смещение до ее начала, так что кодом строки является последовательность указателей и литералов; например, ЬХ77-кодо.м строки ааааЬ будет а < 3, 1 > Ь или аа < 2,2 > Ь и т. д.

В главе 4 предложен способ кодирования текстов на естественных языках (русском, английском, немецком и т. д.) заменой слов и последовательностей разделителей (пробелов, запятых, точек и т. д.) их номерами в словаре. Используя известный закон Ципфа о том, что вероятность появления г-го по частоте использования слова обратно пропорциональна г, доказано. что стоимость оптимального кодирования не меньше

£(,У) = !^ + 1оё21о82Л'-5

битов на слово, где N — количество различных использованных в тексте слов (обычно 10-40 тыс., на очень длинных тек-

стах — 2-5 Гб — до 1 млн.), а 8 е [0.82,0.96] при N > 2048. Для кодирования номеров слов было предложено отсортировать все слова по частоте появления и разбить на \l0g2N] групп, так что слово с номером п € [2т, 2т+1 — 1] кодируется парой < т, п — 2т >, причем первый элемент кодируется по Хаффману, а второй — равномерно п битами. Было доказано, что избыточность такого кодирования (с учетом избыточности кода Хаффмана) не превышает 2%. Автором было предложено использовать единый словарь для всех лексем (и слов, и разделителей) и вообще не кодировать самую часто используемую лексему (как правило, одиночный пробел); если при декодировании встречаются две идущие подряд лексемы одного класса, то между ними нужно вставить удаленную. Был также предложен эффективный метод сжатия словаря, способы построения модифицируемых словарей, сжатия изменяемых текстов, хранения словаря в сжатом виде и во время декодирования и т. д. Показано, что, в отличие от известных, предложенный метод кодирования допускает доступ к сжатых данным в почти произвольном порядке (что важно для работы с гипертекстами) и обладает в 1.5-2 раза лучшим качеством сжатия.

В главе 5 изучены методы построения оптимального по стоимости Ь277-кода: т. к. каждая строка может быть закодирована многими способами, возникает проблема построения 1^77-кода минимальной длины. При прямолинейном кодировании строка просматривается слева направо, и если в текущей позиции г в окне ширины Ш существует подстрока, являющаяся началом незакодированной части, порождается указатель < £,р > и кодировщик сдвигается на £ символов (если таких подстрок несколько, то выбирается самая правая и наиболее длинная подстрока); если же подстроки не найдено, то порождается литерал (текущий символ) и кодировщик смещается на один символ вправо. Прямолинейное кодирование не оптимально; длина такого кода может быть в раз больше оптимальной (Р — стоимость передачи указателя, а С — литерала). Для построения оптимального 1^77-кода можно применить известный алгоритм динамического программирования Миллера — Вег-мана, что потребует 3|5| слов дополнительной памяти, где ]5| — длина кодируемой строки; на практике это не приемлемо.

Кроме того, для алгоритма Миллера — Вегмана необходимо для каждой позиции осуществить поиск подстроки, тогда как при прямолинейном кодировании поиск осуществляется гораздо реже, поскольку при кодировании указателя поиск подстроки в следующих — 1) позициях не требуется. Таким образом, алгоритм Миллера -- Вегмана в /аие ~ 4 6 раз медленнее прямолинейного и поэтому никогда не используется; вместо этого применяются всевозможные эвристики. Автором были разработаны и обоснованы новые однопроходные методы построение почти оптимального 1^77-кода, требующие 5М слов дополнительной памяти при относительной избыточности менее

(при М = кодирование оптимально). Показано, что они минимизируют количество требуемых поисков подстрок и линейны по количеству неоднозначностей кодирования, а их скорость (с учетом количества необходимых поисков подстрок) близка к скорости прямолинейного кодирования. Более того, показано, что все используемые методы кодирования и эвристики — частные случаи предложенных при Р — 2С и М = 0,1,2. Важным свойством предложенных алгоритмов является, что при каждом поиске подстрок заранее известна минимальная длина интересующей подстроки (тт > т е- процедура поиска может пропускать совпадающие подстроки длины меньше (тгп.

В главе 6 описаны предложенные автором эффективные методы поиска подстрок и новые варианты [/¿77. Поскольку поиск осуществляется относительно редко, асимптотически оптимальные методы поиска подстрок, использующие деревья суффиксов. не являются наилучшими для 1^77: процесс вставки новой подстроки не отличается от поиска; удаление подстрок, не попадающих в окно, чрезвычайно нетривиально; вычислительная сложность алгоритма и объем требуемой памяти очень большие; средняя производительность очень низкая. Вместо этого было предложено осуществлять поиск прямым перебором хэш-списка подстрок с одинаковым значением хэш-суммы, построенной по первым п — яа 3 -г 4 символам;

доказано, что для источников Берпулли в среднем требуется перебирать не более \¥0" подстрок, где 0 = (обычно в « 0.05 -г 0.075), поэтому при ограниченной ширине окна (IV < 216 218), обеспечивающей достаточно хорошее качество

сжатия при относительно небольшом объеме требуемой памяти, требуется перебирать не более 16-64 подстрок. Для уменьшения количества коллизий необходимо уметь строить хэш-функции, близкие к идеальным; было показано, что описанный автором табличный способ вычисления хэш-функций по качеству хэширования практически не уступает оптимальному полиномиальному хэшированию, а по скорости превосходит все известные. Чтобы избежать полного сравнения всех подстрок хэш-списка с образцом, было предложено воспользоваться тем, что минимальная длина интересующей подстроки или длина ранее найденной подстроки известна, и сравнивать строки с конца — сначала £-е символы, потом (£ — 1)-е и т. д.; показано, что если текущая строка является неудлиняющей (т. е. длина общего начала меньше £), то с вероятностью 95-98% последние два символа различны; если же они совпадают, то с вероятностью 80-90% длина общего начала текущей подстроки хэш-списка и незакодированной части сообщения длиннее найденного ранее. С целью гарантировать линейность времени поиска было предложено принудительно ограничить глубину поиска О подстроками, и показано, что при И и 50 -г-150 такое ограничение практически не влияет на качество сжатия, ускоряя его в 1.5-2 раза. Наконец, был предложен новый вариант 1^77 со «скользящим» окном — 1^77 с «прыгающим» окном, который при таком же качестве сжатия требует вдвое меньше памяти и в 1.5-2 раза быстрее. Таким образом, применение разработанных методов поиска подстрок позволило ускорить сжатие в 25 раз и вдвое уменьшить объем требуемой памяти.

В главе 7 описаны разработанные автором эффективные методы записи 1^77-кода с использованием кодов Хаффмана; т. к. вероятности появления литералов, длин и смещений обладают ярко выраженной неравномерностью, оптимальное кодирование обычно на 10-25% лучше равномерного, а поскольку диапазоны возможных значений длин и смещений очень велики, реализация такого кодирования не тривиальна. Было показано, что групповые и шаговые коды, аналогичные использованным для кодирования текстов на естественных языках, почти оптимальны: их избыточность не превышает 2-3%. Таким образом, применение таких кодов позволило улучшить качество сжа-

тия на 10-20% и одновременно избежать серьезных проблем, связанных с необходимостью кодирования очень больших алфавитов, содержащих сотни тысяч-символов._____

В четБехэтой части работы описана разработанная автором новая методика построения систем сжатия данных, основанная на преобразовании Барроуза — Уилера данных сортировкой блоков. Имея кодируемую строку 5 € длины N, образуем матрицу .1/, составленную из всех А' циклических вращений ¿> на 0, 1, ..., (Аг — 1) символов; отсортировав строки М в лексикографическом порядке (индуцированном естественным полным порядком на Е), получим матрицу М'. Утверждается, что если известен последний столбец Ь матрицы М' и номер в М' исходной строки, то ее можно восстановить за 0(Аг) операций с использованием 0(№) слов дополнительной памяти. Поскольку длина общего начала двух соседних строк отсортированной матрицы М', скорее всего, значительна, предшествующие символы с высокой вероятностью совпадают, а т. к. строки М' — циклические вращения 5, то символы последнего столбца Ь предшествуют первым символам строк М'. Таким образом, Ь обладает ярко выраженной избыточностью, выражающейся в наличии большого количества серий повторов одного и того же символа, и может быть эффективно закодирована достаточно простыми методами.

Матрица М Матрица М'

а ъ с ь с а Ъ а ь с а Ь 0 а Ь а Ъ с а Ь . а Ь с Ь с

Ь с Ъ с а Ь а Ь с а Ъ а 1 а Ь с а Ь . а Ъ с Ь с а Ъ

с Ъ с а Ь а Ъ с а Ь а Ъ 2 ==> а Ь с Ъ с а Ь а Ъ с а Ъ

Ъ с а ь а Ь с а Ъ а Ъ с 3 а Ъ . а Ъ с Ь с а Ъ а Ъ с

а Ъ а ъ с а Ъ . а ъ с Ъ с 4 Ъ а Ъ с а Ь . а Ъ с Ъ с а

Ъ а Ъ с а Ь . а Ь с Ь с а 5 Ъ с а Ъ а Ь с а Ъ а Ь с

а Ь с а Ъ . а Ь с Ъ С а Ъ 6 ь с а Ь . а Ъ с ъ с а Ъ а

Ь с а Ь . а Ь с Ь с а Ъ а 7 ь с Ъ с а Ь а Ь с а Ъ . а

с а Ъ а Ь с Ь с а Ъ а Ъ 8 с а Ъ . а Ь с Ь с а Ь а Ъ

а Ъ а Ь с Ь с а Ь а Ъ с 9 с Ь с а Ь а Ь с а Ъ а Ъ

а Ъ с Ь с а Ь а Ъ с а Ъ 10 а Ъ с Ь с а Ь а ь с а Ъ

В главе 8 описывается разработанный автором алгоритм блочной сортировки матрицы циклических вращений М, который является центральной частью одноименного метода сжа-

тил данных и во многом (на 80-90%) определяет скорость сжатия и объем требуемой памяти. Известные асимптотически оптимальные непрямые методы решения этой задачи (основанные на применении деревьев суффиксов) требуют слишком много оперативной памяти — 8N-10N слов (32-64 Мб при N = 1-^-2 Мб) —- и обладают очень низкой средней производительностью, поэтому используются всевозможные эвристические методы сортировки, требующие (2N + |£|) слов памяти и обладающие высокой средней скоростью (0(N log log N) операций); к сожалению, в наихудшем случае время сортировки увеличивается в тысячи раз, достигая 0(N\/N log N). Таким образом, известные методы сортировки не пригодны для практического использования. Алгоритм, разработанный автором, требует (2N -f |£|) слов памяти; доказано, он оптимален в классе алгоритмов сортировки удвоением, поэтому среднее время сортировки равно 0(iVloglog N) и в наихудшем случае не превышает 0(N log N), оставаясь приемлемым. Показано, что реальная производительность этого алгоритма лучше всех известных.

В главе 9 автором предложен новый класс алгоритмов сжатия частичной сортировкой блоков. Вместо того, чтобы полностью сортировать исходную матрицу М, отсортируем ее по первым F символам устойчивым образом, что может быть сделано с помощью известного алгоритма сортировки расстановкой за 0((N -f |£|)F) операций с использованием (2N + |£|) слов дополнительной памяти; важно отметить, что время такой сортировки не зависит от сортируемых данных. Автором доказано, что если сортировка устойчива, т. е. сохраняет исходный порядок следования строк М при совпадении первых F символов, преобразование частичной сортировкой блоков, равно как и полной, обратимо. Доказано, что предложенные способы реализации обратного преобразования восстанавливают исходные данные за C>(|£| + iVlogF) операций при Bp ф 0 и за 0(N + Y.) при Bp = 0 с использованием (2N+ |£|) слов дополнительной памяти. Доказано, что преобразование Барроуза — Уилера является частным случаем преобразования частичной сортировкой. Показано, что при F = 4 скорость такого сжатия вдвое выше, чем при полной сортировке, а качество хуже лишь на 1-5%.

В главе 10 предложены новые методы кодирования резуль-

татов преобразования сортировкой блоков (полной или частичной) и эффективные способ!,i их реализации. Поскольку кодируемая последовательность содержит много повторений символов. иногда перемежаемых другими символами (например, типичная последовательность выглядит как aaaabaababbbabbb-beb), применяется локально-адаптивное, кодирование. Было показано, что наилучшие результаты получаются использованием Inverted Frequency Coding (IF-преобразования): просматривая строк}1, при обнаружении символа а будем генерировать число, равное количеству символов, лексикографически больших а, ртделяющих текущее и предыдущее вхождение а; затем это проделывается для следующего за су символа и т. д.; например, строка aabaebba будет преобразована в (а : 0013,6 : 010, с : 0); полученная последовательность целых сжимается с применением кодов Хаффмана, групповых и шаговых кодов и т. п. Так как и при кодировании, и при декодировании требуется |£| проходов по строке, то при |£| > 100 время IF-преобразования очень значительно и равняется 1j). Автором был предложен алгоритм прямого и обратного IF-преобразования с временной сложностью 0(.Y log которые быстрое на порядок. Кроме того, были предложены эффективные способы построения моделей высоких порядков (4-5-го) для кодирования результата 1 К-преобразования. Было показало, что при использовании 5-50 Кб дополнительной памяти скорость такого кодирования очень высокая, а качество на 10-25% выше, чем у применявшихся ранее методов кодирования, и не уступает качеству сжатия лучших известных методов статистического моделирования.

Пятая часть работы — заключительная и состоит из двух г л а в

В главе 11 приводятся результаты экспериментов по сжатию данных из стандартных наборов тестов Calgary и Canterbury Data Compression Corpus(es). Методы сжатия, разработанные и реализованные автором, представлены программой PRS: при опциях L1-L7 используется LZ77 с «прыгающим» окном в 3264 Кб при различной максимальной глубине перебора и различных методах построения ЬХ77-кода (об ьем требуемой памяти — 300 Кб), при опции F — сжатие полной сортировкой блоков размером в 1 Мб, а при Р4 и Р8 — частичной сортировкой по пер-

вым 4 и 8 символам (объем требуемой памяти — 9 Мб). Кроме того, рассмотрены наиболее эффективные современные архиваторы, реализующие LZ77 со «скользящим» окном в 32-64 Кб и требующие 300—500 Кб памяти (PKZIP 2.04G, RAR 2.02, ARJ 2.41, LHA4), алгоритмы сжатия сортировкой блоков размером в 1 Мб, требующие 6-10 Мб памяти, (BRED, BRED3, XI 0.94L -аш7), методы статистического моделирования, требующие 16-20 Мб памяти: АСВ (АСВ 1.23С), DMC (DMC1 в авторской реализации, коротая вдвое быстрее оригинальной версии при прочих равных параметрах), PPM (XI 0.94L -ашЗ и -am4, RKIVE 1.4, НА 0.999С). Из приведенного сравнения видно, что авторская реализация LZ77 при таком же или лучшем качестве сжатия в 2-5 раз быстрее и требует вдвое меньше памяти (300 Кб), а разработанные методы сжатия сортировкой блоков при таком же или меньшем объеме используемой памяти (9 Мб) превосходят другие реализации сжатия сортировкой блоков по качеству на 10-20% и не уступают по скорости, опережая по скорости методы сжатия статистическим моделированием 4-20 раз на текстовых данных и в 20-30 раз на двоичных при таком же и часто лучшем качестве сжатия.

В таблице на стр. 17 приведены результаты сжатия файлов bookl и book2 из Calgary Data Compression Corpus. Тесты проводились на IBM PC с процессором Intel Pentium при тактовой частотой 100 МГц, 32 Мб оперативной памяти, под операционной системой Microsoft Windows 95. Время сжатия определялось с точностью до 0.001 с и усреднялось по И запускам; наихудшее время не учитывалось.

В главе 12 перечисляются основные результаты работы.

4 ЬНА заметно уступает другим рассмотренным архиваторам по всем параметрам, т. к. это единственная [из рассмотренных] реализация \Л77 со «скользящим» окном [всего] в 8 Кб, использующая для поиска подстрок дерево суффиксов. Этот пример наглядно показывает, что асимптотически оптимальные алгоритмы — не всегда наилучшие на практике.

Результаты сжатия файлов из Calgary Corpus

bookl (768771 байтов) Ьоок2 (610856 байтов)

Архиватор и опции Время. с Длина сжатых данных, байтов Л рхи-ватор и опции Время, с Длина сжатых данных, байтов

prs Р8 4.648 219905 prs Р8 3.480 152616

prs F 5.753 219708 prs F 4.450 152465

xl ат4!9 18.265 219688 xl am419 13.815 152539

xl атпЗШ 19.250 219821 xl ат319 14.500 152832

rkive -mt 29.880 219672 rkive -mt 19.880 149881

rkive -mtx 48.610 219913 rkive -mtx 32.300 149682

prs P4 2.896 227652 acb b 51.250 150591

acb b 86.830 226609 acb u 82.280 149743

acb u 142.150 224525 prs P4 2.181 158853

dmcl с 9.650 235619 ha a2 13.210 163566

ba a2 17.245 235764 rkive -mb 15.190 164570

ach В 40.200 241260 acb В 24.500 159133

bred:) -All 5.355 24997т bred3 -Alf 3.827 167255

xl аш7 7.413 250121 xl am7 5.313 167422

bred -Ml 7.633 250086 bred -Ml 5.492 167387

rkive -mb 23.780 252317 drnc 1 с 7.507 167244

prs 1/1 3.947 304737 prs L4 2.603 200965

prs L5 5.013 301107 prs L5 3.310 198574

prs L6 5.945 299393 prs Lö 3.928 197589

prs L7 6.960 296524 prs L7 4.482 195879

rar -шЗ 7.377 305906 rar -m3 4.712 199440

rar -mi) 14.115 301298 rar -rnö 8.183 196803

prs LI г" 2.011 330325 prs LI 1.407 220968

prs L2 2.794 314942 prs L2 1.884 208465

prs L3 3.327 311627 prs L3 2.270 206029

pkzip -en 4.020 316107 pkzip -en 2.547 209169

rar -ni2 4.132 319837 rar -iu2 2.808 208902

arj -ш2 5.315 322381 pkzip -ex 3.990 206621

pkzip -ex 6.015 312598 arj -ш2 3.397 212659

arj -ml 7.890 319166 arj -ml 4.756 210431

1ha а 8.970 339107 1ha а 6.753 228475

Основные результаты

1. Разработаны, изучены и обоснованы новые методы построения и декодирования кодов Хаффмана, которые в 3-6 раз быстрее известных алгоритмов.

2. Предложены и обоснованы новые алгоритмы сжатия текстов на естественных языках, которые в 5--50 раз быстрее известных при лучшем в 1.5-2 раза качестве сжатия.

3. Разработаны, исследованы и обоснованы новые варианты алгоритма \IL77, новые методы управления поиском, новые способы реализации поиска подстрок для 1^77-схем со «скользящим» окном, применение которых позволило в 25 раз увеличить скорость сжатия (до 250-450 Кб/с) и на 3-5% — качество, при таком же и часто меньшем объеме требуемой памяти (300 Кб при ширине окна 64 Кб).

4. Разработана новая методика сжатия данных сортировкой блоков:

• предложены, изучены и обоснованы алгоритмы сжатия полной сортировкой блоков, которые по средней производительности (130-150 Кб/с.) превосходят почти все другие известные реализации (при таком же объеме требуемой памяти), в отличие от них обеспечивая приемлемую скорость сжатия и в наихудшем случае, при лучшем на 15-20% качестве, не уступающем качеству сжатия методов статистического моделирования;

• разработан и изучен новый класс алгоритмов сжатия частичной сортировкой блоков, которые скорости сжатия (250-300 Кб/с) вдвое опережают алгоритмы сжатия полной сортировкой блоков и часто быстрее алгоритмов семейства Ь277] показано, что скорость такого сжатия не зависит от сжимаемых данных, а качество лишь на 15% хуже, чем при полной сортировке, и в 1.3-1.7 раза лучше, чем у \ЛП1.

Таким образом, разработанные методы сжатия являются наилучшими по всем параметрам как среди требующих очень небольшого объема памяти алгоритмов (словарного сжатия), так и среди более ресурсоемких (сжатия сортировкой блоков и статистическим моделированием).

Публикации по теме диссертации

1. Кадач A.B. Оптимизация качества сжатия в LZ77-cxeMax // В сб. «Средства и инструменты окружений программирования». — Новосибирск, 1995. -- С. 127-142.

2. Кадач A.B. Поиск подстрок в LZ77-cxeMax // В сб. «Средства и инструменты окружений программирования». — Новосибирск, 1995. ■ — С. 143-160.

1. Кадач A.B. Эффективные алгоритмы нгискажающего сжатия данных сортировкой блоков. Ч. I: Преобразование Барроуза -- Уилера и его модификации. — Новосибирск, 1997. — 43 с. — (Преир. / Сиб. отд-ние РАН; Институт систем информатики им. А.П. Ершова; N 42/1).

4. Кадач A.B. Эффективные алгоритмы нсискажающгго сжатия данных сортировкой блоков. Ч. II: Кодирование выхода преобразования Барроуза — Уилера. — Новосибирск, 1997. — 39 с. — (Препр. / Сиб. отд-ние РАН; Институт систем информатики им. А.П. Ершова; N 42/2).

5. Кадач A.B. Эффективные методы создания и передачи префиксных кодов. — Новосибирск, 1997. — 27 с. — (Препр. / Сиб. отд-ние РАН; Институт систем информатики им. А.П. Ершова; N 44).

S. Кадач A.B. Свойства кодов Хаффмана и эффективные алгоритмы декодирования префиксных кодов. — Новосибирск, 1997. — 44 с. — (Препр. / Сиб огд-нис РАИ; Институт систем информатики им. А.П. Ершова:

7 Кадач A.B. Сжатие текстов и гипертекстов // Программирование. —

N 45)

1997 -- X 4. С. 47-57.

Подписано в печать 29.12.1997 Объем 1.1 Формат бумаги 60x84 1/16

Объем 1.1 уч.-изд.л., 1.2 п.л.

Тираж 100 экз.

Отпечатано на ризографе «AL Group» 330090, г. Новосибирск, пр. ак. Лаврентьева, 3.