Дослідження сучасних методів стиснення XML

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

Часто використовувані скорочення

XML є однією з найбільш корисних і важливих технологій, що з'явилися в зв'язку з неймовірною популярністю HTML і Інтернету. XML вирішує безліч проблем, пропонуючи нейтральне уявлення даних в різних архітектурах, з мінімальними витратами створюючи мости між програмними системами і дозволяючи зберігати великі обсяги частково структурованих даних.

Часто формат XML називають самодокументіруемим, оскільки його структура така, що одна і та ж схема повторюється для кожного запису в документі. Ця особливість надає формату XML неймовірну гнучкість, але в той же час породжує проблему багатослівності, яка призводить до суттєвого зростання розмірів документів. У зв'язку з широким розповсюдженням XML і великим числом сховищ XML-документів виникає гостра потреба в ефективному стисненні цього формату.

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

Серед переваг компресорів XML слід згадати зниження пропускної здатності мережі, необхідної для обміну даними, скорочення обсягу дискового простору, необхідного для зберігання даних, і зниження вимог до пам'яті для обробки XML-документів.

Малюнок 1. Переваги застосування компресора XML для передачі даних по мережі

Огляд компресорів даних, які розпізнають і не розпізнають XML, і запитів, які можна (або не можна) виконувати Часто використовувані скорочення CDATA: чисельні дані DTD: визначення типу документа GPS: глобальна система навігації HTML: мова гіпертекстової розмітки PPM: прогноз щодо часткового збігу SAX: простий API для XML W3C: консорціум W3C XML: розширювана мова розмітки XML є однією з найбільш корисних і важливих технологій, що з'явилися в зв'язку з неймовірною популярністю HTML і Інтернету

В принципі компресори XML можна класифікувати за двома основними характеристиками. малюнок 2 ілюструє першу характеристику, засновану на знанні компресором структури XML-документа. Відповідно до цієї класифікації, компресори можна розділити на дві групи:

Універсальні текстові компресори. Оскільки дані XML зберігаються в текстових файлах, перший логічний підхід до стиснення XML-документів полягає в застосуванні традиційних універсальних програм стиснення тексту (наприклад, gzip, bzip2). Компресори цієї групи нічого не знають про структуру XML, тобто вони вважають XML-документи звичайними текстовими документами і застосовують до них традиційні методи стиснення тексту.
Компресори, обізнані про XML. Компресори цієї групи використовують знання структури XML-документа для досягнення більшого ступеня стиснення в порівнянні з універсальними текстовими компресорами. У свою чергу цю група компресорів можна розділити на їхню залежності від наявності схеми XML-документа:
- Компресори, залежні від схеми. Для виконання стиснення і кодер, і декодер повинні мати доступ до схеми документа (наприклад, rngzip).
- Компресори, які не залежать від схеми. Для виконання кодування і декодування інформація про схему документа не потрібно (наприклад, XMill, SCMPPM).

Малюнок 2. Класифікація компресорів XML по їх обізнаності про структуру XML-документів

малюнок 3 ілюструє другий спосіб класифікації компресорів XML, заснований на їх здатності підтримувати запити:

Компресори XML, які не підтримують запити (архіватори). Ця група компресорів не дозволяє звертатися із запитами до стиснення формату (наприклад, gzip, bzip2, XMill). Основне призначення цієї групи - забезпечення максимальної ступеня стиснення. Універсальні текстові компресори за замовчуванням відносяться саме до цієї групи.
Компресори XML, що підтримують запити. Ця група компресорів дозволяє звертатися із запитами до стисненим форматам. Як правило, ступінь стиснення компресорів цієї групи гірше, ніж у архівуються компресорів. Втім, основне призначення цієї групи полягає в тому, щоб уникнути повної декомпресії документа в процесі обробки запиту. Насправді можливість звернення із запитами до стисненим форматам XML дуже важлива для багатьох програм, які потребують пристроях з обмеженими ресурсами, таких як мобільні пристрої і системи GPS. За замовчуванням всі компресори, що підтримують запити, обізнані про структуру XML. Цю групу компресорів можна додатково класифікувати за способом кодування структурних та інформаційних частин XML-документа:
- Гомоморфні компресори. Зберігають початкову структуру XML-документа, що дозволяє звертатися до стиснення формату і виконувати синтаксичний аналіз аналогічно тому, як це робиться з вихідним форматом (наприклад, XGrind).
- Негомоморфние компресори. У процесі кодування структурна частина XML-документа відокремлюється від інформаційної (наприклад, XQueC). В результаті структура стисненого формату відрізняється від структури вихідного XML-документа.

Малюнок 3. Класифікація компресорів XML з підтримки запитів

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

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

на малюнку 5 наведено приклад поділу XML-файла на структуру і дані. Таблиці елементів і атрибутів містять структурні контейнери документа XML. Значення кожного унікального маршруту (елемента або атрибута) зберігаються в окремих таблицях (контейнерах). Таким чином, значення в кожному контейнері стають гомогенними і можуть стискатися ефективніше. Цей приклад включає окремі таблиці для елементів (клієнти, клієнти / клієнт, клієнти / клієнт / ім'я, клієнти / клієнт / прізвище, клієнти / клієнт / рахунок, клієнти / клієнт / рахунок / компоненти і клієнти / клієнт / рахунок / компоненти / компонент) і атрибутів (клієнти / клієнт / @ ідентифікатор і клієнти / клієнт / рахунок / @ всього).

Малюнок 5. Приклад поділу XML-файла на структурні та інформаційні контейнери

на малюнку 6 показані опції командного рядка компресора XMill.

Малюнок 6. Опції командного рядка компресора XMill

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

Малюнок 7. Результат стиснення XML-файла за допомогою компресора XMill

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, що підтримують запити і використовують методи стиснення на основі граматики, поки немає. Обидві ці області відкривають багато цікавих шляхів для подальшого дослідження.

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

Схожі тими

Підпишіть мене на повідомлення до коментарів

Nav view search

Навигация

Курсы

бесплатные приколы

шаблоны joomla 1.7

Дополнительная информация

Новости

Учебный центр "Магнат"...

Дизаин интерьера и...

web-дизайн

Практическая...

Курсы массажа