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

• Автор: Елхов, Алексей Викторович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 109 с. : ил.

ОГЛАВЛЕНИЕ

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

ВВЕДЕНИЕ.

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

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

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

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

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

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

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

ПРЕДОБРАБОТКУ.

1.3.1. ХМШ
1.3.2. i.
1.3.3. Алгоритм структурного сжатия .
1.3.4. Xi.
1.3.5. Скелетное сжатие X.
1.3.6. X.
1.3.7. Xi.
2. МЕТОД ПРЕДСКАЗАНИЯ ПО ЧАСТИННОМУ СОВПАДЕНИЮ С НАСЛЕДОВАНИЕМ ИНФОРМАЦИИ
2.1. Сжатие с помощью универсального моделирования и кодирования
2.2. Алгоритм предсказания по частичному совпадению с наследованием информации
2.2.1. Механизм наследования информации.
2.2.2. Расчет обобщенных частот символов
2.2.3. Адаптивная оценка вероятности ухода
. Интервальное кодирование.
3. МЕТОДИКА ОПЕРАТИВНОГО СЖАТИЯ ДОКУМЕНТОВ
ФОРМАТА X
3.1. Влияние иерархических зависимостей на точность прогнозирования символов
3.2. Синхронное преобразование потока входных данных.
3.3. Метод предобработки да ньх X.
3.3.1. Декомпозиция иерархической модели
3.3.2. Алгоритм предобработки.
3.3.3. Кодирование элементов
3.4. Программная реализация методики.
4. ТЕСТИРОВАНИЕ РАЗРАБОТАННОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
4.1. Описание корпуса тестовых файлов
4.2. Анализ результатов тестирования.
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Таким образом, необходимость максимального сжатия XML без потерь информации возникает в корпоративных хранилищах документов и системах документооборота, электронных библиотеках, в XML-ориентированных базах данных (при хранении и резервном копировании), а также при передаче гипертекстовых данных по каналам с низкой пропускной способностью. Ранее проведенные исследования [4-6] показали, что универсальные текстовые компрессоры не способны обеспечить сжатие XML до размеров близких к представлению в двоичных форматах XML, что обусловлено неоднородностью гипертекстовых слабоструктурированных данных. В гоже время XML-ориентированные методики, осуществляющие предварительную обработку документов, в среднем демонстрируют лучшее сжатие. Однако при разработке большинства методик подобного рода особое внимание уделялось скорости работы алгоритмов и потребления ресурсов из-за ограниченных возможностей вычислительной техники и особенно портативных устройств. По этой причине существующие методы предобработки XML [7-] ориентированы на словарные [,] и блочно-преобразующие алгоритмы сжатия []. Но прогрессивный рост объемов памяти и производительности компьютеров в последние годы отодвинул на второй план проблему скорости алгоритмов и сделал менее актуальным вопрос потребления ресурсов при кодировании текстовых данных. Эти факторы обусловили актуальность использования семейства адаптивных статистических алгоритмов предсказания но частичному совпадению (prediction by partial matching, PPM) [-], которые обеспечивают лучшую степень сжатия текстовой информации. При передаче документов в архитектуре клиент-сервер большое значение имеет оперативность распаковки, позволяющая браузерам и выводить документы постепенно малыми фрагментами, не дожидаясь полного декодирования файлов, что существенно сокращает промежуток времени между запросом и выводом первого информативного фрагмента документа. Таким образом, задача разработки и исследования методов оперативного сжатия данных формата XML является актуальной. Цель: Разработка методики оперативного сжатия гипертекстовых документов формата XML без потерь информации на основе многопоточного расщепления входных данных с сохранением связанных иерархических контекстов вложенных элементов и применения метода предсказания по частичному совпадению. Основные задачи исследования. Проведение обзора и сравнительного анализа специализированных методов предобработки и методик сжатия данных XML, по критериям степени сжатия, скорости сжатия/распаковки и объема потребляемой памяти. Выбор алгоритмов моделирования источников и кодирования слабоструктурированных гипертекстовых данных, для эффективного сжатия XML. Разработка метода предобработки данных XML с учетом особенностей их иерархической структуры. Разработка алгоритма предобработки документов XML. Разработка методики оперативного сжатия гипертекстовых документов формата XML. Разработка программного обеспечения совместимого со стандартизированной технологией однопроходного разбора файлов XML. Испытания ПО и анализ результатов с целью определения области эффективного применения разработанного алгоритма сжатия. Объект исследования. XML. Методы исследования. В работе используются методы теории информации, теории формальных языков, энтропийного кодирования, контекстного моделирования данных, теории вероятностей, теории алгоритмов, объектно-ориентированного программирования, численные методы. Научная новизна. Полученный в работе комплекс теоретических и практических результатов позволил создать методику оперативного сжатия документов формата XML, в основу которой положен метод предобработки гипертекстовых данных, позволяющий эффективно применить адаптивный статистический алгоритм. Разработан метод декомпозиции иерархической модели слабоструктурированных гипертекстовых данных формата XML, с учетом влияния зависимостей вложенных элементов на точность прогнозирования символов при контекстном моделировании. На основе предложенного метода разработан алгоритм предобработки документов XML, позволяющий снизить избыточность, повысить однородность данных и обеспечить возможность эффективного применения семейства адаптивных статистических алгоритмов предсказания по частичному совпадению.