Обґрунтовано доцільність використання методів екстракції структурованих даних з множини HTML-сторінок для здійснення інформаційного пошуку в мережі Internet. Проаналізовано основні методи екстракції структурованих даних з множини веб-сторінок, які сформовані спільним сценарієм, але різними наборами даних. Розглянуто класифікацію методів за ступенем автоматизації (фактору впливу користувача) процесу формування шаблону. Детально описано принципи роботи основних неконтрольованих методів (Roadrunner, FiVaTech, Trinity), розглянуто їхні переваги та недоліки. Обґрунтовано доцільність використання методу Trinity для екстракції даних порівняно з іншими методами. Показано проблему вибору вхідних документів методу серед множини HTML-сторінок для формування узагальненого шаблону. Проведено експериментальну перевірку методу Trinity на множині HTML-сторінок англомовних статей українських наукових журналів. Для формування тестової множини HTML-сторінок виконано автоматизований обхід веб-сайтів журналів за допомогою пошукового роботу. Реалізацію пошукового роботу здійснено за рахунок обробки об'єктної моделі HTML-документів, отриманих з веб-сайтів. Шаблони (регулярні вирази), сформовані методом Trinity, застосовано до всього набору вхідних HTML-сторінок. Результати екстракції - структуровані дані про статті (назва, автори, анотація, ключові слова) - експортовано до бази даних з можливістю їх подальшого аналізу. Здійснено порівняння отриманих результатів з даними про статті, одержаними за допомогою аналізу об'єктної моделі веб-сторінок власноруч. Обраховано похибку використання методу Trinity на експериментальній множині HTML-сторінок. Ключові слова: екстракція даних; методи екстракції; класифікація методів екстракції; метод Trinity; тернарне дерево документу; префіксний обхід дерева; об'єктна модель HTML-сторінки; автоматизоване збирання веб-сторінок; пошуковий робот; шаблон HTML-сторінки; формування регулярного виразу. Обоснована целесообразность использования методов экстракции структурированных данных из множества HTML-страниц для осуществления информационного поиска в сети Internet. Проанализированы основные методы экстракции структурированных данных из множества веб-страниц, которые сформированы общим сценарием, но разными наборами данных. Рассмотрена классификация методов по степени автоматизации (фактора влияния пользователя) процесса формирования шаблона. Подробно описаны принципы работы основных неконтролируемых методов (Roadrunner, FiVaTech, Trinity), рассмотрены их преимущества и недостатки. Обоснована целесообразность использования метода Trinity для экстракции данных по сравнению с другими методами. Показана проблема выбора входных документов метода среди множества HTML-страниц для формирования обобщенного шаблона. Осуществлена экспериментальная проверка метода Trinity на множестве HTML-страниц англоязычных статей украинских научных журналов. Для формирования тестового множества HTML-страниц выполнено автоматизированный обход веб-сайтов журналов с помощью поискового робота. Реализацию поискового робота осуществлено за счет обработки объектной модели HTML-документов, полученных с веб-сайтов. Шаблоны (регулярные выражения), сформированные методом Trinity, применены ко всему набору входных HTML-страниц. Результаты экстракции - структурированные данные о статьях (название, авторы, аннотация, ключевые слова) - экспортировано в базу данных с возможностью их последующего анализа. Осуществлено сравнение результатов экстракции с данными о статьях, полученными с помощью самостоятельного анализа объектной модели веб-страниц. Рассчитана погрешность использования метода Trinity на экспериментальном множестве HTML-страниц. Ключевые слова: экстракция данных; методы экстракции; классификация методов экстракции; метод Trinity; тернарное дерево документа; префиксный обход дерева; объектная модель HTML-страницы; автоматизированный сбор веб-страниц; поисковый робот; шаблон HTML-страницы; формирование регулярного выражения. The expediency of using methods of structured data extraction from a set of HTML pages for the information search in the Internet is substantiated. The main methods of structured data extraction from the set of web pages, which are formed by a common scenario with different sets of data, are analyzed. The classification of methods according to the degree of automation (the factor of user influence) of the template formation process is considered. The principles of work of the main unsupervised methods (Roadrunner, FiVaTech, Trinity) are described in detail. Advantages and disadvantages of methods are shown. The expediency of using the Trinity method for data extraction in comparison with other methods is substantiated. The problem of choosing input documents for method among a set of HTML pages for generating a common template is considered. Experimental verification of Trinity method on the set of HTML pages, which represent articles of Ukrainian scientific journals, is made. To create a test set of HTML pages, an automated crawl of web site is performed. The realization of the search bot is done by processing the object model of HTML documents obtained from web sites. Templates (regular expressions) formed by the Trinity method are applied to the entire set of input HTML pages. Extraction results (structured data about articles) are exported to the database with the possibility of further analysis. The obtained results are compared with the data about the articles obtained by the manual analysis of the object model of web pages. The error in using the Trinity method on the experimental set of HTML pages is calculated.
неструктурованих даних. Відсутність стандартного представлення набору даних на веб-ресурсі призводить до
необхідності аналізу кожної веб-сторінки окремо, що значно ускладнює процес пошуку інформації. Нова
концепція розвитку мережі Internet – семантичний веб – впроваджується організацією W3C для стандартизації
формату представлення даних на веб-ресурсі [
Roadrunner. Метод Roadrunner був запропонований у 2001 році [
FiVaTech. Принцип роботи методу FiVaTech [
Trinity. Метод Trinity [
Таблиця 1. Порівняння методів екстракції інформації з веб-сторінок Метод Roadrunner FiVaTech
Trinity Кількість документів для формування шаблону
2 2 і більше 2 і більше Тип вхідних даних
Часова складність DOM-дерево DOM-дерево Рядок Поліноміальна
–
Поліноміальна
Для програмної реалізації екстракції даних з веб-сторінок доцільно обрати метод Trinity. Головною
перевагою методу Trinity є можливість роботи з HTML-документами, які мають некоректно сформовану
розмітку, що дозволяє уникнути попередньої обробки вхідних документів. Крім того, метод Trinity має
графічне представлення інформації – тернарне дерево, тому дозволяє відслідкувати процес знаходження
спільних елементів шаблону та проаналізувати хід процесу формування загального шаблону.
Проблемою застосування будь-якого з наведених вище методів екстракції даних з веб-сторінок є процес
формування колекції HTML-документів з множини вхідних документів для побудови шаблону. Шаблон
повинен бути універсальним, тобто відповідати всім варіантам веб-сторінок, сформованих спільним
сценарієм, але різними наборами даних. Тому до колекції документів мають входити веб-сторінки, які
містять елементи розмітки чи навіть фрагменти тексту, унікальні відносно інших веб-сторінок. Наприклад,
розглянемо наступні фрагменти вхідних HTML-документів, які описують інформацію про випуск наукового
журналу:
<b>Data Rec., Storage & Processing. — 2017. — Vol. 19, N 1.</b>
<b>Data Rec., Storage & Processing. — 2016. — Vol. 1, N 2.</b>
<b>Data Rec., Storage & Processing. — 2016. — Vol. 2, N 3.</b>
Фрагмент сформованого шаблону для наведених вище рядків виглядатиме так:
<b>Data Rec., Storage & Processing. — 201{A}. — Vol. {B}, N {C}.</b>,
де A, B, C – мітки, які описують змінне значення. Але такий шаблон не відповідатиме рядку, який міститиме
інформацію про випуск журналу 2005 року:
<b>Data Rec., Storage & Processing. — 2005. — Vol. 1, N 1.</b>
Тобто, вибір вхідних документів для формування шаблону є важливим кроком перед початком роботи
будь-якого з наведених вище методів, адже саме різноманітність розмітки та даних веб-сторінок дозволить
сформувати узагальнений регулярний вираз, відповідний всім можливим варіантам досліджуваної
веб-сторінки.
Експериментальна перевірка функціонування методу Trinity
Для програмної реалізації методу Trinity та перевірки його функціонування було створено застосування.
Предметом аналізу обрано веб-сторінки статей різних українських наукових журналів з метою отримання
корисної інформації про статтю: назва, автори, анотація тощо. Завданням застосування є автоматизоване
збирання інформації про статті з веб-сайтів журналів, отримання набору даних з веб-сторінок за допомогою
методу Trinity та перевірка коректності отриманих результатів.
Приклад роботи застосування. Розглянемо на прикладі обробки журналу «Реєстрація, зберігання і обробка
даних» [
1) 2) 3) 4)
Matov; 06. — Vol. 8, N 4; 64-74; width="25px" alt="">PDF,DOC;
Generalized noise combating codes for the use in the tasks of providing integrity of information holding objects in the conditions of natural factors influence are proposed. Fig.: 3. Refs.: 4 titles.;
distortion discovery, distortion correction, integrity control, noise combating correcting codes.;
References</td><td>1. Матов О.А., Василенко В.С. Узагальнені завадостійкі
коди в задачах забезпечення цілісно-сті інформаційних об’єктів. Код
умовних лишків. // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8,
№ 3. — С. 48–66.<br>2. Дубровский В.В. CDMA — взгляд глазами профессионала
// mailto:v_dubrovskii@mail.ru.<br>3. Акушский И.Я., Юдицкий Д.И. Машинная
арифметика в остаточных классах. — М.: Сов. радио, 1966. — 421 с.<br>4.
Василенко В.С., Будько М.М., Короленко М.П. Контроль и відновлення
цілісності інформації в автоматизованих системах // Правове, нормативне та
метрологічне забезпечення Системи захисту інформації в Україні. — К.: НТУУ
«КПІ», 2002. — Вип. 4. — С. 119–128.;
10) File;
11) stattja.doc;
12) null.
Серед отриманих даних варто зазначити назву статті, авторів, анотацію і ключові слова (рядки № 5–8). Інші
рядки можуть не мати змістовного навантаження для користувача без контексту. Наприклад, рядок № 2
описує рік та номер журналу, а рядок № 3 вказує на сторінки розміщення статті у журналі.
Отримання інформації про статті власноруч. Для перевірки коректності результатів, отриманих методом
Trinity, здійснюється екстракція даних з веб-сторінок шляхом обробки об’єктної моделі HTML-документу.
Внаслідок аналізу розмітки веб-сторінки створюється алгоритм пошуку атрибутів статті у DOM-дереві
документа для поточного веб-сайту.
Оцінка похибки функціонування методу Trinity. Атрибути статей, отримані шляхом застосування методу
Trinity та аналізу об’єктної моделі HTML-сторінки, порівнюються між собою. У випадку невідповідності
одного з атрибутів статті фіксується випадок помилкової екстракції даних. Похибка розраховується як
відношення кількості помилково розпізнаних статей до загальної кількості вхідних документів.
Створене застосування реалізовано у вигляді двох сценаріїв, які здійснюють наступні функції:
1) автоматизоване збирання веб-сторінок статей з веб-сайтів наукових журналів;
2) екстракція змінних значень з множини HTML-документів за допомогою методу Trinity та оцінка
отриманих результатів.
Консольні сценарії реалізовано мовою програмування Java (версія SE 8). Розглянемо більш детально роботу
кожного зі сценаріїв.
Сценарій 1. Автоматизоване збирання веб-сторінок. Автоматизоване збирання веб-сторінок здійснено
за допомогою реалізації пошукового роботу для сайтів наукових журналів. Алгоритм обходу
для кожного сайту є унікальним. Робот починає пошук з початкової HTML-сторінки, заданої
користувачем. На сторінці, яка розглядається роботом як DOM-дерево, здійснюється пошук необхідних
посилань на сайті. Знайшовши посилання, робот переходить до наступних сторінок; якщо робот потрапив
на сторінку статті, він здійснює мінімізацію отриманого HTML-документу та зберігає вміст документу до
текстового файлу.
Пошуковим роботом було здійснено пошук англомовних веб-сторінок статей журналів. В таблиці 2
наведений результат роботи пошукового роботу для сайтів наукових журналів. Для обробки
HTML-документів використано бібліотеку Jsoup [
Системні
дослідження та
інформаційні
технології [
Системні дослідження та інформаційні
технології Наявність англомовної версії Початковий рік статей на сайті Кінцевий рік статей
на сайті 2005 2008 2017 2017 Кількість знайдених статей 517 478 інструментів обходу DOM-дерева. Також за допомогою бібліотеки Jsoup здійснено мінімізацію документів для пришвидшення роботи наступного сценарію. Таблиця 2. Результат роботи пошукового роботу Сценарій 2. Екстракція змінних значень з множини HTML-документів. Для формування шаблону обрано 20 % вхідних документів. Попередньо множину вхідних документів було впорядковано за датою та номером випуску журналів. Вибір вхідних документів методу Trinity здійснено рівномірно по впорядкованій множині веб-сторінок. Такий підхід обумовлений необхідністю врахування особливостей розмітки та даних веб-сторінок статей всіх років для кращого узагальнення шаблону. Результатом застосування сценарієм методу Trinity до набору вхідних документів є шаблон (регулярний вираз). Отриманий шаблон сформований згідно з синтаксисом регулярних виразів у мові програмування Java. Для роботи з регулярними виразами використано пакет java.util.regex. Далі застосовано шаблон до множини всіх статей, отриманих з веб-версії журналу. Результатом застосування шаблону до веб-сторінки є набір змінних значень. У випадку невідповідності шаблону веб-сторінці набір таких значень відсутній. Результати екстракції даних з веб-документів були експортовані до бази даних MySQL. Наступним кроком є здійснення перевірки коректності рядків, які відповідають інформації про статтю: Для перевірки коректності наведених вище рядків було створено окремий програмний компонент сценарію. Функцією програмного компонента є отримання атрибутів статті за допомогою аналізу DOM-дерева різних веб-сторінок. Для роботи з DOM-деревом використано бібліотеку Jsoup. Пошук атрибутів статті здійснено за допомогою CSS-запитів та обходу об’єктної моделі веб-сторінки. Отримані структуровані дані про статті було експортовано до бази даних MySQL. Результат роботи програмного компоненту було порівняно з вихідними даними методу Trinity. Стаття вважалася нерозпізнаною у випадку невідповідності щонайменше одного з атрибутів. Порівняння результатів було здійснено за допомогою виконання відповідних SQL-запитів. Результати аналізу отриманих даних наведено в таблиці 3.
Кількість змінних значень на сторінці Загальна кількість статей 517 478 Таблиця 3. Результати аналізу екстрагованої інформації Відсоток статей, які не відповідають шаблону 2.5 % 0 % Відсоток помилково розпізнаних статей 1.6 % 3.7 % Відсоток статей, які не відповідають шаблону, дозволяє зробити висновок про успішність вибору вхідного набору веб-сторінок для формування регулярного виразу. Ненульові показники цього значення (2.5 %) означають, що серед вхідних веб-сторінок методу Trinity були відсутні деякі документи з унікальними елементами розмітки чи тексту. Врахування цих документів для створення регулярного виразу дозволить сформувати більш універсальний шаблон та зменшити наведений вище показник невідповідності. Показники помилково розпізнаних статей вказують на похибку роботи методу Trinity та якість вибору документів для формування шаблону. Невідповідність результатів методу Trinity фактичній інформації про статтю обумовлена наявністю в отриманих атрибутах статті певних додаткових елементів розмітки, що може вказувати на некоректність розмітки HTML-документа чи особливості генерації веб-сторінок на сервері. Проаналізовано методи екстракції змінних значень з веб-сторінок і обґрунтовано ефективність (з точки зору узагальнення сформованого шаблону) застосування методу Trinity. Обмеженням методу Roadrunner є можливість формування шаблону тільки з двох документів, а для коректної роботи методу FiVaTech необхідне попереднє вирівнювання вхідних документів згідно зі специфікацією XHTML. На відміну від двох останніх метод Trinity може працювати з довільною кількістю HTML-документів, в тому числі з тими, які мають некоректно сформовану розмітку. Крім цього, шаблон, сформований методом Trinity, має коректну розмітку незалежно від структури вхідних документів, що дозволяє здійснювати подальшу обробку шаблона як об’єктної моделі HTML-сторінки. Отримано експериментальні результати застосування методу Trinity до веб-сторінок статей українських наукових журналів і показано можливість використання цього методу для екстракції структурованих даних з HTML-документів та їх подальшої обробки. Зменшення похибки роботи методу можливе за рахунок покращення алгоритму вибору вхідного набору HTML-документів для генерації шаблону.