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

003449340

На правое рукописи

Елхов Алексей Викторович

Методика оперативного сжатия документов формата XML на основе декомпозиции иерархической модели данных

05 13 17 — Теоретические основы информатики

АВТОРЕФЕРАТ

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

1 6 0 KT 2008

Москва 2008

003449940

Работа выполнена в Московском государственном университете печати на кафедре прикладной математики и моделирования систем

Научный руководитель

доктор технических наук, доцент Е. В. Никульчев

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

А. Н. Пылькин

кандидат технических наук А. В. Челпанов

Ведущая организация

МГТУ «Станкин»

Защита состоится «06» ноября 2008 г в 1600 на заседании диссертационного совета Д 212 147 03 в Московском государственном университете печати по адресу Москва, ул Прянишникова, 2А

С диссертацией можно ознакомиться в библиотеке МГУП

Автореферат разослан «04» октября 2008 г

Ученый секретарь диссертационного совета д т н, профессор

В Н Агеев

Общая характеристика диссертационной работы

Актуальность Документ формата XML представляет собой набор слабоструктурированных данных, описанных средствами языка XML С момента своего появления в 1998 году этот язык получил распространение благодаря своим основным преимуществам адаптивности, расширяемости, легкости в обработке и гибкости при публикации неоднородных данных В настоящее время создано и продолжает создаваться большое количество спецификаций XML, согласованных различными профессиональными сообществами Известны версии шаблонов и схем для применения в полиграфии и издательском деле (в частности, широко распространенный формат JDF), электронных СМИ (например, RSS), библиографии, географии, химии, астрономии, истории и др

После того как в 2006 году формат OpenDocument, основанный на XML, был принят в качестве международного стандарта ISO 26300, он стал базовым форматом документов для большинства свободно распространяемых офисных программных продуктов, главным образом разработанных для Unix-систем Кроме того, корпорация Microsoft в своем продукте Office, начиная с версии 2007, использует собственный открытый формат OOXML, который в свою очередь лег в основу стандарта ISO 29500, принятого 1 апреля 2008 г К настоящему моменту системы документооборота многих государств и частных компаний базируются на вышеупомянутых форматах По прогнозам экспертов, в ближайшие годы основная масса редактируемых электронных документов в мире будет переведена на основу XML Кроме того, в последнее время активно развиваются технологии баз данных, в которых XML используется в качестве языка определения данных

Однако, этот язык по своей природе чрезвычайно избыточен, и документы XML в среднем на 80% больше, чем эквивалентный не стандартизированный текст или двоичные форматы Проблема размера документов XML -единственное серьезное препятствие на пути его распространения во многих областях, так как существенно увеличиваются затраты на хранение, обработку и обмен информацией Этот недостаток наиболее очевиден в каналах связи с ограниченной пропускной способностью и больших хранилищах информации

Таким образом, необходимость максимального сжатия XML без потерь информации возникает в корпоративных хранилищах документов и системах документооборота, электронных библиотеках, в XML-ориентированных базах данных (при хранении и резервном копировании), а также при передаче гипертекстовых данных по каналам с низкой пропускной способностью

Проведенные исследования (С J Augen, D A Bulutoglu, В Е Mullins, R О Baldwin, W Ng, L W Yeung, J Cheng) показали, что универсальные текстовые компрессоры не способны обеспечить сжатие XML до размеров,

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

Однако при разработке большинства методик подобного рода особое внимание уделялось скорости работы алгоритмов и потребления ресурсов из-за ограниченных возможностей вычислительной техники и особенно портативных устройств По этой причине существующие методы предобработки XML ориентированы на словарные и блочно-преобразующие алгоритмы сжатия (J Cheney, Р Tolam, J. Hantsa, H Liefke, D Suciu, J. Min, M Park, С Chung, G Leighton, J Diamond, T. Muldner, M. Girardot, N Sundaresan, N Sundaresan, R Moussa) Но прогрессивный рост объемов памяти и производительности компьютеров в последние годы отодвинул на второй план проблему скорости алгоритмов и сделал менее актуальным вопрос потребления ресурсов при кодировании текстовых данных В то же время для многих XML-приложений пропускная способность каналов передачи данных в сетях по-прежнему остается узким местом и требует максимального повышения степени сжатия транслируемых данных при минимальных затратах на передачу словарей и прочих служебных составляющих кода Эти факторы обусловили актуальность использования семейства адаптивных статистических алгоритмов предсказания по частичному совпадению (prediction by partial matching, PPM), которые обеспечивают лучшую степень сжатия текстовой информации

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

Таким образом, задача разработки и исследования методов оперативного сжатия данных формата XML является актуальной

Цель Разработка методики оперативного сжатия гипертекстовых документов формата XML без потерь информации на основе многопоточного расщепления входных данных с сохранением связанных иерархических контекстов вложенных элементов и применения метода предсказания по частичному совпадению

Основные задачи исследования

1. Проведение обзора и сравнительного анализа специализированных методов предобработки и методик сжатия данных XML, по критериям степени сжатия, скорости сжатия/распаковки и объема потребляемой памяти

2 Выбор алгоритмов моделирования источников и кодирования слабоструктурированных гипертекстовых данных для эффективного сжатия XML

3 Разработка метода предобработки данных XML с учетом особенностей их иерархической структуры

4 Разработка алгоритма предобработки документов XML

5 Разработка методики оперативного сжатия гипертекстовых документов формата XML

6 Разработка программного обеспечения совместимого со стандартизированной технологией однопроходного разбора файлов XML

7. Испытания ПО и анализ результатов с целью определения области эффективного применения разработанного алгоритма сжатия

Объект исследования Слабоструктурированные данные, представленные в гипертекстовом формате XML

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

Научная новизна Полученный в работе комплекс теоретических и практических результатов позволил создать методику оперативного сжатия документов формата XML, в основу которой положен метод предобработки гипертекстовых данных, позволяющий эффективно применить адаптивный статистический алгоритм При этом

1 Разработан метод декомпозиции иерархической модели слабоструктурированных гипертекстовых данных формата XML, с учетом влияния зависимостей вложенных элементов на точность прогнозирования символов при контекстном моделировании

2 На основе предложенного метода разработан алгоритм предобработки документов XML, позволяющий снизить избыточность, повысить однородность данных и обеспечить возможность эффективного применения семейства адаптивных статистических алгоритмов предсказания по частичному совпадению

3 Разработана методика оперативного сжатия данных XML с применением предложенного алгоритма предобработки

Практическая ценность На основе исследований, проведенных в диссертационной работе, реализован комплекс программных средств, совместимых со стандартной технологией Simple API for XML (SAX), позволяющий осуществлять оперативное сжатие документов XML

Реализация результатов Разработанное программное обеспечение используется в системе документооборота ООО «МЕКО»

Апробация результатов Результаты работы докладывались и обсуждались на научных конференциях

- Восьмой всероссийской научной конференции молодых ученых по математическому моделированию и информационным технологиям (Новосибирск, ИВТ СО РАН, 2007),

- Международной научно-технической конференции «Информационные технологии и системы» (Нижний Новгород, НГТУ, 2008),

- Семинаре молодых ученых «Задачи системного анализа, управления и обработки информации» (Москва, 2006),

- Конференции молодых ученых университета печати (МГУП, 2008)

Публикации по теме диссертации Основные результаты диссертации

опубликованы в 5-ти работах, в том числе 1-ой статье в журнале, рекомендованном ВАК РФ и 4-х печатных работах в сборниках научных трудов и других изданиях

Структура и объем диссертации Диссертация изложена на 108 с машинописного текста, и состоит из введения, четырех глав, заключения и одного приложения

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

Во введении описана проблема избыточности и неоднородности документов, представленных в формате XML, обоснована актуальность исследования моделей гипертекстовых слабоструктурированных данных и разработки технологий оперативного сжатия XML, основанных на специализированных методах предобработки Также формулируются цели и задачи исследования, приводится краткая характеристика основных разделов диссертации

В первой главе приведен обзор универсальных алгоритмов моделирования и кодирования источников данных без памяти, применяемых для сжатия текстовых данных без потерь Приведена оценка их относительной эффективности Рассмотрена концепция и преимущества арифметического кодирования (A Moffat)

Проведено тестирование универсальных текстовых компрессоров, применяемых для сжатия XML (gzip, Deflate, bzip2), результаты которого показали существенную разницу значений степени сжатия для разных компрессоров при обработке одних и тех же документов XML На основе этих результатов сделан вывод о влиянии нелокальной избыточности данных XML, обусловленной иерархической структурой, на возможность максимального сжатия

Описаны преимущества применения методов предсказания по частичному совпадению (J G Cleary, I Н Witten, Р G Howard, A Moffat, Т С

Bell) для адаптивного статистического моделирования источников дискретных данных

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

На основании проведенного исследования сделаны выводы о необходимости обнаружения наиболее значимых иерархических связей XML, осуществления предобработки данных с сохранением этих связей Обоснован выбор метода РРМ в совокупности с интервальным кодированием для оперативного сжатия гипертекстовых данных

Во второй главе предложено применять для сжатия данных XML парадигму компрессии с помощью универсального моделирования и кодирования (рис 1), разработанную Риссаненом (J J Rissanen) и Лэнгдоном (G G Langdon), которая положена в основу наиболее эффективных методов сжатия текстовых данных Полученные в результате предобработки потоки элементов подвергаются сжатию в два этапа- моделирование и кодирование Под моделированием понимается построение вероятностной модели источника данных, а под кодированием - генерация выходного потока рационально закодированных данных на основе построенной модели

Источник данных

Исходные давние

Компрессор

Моделнровщнк

Верощвостиая модель

Кодировщик

Сжетые

Рис 1 Парадигма компрессии с помощью универсального моделирования и

кодирования

Проведен анализ существующих модификаций алгоритма РРМ Показано, что для гипертекстовых данных эффективно по степени сжатия применять модифицированный метод РРМ с наследованием информации

(Д Шкарин) Выбранная модификация превосходит другие исследуемые результаты в среднем на 3-6% Используется механизм наследования информации позволяет учитывать функции распределения частот символов в родительских и дочерних контекстах, и используется для повышения точности оценок в контекстных моделях высоких порядков

Согласно модификации, предложенной Д Шкариным, обобщенные частоты символов определяются следующим образом Пусть s„ — контекст порядка п символа а Тогда новая создаваемая контекстная модель обозначается s„ а символ а оценивается в контексте Ветвь дерева контекстов сокращается до высоты к, что позволяет устранить искажение функции распределения вероятностей символов в узле s¡¡ Таким образом, анализируется только цепочка контекстов sp k<j<¡ Сумму обобщенных частот контекста s„ обозначается как T(s„), а значение счетчика обобщенных частот символа а для контекста s„ как t(a\s„) В этих обозначения, определение обобщенных частот символов имеет вид

'О IS,) = /„ (а IS,) + £ si (a,s„ í,+1) + ]£ 8г (a, , s,, sM) (4)

Здесь слагаемое (^(адл+О вычисляется после кодирования символа а и реализует частичные обновления

3/4, если = s{a) C\t(a\sl)<2r\ t(s¡) < 4, 1, если = j(a)n/(a|í,.)>2u/(í^)>4, ^

1/2, если s¡= 5(а) сл1(а\ ) < 8, О, иначе

Слагаемое ^(«.■s'i-i.^.-s'i+i) корректирует обобщенную частоту наиболее вероятного символа с помощью информации о символе из родительского контекста, если дочерний контекст не набрал еще достаточной статистики и выдает заниженную оценку наиболее вероятного символа по сравнению с родительским контекстом Новое значение обобщенной частоты находится с помощью взвешивания значения /(ají,) частоты символа в текущем контексте и значения t'(a\s,.i) частоты в родительском контексте Таким образом,

tf2(a,,sM) = 0'(а | - /(a |s,))> (6)

Для оценки вероятности ухода используется адаптивный подход При этом все контексты разделяются на три категории бинарные - содержащие только один символ, небинарные — без замаскированных символов, небинарные — с замаскированными символов,

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

обеспечивающий скоростную генерацию кодов для потоков байтов в двоичных ЭВМ

Выявлены особенности применения интервального кодирования в рамках рассматриваемой задачи Согласно методу для кодирования символов используется целочисленная последовательность из N возможных значений Для каждого символа выделяется диапазон значений [N(Fa),N(Fa+fa)] в исходной последовательности, где Fa - накопленная частота символов, предшествующих символу а в алфавите, N(f) - значение, соответствующее частоте/в исходной последовательности

Организовать процесс кодирования адаптивно позволяют следующие факторы

1 Основной шаг алгоритма состоит из двух циклических операций

Ni = N,+(Nh-NM)*tJ2,

где Ni, Nh - верхняя и нижняя границы диапазона, ta, ta+i - обобщенные частоты текущего и наиболее вероятного символов соответственно

2 Перераспределение диапазонов не влияет на порядок вычислений

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

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

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

В третьей главе показана недостаточность разбиения гипертекста на последовательности однотипных элементов для эффективного устранения неоднородности данных Экспериментально доказано влияние иерархических зависимостей вложенных элементов в структуре XML на точность прогнозирования символов при применении методов контекстного моделирования.

Разработана методика оперативного сжатия документов XML, основанная на синхронном преобразовании потока входных данных по трем алгоритмам - РРМ-ориентированная предобработка,

- моделирование по модифицированному методу РРМ с наследованием информации,

- интервальное кодирование (М Шиндлер)

Разработан метод предобработки, основанный на двух принципах- декомпозиция иерархической модели данных XML с сохранением вложенных зависимостей,

- однозначное кодирование структурных элементов XML

Цели предобработки - подготовка входного потока данных к статистическому моделированию посредством РРМ и частичное устранение избыточности

Пусть входной документ имеет следующую структуру <тег1>

<тег2 атр21="ааа">

<тегЗ >данные1 </тегЗ> </тег2>

<тег2 атр21="ббб">

<тегЗ > данные2 </тегЗ> </тег2> </тег1>

Ему соответствует иерархическая модель данных XML, приведенная на

рис 2

<

тег!

/-»I V

тегЗ

тег2

>

^»/«4.21 /■»] -666-

К

тегЗ

тегЗ

> тег2 \ тег ! \

Рис 2 Иерархическая модель данных XML

В процессе разбора документа SAX-анализатор генерирует последовательность событий, которые инициируют вызовы функций предобработчика На этапе предобработки входной поток элементов расщепляется на четыре параллельных потока

- поток имен элементов и атрибутов (ПИ),

- поток элементов (ПЭ),

- поток атрибутов (ПА),

- поток строчных значений (ПСЗ)

Предобработчик ставит однобайтные коды в соответствие каждому элементу древовидной структуры XML При этом коды стандартных элементов (открывающий и закрывающий теги, атрибут, строчное значение и тп) предопределены и известны декомпрессору (табл 1) Имена элементов и атрибутов кодируются в процессе предобработки и направляются в поток ПИ, а их коды - соответственно в потоки ПЭ и ПА Уникальный код генерируется при первом возникновении каждого нового имени и далее используется всякий раз в случае его повторного обнаружения Замена элементов короткими кодами позволяет сократить объем входного файла без потери информации Символьные данные записываются в потоки в исходном виде строчные значения - в поток ПСЗ, а значения атрибутов - в поток ПА После каждого элемента символьных данных в поток записывается нулевой байт

Таблица 1 Коды стандартных элементов XML

CDATA FA

сущность FB

инструкция обработки FC

комментарий FD

символы FE

С целью сохранения иерархических зависимостей исходной модели в потоки записываются дополнительные ссылочные коды непосредственно перед элементами-потомками В качестве ссылочных кодов используются коды родительских элементов

Результаты предобработки представлены на рис 3

<T«ll> <таг2 «р21* •W > <ти> дшхне1 </гегЗ» </тег2>

пи тег] 00 зрг200 мр2100 «гЗ

ПЭ 01 02 04 FE FF IT

ПА [02] 03 •W [02] FT

ПСЗ [М]имш«1 Ш

«кг2 «121- '«86" > <ягЗ» 1Иуотт>2 «УигЗ» <1п г> </яг1»

пи пз ПА псз 02 К2]03 "566" P21IT 04 ге |Р4]виаак200 IT IT FF

Рис 3 Формирование потоков модулем предобработки

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

/ тег1

■а

тег2 у ! атр21 /-»j "«»а"

Рис 4 Декомпозированная модель данных XML

Алгоритм предобработки состоит из следующих шагов

1 Идентификация структур потоков

2 Для каждого события SAX

2.1 Расшифровка,

2.2 Для каждого элемента

2 2 1 Генерация кода, 2 2 2 Если иерархическая связь, то

2 2 2 1. Посылка ссылочного кода в поток, 2 2 3 Посылка кода элемента в соответствующий поток, 2 2 4 Вызов функции моделировщика Разработана структура программного обеспечения (рис 5) Процесс моделирования и кодирования символов осуществляется синхронно с анализом Для каждого потока строится автономная модель источника по модифицированному алгоритму РРМ При этом моделировщик исследует контексты, сформированные потоками и межпотоковыми зависимостями, осуществляя переходы, обусловленные ссылочными кодами

Модуль разбора

SAX-анализ

разбор XML-документа

Модуль предобработки

кодирование элементов расщепление потоков

(^'Мйд>-ль PPAt^ моделирования

сбор статистики создание и обновление моделей вычисление относительных вероятностей символов

Модуль кодирования

формирование кодовых пространств арифметическое кодирование генерация потоков сжатых данных

Модуль РРМ-моделнр ов ашш

сбор статистики создание и обновление моделей вычисление относительных вероятностей символов

Модуль кодирования

формирование кодовых пространств арифметическое декодирование генерация потоков исходных данных

Модуль постобработки

слияние потоков замена кодов элементами

Модуль синтеза

синтез XML-докумекта

а) б)

Рис 5 Структурная схема программного обеспечения а) - компрессор, б) - декомпрессор

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

В работе методика декомпрессии организована симметрично сжатию, благодаря использованию адаптивных методов, что позволило обеспечить последовательный вывод на экран информативных элементов XML-документа, не дожидаясь полной передачи и распаковки архива

Выходные данные модуля кодирования можно представить в виде четырех составляющих

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

2 Один элемент (бит или байт), который может быть изменен переносом, если последний возникнет при сложении значений нижней границы диапазона и его размера

3 Блок элементов, имеющих максимальное значение, через которые по цепочке может пройти перенос

4 Текущее состояние кодера, представленное нижней границей интервала

В реализации использовалась упрощенная процедура нормализации, разработанная Д. Субботиным При выполнении нормализации возможны следующие действия

а) Если интервал имеет приемлемый для обеспечения заданной точности размер, нормализация не нужна

б) Если при сложении значений нижней границы интервала и размера интервала не возникает переноса, составляющие 2 и 3 могут быть записаны в выходной файл без изменений

в) В случае возникновения переноса он выполняется в составляющих 2 и 3, после чего они также записываются в выходной файл

г) Если элемент, претендующий на запись в выходной файл, имеет максимальное значение (OxFF), то он может повлиять на предыдущий при возникновении переноса Поэтому этот элемент записывается в блок, соответствующий третьей составляющей

Оперативность предполагает использование однопроходных алгоритмов предобработки и моделирования, при условии подключения однопроходного анализатора Вместе с тем, чтобы обеспечить возможность внедрения технологии сжатия XML в реальные промышленные системы, необходимо использовать стандартизированный анализатор. Большинство современных серверов поддерживают однопроходный анализ и разбор документов XML по стандартной технологии SAX Предложенный алгоритм предобработки может использовать результаты разбора файлов анализатором SAX в качестве входных данных.

В четвертой главе представлены результаты тестирования относительно существующих методов сжатия данных XML (рис 6-10) Для тестирования использовался корпус файлов XML (составители Wilfred Ng, Lam Wai Yeung, James Cheng), широко применяемый в современных исследованиях для

сравнения XML-ориентированных методов сжатия. Данный корпус состоит из 6-ти наборов данных и охватывает широкий спектр типов XML-документов, использующихся на практике.

Сравнение производилось со следующими популярными методиками сжатия XML, имеющими программную реализацию: XMill, XMLZIP, Gzip, XGrind. На всех диаграммах разработанный метод обозначен аббревиатурой ХРРМ. На горизонтальных осях представлены текстовые файлы корпуса.

□ ХРРМ

□ хмш

□ XML2IP

■ Gzip 0 XGrind

й

1

Ш

шж

ш

I

ХМаЛ DBLP Slakeipcatc ТРС-Н Woblos S»i»ftd

Рис.6. Степень сжатия.

,Я 2.5

т.

I

|

а,

о

1.5

0.5

-

-

-

-

шшш -

ХРРМ ХМШ XMLZIP GZip KÖiind Рис.7. Средняя степень сжатия.

g £

90

so 70 (.0 50 ДО

да »

ю о

s 50

£ JO

□ ХРРМ

□ хм ill

□ XMLZIP ■ Gzip

¡3 XCrind

Ml

mi

DBLP SMkspmic TPC-H Wcbloj S»issPK4

Рис.8. Время сжатия.

□ ХРРМ

□ хмш

□ XMLZIP ■ Gzip

Ш XGrlnd

_n-Ea.

XMarti DBLP Shakesprate TPC-H Weblog SwissProl

Рис.9. Время декомпрессии.

Li

Ш

мШм

ш.

ЕЗ ОбММДЛННЫХ

□ ХРРМ

□ хмш В XMLZip ■ GZip Е XGrind

La

XMark DBLP Shakespeare TPC-H Weblog SwissProt

Рис.10. Объемы потребляемой памяти.

Анализ результатов тестирования показал, что разработанная методика позволяет обеспечить наибольшее значение показателя средней степени сжатия данных в формате XML по сравнению с широко применяемыми в настоящее время алгоритмами

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

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

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

2 Проведен обзор и сравнительный анализ XML-ориентированных методов предобработки данных и основанных на них методик сжатия по критериям степени сжатия, скорости сжатия/распаковки и объемов потребляемой памяти

3 Обоснован выбор метода РРМ в совокупности с интервальным кодированием, для оперативного сжатия слабоструктурированных данных

4 Показана недостаточность разбиения гипертекста на последовательности однотипных элементов для эффективного устранения неоднородности данных

5. Выявлено влияние иерархических контекстов XML на точность прогнозирования символов

6. Разработан метод декомпозиции иерархической модели XML с сохранением информации о связях между вложенными элементами

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

8 Разработана методика оперативного сжатия слабоструюурированных данных формата XML

9 Разработано программное обеспечение для сжатия файлов XML, с использованием модифицированного алгоритма предсказания по частичному совпадению PPMII

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

Публикации по теме диссертации В журналах, входящих в перечень периодических изданий ВАК

1. ЕлховАВ Повышение эффективности сжатия HTML-страниц на основе программного кодирования коротких естественноязыковых фрагментов по алгоритму РРМ // Известия ВУЗов Проблемы полиграфии издательского дела -2007 -№6 - С 47-51. В других изданиях

2 Елхов А В Применение алгоритма кодирования РРМ для программного сжатия естественноязыковых фрагментов Web-страниц // Вестник МГУП — 2008 — № 10 — С 41^5

3 Елхов А В Метод повышения эффективности сжатия XML-страниц на основе программного кодирования по алгоритму РРМ // Информационные технологии и системы Материалы межд науч -техн конференции — Нижний Новгород НГТУ, 2008 —С 219-221

4 Елхов А В Сжатие коротких естественноязыковых фрагментов HTML-страниц по алгоритму РРМ // 8-я Всероссийская конф молодых ученых по математическому моделированию и информационным технологиям -Новосибирск ИВТ СО РАН, 2007 - С 94-95

5 Елхов А В. Применение грамматики связей в алгоритме синтаксического анализа русскоязычных предложений // Задачи системного анализа, управления и обработки информации Межвуз. сб науч трудов Вып 1 -М МГУП,2006 -С 100-104

Подписано в печать 02 10 08 г Формат 60x84/16 Услпечл 1.0 Тираж 100 экз Заказ №287/264 Отпечатано в РИО Московского государственного университета печати 127550, Москва, ул Прянишникова,2а

СПИСОК СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

1. ОБЗОР СОВРЕМЕННЫХ МЕТОДОВ СЖАТИЯ ГИПЕРТЕКСТОВЫХ ДАННЫХ.

1.1. Универсальные алгоритмы сжатия текстовых данных без потерь.

1.1.1. Словарные алгоритмы на основе методов Зива-Лемпела.

1.1.2. Блочно-ориентированные алгоритмы.

1.1.3. Алгоритмы контекстного моделирования.

1.1.4. Арифметическое кодирование.

1.2. Текстовые компрессоры, применяемые для сжатия XML в сетях.

1.3. Технологии сжатия XML, использующие специализированную предобработку.

1.3.1. XMill.

1.3.2. Millau.

1.3.3. Алгоритм структурного сжатия SCA.

1.3.4. XGrind.

1.3.5. Скелетное сжатие XML.

1.3.6. XPress.

1.3.7. XMLZip.

Выводы.

2. МЕТОД ПРЕДСКАЗАНИЯ ПО ЧАСТИЧНОМУ СОВПАДЕНИЮ С НАСЛЕДОВАНИЕМ ИНФОРМАЦИИ.

2.1. Сжатие с помощью универсального моделирования и кодирования

2.2. Алгоритм предсказания по частичному совпадению с наследованием информации.

2.2.1. Механизм наследования информации.

2.2.2. Расчет обобщенных частот символов.

2.2.3. Адаптивная оценка вероятности ухода.

2.3. Интервальное кодирование.

Выводы.

3. МЕТОДИКА ОПЕРАТИВНОГО СЖАТИЯ ДОКУМЕНТОВ

ФОРМАТА XML.

3.1. Влияние иерархических зависимостей на точность прогнозирования символов.

3.2. Синхронное преобразование потока входных данных.

3.3. Метод предобработки да1 1ных XML.

3.3.1. Декомпозиция иерархической модели.

3.3.2. Алгоритм предобработки.

3.3.3. Кодирование элементов.

3.4. Программная реализация методики.

Выводы.

4. ТЕСТИРОВАНИЕ РАЗРАБОТАННОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

4.1. Описание корпуса тестовых файлов.

4.2. Анализ результатов тестирования.

Выводы.

Актуальность. Документ формата XML [1] представляет собой набор слабоструктурированных данных описанных средствами языка XML (extensible markup language, расширяемый язык разметки). С момента своего появления в 1998 году этот язык получил широчайшее распространение благодаря своим основным преимуществам: адаптивности, расширяемости, легкости в обработке и гибкости при публикации неоднородных данных. В настоящее время создано и продолжает создаваться большое количество спецификаций XML, согласованных различными профессиональными сообществами. Известны, в частности, версии шаблонов и схем для применения в электронных СМИ, библиографии, географии, химии, астрономии, истории и др.

После того как в 2006 году формат OpenDocument основанный на XML был принят в качестве международного стандарта ISO 26300, он стал базовым форматом документов для большинства свободно распространяемых офисных программных продуктов, главным образом разработанных для Unix-систем. Кроме того, корпорация Microsoft в своем продукте Office, начиная с версии 2007, использует собственный открытый формат OOXML, который в свою очередь лег в основу стандарта ISO 29500 принятого 1 апреля 2008 г. К настоящему моменту системы документооборота многих государств и частных компаний базируются на вышеупомянутых форматах. По прогнозам экспертов, в ближайшие годы основная масса редактируемых электронных документов в мире будет переведена на основу XML. Кроме того, в последнее время активно развиваются технологии баз данных, в которых XML используется в качестве языка определения данных.

Однако, этот язык по своей природе чрезвычайно избыточен, и документы XML в среднем на 80% больше чем эквивалентный не стандартизированный текст или представления в двоичных форматах XML

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

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

Ранее проведенные исследования [4-6] показали, что универсальные текстовые компрессоры не способны обеспечить сжатие XML до размеров близких к представлению в двоичных форматах XML, что обусловлено неоднородностью гипертекстовых слабоструктурированных данных. В тоже время XML-ориентированные методики, осуществляющие предварительную обработку документов, в среднем демонстрируют лучшее сжатие.

Однако при разработке большинства методик подобного рода особое внимание уделялось скорости работы алгоритмов и потребления ресурсов из-за ограниченных возможностей вычислительной техники и особенно портативных устройств. По этой причине существующие методы предобработки XML [7-31] ориентированы на словарные [31,32] и блочно-преобразующие алгоритмы сжатия [33]. Но прогрессивный рост объемов памяти и производительности компьютеров в последние годы отодвинул на второй план проблему скорости алгоритмов и сделал менее актуальным вопрос потребления ресурсов при кодировании текстовых данных. В то же время пропускная способность каналов передачи данных в сетях по-прежнему остается узким местом, и требует максимального повышения степени сжатия транслируемых данных при минимальных затратах на передачу словарей и прочих служебных составляющих кода. Эти факторы обусловили актуальность использования семейства адаптивных статистических алгоритмов предсказания по частичному совпадению (prediction by partial matching, PPM) [34-36], которые обеспечивают лучшую степень сжатия текстовой информации.

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

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

Цель: Разработка методики оперативного сжатия гипертекстовых документов формата XML без потерь информации на основе многопоточного расщепления входных данных с сохранением связанных иерархических контекстов вложенных элементов и применения метода предсказания по частичному совпадению.

Основные задачи исследования.

1. Проведение обзора и сравнительного анализа специализированных методов предобработки и методик сжатия данных XML, по критериям степени сжатия, скорости сжатия/распаковки и объема потребляемой памяти.

2. Выбор алгоритмов моделирования источников и кодирования слабоструктурированных гипертекстовых данных, для эффективного сжатия XML.

3. Разработка метода предобработки данных XML с учетом особенностей их иерархической структуры.

4. Разработка алгоритма предобработки документов XML.

5. Разработка методики оперативного сжатия гипертекстовых документов формата XML.

6. Разработка программного обеспечения совместимого со стандартизированной технологией однопроходного разбора файлов XML.

7. Испытания ПО и анализ результатов с целью определения области эффективного применения разработанного алгоритма сжатия. Объектисследования. Слабоструктурированные данные, представленные в гипертекстовом формате XML.

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

Научная новизна. Полученный в работе комплекс теоретических и практических результатов позволил создать методику оперативного сжатия документов формата XML, в основу которой положен метод предобработки гипертекстовых данных, позволяющий эффективно применить адаптивный статистический алгоритм. При этом:

1. Разработан метод декомпозиции иерархической модели слабоструктурированных гипертекстовых данных формата XML, с учетом влияния зависимостей вложенных элементов на точность прогнозирования символов при контекстном моделировании.

2. На основе предложенного метода разработан алгоритм предобработки документов XML, позволяющий снизить избыточность, повысить однородность данных и обеспечить возможность эффективного применения семейства адаптивных статистических алгоритмов предсказания по частичному совпадению.

3. Разработана методика оперативного сжатия данных XML с применением предложенного алгоритма предобработки. Практическая ценность. На основе исследований, проведенных в диссертационной работе, реализован комплекс программных средств, совместимых со стандартной технологией Simple API for XML (SAX), позволяющий осуществлять оперативное сжатие документов XML.

Реализация результатов работы. Разработанное программное обеспечение используется в системе документооборота ООО «МЕКО».

Основные результаты диссертации опубликованы в 5-ти работах, в том числе 1-ой статье в журнале, рекомендованном ВАК РФ и 4-х печатных работы в сборниках научных трудов. Результаты работы докладывались и обсуждались на научных конференциях.

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

Во второй главе предложено применять для сжатия данных XML парадигму компрессии с помощью универсального моделирования и кодирования. Описаны модификации метода РРМ с наследованием информации и арифметического кодирования.

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

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

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

Выводы

Разработанная методика сжатия документов формата XML позволяет обеспечить наибольшее значение показателя средней степени сжатия данных в формате XML по сравнению с широко применяемыми в настоящее время подходами.

Определена область эффективного применения разработанной методики, которую составляют корпоративные системы документооборота, хранилища документов XML, электронные библиотеки, слабоструктурированные базы данных.

Оперативность разработанной методики позволяет устранить зависимость времени вывода первого информативного блока информации от размера передаваемого XML-документа.

Заключение

В работе получены следующие результаты и выводы:

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

2. Проведен обзор и сравнительный анализ XML-ориентированных методов предобработки данных и основанных на них методик сжатия по критериям степени сжатия, скорости сжатия/распаковки и объемов потребляемой памяти.

3. Обоснован выбор метода РРМ в совокупности с интервальным кодированием для оперативного сжатия слабоструктурированных данных.

4. Показана недостаточность разбиения гипертекста на последовательности однотипных элементов для эффективного устранения неоднородности данных.

5. Выявлено влияние иерархических контекстов XML на точность прогнозирования символов.

6. Разработан метод декомпозиции иерархической модели XML с сохранением информации о связях между вложенными элементами.

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

8. Разработана методика оперативного сжатия слабоструктурированных данных формата XML.

9. Разработано программное обеспечение для сжатия файлов XML с использованием модифицированного алгоритма предсказания по частичному совпадению PPMII.

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

1. ТРС-Н XML-отчеты (выборка) баз данных низкая 34

2. Weblog Данные журналов событий Web-серверов высокая 30

3. SwissProt Последовательности кодов ДНК низкая 21

4. Extensible Markup Language (XML) 1.0 (Second Edition) W3C Recommendation. (http://www.w3.org/TR/REC-xml/). October 2000.

5. Document Object Model (DOM) Level 2 Specification Version 1.0, W3C Recommendation (http://www.w3 .org/TR/2000/REC-DOM-Level-2-Core-20001113). November 2000.3.

6. Д. А. Шкарин. Повышение эффективности алгоритма РРМ // Проблемы передачи информации. 2001. Т. 37. Вып. 3. С 44-54.

7. Augeri С. J., Mullins В. Е., Bulutoglu D. A., Baldwin R. О. An Analysis of XML Binary Formats and Compression // ExpCS '07. San Diego, California, USA. June 13- 14, 2007.

8. Augeri C. J., Mullins В. E., Bulutoglu D. A., Baldwin R. O. An Analysis of XML Compression Efficiency // Proceedings of the 2007 workshop on Experimental computer science. New York, NY, USA. Article No. 7. 2007.

9. Ng Lam W., Yeung W., Cheng J. Comparative Analysis of XML Compression Technologies // Kluwer Academic Publishers, Hingham, MA, USA. 2006. P. 5-33

10. H. Liefke , D. Suciu. XMill: an efficient compressor for XML data // Proceedings of ACM SIGMOD international conference on Management of data, May 15-18, 2000, Dallas, Texas, United States. P.153-164.

11. C. League, K. Eng. Schema-Based Compression, of XML Data with Relax NG // Long Island University Computer Science, Brooklyn, NY, USA. 2006.

12. League, C. Eng, K. Type-Based Compression of XML Data // Data Compression Conference, 2007. P. 273-282.

13. J. Min, M. Park, C. Chung. A compressor for effective archiving, retrieval, and updating of XML documents // ACM Transactions on Internet Technology. Volume 6, Issue 3. August 2006. P. 223 258.

14. J. Min, M. Park, C. Chung. XPRESS: a queriable compression for XML data // Proceedings of the 2003 ACM SIGMOD international conference on Management of data table of contents San Diego, California. 2003. P. 122-133.

15. P. Skibinski, J. Swacha, S. Grabowski. Effective asymmetric XML compression // University of Wroclaw, Institute of Computer Science, Poland. 2007.

16. P. Skibinski, J. Swacha, S. Grabowski. Combining Efficient XML Compression with Query Processing // University of Wroclaw, Institute of Computer Science, Poland. 2007.

17. P. Skibinski, J. Swacha, S. Grabowski. A Highly Efficient XML Compression Scheme for the Web // University of Wroclaw, Institute of Computer Science, Poland. 2008.

18. S. Hariharan, P. Shankar. Compressing XML Documents Using Recursive Finite State Automata // Department of Computer Science and Automation, Indian Institute of Science, India. 2005.

19. S. Hariharan, P. Shankar. Evaluating the Role of Context in Syntax Directed Compression of XML Documents // Data Compression Conference. 2006.

20. S. Harrusi, A. Averbuch, A. Yehudai. Compact XML grammar based compression // School of Computer Science, Tel Aviv University. Israel. 2007.

21. Leighton G., Diamond J., Muldner Т. AXECHOP: a grammar-based compressor for XML // Data Compression Conference, 2005. P. 467.

22. Leighton G., Diamond J., Muldner T. Treechop: A tree-based query-able compressor for XML // In Proceedings of the Ninth Canadian Workshop on Information Theory. 2005.

23. W. Ng, W.-Y. Lam, P. T. Wood, M. Levene. XCQ: A queriable XML compression system Knowledge and Information Systems, Volume 10 , Issue 4 . October 2006. P 421-452.

24. W. Ng, X. Wang, J. He, A. Jhou. MQX: multi-query engine for compressed XML data // ACM Special Interest Group on Information Retrieval, New York, NY, USA. 2007. P. 897.

25. Y. Natchetoi, H. Wu , G. Babin, S. Dagtas. EXEM: Efficient XML data exchange management for mobile applications // Information Systems Frontiers, Volume 9, Number 4, 2007. Springer Netherlands. P. 439-448.

26. M. Girardot, N. Sundaresan. Efficient Representation and Streaming of XML Content over the Internet Medium // IEEE International Conference on Multimedia and Expo (I), pp. 67-70 (2000).

27. M. Girardot, N. Sundaresan. Millau: An Encoding Format for Efficient Representation and Exchange of XML over the Web // Proceedings of the 9th International WWW Conference, pp. 747-765, May (2000).

28. P. M. Tolani, J. R. Haritsa. XGRIND: A Query-friendly XML Compressor // IEEE Proceedings of the 18th International Conference on Data Engineering (2002).

29. A. R. Schmidt, F. Waas, M. L. Kersten and M. J. Carey and I. Manolescu and R. Busse. XMark: A Benchmark for XML Data Management // Proceedings of VLDB, (2002).

30. M. Levene, P. T. Wood. XML Structure Compression //Proceedings of the Second International Workshop on Web Dynamics, May (2002).

31. M. Kalman, F. Havasi, T. Gyimothy. Compacting XML documents // Information and Software Technology, Volume 48, Issue 2. 2006. P. 90-106.

32. P. Buneman, M. Grohe, C. Koch. Path Queries on Compressed XML // Proceedings of the 29th International Conference on Very Large Data Bases (VLDB'03), May (2003).

33. A. Arion, A. Bonifati, G. Costa, I. Cnr, I. Manolescu, A. Pugliese, D. Unical. XQueC: Pushing Queries to Compressed XML Data // The Pennsylvania State University CiteSeer Archives. 2003.

34. H. Liefke, D. Suciu. An extensible compressor for XML data // ACM SIGMOD Record, Volume 29 , Issue 1. 2000. P.57-62.

35. XML Binary Characterization // www.w3.org/XML/Binary.

36. J. Ziv, A. Lempel. A Universal Algorithm for Sequential Data Compression 11 IEEE Trans. Inform. Theory, IT-23, no.3. May 1977. P. 337-343.

37. J. Ziv, A. Lempel. Compression of Individual Sequences via Variable Rate Coding//IEEE Trans. Inform. Theory, IT-24, no. 5. Sept. 1978. P. 530-536.

38. M. Burrows, D.J. Wheeler. A Block-Sorting Lossless Data Compression Algorithm // Technical Report, Digital Equipment Corporation. 1994. Palo Alto, California.

39. Cleary J.G., Witten LH. Data Compression Using Adaptive Coding and Partial String Matching// IEEE Trans. Commun. 1984. V. 32. №4. P. 396-402.

40. J. Cleary, W. Teahan, I. Witten. Unbounded Length Contexts for PPM // Proceeding of the IEEE Data Compression Conference. March 1995. P. 52-61.

41. J. G. Clearly, I. H. Witten. Data Compression Using Contexts for PPM // Computer Journal, Vol. 40, Nos (2/3). 1997. P. 67-75.

42. J. A. Storer, T. G. Szymanski: Data compression via textural substitution // ACM 29(4). 1982. P. 928-951.

43. Z. Arnavutl, S. S. Magliveras. Lexical Permutation Sorting Algorithm // The Computer Journal, 1997, 40(5). P. 292-295.

44. Ryabko, B. Ya. Data compression by means of a "book stack" // Problems Inform. Transmission 16, 1980, no. 4. P. 265-269.

45. I. H. Witten, Т. C. Bell. The Zero Frequency Problem: Estimating the Probabilities of Novel Events in Adaptive Text Compression // IEEE Trans. Inform. Theory, IT-37, no. 4. July 1991. P. 1085-1094.

46. Moffat A. Implementing the PPM Data Compression Scheme // IEEE Trans. Commun. 1990. V. 38. №11. p. 1917-1921.

47. Howard P. G. The design and analysis of efficient lossless data compression systems // PhD thesis, Brown University. 1993.

48. P. G. Howard, J. S. Witter. Practical Implementations of Arithmetic Coding // in Image and Text Compression, J. A. Storer, Ed. Norwell, MA: Kluwer Academic Publishers. 1992. P. 85-112.

49. P. G. Howard, J. S. Witter. Design and Analysis of Fast Text Compression Based on Quasi-Arithmetic Coding // in Proc. Data Compression Conference, J. A. Storer and M. Cohn, Eds. Snowbird, Utah. Mar. 30-Apr. 1, 1993. P. 98-107.

50. P. G. Howard, J. S. Witter. Analysis of Arithmetic Coding for Data Compression // Information Processing and Management, 28, no. 6, pp. 749-763, 1992.

51. I. H. Witten, R. M. Neal, J. G. Cleary. Arithmetic Coding for Data Compression // Comm. ACM, 30, no. 6. June 1987. P. 520-540.

52. A. M. Moffat, N. Sharman, I. H. Witten, Т. C. Bell. An Empirical Evaluation of Coding Methods for Multi-Symbol Alphabets // in Proc. Data Compression Conference, J. A. Storer and M. Cohn, Eds. Snowbird, Utah. Mar. 30-Apr. 1, 1993. P. 108-117.

53. Hufman D. A. A Method for the Construction of Minimum Redundancy Codes // Proceedings of the Institute of Radio Engineers, 40. 1952. P. 1098-1101.

54. J. J. Rissanen. Generalized Kraft Inequality and Arithmetic Coding // IBM J. Res. Develop., 20, no. 3., May 1976. P. 198-203.

55. F. Rubin. Arithmetic Stream Coding Using Fixed Precision Registers // IEEE Trans. Inform. Theory, IT-25, no. 6. Nov. 1979. P. 672-675.

56. J. J. Rissanen, G. G. Langdon. Arithmetic Coding // IBM J. Res. Develop., 23. no. 2. Mar. 1979. P. 146-162.

57. XMLZip XML Solutions, http://www.xmls.com/.

58. Aberg J., Shtarkov Yu.M. and Smeets BJ.M. Multialphabet coding with separate alphabetdescription, // Proc. of Compression and Complexity of Sequences 97, Positano, Salerno, Italy, IEEE Сотр. Soc. Press, 1998. P. 56 65.

59. Bloom C. Solving the Problems of Context Modeling // (http://www.cbloom.com/papers/). 1996.

60. Seward J. BZip2 v. 1.0 block-sorting file compressor (http://www.muraroa.demon.co.uk/). 2000.