Статья: Исследование зависимости времени извлечения данных из XML-файлов от объема выборки файлов в условиях избыточности данных

Самарский национальный исследовательский университет им. академика С.П. Королева

ИССЛЕДОВАНИЕ ЗАВИСИМОСТИ ВРЕМЕНИ ИЗВЛЕЧЕНИЯ ДАННЫХ ИЗ XML-ФАЙЛОВ ОТ ОБЪЕМА ВЫБОРКИ ФАЙЛОВ В УСЛОВИЯХ ИЗБЫТОЧНОСТИ ДАННЫХ

Кочетков В.С., Логанова Л.В.

Самара

Аннотация

синтаксический информация файл парсинг

В данной работе произведено исследование и сравнение двух различных методов синтаксического анализа информации, хранящейся в XML-файлах: DOMm SAX. Выполнен анализ результатов тестирования методов парсинга на различных контрольных выборках документов, при разном объеме извлекаемых данных. В результате выполнения работы было сформулированы рекомендации по выбору оптимального метода парсинга данных.

Введение

В наши дни обсуждение XML зачастую проходит в контексте Web-сервисов, преобразований Java объектов в XML и обратно, и даже использования баз данных XML вместо реляционных или объектно-ориентированных.[1] Формат очень широко используется в информационных технология, рекомендован Консорциумом Всемирной паутины ^3С).Примером применения технологии XML могут служить открытые данные информационной системы zakupki.gov.ru, доступные на соответствующем ftp: объём ежедневных обновлений - десятки и сотни тысяч XML файлов объемом в гигабайты или десятки гигабайт, в среднем раз в несколько недель выходит новая версия схемы данных.

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

В случае с ftp-сервером государственных закупок структура данных следует за требованиями законодательства. В связи с этим информация об извещениях о проведении государственных закупок представлена более чем десятком типов документов fcsNotification* в зависимости от типа закупки (электронный аукцион fcsNotificationEF, запрос котировок fcsNotificationZK, закупка у единственного поставщика fcsNotificationEP и т. п.). Все эти документы основаны на одном базовом типе извещения, но отличаются в деталях, и это требуется учитывать при импорте и анализе данных. [2]

На сайте существует ограничение в количестве результатов. Поиск выдает не более, чем 500 строк, и скачивание данных о конкурсах (в виде таблицы.csv формата) средствами сайта невозможно. При этом потребность иметь регулярно обновляемые сведения о проходящих конкурсах, попадающих под определенные критерии, возникает у каждой организации, участвующей в государственных закупках.[3]

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

DOM-парсер.

DOM (Document Object Model - объектная модель документов - платформенно-независимый программный интерфейс, позволяющий программными скриптами управлять содержимым документов HTML и XML, а также изменять их структуру и оформление. Модель DOM не накладывает ограничений на структуру документа. Любой документ известной структуры с помощью DOM может быть представлен в виде дерева узлов, каждый узел которого содержит элемент, атрибут, текстовый, графический или любой другой объект. Узлы связаны между собой отношениями родитель-потомок.

Способ доступа через DOM удобен, когда структура документа должна (или может) быть доступна в целом и легко модифицироваться - например так, как это происходит в документе Word или при формировании страницы DHTML.

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

Анализ документов методом DOMпутем парсинга XML-файла предполагает создание DocumentBuilderFactory, с помощью которой создается DocumentBuilder, который, в свою очередь, выполняет разбор XML документа для создания объекта Document и последующего извлечения информации путем прохода по всем узлам(nodes)объекта для нахождения искомых атрибутов.

Рисунок 1 Условие извлечения тега в DOM

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

SAX-парсер

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

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

Недостаток SAX - необходимость хранения состояния в процессе разбора XML-потока, то есть в случае со сложной и/или недетерминированной структурой придется частично реконструировать узловую модель для отслеживания уровней вложения.

Средства парсинга с потоковой обработкой применимы в задачах, где повторное обращение не нужно. В таком случае происходит последовательный перебор узлов до нужного и поочередная загрузка в память только текущего узла. Данные средства могут анализировать очень большие документы и подходят для таких задач, как индексация или преобразование в другие форматы (например, замена дескрипторов XML на дескрипторы HTML). [4]

SAX-парсер реализует интерфейс DefaultHandler, который использует функции обратного вызова, для извлечение данных по набору условий вида:

Рисунок 2 Условие извлечения тега в SAX

В первую очередь обрабатывается событие startDocumentKo^a синтаксический анализатор SAX разбирает XML и встречает запуск тега (например, <something>), он запускает событие tagStarted (фaктическoе название события может отличаться). Аналогично, когда конец тега встречается во время разбора (<something>), он запускаетtagEnded. Использование анализатора SAX подразумевает, что вам необходимо обрабатывать эти события и понимать данные, возвращаемые с каждым событием. Если в элементе есть содержимое, будут вызываться такие события, как characters для дополнительного текста, startElement и endElement для дочерних элементов и т.п. Заканчивается работа парсера событием endDocument.

Сравнение методов, экспериментальные исследования

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

Для сравнения времени, затрачиваемого на извлечение и обработку информации из ХМL файлов с ftp-сервера zakupki.gov.ru был выгружена и размещена на локальном компьютере контрольная выборка документов, чтобы минимизировать влияние на время обработки файлов факторов, не относящихся к теме исследования. В качестве средства реализации был выбран язык Тауа, на котором были написаны классы, реализующие описанные ранее методы обработки слабоструктурированной информации, а также классы сущностей (Simple API for XML) различными наборами атрибутов, для параллельного исследованию времени обработки различного количества файлов, исследования влияния количества извлекаемых тегов на время выполнения обработки файлов.

Эксперименты проводились для контрольных выборок документов размера N = 1000, N = 5000, N = 10000. Такие размеры был выбраны для сравнения полученных результатов с целью выявления зависимости между числом обрабатываемых документов и общим временем их обработки, и дальнейшего прогнозирования времени парсинга фиксированного набора документов.

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

И в случае работы SAX-парсера, и в случае работы DOM-парсера, набор тегов передается конструктору объекта Notification для последующей записи объекта в репозиторий.

Полученные значения времени извлечения информации при использовании8АХ-парсера отражены в таблице 1, при использовании DOM - в таблице 2.

Таблица 1

Зависимость времени выполнения парсинга XMLфайлов методом SAX от количества файлов в выборке и набора извлекаемых тегов

Следует отметить, что на время выполнения обработки существенное влияние оказывает набор извлекаемой информации. В случае использования метода SAX, и в случае использования метода DOM добавление условий для извлечения дополнительных наборов тегов значительно влияет на время обработки файлов. На рисунке 3 представлены диаграммы времени обработки контрольных наборов файлов методами DOM и SAX

Рисунок 3 Диаграмма времени обработки контрольных выборок документов методом DOM и SAX при различном наборе извлекаемых тегов (на вертикальной оси показано время в миллисекундах, на горизонтальной три группы столбцов для выборок размером N=1000, 5000, 10000 соответственно)

Использование метода SAX позволяет в среднем до 1,5 раз уменьшить время, затрачиваемое на обработку XML-файлов с целью извлечения данных по сравнению с аналогичными операциями, производимыми над тем же набором файлов, но при использовании метода DOM.

В случае SAX-парсера увеличение количества тегов в 4 раза дало прирост времени обработки файлов в 1,33 раза.

SAX и DOM подходы иногда сочетают между собой. Так, веб-браузер отображает элементы в процессе получения методом SAX, но после получения документа строит его DOM-модель для DHTML-доступа в терминах иерархии объектов. [5]

Сравнение методов, экспериментальные исследования

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

Для сравнения времени, затрачиваемого на извлечение и обработку информации из ХМL-файловс ftp-сервераzakupki.gov.ru был выгружена и размещена на локальном компьютере контрольная выборка документов, чтобы минимизировать влияние на время обработки файлов факторов,не относящихся к теме исследования. В качестве средства реализации был выбран языкТауа, на которомбыли написаныклассы, реализующие описанные ранее методы обработки слабоструктурированной информации, а также классы сущностей ИоШюайопс различными наборами атрибутов, для параллельного исследованию времени обработки различногоколичества файлов, исследования влияния количества извлекаемых тегов на время выполнения обработки файлов.

Эксперименты проводились для контрольных выборок документов размера N = 1000, N = 5000, N = 10000. Такие размеры был выбраны для сравнения полученных результатов с целью выявления зависимости между числом обрабатываемых документов и общим временем их обработки, идальнейшего прогнозирования времени парсинга фиксированного набора документов.

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