Методика оперативного сжатия документов формата XML на основе декомпозиции иерархической модели данных тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Елхов, Алексей Викторович

• Елхов, Алексей Викторович
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Елхов, Алексей Викторович

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

ВВЕДЕНИЕ.

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

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

1.1.1. Словарные алгоритмы на основе методов Зива-Лемпела.

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

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

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

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

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

1.3.1. XMill.

1.3.2. Millau.

1.3.3. Алгоритм структурного сжатия SCA.

1.3.4. XGrind.

1.3.5. Скелетное сжатие XML.

1.3.6. XPress.

1.3.7. XMLZip.

Выводы.

2. МЕТОД ПРЕДСКАЗАНИЯ ПО ЧАСТИЧНОМУ СОВПАДЕНИЮ С НАСЛЕДОВАНИЕМ ИНФОРМАЦИИ.

2.1. Сжатие с помощью универсального моделирования и кодирования

2.2. Алгоритм предсказания по частичному совпадению с наследованием информации.

2.2.1. Механизм наследования информации.

2.2.2. Расчет обобщенных частот символов.

2.2.3. Адаптивная оценка вероятности ухода.

2.3. Интервальное кодирование.

Выводы.

3. МЕТОДИКА ОПЕРАТИВНОГО СЖАТИЯ ДОКУМЕНТОВ

ФОРМАТА XML.

3.1. Влияние иерархических зависимостей на точность прогнозирования символов.

3.2. Синхронное преобразование потока входных данных.

3.3. Метод предобработки да1 1ных XML.

3.3.1. Декомпозиция иерархической модели.

3.3.2. Алгоритм предобработки.

3.3.3. Кодирование элементов.

3.4. Программная реализация методики.

Выводы.

4. ТЕСТИРОВАНИЕ РАЗРАБОТАННОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

4.1. Описание корпуса тестовых файлов.

4.2. Анализ результатов тестирования.

Выводы.

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

Актуальность. Документ формата XML [1] представляет собой набор слабоструктурированных данных описанных средствами языка XML (extensible markup language, расширяемый язык разметки). С момента своего появления в 1998 году этот язык получил широчайшее распространение благодаря своим основным преимуществам: адаптивности, расширяемости, легкости в обработке и гибкости при публикации неоднородных данных. В настоящее время создано и продолжает создаваться большое количество спецификаций XML, согласованных различными профессиональными сообществами. Известны, в частности, версии шаблонов и схем для применения в электронных СМИ, библиографии, географии, химии, астрономии, истории и др.

После того как в 2006 году формат OpenDocument основанный на XML был принят в качестве международного стандарта ISO 26300, он стал базовым форматом документов для большинства свободно распространяемых офисных программных продуктов, главным образом разработанных для Unix-систем. Кроме того, корпорация Microsoft в своем продукте Office, начиная с версии 2007, использует собственный открытый формат OOXML, который в свою очередь лег в основу стандарта ISO 29500 принятого 1 апреля 2008 г. К настоящему моменту системы документооборота многих государств и частных компаний базируются на вышеупомянутых форматах. По прогнозам экспертов, в ближайшие годы основная масса редактируемых электронных документов в мире будет переведена на основу XML. Кроме того, в последнее время активно развиваются технологии баз данных, в которых XML используется в качестве языка определения данных.

Однако, этот язык по своей природе чрезвычайно избыточен, и документы XML в среднем на 80% больше чем эквивалентный не стандартизированный текст или представления в двоичных форматах XML

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

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

Ранее проведенные исследования [4-6] показали, что универсальные текстовые компрессоры не способны обеспечить сжатие XML до размеров близких к представлению в двоичных форматах XML, что обусловлено неоднородностью гипертекстовых слабоструктурированных данных. В тоже время XML-ориентированные методики, осуществляющие предварительную обработку документов, в среднем демонстрируют лучшее сжатие.

Однако при разработке большинства методик подобного рода особое внимание уделялось скорости работы алгоритмов и потребления ресурсов из-за ограниченных возможностей вычислительной техники и особенно портативных устройств. По этой причине существующие методы предобработки XML [7-31] ориентированы на словарные [31,32] и блочно-преобразующие алгоритмы сжатия [33]. Но прогрессивный рост объемов памяти и производительности компьютеров в последние годы отодвинул на второй план проблему скорости алгоритмов и сделал менее актуальным вопрос потребления ресурсов при кодировании текстовых данных. В то же время пропускная способность каналов передачи данных в сетях по-прежнему остается узким местом, и требует максимального повышения степени сжатия транслируемых данных при минимальных затратах на передачу словарей и прочих служебных составляющих кода. Эти факторы обусловили актуальность использования семейства адаптивных статистических алгоритмов предсказания по частичному совпадению (prediction by partial matching, PPM) [34-36], которые обеспечивают лучшую степень сжатия текстовой информации.

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

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

Цель: Разработка методики оперативного сжатия гипертекстовых документов формата XML без потерь информации на основе многопоточного расщепления входных данных с сохранением связанных иерархических контекстов вложенных элементов и применения метода предсказания по частичному совпадению.

Основные задачи исследования.

1. Проведение обзора и сравнительного анализа специализированных методов предобработки и методик сжатия данных XML, по критериям степени сжатия, скорости сжатия/распаковки и объема потребляемой памяти.

2. Выбор алгоритмов моделирования источников и кодирования слабоструктурированных гипертекстовых данных, для эффективного сжатия XML.

3. Разработка метода предобработки данных XML с учетом особенностей их иерархической структуры.

4. Разработка алгоритма предобработки документов XML.

5. Разработка методики оперативного сжатия гипертекстовых документов формата XML.

6. Разработка программного обеспечения совместимого со стандартизированной технологией однопроходного разбора файлов XML.

7. Испытания ПО и анализ результатов с целью определения области эффективного применения разработанного алгоритма сжатия. Объектисследования. Слабоструктурированные данные, представленные в гипертекстовом формате XML.

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

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

1. Разработан метод декомпозиции иерархической модели слабоструктурированных гипертекстовых данных формата XML, с учетом влияния зависимостей вложенных элементов на точность прогнозирования символов при контекстном моделировании.

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

3. Разработана методика оперативного сжатия данных XML с применением предложенного алгоритма предобработки. Практическая ценность. На основе исследований, проведенных в диссертационной работе, реализован комплекс программных средств, совместимых со стандартной технологией Simple API for XML (SAX), позволяющий осуществлять оперативное сжатие документов XML.

Реализация результатов работы. Разработанное программное обеспечение используется в системе документооборота ООО «МЕКО».

Основные результаты диссертации опубликованы в 5-ти работах, в том числе 1-ой статье в журнале, рекомендованном ВАК РФ и 4-х печатных работы в сборниках научных трудов. Результаты работы докладывались и обсуждались на научных конференциях.

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

Во второй главе предложено применять для сжатия данных XML парадигму компрессии с помощью универсального моделирования и кодирования. Описаны модификации метода РРМ с наследованием информации и арифметического кодирования.

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

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

В заключении приводятся основные выводы и результаты работы.

Заключение диссертации по теме «Теоретические основы информатики», Елхов, Алексей Викторович

Выводы

Разработанная методика сжатия документов формата XML позволяет обеспечить наибольшее значение показателя средней степени сжатия данных в формате XML по сравнению с широко применяемыми в настоящее время подходами.

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

Оперативность разработанной методики позволяет устранить зависимость времени вывода первого информативного блока информации от размера передаваемого XML-документа.

Заключение

В работе получены следующие результаты и выводы:

1. Проведен обзор универсальных алгоритмов, применяющихся для моделирования источников и кодирования данных формата XML.

2. Проведен обзор и сравнительный анализ XML-ориентированных методов предобработки данных и основанных на них методик сжатия по критериям степени сжатия, скорости сжатия/распаковки и объемов потребляемой памяти.

3. Обоснован выбор метода РРМ в совокупности с интервальным кодированием для оперативного сжатия слабоструктурированных данных.

4. Показана недостаточность разбиения гипертекста на последовательности однотипных элементов для эффективного устранения неоднородности данных.

5. Выявлено влияние иерархических контекстов XML на точность прогнозирования символов.

6. Разработан метод декомпозиции иерархической модели XML с сохранением информации о связях между вложенными элементами.

7. Предложен алгоритм предобработки данных XML на основе разработанного метода декомпозиции, использующий результаты разбора файлов однопроходным анализатором SAX в качестве входных данных.

8. Разработана методика оперативного сжатия слабоструктурированных данных формата XML.

9. Разработано программное обеспечение для сжатия файлов XML с использованием модифицированного алгоритма предсказания по частичному совпадению PPMII.

10. Проведены испытания ПО, и на основе полученных результатов выявлена область эффективного применения разработанной методики.

Список литературы диссертационного исследования кандидат технических наук Елхов, Алексей Викторович, 2008 год

1. ТРС-Н XML-отчеты (выборка) баз данных низкая 34

2. Weblog Данные журналов событий Web-серверов высокая 30

3. SwissProt Последовательности кодов ДНК низкая 21

4. Extensible Markup Language (XML) 1.0 (Second Edition) W3C Recommendation. (http://www.w3.org/TR/REC-xml/). October 2000.

5. Document Object Model (DOM) Level 2 Specification Version 1.0, W3C Recommendation (http://www.w3 .org/TR/2000/REC-DOM-Level-2-Core-20001113). November 2000.3.

6. Д. А. Шкарин. Повышение эффективности алгоритма РРМ // Проблемы передачи информации. 2001. Т. 37. Вып. 3. С 44-54.

7. Augeri С. J., Mullins В. Е., Bulutoglu D. A., Baldwin R. О. An Analysis of XML Binary Formats and Compression // ExpCS '07. San Diego, California, USA. June 13- 14, 2007.

8. Augeri C. J., Mullins В. E., Bulutoglu D. A., Baldwin R. O. An Analysis of XML Compression Efficiency // Proceedings of the 2007 workshop on Experimental computer science. New York, NY, USA. Article No. 7. 2007.

9. Ng Lam W., Yeung W., Cheng J. Comparative Analysis of XML Compression Technologies // Kluwer Academic Publishers, Hingham, MA, USA. 2006. P. 5-33

10. H. Liefke , D. Suciu. XMill: an efficient compressor for XML data // Proceedings of ACM SIGMOD international conference on Management of data, May 15-18, 2000, Dallas, Texas, United States. P.153-164.

11. C. League, K. Eng. Schema-Based Compression, of XML Data with Relax NG // Long Island University Computer Science, Brooklyn, NY, USA. 2006.

12. League, C. Eng, K. Type-Based Compression of XML Data // Data Compression Conference, 2007. P. 273-282.

13. J. Min, M. Park, C. Chung. A compressor for effective archiving, retrieval, and updating of XML documents // ACM Transactions on Internet Technology. Volume 6, Issue 3. August 2006. P. 223 258.

14. J. Min, M. Park, C. Chung. XPRESS: a queriable compression for XML data // Proceedings of the 2003 ACM SIGMOD international conference on Management of data table of contents San Diego, California. 2003. P. 122-133.

15. P. Skibinski, J. Swacha, S. Grabowski. Effective asymmetric XML compression // University of Wroclaw, Institute of Computer Science, Poland. 2007.

16. P. Skibinski, J. Swacha, S. Grabowski. Combining Efficient XML Compression with Query Processing // University of Wroclaw, Institute of Computer Science, Poland. 2007.

17. P. Skibinski, J. Swacha, S. Grabowski. A Highly Efficient XML Compression Scheme for the Web // University of Wroclaw, Institute of Computer Science, Poland. 2008.

18. S. Hariharan, P. Shankar. Compressing XML Documents Using Recursive Finite State Automata // Department of Computer Science and Automation, Indian Institute of Science, India. 2005.

19. S. Hariharan, P. Shankar. Evaluating the Role of Context in Syntax Directed Compression of XML Documents // Data Compression Conference. 2006.

20. S. Harrusi, A. Averbuch, A. Yehudai. Compact XML grammar based compression // School of Computer Science, Tel Aviv University. Israel. 2007.

21. Leighton G., Diamond J., Muldner Т. AXECHOP: a grammar-based compressor for XML // Data Compression Conference, 2005. P. 467.

22. Leighton G., Diamond J., Muldner T. Treechop: A tree-based query-able compressor for XML // In Proceedings of the Ninth Canadian Workshop on Information Theory. 2005.

23. W. Ng, W.-Y. Lam, P. T. Wood, M. Levene. XCQ: A queriable XML compression system Knowledge and Information Systems, Volume 10 , Issue 4 . October 2006. P 421-452.

24. W. Ng, X. Wang, J. He, A. Jhou. MQX: multi-query engine for compressed XML data // ACM Special Interest Group on Information Retrieval, New York, NY, USA. 2007. P. 897.

25. Y. Natchetoi, H. Wu , G. Babin, S. Dagtas. EXEM: Efficient XML data exchange management for mobile applications // Information Systems Frontiers, Volume 9, Number 4, 2007. Springer Netherlands. P. 439-448.

26. M. Girardot, N. Sundaresan. Efficient Representation and Streaming of XML Content over the Internet Medium // IEEE International Conference on Multimedia and Expo (I), pp. 67-70 (2000).

27. M. Girardot, N. Sundaresan. Millau: An Encoding Format for Efficient Representation and Exchange of XML over the Web // Proceedings of the 9th International WWW Conference, pp. 747-765, May (2000).

28. P. M. Tolani, J. R. Haritsa. XGRIND: A Query-friendly XML Compressor // IEEE Proceedings of the 18th International Conference on Data Engineering (2002).

29. A. R. Schmidt, F. Waas, M. L. Kersten and M. J. Carey and I. Manolescu and R. Busse. XMark: A Benchmark for XML Data Management // Proceedings of VLDB, (2002).

30. M. Levene, P. T. Wood. XML Structure Compression //Proceedings of the Second International Workshop on Web Dynamics, May (2002).

31. M. Kalman, F. Havasi, T. Gyimothy. Compacting XML documents // Information and Software Technology, Volume 48, Issue 2. 2006. P. 90-106.

32. P. Buneman, M. Grohe, C. Koch. Path Queries on Compressed XML // Proceedings of the 29th International Conference on Very Large Data Bases (VLDB'03), May (2003).

33. A. Arion, A. Bonifati, G. Costa, I. Cnr, I. Manolescu, A. Pugliese, D. Unical. XQueC: Pushing Queries to Compressed XML Data // The Pennsylvania State University CiteSeer Archives. 2003.

34. H. Liefke, D. Suciu. An extensible compressor for XML data // ACM SIGMOD Record, Volume 29 , Issue 1. 2000. P.57-62.

35. XML Binary Characterization // www.w3.org/XML/Binary.

36. J. Ziv, A. Lempel. A Universal Algorithm for Sequential Data Compression 11 IEEE Trans. Inform. Theory, IT-23, no.3. May 1977. P. 337-343.

37. J. Ziv, A. Lempel. Compression of Individual Sequences via Variable Rate Coding//IEEE Trans. Inform. Theory, IT-24, no. 5. Sept. 1978. P. 530-536.

38. M. Burrows, D.J. Wheeler. A Block-Sorting Lossless Data Compression Algorithm // Technical Report, Digital Equipment Corporation. 1994. Palo Alto, California.

39. Cleary J.G., Witten LH. Data Compression Using Adaptive Coding and Partial String Matching// IEEE Trans. Commun. 1984. V. 32. №4. P. 396-402.

40. J. Cleary, W. Teahan, I. Witten. Unbounded Length Contexts for PPM // Proceeding of the IEEE Data Compression Conference. March 1995. P. 52-61.

41. J. G. Clearly, I. H. Witten. Data Compression Using Contexts for PPM // Computer Journal, Vol. 40, Nos (2/3). 1997. P. 67-75.

42. J. A. Storer, T. G. Szymanski: Data compression via textural substitution // ACM 29(4). 1982. P. 928-951.

43. Z. Arnavutl, S. S. Magliveras. Lexical Permutation Sorting Algorithm // The Computer Journal, 1997, 40(5). P. 292-295.

44. Ryabko, B. Ya. Data compression by means of a "book stack" // Problems Inform. Transmission 16, 1980, no. 4. P. 265-269.

45. I. H. Witten, Т. C. Bell. The Zero Frequency Problem: Estimating the Probabilities of Novel Events in Adaptive Text Compression // IEEE Trans. Inform. Theory, IT-37, no. 4. July 1991. P. 1085-1094.

46. Moffat A. Implementing the PPM Data Compression Scheme // IEEE Trans. Commun. 1990. V. 38. №11. p. 1917-1921.

47. Howard P. G. The design and analysis of efficient lossless data compression systems // PhD thesis, Brown University. 1993.

48. P. G. Howard, J. S. Witter. Practical Implementations of Arithmetic Coding // in Image and Text Compression, J. A. Storer, Ed. Norwell, MA: Kluwer Academic Publishers. 1992. P. 85-112.

49. P. G. Howard, J. S. Witter. Design and Analysis of Fast Text Compression Based on Quasi-Arithmetic Coding // in Proc. Data Compression Conference, J. A. Storer and M. Cohn, Eds. Snowbird, Utah. Mar. 30-Apr. 1, 1993. P. 98-107.

50. P. G. Howard, J. S. Witter. Analysis of Arithmetic Coding for Data Compression // Information Processing and Management, 28, no. 6, pp. 749-763, 1992.

51. I. H. Witten, R. M. Neal, J. G. Cleary. Arithmetic Coding for Data Compression // Comm. ACM, 30, no. 6. June 1987. P. 520-540.

52. A. M. Moffat, N. Sharman, I. H. Witten, Т. C. Bell. An Empirical Evaluation of Coding Methods for Multi-Symbol Alphabets // in Proc. Data Compression Conference, J. A. Storer and M. Cohn, Eds. Snowbird, Utah. Mar. 30-Apr. 1, 1993. P. 108-117.

53. Hufman D. A. A Method for the Construction of Minimum Redundancy Codes // Proceedings of the Institute of Radio Engineers, 40. 1952. P. 1098-1101.

54. J. J. Rissanen. Generalized Kraft Inequality and Arithmetic Coding // IBM J. Res. Develop., 20, no. 3., May 1976. P. 198-203.

55. F. Rubin. Arithmetic Stream Coding Using Fixed Precision Registers // IEEE Trans. Inform. Theory, IT-25, no. 6. Nov. 1979. P. 672-675.

56. J. J. Rissanen, G. G. Langdon. Arithmetic Coding // IBM J. Res. Develop., 23. no. 2. Mar. 1979. P. 146-162.

57. XMLZip XML Solutions, http://www.xmls.com/.

58. Aberg J., Shtarkov Yu.M. and Smeets BJ.M. Multialphabet coding with separate alphabetdescription, // Proc. of Compression and Complexity of Sequences 97, Positano, Salerno, Italy, IEEE Сотр. Soc. Press, 1998. P. 56 65.

59. Bloom C. Solving the Problems of Context Modeling // (http://www.cbloom.com/papers/). 1996.

60. Seward J. BZip2 v. 1.0 block-sorting file compressor (http://www.muraroa.demon.co.uk/). 2000.