Автоматизированное понимание таблиц на основе системы исполнения правил ©А ОШигаров shigarov@icc.ru Автоматизированное понимание таблиц на основе системы исполнения правил 3936F2DC75DDEE735F023CD8EE583603 GROBID - A machine learning software for extracting information from scholarly documents
Аннотация
Введение

По оценки исследователей Merrill Lynch [16] примерно 80 процентов всей бизнес информации представлено в неструктурированном виде. Такая информация не имеет предопределенной формальной модели данных (например, научная статья, финансовый отчет, сообщение электронной почты) [1] и является противоположностью структурированной информации (например, реляционным базам данных).

Многие исследователи, в том числе, W. Inmon [11][12], отмечают важность вопросов интеграции неструктурированной информации. Одним из наиболее интересных вопросов является интеграция неструктурированных текстов, включая таблицы. Многие слабоструктурированные (ASCII-текст, файлы печати PDF и др.) и полуструктурированные (документы Word, книги Excel, HTML страницы и др.) документы [7] 2) Извлечение информации из таблицы [5] является аналогом задачи извлечения информации из текста и состоит в выборочном извлечении фактов, формирующих целевую базу данных.

3) Понимание таблицы [5,9] 2) Внутри ячейки не могут располагаться другие ячейки или таблицы (это не допускается в Excel).

3) Содержимое ячейки может являться либо меткой (заголовком), либо вхождением (данными). Используемые здесь термины «вхождение» и «метка» соответствуют смыслу терминов «entry» и «label» соответственно из работы Wang X. [20].

2

)
Представление и исполнение правил анализа табличной структуры

Схема преобразования табличной информации от неструктурированной к структурированной форме показана на рис. 3. Предполагается, что этапы обнаружения и распознавания таблицы выполняются в сторонних системах. Например, для извлечения таблиц из PDF документов могут использоваться системы Tabula [18] или PDFGenie [15] Пример канонической формы обработанной таблицы приводится на Рис. 5. Сформированная каноническая таблица может экспортироваться в реляционную базу данных с помощью стандартных средств интеграции данных известных систем управления базами данных (СУБД). Например, службы "SQL Server Integration Services" [17], позволяют импортировать данные из таблиц с простой "решеточной" структурой в форматах Excel, CSV в базы данных под управлением СУБД "SQL Server". Работа выполнена при финансовой поддержке РФФИ грант № 14-07-00166 и Совета по грантам Президента РФ СП-3387.2013.5.

[24] Шигаров А.О. Технология извлечения табличной информации из электронных документов разных форматов : дис. … канд. техн. наук. Иркутск, 2009. С. 143.

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.

1 )Уровень физической структуры Tp=(Sr, Sc, С) состоит из: (1) пространства строк -Sr и столбцов -Sc; (2) набора ячеек -С, в котором каждая ячейка -с=(p, c', S) включает: координаты в пространстве строк Sr и столбцов Sc -p=(cl, rt, cr, rb), содержаниеc', стилевая информация (цветовые схемы, шрифтовые метрики, выравнивание, стили оформлении границ и др.) -S.
4 )Уровень логической структуры 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 является оболочкой для структуры LABEL и обеспечивает представление деревьев меток. Рис. 1. Примеры объединения плиток сетки в ячейки таблицы, обозначенные как 1, 2 и 3: так ячейка может объединять несколько плиток в Excel, Word, HTML и LaTeX (а); так ячейка может визуально (для восприятия человеком) включать несколько плиток с помощью разграфки (б); скорее всего, так ячейки никто не представляет (в) Очевидно, что сделанные предположения описывают широкий класс обрабатываемых таблиц. Пример сводной таблицы, полностью укладывающейся в данную модель, приводится на рис. 2.Все предложенные структуры данных и алгоритмы реализованы на платформе Java. Это обеспечивает возможность использовать их напрямую для представления фактов о таблицах в процессе логического вывода, выполняемого в системе исполнения правил с поддержкой спецификации JSR-94 (Java Rule Engine API).
Рис. 2 .Рис. 4 .Пример сводной таблицы Рис. 3. Схема структурирования табличной информации ... when $c : CCell( cl == 1, style.getFont().getColor() == "#ff0000") then modify ( $c ) { setRole( Role.ROWLABEL ) } а ... when $c1 : CCell() $c2 : CCell( rt == $c1.rb + 1, ( $c1.cl <= cl && cr < $c1.cr ) || ( $c1.cl < cl && cr <= $c1.cr ) ) then $c1.addConnectedCell( $c2 ) б ... when $c : CCell( text matches "(?i).*(total)" ) then modify ( $c ) { setIgnored( true ) } ... в Примеры правил анализа табличной структуры
Рис. 5 .Каноническая форма таблицы из рис. 1: все метки сопоставлены измерениям, поэтому поля COL_LABEL и ROW_LABEL отсутствуют 3 Экспериментальные результаты
7Tobacco: 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 ГГц. Экспериментальные результаты показывают эффективность применения предлагаемого подхода для широкого класса таблиц.
, что для одного или нескольких схожих источников можно разработать непротиворечивый набор правил анализа структуры содержащихся в них таблиц. Однако разработка достаточно универсальных баз знаний для многих разнородных источников имеет слишком высокую цену и не всегда возможна из-за противоречий, содержащихся в самих источниках. Поэтому данный подход предназначен в основном для задач управления данными, прежде всего для массовой интеграции табличной информации из наборов похожих источников. Рис. 7. Примеры тестовых таблиц Подход положен в основу развиваемой авторами системы понимания таблиц в формате Excel. Полученные экспериментальные результаты показывают эффективность её применения для широкого класса таблиц, представленных в формате Excel. В то же время необходимо дальнейшее исследование возможностей для упрощения правил анализа структуры таблицы за счет развития структур данных представления табличной информации и дополнительных алгоритмов её предобработки и постобработки.
Труды 16-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» -RCDL-2014, Дубна, Россия, 13-16 октября 2014 г.Ячейка может располагаться в одной или нескольких соседних строках и в одном или нескольких соседних столбцах (например, атрибуты COLSPAN и ROWSPAN в HTML) и имеет прямоугольную форму в пространстве строк и столбцов, как показано на рис. 1, а.анализ (определение того, какую роль играет ячейка в таблице); (4) структурный анализ (определение связей между ячейками); и (5) интерпретацию таблицы (извлечение фактов из таблицы). В настоящей работе обсуждается автоматизация 1) Модель включает два уровня: физической и формате CSS2 (Cascading Style Sheets Level 2). В частности, ими предлагается выполнять интерпретацию таблиц 3.2 Модель таблицы (восстановление логической структуры, которые в упрощенном виде семантических отношений) на основе эвристик о стилевой информации подготовленного для набора можно описать следующим образом.следующих из перечисленных этапов пониманиинаиболее общих типов изображения web-таблиц.таблиц: (3) функционального и (4) структурного анализ, и (5) интерпретации таблицы.В работе D.W. Embley и др. [6] предлагаются методы обнаружения таблиц внутри HTML страниц,2 Родственные работыи извлечения из них информации. При этом предполагается, что таблица может включатьСуществует огромное разнообразие способов изображения таблиц. Это приводит к высокой сложности анализа и обработки неструктурированной табличной информации. Как показано в обзорах [4, 5, 13, 22], посвященных проблемам анализа и обработки таблиц, сейчас наиболее изучены, хотя и не решены полностью, проблемы обнаружения и распознавания таблиц. При этом проблемы высокоуровневого анализа и интерпретации таблиц остаются менее изученными. Вопросы понимания таблиц, связанные с задачами их (3) функционального и (4) структурного анализ, а также (5) интерпретации, рассматриваются в ряде работ [2, 4, 6, 8, 10, 19, 23-24]. Ниже приводится анализ некоторых из них. В работах Douglas S. и др. [2] и Tijerino Y. и др. [19] рассматривается преобразование (структурирование) табличной информации,вложенные таблицы на связанных страницах. В частности, для поиска атрибутов (меток) и значений (данных) среди содержания ячеек таблицы предлагается использовать онтологии, специально разрабатываемые для извлечения данных. Такие онтологии извлечения помимо понятий (объектов), отношений и ограничений содержат привязанные к объектам фреймы, которые с помощью регулярных выражений позволяют связать содержание таблицы с объектами онтологии. Для связывания атрибутов со значениями, дополнительно к онтологиям извлечения используется набор эвристик о пространственной структуре и содержании таблиц. В отличие от приведенных исследований нами предлагается автоматизировать понимание таблиц за счет анализа и интерпретации, как их естественно-языковой, так и пространственной и графической (стилевой) информации.называемое каноникализацией таблицы. В работеDouglas S. и др. предлагается метод интерпретациии каноникализации таблиц, которые содержатся вДля понимания таблиц нами предлагаетсяспецификациях, используемых в строительнойподход, основанный на исполнении правил анализапромышленности. Для этого они предлагаютструктуры таблиц. Идея, лежащая в основеиспользовать обработку естественного языка напредлагаемого подхода, состоит в следующем.основе онтологии предметной области (подъязыкаОбычновнутритематическойколлекцииспецификаций строительной промышленности).документов от одного поставщика таблицыПредлагаемый Tijerino Y. и др. [19] способ каноникализации основан на использовании библиотеки фреймов, содержащей знания о лексическом содержании таблиц. Каждый фрейм данных описывает один тип данных и используется для отнесения выражений на естественном языке (табличных заголовков и значений) к этому типу. Для описания типов данных ими предлагается использовать регулярные выражения, словари и некоторые открытые ресурсы, например, WordNet [21]. В перечисленных работах [2-19] предлагаютсякомпонуются и форматируются однообразно. Для такой коллекции документов можно определить набор формализованных правил анализа табличной структуры, который удовлетворяет всем или почти всем ее таблицам. Эти правила можно представить в виде базы знаний, а процесс восстановления семантических отношений в таблице реализовать как логический вывод. При этом база фактов, используемая в процессе логического вывода, может включать информацию о пространственном, графическом и естественно-языковом содержании таблицы.пространственной и стилевой информации в методы каноникализации таблиц, основанные на анализе и интерпретации представленной в таблицах естественно-языковой информации. На практике этого не всегда достаточно, для более точного и полного извлечения информации из таблицы часто также требуется анализ пространственной и графической информации. W. Gatterbauer и др. в работе [8] напротив предлагают предметно-независимый метод извлечения информации из HTML таблиц, основанный на анализе исключительносостоит в метками (заголовками) и значениями данных, а также между восстановлении отношений между метками и измерениями (доменами). Как определяется в работе [9] понимание таблиц в общем случае включает следующие этапы: (1) обнаружение таблицы (поиск позиций ограничивающего прямоугольника таблицы внутри источника); (2) распознавание таблицы (разделение её на отдельные ячейки); (3) функциональный 3.1 Базовые предположения о таблицах На основе ограничений табличной структуры, характерных для представлений табличной информации в широко распространенных форматах данных, таких как Excel, Word, HTML и LaTeX, предлагается достаточно общая модель таблицы CELLS, которая ориентирована на представление фактов о табличной информации в процессе логического вывода. В модели сделано несколько общих для этих представлений предположений.
3 Представление фактов о таблицах
Если ячейка $c находится в 1-ом столбце, а её текст выделен красным цветом, то она выполняет роль метки строки (рис. 4, а). Если ячейка $c1 расположена непосредственно над ячейкой $c2 и при этом полностью охватывает её по столбцам, то они связаны (рис. 2, б). Если ячейка $c содержит текст, удовлетворяющий регулярному выражению "(?i).*(total)", то её необходимо игнорировать при формировании выходных данных (рис. 2, в).видимыми границами позволяет упростить правилаанализа структуры таблицы.Полученные в результате данные о таблице,которые формируют базу фактов для логическоговывода. Кроме того, факты могут быть дополненывнешней информацией об измерениях.Для обработки набора таблиц формируется базазнаний, которая состоит из продукционных правиланализа табличной структуры. Они отображаютдоступную информацию: позиции (координаты),графическое форматирование и естественно-языковое содержание ячеек, в отсутствующиеизначальноотношениямеждуметками,вхождениями и измерениями. Полученные впроцессе вывода новые факты о семантическихотношениях должны быть достаточными дляканоникализации таблицы.В качестве система исполнения таких правилможет использоваться свободная системы DroolsExpert [3], реализующая спецификацию JSR-94. Приэтом сами правила могут быть представлены наязыке выражений MVEL [14].На Рис. 4 приводится ряд простых примероввозможных правил анализа структуры на языкеMVEL. Примеры правил, которые применялись притестировании системы CELLS, можно найти поадресу http://cells.icc.ru/test.В процессе логического вывода накапливаетсяинформация о логической структуре таблицы. Дляэтой информации выполняется постобработка,котораявключает:приведениетекстовогосодержания ячеек к эталонным написаниям,сопоставлениеметоксизмерениямииформирование канонической формы таблицы.Из восстановленной информации модели, для документов, напечатанных в файлы формата EMF, может использоваться технология, предложенная в работах [24]. Выходом таких систем являются таблицы в форматах Excel, HTML или таблицы CELLS формируется таблица в канонической форме, которая включает следующие поля: DATA -данные (вхождения); ROW_LABEL -пути меток от листьев до корней из невырожденного дерева Lr; COL_LABEL -пути меток от листьев до корней из невырожденного дерева Lc; D1,..., Dn -поля значений измерений Di из набора D. Каждый кортеж в такой канонической форме представляет связь между вхождением, путями в деревьях меток и значениями восстановленных измерений. Дополнительно поле ROW_LABEL/COL_LABEL может быть разделено на несколько отдельных полей, каждое из которых будет соответствовать одному уровню вложенности в дереве меток строк/столбцов.XML, которые могут быть приведены к физическому уровню модели CELLS. В процессе загрузки таблиц из полученных файлов Excel, HTML или XML в структуры данных, реализующих модель CELLS, табличная информация подвергается предобработки. Это включает опционально: удаление лишних пробельных и служебных символов из текстового содержания, исключение из таблицы пустых строк и столбцов и восстановление отсутствующих настроек стилей границ ячеек. Последнее необходимо, поскольку видимые и физические границы ячейки не всегда совпадают. Визуально они могут быть образованы границами соседних ячеек. Приведение стилей физических границ ячеек в соответствии с её
Для экспериментальной оценки сформирована коллекция тестовых данных, которая включает 97 таблиц в формате Excel, собранных из 7 различных источников. Коллекция доступна по адресу http://cells.icc.ru/test. Её краткое описание приводится в табл. 1. Excel. При этом, насколько это было возможно, в полученных тестовых таблицах было сохранено графическое форматирование, представленное в соответствующих им PDF источниках. 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.Таблица 1. Экспериментальные результатыКодКол-воКол-воКол-воКол-воКол-во связейКол-воВремяисточникатаблицячееквхожденийметокмеждуправилисполненияметками *правил (мс)JAPAN_STAT 115108873425710210417AEROFLOT 213204772732116716526BOEING 321215696447019614663CHINA_STAT 4187216418086255112964CHEVRON 578122681418912283USDA_NASS 671553117531317416638TOBACCO 71628442195508335107301Экспериментальная оценка представленногоподхода выполнена с помощью системы CELLS, вкоторойреализованыструктурыданных,представляющие модель таблицыCELLS, иалгоритмы: 1) загрузки исходной табличнойинформации в формате Excel (тестовых данных соспециальнойразметкой);2) структурированиятабличнойинформации,восстановленнойвпроцесселогическоговывода;3) экспортарезультатов в формате Excel.Для формирования коллекцииисходнаятабличнаяинформациябылапреобразована из формата PDF в Excel.Источниками тестовых данных послужилислабоструктурированныедокументывнизкоуровневом формате файлов печати PDF -государственные и финансовые статистическиеотчеты с богатым табличным содержанием. Дляформирования коллекции исходная табличнаяинформация была преобразована из формата PDF в
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.
The problem with unstructured data // DM Review RBlumberg SAtre 2003 Using Natural Language Processing for Identifying and Interpreting Tables in Plain Text SDouglas MHurst DQuinn Proc. of the 4th Annual Symposium on Document Analysis and Information Retrieval of the 4th Annual Symposium on Document Analysis and Information Retrieval
Las Vegas
 1995 Design of an end-to-end method to extract information from tables ACSilva AMJorge LTorgo Int. J. on Document Analysis and Recognition 8 2 2006 Table-processing paradigms: a research survey DWEmbley MHurst DLopresti GNagy Int. J. on Document Analysis and Recognition 8 2 2006 Automating the Extraction of Data from HTML Tables with Unknown Structure // Data & Knowledge Engineering DWEmbley CTao SWLiddle 2005 Elsevier 54 RFeldman JSanger The Text Mining Handbook: Advanced Approaches in Analyzing Unstructured Data Cambridge University Press 2006 422 Towards Domain-Independent Information Extraction from Web Tables WGatterbauer PBohunsky MHerzog BKrüpl BPollak Proc. of the 16th Int. Conf. on World Wide Web of the 16th Int. Conf. on World Wide Web
New York, NY, US
 ACM 2007 Layout and Language: Challenges for Table Understanding on the Web MHurst Proc. of the 1st Int. Workshop on Web Document Analysis of the 1st Int. Workshop on Web Document Analysis 2001 The Interpretation of Tables in Texts MHurst 2000 UK School of Cognitive Science, Informatics, the University of Edinburgh PhD thesis WHInmon Matching unstructured data and structured data // The data administration newsletter 2006 Tapping into Unstructured Data: Integrating Unstructured Data and Textual Analytics into Business Intelligence WHInmon ANesavich 2007 Prentice Hall PTR 1st edition A tabular survey of automated table processing DLopresti GNagy Lecture Notes in Computer Science 2000. 1941 <author> <persName><surname>Pdfgenie</surname></persName> </author> <ptr target="http://www.pdftron.com/pdfgenie" /> <imprint/> </monogr> </biblStruct> <biblStruct xml:id="b13"> <monogr> <title level="m" type="main">Enterprise Information Portals // Merrill Lynch CCShilakes JTylman 1998 SQL Server Integration Services Tabula Towards ontology generation from tables // World Wide Web: Internet and Web Information Systems YTijerino DEmbley DLonsdale GNagy 2005 8 Tabular Abstraction, Editing, and Formatting XWang 1996 Waterloo, Ontario, Canada PhD thesis WordNet A survey of table recognition: Models, observations, transformations, and inferences RZanibbi DBlostein JRCordy Int. J. on Document Analysis and Recognition 7 2004 <author> <persName><forename type="first">P</forename></persName> </author> <imprint> <biblScope unit="page" from="1" to="16" /> </imprint> </monogr> </biblStruct> <biblStruct xml:id="b21"> <analytic> <title level="a" type="main">Адаптивные методы извлечения информации из статистических таблиц, представленных в текстовом виде ПКудинов дис. … канд. техн. наук. М 105 2011