В работе обсуждаются вопросы автоматизации процесса понимания таблиц, т.е. восстановления изначально отсутствующей в них информации о семантических отношениях (пары вида, ячейка-роль, метка-значение, метка-метка, метка-измерение). Предлагается подход, при котором понимание таблицы реализуется как исполнение правил анализа табличной структуры. На основе этого подхода разработана система для массового преобразования неструктурированной табличной информации, представленной в формате табличного процессора Excel, к структурированному виду. Результатом понимания таблиц являются структурированные данные ― таблицы в канонической форме, которые структурно соответствуют таблицам реляционной базы данных. Полученные экспериментальные результаты показывают эффективность применения предлагаемого подхода для широкого класса сводных таблиц из статистических отчетов.
По оценки исследователей Merrill Lynch [
Многие исследователи, в том числе, W. Inmon
[
На практике решения многих задач связаны с необходимостью извлекать информацию из таких таблиц и загружать её в базы данных. Поскольку, таблицы, представленные в неструктурированном виде, часто оказываются единственным доступным источником информации. Только после преобразование такой табличной информации к структурированной форме она становится доступной для использования в бизнес-аналитике, включая, аналитическую обработку в реальном времени (OLAP), интеллектуальный анализ данных, и извлечение знаний.
В литературе рассматриваются следующие задачи, которые являются преобразованием неструктурированной табличной информации к структурированному виду.
1) Каноникализация таблицы [
2) Извлечение информации из таблицы [
3) Понимание таблицы [
Как определяется в работе [
Существует огромное разнообразие способов
изображения таблиц. Это приводит к высокой
сложности анализа и обработки
неструктурированной табличной информации. Как
показано в обзорах [
Вопросы понимания таблиц, связанные с
задачами их (3) функционального и (4) структурного
анализ, а также (5) интерпретации, рассматриваются
в ряде работ [
В работах Douglas S. и др. [
Предлагаемый Tijerino Y. и др. [
В перечисленных работах [
W. Gatterbauer и др. в работе [
В работе D.W. Embley и др. [
В отличие от приведенных исследований нами предлагается автоматизировать понимание таблиц за счет анализа и интерпретации, как их естественно-языковой, так и пространственной и графической (стилевой) информации. 3 Представление фактов о таблицах
Для понимания таблиц нами предлагается подход, основанный на исполнении правил анализа структуры таблиц. Идея, лежащая в основе предлагаемого подхода, состоит в следующем. Обычно внутри тематической коллекции документов от одного поставщика таблицы компонуются и форматируются однообразно. Для такой коллекции документов можно определить набор формализованных правил анализа табличной структуры, который удовлетворяет всем или почти всем ее таблицам. Эти правила можно представить в виде базы знаний, а процесс восстановления семантических отношений в таблице реализовать как логический вывод. При этом база фактов, используемая в процессе логического вывода, может включать информацию о пространственном, графическом и естественно-языковом содержании таблицы. 3.1 Базовые предположения о таблицах
На основе ограничений табличной структуры, характерных для представлений табличной информации в широко распространенных форматах данных, таких как Excel, Word, HTML и LaTeX, предлагается достаточно общая модель таблицы CELLS, которая ориентирована на представление фактов о табличной информации в процессе логического вывода. В модели сделано несколько общих для этих представлений предположений.
1) Ячейка может располагаться в одной или нескольких соседних строках и в одном или нескольких соседних столбцах (например, атрибуты COLSPAN и ROWSPAN в HTML) и имеет прямоугольную форму в пространстве строк и столбцов, как показано на рис. 1, а.
2) Внутри ячейки не могут располагаться другие ячейки или таблицы (это не допускается в Excel).
3) Содержимое ячейки может являться либо
меткой (заголовком), либо вхождением (данными).
Используемые здесь термины «вхождение» и
«метка» соответствуют смыслу терминов «entry» и
«label» соответственно из работы Wang X. [
4) Метки могут адресовать вхождения либо в строках ― метки строк, либо в столбцах ― метки столбцов.
Рис. 1. Примеры объединения плиток сетки в ячейки таблицы, обозначенные как 1, 2 и 3: так ячейка может объединять несколько плиток
в Excel, Word, HTML и LaTeX (а); так ячейка может визуально (для восприятия человеком) включать несколько плиток с помощью разграфки (б); скорее всего, так ячейки никто не представляет (в) Очевидно, что сделанные предположения описывают широкий класс обрабатываемых таблиц. Пример сводной таблицы, полностью укладывающейся в данную модель, приводится на рис. 2.
Рис. 2. Пример сводной таблицы 3.2 Модель таблицы
Модель включает два уровня: физической и логической структуры, которые в упрощенном виде можно описать следующим образом.
1) Уровень физической структуры Tp=(Sr, Sc, С) состоит из: (1) пространства строк ― Sr и столбцов ― Sc; (2) набора ячеек ― С, в котором каждая ячейка ― с=(p, c', S) включает: координаты в пространстве строк Sr и столбцов Sc ― p=(cl, rt, cr, rb), содержание ― c', стилевая информация (цветовые схемы, шрифтовые метрики, выравнивание, стили оформлении границ и др.) ― S.
2) Уровень логической структуры Tl=(D, Lr, Lc, E) состоит из: (1) набора представленных в обрабатываемой таблице измерений ― D={Di}, каждое из которых содержит значения Di={dj}; (2) дерева меток строк ― Lr и (3) столбцов ― Lc, отражающих связи между метками, не являющимися значениями измерений Di из набора D ― l=(l'), где l' ― содержание метки; (4) набора вхождений ― E, в котором каждое вхождение ― e=(e', D', L') включает: содержание ― e', набор связанных с ним значений измерений Di из набора D ― D', набор связанных с ним меток из деревьев Lr и Lc ― L'. 3.3 Структуры данных
Предлагаемая в работе модель таблицы реализована в виде ряда структур данных, основные из которых перечислены далее: CELL, ENTRY, LABEL, LABELNODE. Структура CELL предназначена для представления ячейки и прежде всего информации о её физической структуре, однако она также включает уровень логической структуры ячейки (т.е. она позволяет накапливать информацию о ее связях с другими ячейками, ее роли и типе данных). На практике это позволяет разрабатывать правила анализа табличной структуры в более лаконичной манере по сравнению со случаем, при котором используются дополнительные структуры данных для представления информации уровня логической структуры. Структуры ENTRY, LABEL, LABELNODE используются исключительно на уровне логической структуры. ENTRY служит для представления вхождения, а LABEL — метки. Структура LABELNODE является оболочкой для структуры LABEL и обеспечивает представление деревьев меток.
Все предложенные структуры данных и алгоритмы реализованы на платформе Java. Это обеспечивает возможность использовать их напрямую для представления фактов о таблицах в процессе логического вывода, выполняемого в системе исполнения правил с поддержкой спецификации JSR-94 (Java Rule Engine API). $c : CCell( cl == 1, style.getFont().getColor() == "#ff0000") modify ( $c ) { setRole( Role.ROWLABEL ) } $c1 : CCell() 4. Представление и исполнение правил анализа табличной структуры
Схема преобразования табличной информации
от неструктурированной к структурированной
форме показана на рис. 3. Предполагается, что
этапы обнаружения и распознавания таблицы
выполняются в сторонних системах. Например, для
извлечения таблиц из PDF документов могут
использоваться системы Tabula [
приведены к В процессе загрузки таблиц из полученных файлов Excel, HTML или XML в структуры данных, реализующих модель CELLS, табличная информация подвергается предобработки. Это включает опционально: удаление лишних пробельных и служебных символов из текстового содержания, исключение из таблицы пустых строк и столбцов и восстановление отсутствующих настроек стилей границ ячеек. Последнее необходимо, поскольку видимые и физические границы ячейки не всегда совпадают. Визуально они могут быть образованы границами соседних ячеек. Приведение стилей физических границ ячеек в соответствии с её видимыми границами позволяет упростить правила анализа структуры таблицы.
Полученные в результате данные о таблице, которые формируют базу фактов для логического вывода. Кроме того, факты могут быть дополнены внешней информацией об измерениях.
Для обработки набора таблиц формируется база знаний, которая состоит из продукционных правил анализа табличной структуры. Они отображают доступную информацию: позиции (координаты), графическое форматирование и естественноязыковое содержание ячеек, в отсутствующие изначально отношения между метками, вхождениями и измерениями. Полученные в процессе вывода новые факты о семантических отношениях должны быть достаточными для каноникализации таблицы.
В качестве система исполнения таких правил
может использоваться свободная системы Drools
Expert [
На Рис. 4 приводится ряд простых примеров возможных правил анализа структуры на языке MVEL. Если ячейка $c находится в 1-ом столбце, а её текст выделен красным цветом, то она выполняет роль метки строки (рис. 4, а). Если ячейка $c1 расположена непосредственно над ячейкой $c2 и при этом полностью охватывает её по столбцам, то они связаны (рис. 2, б). Если ячейка $c содержит текст, удовлетворяющий регулярному выражению "(?i).*(total)", то её необходимо игнорировать при формировании выходных данных (рис. 2, в). Примеры правил, которые применялись при тестировании системы CELLS, можно найти по адресу http://cells.icc.ru/test.
В процессе логического вывода накапливается информация о логической структуре таблицы. Для этой информации выполняется постобработка, которая включает: приведение текстового содержания ячеек к эталонным написаниям, сопоставление меток с измерениями и формирование канонической формы таблицы.
Из восстановленной информации модели таблицы CELLS формируется таблица в канонической форме, которая включает следующие поля: DATA ― данные (вхождения); ROW_LABEL ― пути меток от листьев до корней из невырожденного дерева Lr; COL_LABEL ― пути меток от листьев до корней из невырожденного дерева Lc; D1,..., Dn ― поля значений измерений Di из набора D. Каждый кортеж в такой канонической форме представляет связь между вхождением, путями в деревьях меток и значениями восстановленных измерений. Дополнительно поле ROW_LABEL/COL_LABEL может быть разделено на несколько отдельных полей, каждое из которых будет соответствовать одному уровню вложенности в дереве меток строк/столбцов.
Рис. 5. Каноническая форма таблицы из рис. 1: все метки сопоставлены измерениям, поэтому поля
COL_LABEL и ROW_LABEL отсутствуют 3 Экспериментальные результаты
Экспериментальная оценка представленного подхода выполнена с помощью системы CELLS, в которой реализованы структуры данных, представляющие модель таблицы CELLS, и алгоритмы: 1) загрузки исходной табличной информации в формате Excel (тестовых данных со специальной разметкой); 2) структурирования табличной информации, восстановленной в процессе логического вывода; 3) экспорта результатов в формате Excel.
Для экспериментальной оценки сформирована коллекция тестовых данных, которая включает 97 таблиц в формате Excel, собранных из 7 различных источников. Коллекция доступна по адресу http://cells.icc.ru/test. Её краткое описание приводится в табл. 1. Для формирования коллекции исходная табличная информация была преобразована из формата PDF в Excel.
Источниками тестовых данных послужили слабоструктурированные документы в низкоуровневом формате файлов печати PDF ― государственные и финансовые статистические отчеты с богатым табличным содержанием. Для формирования коллекции исходная табличная информация была преобразована из формата PDF в Excel. При этом, насколько это было возможно, в полученных тестовых таблицах было сохранено графическое форматирование, представленное в соответствующих им PDF источниках. Код источника
Кол-во таблиц Кол-во ячеек
Кол-во вхождений Кол-во меток Кол-во связей
между метками* Кол-во правил
Время исполнения правил (мс) 15 13 21 18 7 7 16 1088 2047 2156 7216 812 1553 2844 734 727 964 4180 268 1175 2195 257 321 470 862 141 313 508 102 167 196 551 89 174 335 10 16 14 12 12 16 10 417 526 663 964 283 638 730 1 Statistical Handbook of Japan 2007. Statistics Bureau of Japan. Chapter 5, 8. 2 OJSC «Aeroflot – Russian Airlines» Consolidated Financial Statements For the Year Ended December 31, 2006. P. 4–10, 25–26. 3 Boeing Co, Annual Report 2010. P. 50–55, 83–85. 4 China statistical yearbook 2003. National Bureau of Statistics of China. P. 23–48, 555, 559, 571, 584, 590, 664, 708, 774, 765. 5 Chevron Corp. News Release November 2, 2012. Chevron Corp. P. 1, 5–9. 6 USDA NASS. 2003 Agricultural Statistics Annual. USDA (U.S. Department of Agriculture). National Agricultural Statistics Service. Chapter VI. P. 5–7, 12. 7 Tobacco: World Markets and Trade 2005. USDA (U.S. Department of Agriculture). Foreign Agricultural Service. * Исключая связи корней деревьев меток.
Тестовые данные имеют дополнительную разметку для определения местоположения таблицы внутри листа Excel (рис. 6), а также аккуратную декомпозицию на ячейки. Там, где это возможно, их физическая структура и разграфка совпадают. Это позволяет избежать этапов обнаружения и сегментации таблицы. Рис. 6. Дополнительная разметка тестовой таблицы: маркеры «$START» и «$END» указывают соответственно верхний левый и нижний правый угол таблицы в пространстве строк и столбцов На рис. 7 показаны некоторые таблицы из тестовой коллекции данных. Их структуры включают типичные для этой коллекции особенности. Так, таблица, рис. 7, а, содержит иерархии меток строк и столбцов. Тело таблицы, рис. 7, б, пересекают перерезы: «Price per 100 pounds» и «Price per bushel». В таблице, рис. Х, в, столбцы с метками строк чередуются со столбцами с данными.
Полученные экспериментальные результаты приводятся в табл. 1. Логический вывод выполнялся в системе Drools Expert (5.4.0.Final). При этом использовался процессор Intel Core 2 Quad, 2,66 ГГц. Экспериментальные результаты показывают эффективность применения предлагаемого подхода для широкого класса таблиц. 4. Заключение
Предлагаемый подход базируется на предположении о том, что для одного или нескольких схожих источников можно разработать непротиворечивый набор правил анализа структуры содержащихся в них таблиц. Однако разработка достаточно универсальных баз знаний для многих разнородных источников имеет слишком высокую цену и не всегда возможна из-за противоречий, содержащихся в самих источниках. Поэтому данный подход предназначен в основном для задач управления данными, прежде всего для массовой интеграции табличной информации из наборов похожих источников. Литература
Automated Table Understanding
Using a Rule Engine
Alexey O. Shigarov
The paper discusses issues on automation of the table understanding (i.e. recovering relationships of table elements). We propose an approach to table understanding based on the use of a rule engine. A table model oriented on the logical inference and algorithms for processing tabular information are also considered in the paper. The CELLS system for structuring tabular information presented in Excel spreadsheet format has been developed using the proposed approach, model and algorithms. The performance evaluation of the system shows that the approach can be applied to a wide range of tables.