Содержание


XML Matters

Вопросы XML: XML и сжатие

Изучение энтропии документов

Серия контента:

Этот контент является частью # из серии # статей: XML Matters

Следите за выходом новых статей этой серии.

Этот контент является частью серии:XML Matters

Следите за выходом новых статей этой серии.

XML как формат имеет множество замечательных свойств; это чрезвычайно общий способ представления произвольных структур данных, в большей или меньшей степени удобочитаемый для человека. Однако XML имеет одно весьма заметное неприятное свойство. Документы XML являются МНОГОСЛОВНЫМИ; причем не слегка (с точки зрения многоречивости), а почти невероятно огромными. В большей части ситуаций этот недостаток XML фактически ни на что не влияет. Устройства памяти с прямым доступом (DASD) дешевы, а время передачи по проводам может занимать лишь малую часть общего времени обработки. Однако иногда пропускная способность и пространство для хранения данных могут быть важны.

Чтобы дать вам общее представление, отмечу, что вовсе не является необычным тот факт, что документы XML, представляющие таблично-ориентированные данные, оказываются в три раза больше CSV, представления базы данных или даже неформатированного файла. Аналогичное увеличение размера характерно и для представления данных EDI (например, для проектов ebXML). При этом во многих случаях размеры исходных данных начинаются со многих мегабайт.

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

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

Дальнейшее увеличение объемов этих данных в несколько раз может оказаться весьма неудобным, особенно при передаче. Например, для этой статьи я создал XML-представление 1-мегабайтного журнала доступа Apache. Документ XML получился в 3,18 раза больше лежащего в его основе журнала из построчных записей. Единственной информацией, которая была добавлена по ходу действия, стали описательные имена полей, однако их вполне можно было бы указать в одной строке заголовка, занимающей менее сотни байтов. Более того, мое конкретное XML-представление не включало никаких пространств имен в тегах, что могло бы вызвать еще большее увеличение размера.

Размышляя о сжатии документов, вы, как правило, в первую очередь думаете о широко распространенных методах сжатия (например, алгоритмах Лемпеля-Зива и Хаффмана) и общеизвестных утилитах, реализующих различные варианты этих алгоритмов. В частности, на Unix-подобных платформах первое, что обычно приходит в голову, — это утилита gzip; на других платформах большее распространение имеет zip (реализованная в таких утилитах, как PKZIP, Info-ZIP и WinZip). Утилита gzip почти всегда превосходит zip, но лишь ненамного. Эти утилиты действительно обеспечивают существенное уменьшение размеров XML-файлов. Впрочем, также оказывается, что можно добиться значительно более высоких степеней сжатия с помощью двух описанных ниже средств (как при использовании по отдельности, так и в сочетании друг с другом).

Первый метод заключается в использовании алгоритма сжатия Бэрроуза-Уилера вместо последовательных алгоритмов Лемпеля-Зива. В частности, чуть менее распространенная утилита bzip2 (и связанные с ней библиотеки и API) представляет собой одну из реализаций алгоритма Бэрроуза-Уилера для ряда платформ (и распространяется с предоставлением полного исходного кода и лицензии в стиле BSD). Алгоритм Бэрроуза-Уилера работает путем группирования связанных строк в несжатом источнике вместо создания словаря вхождений строк, как это делается в алгоритме Лемпеля-Зива. Утилита bzip2 для многих типов файлов стабильно обеспечивает более высокую степень сжатия по сравнению с gzip, при этом особенно ярко это проявляется в отношении документов XML. Отрицательная сторона заключается в более низкой скорости работы bzip2 по сравнению с gzip. Однако медленная скорость передачи данных зачастую нивелирует разницу в скорости алгоритмов, привязанных к ресурсам ЦП или памяти.

Второй метод заключается в использовании преимуществ весьма специфической структуры документов XML для получения более сжимаемых представлений. Одной из реализаций данного метода является утилита XMill, которую можно приобрести (с исходным кодом на языке C++) в компании AT&T на весьма льготных лицензионных условиях. Однако XMill, похоже, имеет определенные ограничения лицензирования в стиле подсчета количества щелчков по рекламным баннерам, и эта утилита не может распространяться третьими лицами напрямую (по крайней мере, насколько я это понял). Я создал свою собственную реализацию данного общего метода, которую и представляю в настоящей статье. Приведенный в статье код открыт для общего пользования. Метод, реализованный в этом коде, разработан независимо и имеет лишь «поверхностное» сходство с XMill: иногда лучшие результаты обеспечивает XMill, а иногда — мой метод (однако XMill, вероятно, всегда работает быстрее моей первоначальной реализации, в которой внимание уделяется лишь результатам сжатия).

Сравнение базовых алгоритмов

Я получил или создал четыре базовых документа, с помощью которых в этой статье будут производиться сравнения. Первый — пьеса Шекспира Гамлет в виде XML-документа (см. раздел Ресурсы). Разметка включает такие теги, как <PERSONA>, <SPEAKER> и <LINE>, вполне естественно соответствующие элементам типографского оформления, которые можно встретить в печатной копии. Для сопоставления вкладов, которые разметка XML вносит в размер и сжимаемость документа, я создал на основе файла hamlet.xml документ hamlet.txt, в котором удалены все теги XML, но оставлено все содержание. Такое извлечение не является обратимым и определенно представляет собой потерю информации. Человек, читающий файл hamlet.txt, не будет испытывать слишком больших затруднений в семантическом определении того, например, какая часть содержимого относится к имени «говорящего» («speaker»), а какая — к обычной «строке» («line»). Тем не менее не существует простых способов программного восстановления исходного XML-документа.

Следующие два документа — сетевой журнал (Weblog) Apache (компактный набор строчно-ориентированных записей) и документ XML, созданный из этого файла. Поскольку исходный документ представляет собой файл журнала, информация при преобразовании не теряется, при этом точное воссоздание первоначального формата из XML представляет собой тривиальную задачу. Разумеется, при работе с форматом журнального файла вы не можете использовать ни синтаксический анализатор XML, ни DOM, ни какой-либо валидатор, ни DTD. Давайте взглянем на размеры базовых документов, указанные в листинге 1.

Листинг 1. Перечень файлов каталога с базовыми документами
 288754  hamlet.xml
 188830  hamlet.txt
 949474  weblog.txt
3021921  weblog.xml

В обоих случаях файл XML имеет значительно больший размер. В примере с Гамлетом сравнение не является абсолютно справедливым, поскольку содержание фактической информации в текстовой версии также было сокращено. Однако в отношении файла сетевого журнала XML начинает выглядеть откровенно плохо. Но в реальности все не совсем так, как представляется на первый взгляд. Программы сжатия весьма успешно выполняют работу по «выпариванию» из документов всего лишнего, оставляя только фактическое информационное содержимое, при этом в сжатой версии объем не имеющего смысла наполнения стремится к нулю (асимптотически с усилиями по сжатию, при условии, что все проходит удачно). Давайте испытаем в деле утилиты gzip, zip и bzip2 и ознакомимся с полученными результатами в листингах 2 и 3.

Листинг 2. Перечень сжатых файлов каталога с пьесой Шекспира
  78581  hamlet.xml.gz
  72505  hamlet.txt.gz
  78696  hamlet.xml.zip
  72620  hamlet.txt.zip
  57522  hamlet.xml.bz2
  56743  hamlet.txt.bz2
Листинг 3. Перечень сжатых файлов каталога с сетевым журналом
  91029  weblog.txt.gz
 115524  weblog.xml.gz
  91144  weblog.txt.zip
 115639  weblog.xml.zip
  56156  weblog.txt.bz2
  66994  weblog.xml.bz2

При изучении размеров файлов в двух листингах заметен целый ряд интересных аспектов. Для документов обоих стилей (для каждого метода сжатия) разница в размерах сжатых файлов намного меньше разницы между документами XML и текстовыми оригиналами. Также заслуживает внимания то, что результаты работы gzip и zip очень близки друг к другу в соответствующих случаях, в то время как bzip2 всегда срабатывает намного лучше. Кроме того, при использовании bzip2 для документа с пьесой Шекспира разница в размере сжатых файлов между текстовым форматом и XML незначительна, несмотря на то, что размер базового документа в формате XML на 53 % больше.

Тем не менее сетевой журнал выделяется как проблемный случай. Хотя сжатие немного уменьшает «раздувание» в связи с преобразованием в формат XML, даже версия bzip2 все равно позволяет разметке XML увеличивать размер файла примерно на 20 %. Это не всегда следует считать катастрофой, однако создается впечатление, что должна все же существовать какая-то возможность сжатия до истинного информационного содержимого.

Обратимые преобразования

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

Именно это делают утилиты xml2struct.py и struct2xml.py. Приведенные ниже версии имеют некоторые ограничения, однако их достаточно для демонстрации соответствующих принципов. Одно из ограничений состоит в том, что каждый документ может содержать не более 253 разных тегов и что атрибуты и команды обработки не обрабатываются. Тем не менее устранение этих ограничений не должно изменить основную суть результатов. XMill выполняет похожее преобразование, но с некоторыми дополнительными возможностями и меньшим количеством ограничений.

Общий формат «структурированного» документа имеет следующий вид:

  • список тегов, присутствующих в исходном документе XML, разделенный символами перевода строки;
  • разделитель секций: 0x00 (нулевой байт);
  • компактное представление общей структуры документа, где каждый тег начала представлен отдельным байтом, а наличие содержания помечено байтом 0x02.
  • еще один разделитель секций: 0x00 (нулевой байт);
  • содержание всех элементов, указанных в схеме структуры документа, сгруппированное по типам элементов. Каждый отдельный элемент содержания отделяется байтом 0x02, а начало элементов нового типа отделяется байтом 0x01 (последнее не является строго обязательным, но облегчает обратное преобразование).

Ниже приводится полный код Python для выполнения и обращения описанного преобразования. Реализация подобного преобразования на другом языке программирования также не должна вызвать затруднений:

Листинг 4. xml2struct.py
import sys
import xml.sax
from xml.sax.handler import *

class StructExtractor(ContentHandler):
    """Создание специальной структуры/формы содержания документа XML"""
    def startDocument(self):
        self.taglist = []
        self.contentdct = {}
        self.state = []             # стек для состояния тега
        self.newstate = 0           # флаг для продолжения символов в том же элементе
        self.struct = []            # уплотнение структуры документа

    def endDocument(self):
        sys.stdout.write('\n'.join(self.taglist))
                                    # запись списка тегов в первую очередь
        sys.stdout.write(chr(0))    # разделитель секций \0x00
        sys.stdout.write(''.join(self.struct))
                                    # запись списка структуры
        sys.stdout.write(chr(0))    # разделитель секций \0x00
        for tag in self.taglist:    # запись списков всего содержания
            sys.stdout.write(chr(2).join(self.contentdct[tag]))
            sys.stdout.write(chr(1)) # разделитель между типами содержания

    def startElement(self, name, attrs):
        if not name in self.taglist:
            self.taglist.append(name)
            self.contentdct[name] = []
            if len(self.taglist) > 253:
                raise ValueError, "Встречено больше 253 тегов"
        self.state.append(name)     # проталкивание текущего тега
        self.newstate = 1           # символы идут в новый элемент
                                    # одиночный символ для указания тега
        self.struct.append(chr(self.taglist.index(name)+3))

    def endElement(self, name):
        self.state.pop()            # выталкивание текущего тега из стека
        self.newstate = 1           # символы идут в новый элемент
        self.struct.append(chr(1))  # \0x01 – конечный тег в конструкции

    def characters(self, ch):
        currstate = self.state[-1]
        if self.newstate:           # либо добавление новых символов в элемент состояния
            self.contentdct[currstate].append(ch)
            self.newstate = 0
            self.struct.append(chr(2))
                                    # \0x02 заполнитель содержания в конструкции
        else:                       # либо добавление символов в текущий элемент
            self.contentdct[currstate][-1] += ch

if __name__ == '__main__':
    parser = xml.sax.make_parser()
    handler = StructExtractor()
    parser.setContentHandler(handler)
    parser.parse(sys.stdin)

Использование SAX вместо DOM делает это преобразование очень эффективным с точки зрения временных затрат, даже несмотря на то, что при разработке этому не уделялось особого внимания. Для обратного преобразования можно было бы использовать Листинг 5.

Листинг 5. struct2xml.py
def struct2xml(s):
    tags, struct, content = s.split(chr(0))
    taglist = tags.split('\n')      # все теги
    contentlist = []                # список списков элементов содержания
    for block in content.split(chr(1)):
        contents = block.split(chr(2))
        contents.reverse()          # выталкивание элементов содержания с конца
        contentlist.append(contents)
    state =  []                     # стек для состояния тега
    skeleton = []                   # шаблонная версия XML
    for c in struct:
        i = ord(c)
        if i >= 3:                  # начало элемента
            i -= 3                  # корректировка для смещения индекса тегов конструкции
            tag = taglist[i]        # расшифровка тега из списка тегов
            state.append(tag)       # проталкивание текущего тега
            skeleton.append('<%s>' % tag)
                                    # вставка тега начала элемента
        elif i == 1:                # конец элемента
            tag = state.pop()       # выталкивание текущего тега из стека
            skeleton.append('</%s>' % tag)
                                    # вставка тега конца элемента
        elif i == 2:                # вставка содержания элемента
            tag = state[-1]
            item = contentlist[taglist.index(tag)].pop()
            item = item.replace('&','&')
            skeleton.append(item)   # добавление «голого» тега для индикации содержимого
        else:
            raise ValueError, "Unexpected structure tag: ord(%d)" % i

    return ''.join(skeleton)

if __name__ == '__main__':
    import sys
    print struct2xml(sys.stdin.read()),

Сжатие преобразованных вариантов

Истинная суть обсуждаемого преобразования проявляется при попытке сжатия результатов. Если все идет по плану, файл foo.struct будет гораздо более сжимаемым, чем foo.xml, даже несмотря на то, что оба файла содержат одинаковую информацию (что доказуемо, поскольку они являются симметрично выводимыми). В известном смысле xml2struct.py уже является своего рода алгоритмом сжатия (в какой-то степени эта утилита создает файлы меньшего размера), однако на практике эту утилиту следует использовать не напрямую, а в качестве основы для дальнейшего сжатия.

Давайте взглянем на размеры некоторых файлов, включая ряд файлов, рассмотренных выше. Для сравнения включены некоторые результаты работы утилиты XMill; их можно узнать по наличию .xmi в именах файлов. (Утилита XMill доступна в версиях, предусматривающих использование алгоритмов gzip и bzip2).

Листинг 6. Перечень «структурированных XML-файлов» каталога
 228610  hamlet.struct
  57533  hamlet.struct.bz2
  57522  hamlet.xml.bz2
  71060  hamlet.struct.gz
  78581  hamlet.xml.gz
  61823  hamlet.xmi.bz2
  75247  hamlet.xmi.gz

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

Данный метод намного лучше работает с файлами сетевого журнала. Здесь он приносит реальные плоды.

Листинг 7. Перечень 2 «структурированных XML-файлов» каталога
1764816  weblog.struct
  59955  weblog.struct.bz2
  66994  weblog.xml.bz2
  56156  weblog.txt.bz2
  76183  weblog.struct.gz
 115524  weblog.xml.gz
  59409  weblog.xmi.bz2
  74439  weblog.xmi.gz

Как и ранее, реструктуризация XML-файла сетевого журнала исключительно сильно помогает сжатию gzip. Однако, поскольку gzip больше не является предпочтительным для меня методом, это уже не так интересно. Подлинный интерес представляет то, что мне удалось на 11 % улучшить степень сжатия файла, который уже и так прекрасно сжимался утилитой bzip2. Возможно, это и не столь важно, однако имеет весьма существенное значение, если вам не дают покоя лишние мегабайты. Как бы то ни было, XMill в данном случае приносит чуть лучшие результаты, чем xml2struct.py. Также интересен тот факт, что степень сжатия этого реструктурированного XML-файла находится в пределах 7 % от лучшего из достигнутых результатов сжатия исходного текстового сетевого журнала.

Заключение

Несмотря на то, что утилита, представленная в данной статье, представляет собой лишь предварительную попытку разработки, даже в своей первоначальной форме она работает на удивление качественно (по крайней мере, в некоторых случаях), «отжимая» дополнительные байты из сжатых XML-файлов. Ожидается, что после небольших доработок и тестов получится добиться уменьшения размеров файлов еще на несколько процентов. Отчасти написание этой утилиты затрудняется тем, что начинать сжатие приходится с результатов работы, столь хорошо выполняемой утилитой bzip2. Приступив к эмпирической проверке, я был искренне удивлен тем, насколько эффективным является алгоритм Бэрроуза-Уилера.

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


Ресурсы для скачивания


Похожие темы

  • Обширным источником вдохновения для написания этой статьи является работа системы сжатия XML XMill. Информацию об этой утилите и доступную для загрузки версию можно найти на странице XMill. Лицензия требует нажатий по рекламным баннерам, а страница загрузки, к сожалению, имеет содержащий ошибки сценарий, который позволяет производить загрузку не со всех сайтов.
  • Полная библиотека пьес Шекспира в формате XML доступна для загрузки на сайте ibiblio.org. Документ hamlet.xml, использовавшийся в целях тестирования, был взят в этой библиотеке.
  • Прочитайте статью, в которой представлен алгоритм Бэрроуза-Уилера (теперь реализованный в утилите bzip2): М. Бэрроуз (M. Burrows) и Д. Дж. Уилер (D.J. Wheeler), «Алгоритм сжатия данных без потерь с блочной сортировкой». Технический отчет 124, центр Digital System Research, 1994 год.
  • Утилита bzip2 входит в состав стандартного дистрибутива многих Unix-подобных систем. Утилиту bzip2 для других платформ и ее более новые версии можно найти на сайте Redhat.
  • Написанная статья, на мой взгляд, является хорошим общим введением в сжатие данных.
  • Ознакомьтесь с другими статьямив рубрике Дэвида Мерца (David Mertz) Вопросы XML.
  • Оригинал статьи: XML Matters: XML and compression.
static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=XML
ArticleID=946524
ArticleTitle=XML Matters: Вопросы XML: XML и сжатие
publish-date=09262013