Введение к работе
Актуальность Документ формата 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, В Е Mulhns, R О Baldwin, W Ng, L W Yeung, J Cheng) показали, что универсальные текстовые компрессоры не способны обеспечить сжатие XML до размеров,
близких к представлению XML в двоичных форматах, что обусловлено неоднородностью гипертекстовых слабоструктурированных данных В то же время XML-ориентированные методики, осуществляющие предварительную обработку документов, в среднем демонстрируют лучшее сжатие
Однако при разработке большинства методик подобного рода особое внимание уделялось скорости работы алгоритмов и потребления ресурсов из-за ограниченных возможностей вычислительной техники и особенно портативных устройств По этой причине существующие методы предобработки XML ориентированы на словарные и блочно-преобразующие алгоритмы сжатия (J Cheney, Р Tolam, J. Hantsa, Н Liefke, D Suciu, J. Mm, 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, по критериям
степени сжатия, скорости сжатия/распаковки и объема потребляемой
памяти
-
Выбор алгоритмов моделирования источников и кодирования слабоструктурированных гипертекстовых данных для эффективного сжатия XML
-
Разработка метода предобработки данных XML с учетом особенностей их иерархической структуры
-
Разработка алгоритма предобработки документов XML
-
Разработка методики оперативного сжатия гипертекстовых документов формата XML
-
Разработка программного обеспечения совместимого со стандартизированной технологией однопроходного разбора файлов XML
7. Испытания ПО и анализ результатов с целью определения области эффективного применения разработанного алгоритма сжатия
Объект исследования Слабоструктурированные данные, представленные в гипертекстовом формате XML
Методы исследования В работе используются методы теории информации, теории формальных языков, энтропийного кодирования, контекстного моделирования данных, теории вероятностей, теории алгоритмов, объектно-ориентированного программирования, численные методы
Научная новизна Полученный в работе комплекс теоретических и практических результатов позволил создать методику оперативного сжатия документов формата XML, в основу которой положен метод предобработки гипертекстовых данных, позволяющий эффективно применить адаптивный статистический алгоритм При этом
-
Разработан метод декомпозиции иерархической модели слабоструктурированных гипертекстовых данных формата XML, с учетом влияния зависимостей вложенных элементов на точность прогнозирования символов при контекстном моделировании
-
На основе предложенного метода разработан алгоритм предобработки документов XML, позволяющий снизить избыточность, повысить однородность данных и обеспечить возможность эффективного применения семейства адаптивных статистических алгоритмов предсказания по частичному совпадению
-
Разработана методика оперативного сжатия данных XML с применением предложенного алгоритма предобработки
Практическая ценность На основе исследований, проведенных в диссертационной работе, реализован комплекс программных средств, совместимых со стандартной технологией Simple API for XML (SAX), позволяющий осуществлять оперативное сжатие документов XML
Реализация результатов Разработанное программное обеспечение используется в системе документооборота ООО «МЕКО»
Апробация результатов Результаты работы докладывались и обсуждались на научных конференциях
Восьмой всероссийской научной конференции молодых ученых по математическому моделированию и информационным технологиям (Новосибирск, ИВТ СО РАН, 2007),
Международной научно-технической конференции «Информационные технологии и системы» (Нижний Новгород, НГТУ, 2008),
Семинаре молодых ученых «Задачи системного анализа, управления и обработки информации» (Москва, 2006),
- Конференции молодых ученых университета печати (МГУП, 2008)
Публикации по теме диссертации Основные результаты диссертации
опубликованы в 5-ти работах, в том числе 1-ой статье в журнале, рекомендованном ВАК РФ и 4-х печатных работах в сборниках научных трудов и других изданиях
Структура и объем диссертации Диссертация изложена на 108 с машинописного текста, и состоит из введения, четырех глав, заключения и одного приложения
