The paper presents a problem formulation for the development of a theoretical and software framework for creating systems of data extraction from arbitrary spreadsheet tables. The problem covers the tasks of the automatic recovering semantic markup of tables, conceptualization of their natural-language content, data cleaning and lineage, generating relational and linked data, as well as a synthesis of tabular data transformation systems based on table analysis and interpretation rules. We consider the state of the art methods and discuss some perspective techniques for the development of a consistent solution to this problem.
Введение. Произвольные таблицы являются распространённым способом представления информации. Они повсеместно используются в документах и веб-пространстве в форматах HTML, PDF, EXCEL, CSV. Современные оценки, сделанные на основе изучения экспериментальных срезов содержания Веба (COMMONCRAWL и CLUEWEB), показывают, что их количество исчисляется сотнями миллионов (WEB TABLE CORPORA, DRESDEN WEB TABLE CORPUS). Предположительно они содержат сотни миллиардов фактов. Такие таблицы характеризуются большим разнообразием и разнородностью компоновок, стилей и содержания, а также высокой скоростью роста их объема.
Большой объем и свойства структуры таких таблиц делают их ценным источником в приложениях науки о данных и бизнес аналитики. Однако, как правило, они не сопровождаются явной семантикой необходимой для машинной интерпретации своего содержания так, как задумано их автором. Накапливаемая в них информация часто является неструктурированной и не стандартизированной. Анализ этих данных нуждается в их предварительном извлечении и трансформации к структурированному представлению с заданной формальной моделью.
Сегодня, сталкиваясь с перечисленными задачами, исследователи и разработчики прибегают к инструментальным средствам общего назначения, часто предлагая собственные реализации однотипных задач. В сравнении с последними, специализированные инструментальные средства могут позволить сократить время разработки целевого программного обеспечения, скрывая несущественные детали и фокусируясь на обозначенной проблемной области. Это особенно важно в тех случаях, когда необходимо в короткие сроки и при недостатке ресурсов разработать заказное или исследовательское программное обеспечение для массовой обработки слабоструктурированных данных из разнотипных произвольных таблиц.
Проблема управления и интеграции неструктурированной информации включает вопросы извлечения данных из таблиц произвольной формы, представленных в веб-страницах, текстовых и табличных документах. Извлечения табличных данных состоит в восстановлении недостающих структурных и содержательных метаданных (семантики) произвольной таблицы. Как правило произвольная электронная таблица не включает метаданные, описывающие ее структуру и содержание. Неизвестно то, какие роли играют её ячейки (например, содержат ли они данные или атрибуты), как они связаны между собой (например, какие заголовки адресуют значение данных), какими предметными понятиями (категориями) описывается её содержание. Решение обозначенных вопросов позволяет перейти от произвольной (слабоструктурированной) формы таблиц к некоторому структурированному представлению данных (например, реляционной базе данных).
Научная значимость решения этой проблемы определяется расширением знаний о природе произвольных электронных таблиц и процессах их преобразования в структурированную форму. Решение проблемы вносит важный вклад в ряд научных направлений, где произвольные таблицы являются естественным объектом исследований. К таким направления относятся: управление неструктурированными данными (вопросы интеграции табличной информации), информационный поиск (вопросы извлечения данных из произвольных таблиц), а также семантический веб (вопросы формирования открытых связных данных).
В работе предлагается создать теоретическую и инструментальную платформы ускоренной разработки систем извлечения данных из произвольных электронных таблиц. Поставленная задача охватывает исследование и разработку следующих вопросов: (1) алгоритмов ролевого и структурного анализа таблиц (автоматического восстановления их синтаксической и семантической разметки); (2) алгоритмов интерпретации таблиц (очистки и концептуализации их естественно-языкового содержания); (3) объектной модели и формального языка трансформации табличных данных; (4) инструментов синтез исходного кода программ трансформации табличных данных; (5) инструментов генерации реляционных и связных данных из произвольных таблиц.
Современное состояние исследований. Два последних десятилетия активно развиваются методологические основы извлечения и трансформации данных из таблиц, представленных в веб-страницах, текстовых и табличных документах. В работах [1, 6, 8, 11, 16, 22, 24, 27, 29] предлагаются методы ролевого и структурного анализа таблиц (восстановления отношений между ячейками). Каждый из этих методов ограничен обработкой небольшого количества (1-5) широко распространенных видов табличных компоновок. Однако, многие виды таблиц специфичных для некоторых областей (например, паспорта безопасности продуктов в химии или паспорта электротехнического оборудования в энергетике) остаются неохваченными.
Методы интерпретации таблиц [5, 9, 23, 26, 30, 31] предназначены для связывания табличного содержания с внешними концепциями (предметными онтологиями, глобальными таксономиями, открытыми связными данными). В основном, они полагаются на анализ естественно-языкового содержания таблиц и их контекста, пренебрегая их компоновочными и стилевыми особенностями. На практике, это бывает недостаточно, например, часть информации может выражаться через различные шрифтовые или цветовые свойства.
Продолжают развиваться специализированные инструменты для извлечения и трансформации данных из произвольных электронных таблиц в структурированную форму, в т. ч., системы трансформации табличных данных [2, 3, 7, 16–21], системы извлечения связанных данных [13–15, 25, 28]; TANGO ― система трансформации произвольных таблиц к реляционной форме на основе поиска критических ячеек [11, 27]; SENBAZURU ― система извлечения реляционных данных из таблиц с иерархиями заголовков [6], DEEXCELERATOR ― система нормализации данных электронных таблиц к реляционной форме [10]. Инструменты TANGO, SENBAZURU и DEEXCELERATOR преследуют схожие цели с нашими ― преобразовать таблицы от произвольной к реляционной форме. Однако, они используют заданные модели исходных таблиц, при которых смешивается их физическая и логическая компоновка. Это ограничивает возможности их применения сводными таблицами характерными для статистических отчетов.
Анализ современного состояния исследований в рассматриваемой области показывает, что на сегодняшний день не существует специализированных библиотек моделей и платформ для разработки систем извлечения и трансформации табличных данных. Кроме того, нет инструментальных средств, в которых извлечение и трансформация данных выражаются как последовательность известных операций автоматического анализа и интерпретации таблиц. Ценность извлекаемых данных может быть повышена путем их связывания со свободными глобальными таксономиями понятий общего назначения, например, DBPEDIA, YAGO, WIKIDATA, WIKITOLOGY. Согласованные, непротиворечивые и обогащенные URI данные могут быть использованы при дальнейшей их интеллектуальной обработке или построении на их основе интеллектуальных систем. Исследования в данной области представлены работами [12, 17, 25] и др. Однако, перспективным является создание не только связанных RDF и OWL онтологий, но создание узкоспециализированных проблемно-ориентированных таксономий и онтологических паттернов.
Предлагаемые подходы. Процесс извлечение данных из произвольной таблицы включает следующие этапы: (i) ролевой анализ (извлечение единиц данных из табличного содержания и сопоставление их с функциональными ролями); (ii) структурный анализ (восстановление связей между единицами табличных данных); (iii) интерпретация (ассоциирование единиц табличных данных с категориями внешних словарей).
Анализ таблиц может базироваться на следующих решениях: (i) алгоритмах извлечения единиц данных (вхождений, меток, ссылок) из естественно-языкового содержания ячеек на основе восстановления литеральных типов данных и распознавания именованных сущностей; (ii) алгоритмах выделения типичных функциональных областей ячеек (боковик, шапка, тело, подвал, итог) на основе выделения кластеров по восстановленным литеральным типам (распознанным именованным сущностям) и эвристик поиска критических ячеек типа MIPS (Minimum Indexing Point Search); (ii) алгоритмах восстановления иерархических отношений между единицами данных в типичных функциональных областях на основе обучения по прецедентам (предполагается создать модели выбора таких отношений среди кандидатов; сформировать обучающие выборки на основе разметки существующих корпусов таблиц; рассматривать, как компоновочные, так и стилевые признаки, связанные с извлечёнными единицами данных).
Многие ошибки этой фазы возникают из-за того, что произвольные таблицы ориентированы прежде всего на восприятие человеком. Их физическая (синтаксическая) разметка часто не совпадает с визуальной разметкой (передаваемой прочерченными границами), которою читает человек. Например, одна визуальная ячейка может быть составлена из нескольких физических. Для уменьшения ошибок такого рода планируется исследовать возможность реконструкции физической (машиночитаемой) структуры ячеек по их визуальной (человекочитаемой) структуре. Предлагается разработать алгоритмы реконструкции на основе анализа визуальных границ ячеек.
Интерпретация таблиц обеспечивается за счет применения свободных глобальных таксономий понятий общего назначения (DBPEDIA, YAGO, WIKIDATA, WIKITOLOGY) для понимания и концептуализации естественно-языкового содержания произвольных таблиц. Благодаря свойствам табличной компоновки, возможно выделить каждый набор единиц данных, относящихся к одной неизвестной категории. Каждая единица (гипоним) может быть ассоциирована с одной или несколькими категориями (гиперонимами) из заданной глобальной таксономии. Его окружение (гипонимы из того же набора) может использоваться, чтобы уточнить его категорию. Кроме того, предлагается задействовать техники очистки данных для удаления знаков-заполнителей, ссылок на сноски, "мусорных" слов ("из них", "всего" и др.), вычислимых (агрегированных) значений.
Язык правил трансформации произвольных таблиц CRL предлагается усовершенствовать на основе расширения его функциональных возможностей алгоритмами, реализованными в рамках проекта. Планируется разработать специализированный диалект этого языка для выражения лаконичных программ трансформации данных электронных таблиц в виде наборов правил. При этом одна программа может охватывать широкий диапазон произвольных таблиц, разных на просвет, но разделяющих общий набор компоновочных, стилевых и содержательных свойств. В процессе исполнения правила трансформации табличных данных должны отображать факты о физической структуре таблицы (данные о компоновке, стиле и содержании) в факты о ее логической структуре (функциональные единицы и их семантические связи). Для представления фактов предлагается дополнить язык объектной моделью таблицы со строгим разделением физической и логический структуры.
Синтез исходного кода программ трансформации табличных данных. Планируется также дополнить развиваемый язык специализированным диалектом для генерации исходного кода программ трансформации табличных данных в формате языка общего назначения. Предлагается разработать формальную (ANTLR) грамматику предлагаемого языка, объектную модель и интерпретатор данного языка. Это позволит реализовать синтаксический разбор наборов правил, восстановления объектной модели программы и её интерпретацию для синтеза целевого исходного кода. Предполагается, что порожденная программа не должна требовать доработки для компиляции и запуска, но может быть расширена, если это необходимо.
Генерация реляционных и связных данных из произвольных таблиц. Предлагается обобщить опыт исследователей в данной области, в частности [12, 17, 25], и рассмотреть процесс генерации связанных данных как некую последовательность этапов: выявление классовкандидатов из открытой таксономии (далее, LOD), соответствующих столбцам; соотнесение значений ячеек таблиц с соответствующим объектам LOD (если это возможно); выявление отношений между столбцами таблицы и их связь со свойствами LOD; генерация связанного представления данных с указанием URI в формате RDF. Достаточно интересными подзадачами в рамках подхода являются выбор метрик для вычисления близости между понятиями, а также подбор релевантных узлов.
Предлагаемые подходы соответствуют современному мировому уровню исследований. Они во многом преодолевают ограничения присущие мировым конкурентным проектам (TANGO, SENBAZURU и DEEXCELERATOR). В частности, предлагается реализовать принципиально новую объектную модель и формальный язык трансформации табличных данных. По сравнению с конкурентными решениями это позволит работать не только с широко-распространенными, но и со специфичными типами произвольных таблиц. В отличие от конкурентных языков, где табличная компоновка задается строго (например, в абсолютных координатах), нами впервые предлагается язык для выражения неизменяемых компоновочных, стилевых и содержательных свойств, разделяемых некоторым набором таблиц. Таким образом, одна программа может обрабатывать существенно более широкий диапазон произвольных таблиц. Кроме того, впервые предлагается разработать инструменты синтеза программных систем трансформации табличных данных от произвольной к реляционной форме.
Заключение. Проектируемая платформа открывают новые возможности интеллектуализации для ускоренной разработки программного обеспечения извлечения информации в научных и индустриальных приложениях с интенсивным использованием разноструктурированных табличных данных. Планируемые результаты расширяет теоретические знания в области разработки программного обеспечения систем интеграции разнородных табличных данных больших объемов. Результаты проекта внесут вклад в решение следующих проблем: интеграция слабоструктурированной табличной информации, извлечение данных из произвольных таблиц, а также формирование открытых связных данных.
Результаты могут использоваться на практике в сфере бизнес аналитики и науки о данных. Они могут быть положены в основу создания новых наукоёмких технологий, продуктов и услуг интеграции слабоструктурированной табличной информации в приложениях аналитики данных. Особенный интерес для их применения представляет аналитика данных в сферах с интенсивным использованием электронных таблиц (например, финансы, экономика, государственное и бизнес управление). В качестве апробации разрабатываемой платформы предлагается рассмотреть задачи автоматизированного заполнения баз данных: опасных химических веществ, на основе анализа их деклараций, а также результатов диагностирования в рамках проведения экспертизе промышленной безопасности опасных объектов в нефтехимии [4] на основе анализа электронных отчетов.
Работа выполнена при финансовой поддержке Российского научного фонда (грант № 18-71-10001). Результаты получены при использовании ЦКП «Интегрированная информационно-вычислительная сеть Иркутского научно-образовательного комплекса» (http://net.icc.ru).