Исследование современных методов сжатия XML

Обзор компрессоров данных, распознающих и не распознающих XML, и запросов, которые можно (или нельзя) выполнять

Формат XML представляет собой стандарт представления данных и обмена данными в Интернете. XML обладает высокой гибкостью и получил широкое распространение, но при этом имеет один недостаток — большой размер документов. Это приводит к тому, что объём передаваемой, обрабатываемой, сохраняемой или запрашиваемой информации зачастую превышает объём данных других форматов. Для решения этой проблемы можно воспользоваться одним из нескольких методов сжатия XML. В настоящей статье приведён обзор современных методов сжатия XML.

Шериф Сакр, старший научный сотрудник Австралийского национального института информационных и коммуникационных технологий, независимый специалист

Photo of Sherif SakrДоктор Шериф Сакр (Sherif Sakr) – старший научный сотрудник группы систем программного обеспечения в Австралийском национальном институте информационных и коммуникационных технологий (NICTA), г. Сидней. Также он совмещает должность старшего преподавателя школы компьютерных и технических наук в Университете Нового Южного Уэльса. В 2007 году Шериф получил докторскую степень в области компьютерных наук в Университете г. Констанца, Германия. Также имеет степени бакалавра и магистра компьютерных наук Каирского университета, Египет. В 2011 году занимал должность выездного научного работника группы Computing Group (XCG) подразделения Microsoft Research в Редмонде, штат Вашингтон. В 2012 году работал в штате исследователей корпорации Alcatel-Lucent Bell Labs.



17.10.2013

Введение

Часто используемые сокращения

  • CDATA: численные данные
  • DTD: определение типа документа
  • GPS: глобальная система навигации
  • HTML: язык гипертекстовой разметки
  • PPM: прогноз по частичному совпадению
  • SAX: простой API для XML
  • W3C: консорциум W3C
  • XML: расширяемый язык разметки

XML является одной из наиболее полезных и важных технологий, появившихся в связи с невероятной популярностью HTML и Интернета. XML решает множество проблем, предлагая нейтральное представление данных в разных архитектурах, с минимальными затратами создавая мосты между программными системами и позволяя сохранять большие объёмы частично структурированных данных.

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

Развить навыки по этой теме

Этот материал — часть knowledge path для развития ваших навыков. Смотри:

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

Среди преимуществ компрессоров XML следует упомянуть снижение пропускной способности сети, необходимой для обмена данными, сокращение объёма дискового пространства, необходимого для хранения данных, и снижение требований к памяти для обработки XML-документов.

Рисунок 1. Преимущества применения компрессора XML для передачи данных по сети
Diagram of an example of the advantage of using XML compressors in transmitting XML data over the network

В принципе компрессоры XML можно классифицировать по двум основным характеристикам. Рисунок 2 иллюстрирует первую характеристику, основанную на знании компрессором структуры XML-документа. Согласно этой классификации, компрессоры можно разделить на две группы:

  • Универсальные текстовые компрессоры. Поскольку данные XML сохраняются в текстовых файлах, первый логический подход к сжатию XML-документов заключается в применении традиционных универсальных программ сжатия текста (например, gzip, bzip2). Компрессоры этой группы ничего не знают о структуре XML, т.е. они считают XML-документы обычными текстовыми документами и применяют к ним традиционные методы сжатия текста.
  • Компрессоры, осведомленные о XML. Компрессоры этой группы используют знание структуры XML-документа для достижения большей степени сжатия по сравнению с универсальными текстовыми компрессорами. В свою очередь эту группа компрессоров можно разделить по их зависимости от наличия схемы XML-документа:
    • Компрессоры, зависящие от схемы. Для выполнения сжатия и кодер, и декодер должны иметь доступ к схеме документа (например, rngzip).
    • Компрессоры, не зависящие от схемы. Для выполнения кодирования и декодирования информация о схеме документа не требуется (например, XMill, SCMPPM).
Рисунок 2. Классификация компрессоров XML по их осведомленности о структуре XML-документов
Diagram of classification of XML compressors according to their awareness of the structure of XML documents

Рисунок 3 иллюстрирует второй способ классификации компрессоров XML, основанный на их способности поддерживать запросы:

  • Компрессоры XML, не поддерживающие запросы (архиваторы). Эта группа компрессоров не позволяет обращаться с запросами к сжатому формату (например, gzip, bzip2, XMill). Основное назначение этой группы — обеспечение максимальной степени сжатия. Универсальные текстовые компрессоры по умолчанию относятся именно к этой группе.
  • Компрессоры XML, поддерживающие запросы. Эта группа компрессоров позволяет обращаться с запросами к сжатым форматам. Как правило, степень сжатия компрессоров этой группы хуже, чем у архивирующих компрессоров. Впрочем, основное назначение этой группы заключается в том, чтобы избежать полной декомпрессии документа в процессе обработки запроса. На самом деле возможность обращения с запросами к сжатым форматам XML очень важна для многих приложений, работающих в устройствах с ограниченными ресурсами, таких как мобильные устройства и системы GPS. По умолчанию все компрессоры, поддерживающие запросы, осведомлены о структуре XML. Эту группу компрессоров можно дополнительно классифицировать по способу кодирования структурных и информационных частей XML-документа:
    • Гомоморфные компрессоры. Сохраняют исходную структуру XML-документа, что позволяет обращаться к сжатому формату и выполнять синтаксический анализ аналогично тому, как это делается с исходным форматом (например, XGrind).
    • Негомоморфные компрессоры. В процессе кодирования структурная часть XML-документа отделяется от информационной (например, XQueC). В результате структура сжатого формата отличается от структуры исходного XML-документа.
Рисунок 3. Классификация компрессоров XML по поддержке запросов
Diagram of classification of XML compressors according to their support for executing queries

Универсальные текстовые компрессоры

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

Компрессор gzip использует алгоритм сжатия без потерь DEFLATE, который представляет собой комбинацию алгоритма LZ77 с кодированием Хаффмана. Для сжатия данных алгоритм LZ77 заменяет фрагменты данных ссылками на совпадающие фрагменты, которые уже прошли через кодер и декодер. Кодирование Хаффмана использует специальный метод выбора представления символов, в котором часто встречающиеся символы используют более короткие последовательности битов, чем символы, встречающиеся реже.

Компрессор bzip2 использует преобразование Барроуза-Уилера для преобразования часто встречающихся последовательностей символов в строки, состоящие из одинаковых букв, затем применяет перемещение вперед и, наконец, кодирование Хаффмана. Преобразование Барроуза-Уилера меняет порядок символов так, что если исходная строка содержит несколько часто встречающихся подстрок, то преобразованная строка будет иметь несколько участков, в которых один символ повторяется несколько раз подряд. Это полезно для сжатия, поскольку сжатие строки из повторяющихся символов выполняется проще. На практике компрессор bzip2 сжимает файлы лучше, чем gzip, но обладает худшим быстродействием.

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

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


Компрессоры XML, не поддерживающие запросы (архиваторы)

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

  • компрессоры, не зависящие от схемы;
  • компрессоры, зависящие от схемы.

Компрессоры, не зависящие от схемы

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

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

В последних версиях XMill промежуточные двоичные значения сжатого формата могут передаваться в один из трёх альтернативных универсальных компрессоров: gzip, bzip2 или PPM. На рисунке 4 показана общая архитектура компрессора XMill с анализатором XML, контейнерами структуры и данных, одной или несколькими схемами сжатия и сжатым XML-файлом (содержащим сжатую структуру и сжатые данные).

Рисунок 4. Общая архитектура компрессора XMill
Diagram of the general architecture of the XMill compressor

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

Рисунок 5. Пример разделения XML-файла на структурные и информационные контейнеры
Diagram of an example of splitting an XML file into structural and data containers

На рисунке 6 показаны опции командной строки компрессора XMill.

Рисунок 6. Опции командной строки компрессора XMill
Screen capture of command-line options of the XMill compressor

На рисунке 7 показан результат сжатия XML-документа (tpc.xml, размер 282 КБ) с помощью компрессора XMill, в котором выходной файл (tpc.xmi, размер 41 КБ) сжат до 15 процентов от исходного размера.

Рисунок 7. Результат сжатия XML-файла с помощью компрессора XMill
Screen capture of the output of compressing an XML file using the XMill compressot

XMLPPM представляет собой потоковый компрессор XML, использующий мультиплексируемую иерархическую модель PPM, получившую название MHM. XMLPPM является адаптацией метода универсального прогнозирования для схемы сжатия с частичным совпадением (PPM). В XMLPPM файл XML сначала преобразуется с помощью синтаксического анализатора SAX в поток событий SAX, затем каждое событие кодируется байт-кодом ESAX (кодированный SAX). Байт-коды ESAX кодируются с помощью одной из нескольких моделей PPM, мультиплексируемых в зависимости от синтаксической структуры байт-кода (элементов, символов, атрибутов и прочих символов). В качестве примера компрессора XMLPPM можно привести компрессор SCMPPM. SCMPPM объединяет метод моделирования структуры контекста (SCM) со схемой сжатия PPM. Он использует больше моделей PPM, чем XMLPPM, поскольку применяет разные модели для сжатия текста в каждом элементарном символе.

Степень сжатия и скорость работы XMill и XMLPPM сильно зависят от используемых конечных универсальных компрессоров (gzip, bzip2 или PPM). В результате они наследуют компромиссы, присущие их конечным универсальным компрессорам.

Алгоритмы сжатия, зависящие от схемы

Этому классу компрессоров необходима информация о схеме XML-документа. Например, компрессор XAUST преобразует информацию о схеме DTD в набор детерминированных конечных автоматов (DFA), по одному на каждый элемент DTD. Затем каждый переход помечается элементом и вызывается связанная с переходом операция для имитатора DFA элемента, помечающего этот переход. XAUST помещает все данные одного элемента в отдельный контейнер, который пошагово сжимается с помощью единой модели арифметического компрессора 4-го порядка. Используя схему информации DTD, XAUST может отслеживать структуру документа и точно прогнозировать предполагаемые символы. Если предсказанный символ уникален, то в его кодировании нет необходимости, поскольку декодер генерирует ту же самую модель на основе DTD, тем самым создавая такой же уникальный символ.

Компрессор RNGzip сжимает XML-документы, соответствующие заданной схеме Relax NG. В RNGzip отправитель и получатель должны заранее договориться о единстве схемы. В этом смысле схема эквивалентна общему ключу шифрования и дешифрования. Для построения детерминированного дерева автоматизации на основе указанной схемы RNGzip использует проверку подлинности схемы Relax NG. Затем, получив XML-документ, он проверяет, принимается ли XML автоматом. С учетом этого автомата получатель может воссоздать весь XML-документ на основании очень малого объёма переданной информации. Если в автомате встречается точка выбора, RNGzip просто сообщает, какой переход выполнен, а если встречается текстовый переход, то передается соответствующий текст.

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


Компрессоры XML, поддерживающие запросы

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

  • гомоморфные компрессоры;
  • негомоморфные компрессоры.

Гомоморфные компрессоры XML, поддерживающие запросы

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

Благодаря гомоморфной природе сжатого формата XGrind приобретает множество интересных способностей:

  • Сжатый XML-документ можно просматривать так же, как и исходный документ, причём все теги и элементы/атрибуты заменяются их соответствующими кодировками. Следовательно, XGrind можно считать расширенным синтаксическим анализатором SAX.
  • Сжатый XML-документ может индексироваться точно так же, как и обычные XML-документы. В XGrind имена элементов и атрибутов кодируются на основе словаря, а символьные данные сжимаются с помощью полуадаптивного кодирования Хаффмана. Процессор запросов XGrind может обрабатывать только точные совпадения и совпадения префиксов сжатых значений, а также частичные совпадения и диапазоны в распакованных значениях. Впрочем, XGrind не поддерживает некоторые операции, например, выбор по неравенству в сжатой области, поэтому он не может выполнять слияние, объединение, вложенные запросы и конструирование.

Другим поддерживающим запросы гомоморфным компрессором XML является XPress. Для эффективного сжатия и извлечения данных он использует несколько функций. Для кодирования меток и маршрутов XML-документов он применяет метод обратного арифметического кодирования к разным интервалам. Локальные взаимоотношения между интервалами позволяют обрабатывать маршруты в сжатых XML-данных. Схема сжатия XPress является полуадаптивной и предусматривает предварительное сканирование входного файла для сбора статистической информации; при этом правила кодирования данных не зависят от местоположения данных. Кроме того, эта схема использует подходящие кодеры данных на основе автоматической оценки типа информации.

Негомоморфные компрессоры XML, поддерживающие запросы

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

В XSeq лексемы входного XML-файла распределяются по нескольким контейнерам, каждый из которых затем сжимается по алгоритму Sequitur. Алгоритм сжатия Sequitur является линейным динамическим алгоритмом, создающим бесконтекстную грамматику для данной входной строки. Используя определенную бесконтекстную грамматику, XSeq обходится без последовательного сканирования не относящихся к делу сжатых данных и обрабатывает только данные, соответствующие данному запросу. Кроме того, бесконтекстная грамматика позволяет обрабатывать запросы непосредственно в сжатых файлах без полной или частичной распаковки. Для сопоставления данных, сохранённых в разных контейнерах, и ускорения обработки запросов, XSeq применяет набор индексов, которые сохраняются в сжатом файле и загружаются в память перед обработкой правил. Индекс структуры, например, позволяет быстро отыскивать значения данных в контейнере без распаковки, а индекс заголовков содержит список указателей на все контейнеры внутри файла.

Еще одним поддерживающим запросы компрессором XML является TREECHOP, в котором процесс сжатия начинается с синтаксического разбора XML-документа на основе SAX, причём выделенные лексемы заносятся в поток сжатия так, чтобы первыми следовали более глубокие. Кодовое слово каждого узла предваряется кодовым словом родительского узла, в результате два узла дерева XML-документа используют общее кодовое слово, если имеют одинаковый маршрут. Всем секциям CDATA, примечаниям, операторам и узлам без листьев присваиваются двоичные кодовые слова. Эти кодовые слова создаются уникально на основе маршрута узла. Поскольку кодировка узла дерева заносится в поток сжатия в порядке убывания глубины, декомпрессор может восстанавливать исходный документ пошагово, используя информацию об адаптивном кодировании. В TREECHOP могут обрабатываться точные совпадения и диапазоны с помощью одного сканирования потока сжатия.

Система XQuec использует модель фрагментации и хранения сжатых XML-документов, основанную на отделении структуры от контента. Кроме того, работа этой системы зависит от правильного выбора способа группировки контейнеров, поскольку контейнеры, принадлежащие одной группе, должны появляться вместе в условиях запроса. Чтобы оценить условие запроса в сжатой области, упомянутые в условии контейнеры должны принадлежать одной группе и должны быть сжаты алгоритмом, поддерживающим это условие в сжатой области. Информация об условиях прогнозируется по имеющимся запросам. XQueC использует информацию о запросах для разбиения контейнеров на группы в соответствии с исходной моделью и для присвоения наиболее подходящего алгоритма каждой группе. Помимо этого, XQueC создает алгебру для обработки XML-запросов. Эта алгебра используется оптимизатором доступа, который может сочетать обычные операторы и операторы, поддерживающие сжатие.


Заключение

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

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

Ресурсы

Научиться

Получить продукты и технологии

  • Сайт gzip: скачайте и опробуйте gzip (GNU zip), компрессор, призванный заменить compress.
  • Сайт bzip2: скачайте и опробуйте этот бесплатный высококачественный компрессор данных.
  • Сайт проекта XMill: скачайте и опробуйте настраиваемый компрессор XML, разделяющий структуру, компоновку и данные и распределяющий данные в отдельные потоки.
  • Сайт проекта XMLPPM: скачайте и опробуйте программу для сжатия данных, которая объединяет алгоритм сжатия текста PPM с данными MHM, структурированными в виде дерева.
  • Сайт проекта RNgzip: скачайте и опробуйте метод сжатия, основанный на типе документа и оформленный в виде схемы Relax NG.
  • Ознакомительные версии продуктов IBM: скачайте или познакомьтесь с онлайновыми пробными версиями в IBM SOA Sandbox, и вы сможете на практике поработать с инструментами для разработки приложений и промежуточным ПО семейств DB2®, Lotus®, Rational®, Tivoli® и WebSphere®.

Обсудить

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=XML, Open source
ArticleID=948656
ArticleTitle=Исследование современных методов сжатия XML
publish-date=10172013