автореферат диссертации по документальной информации, 05.25.05, диссертация на тему:Технология извлечения табличной информации из электронных документов разных форматов

На правах рукописи

Шигаров Алексей Олегович

Технология извлечения табличной информации из электронных документов разных форматов

05.25.05 - Информационные системы и процессы, правовые аспекты информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

003409993 О

Иркутск - 2009

003489993

Работа выполнена в Учреждении Российской академии наук Институте динамики систем и теории управления Сибирского отделения РАН

Научный руководитель:

член-корреспондент РАН,

доктор технических наук, Бычков Игорь Вячеславович

Официальные оппоненты:

доктор технических наук, Жижимов Олег Львович

доктор технических наук, Тятюшкин Александр Иванович

Ведущая организация:

Государственное образовательное учреждение высшего профессионального образования «Иркутский государственный университет»

Защита состоится «5» февраля 2010 г. в 16:00 на заседании диссертационного совета ДМ 003.046.01 в Учреждении Российской академии наук Институте вычислительных технологий Сибирского отделения РАН по адресу: 630090, Новосибирск, пр. Академика Лаврентьева, 6

С диссертацией можно ознакомиться в специализированном читальном зале вычислительной математики и информатики ГПНТБ СО РАН

Автореферат разослан «30» декабря 2009 г.

Ученый секретарь

диссертационного совета,

доктор физико-математических наук,

профессор

Чубаров Л. Б.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследования. Таблицы являются одним из наиболее используемых способов представления информации в документах. Часто такая табличная информация изначально представлена в базах данных. Однако базы данных не всегда доступны, открыты, содержат полную информацию. В связи с этим актуальность приобретают методы, системы и технологии извлечения табличной информации из документов, которые позволяют преобразовать её к требуемому виду, например, к отношениям в реляционных базах данных.

Актуальность данной проблематики подчеркивается в обзорах авторов Handley J.C. (1999), Lopresti D. и Nagy G. (1999, 2000), Zanibbi R. (2004), Embley D.W. (2006), e Silva A.C. (2006), Полевого Д.В. (2007). В литературе выделяется несколько задач связанных с извлечением табличной информации: 1) обнаружение — поиск на страницах документов областей, ограничивающих таблицы; 2) сегментация — разделение таблицы на отдельные ячейки, строки, столбцы; 3) анализ функций ячеек — определение того, какие функции выполняют отдельные ячейки таблицы (являются ли они заголовками или данными); 4) структурный анализ — определение связей между ячейками таблицы.

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

Автоматическое обнаружение и сегментация таблиц выполняется в некоторых системах оптического распознавания текста, например, «OmniPage» (NuanceCommunications), «Cuneiform» (CognitiveTechnologies), «FineReader» (ABBYY). Перечисленные системы ориентированы на «решёточную» структуру таблиц, характерную табличным процессорам, например, Excel. Это снижает их эффективность для обнаружения и сегментации таблиц со сложными структурами заголовков. Кроме того, оптическое распознавание символов выполняется с потерями информации. В системах «PDF2XL» (Cogniview) и «Solid Converter PDF» (Solid Documents), в частности, выполняется преобразование таблиц из документов PDF в файлы Excel/Word. Эти системы также ориентированы на «решёточную» структуру таблиц и выполняют только их обнаружение и сегментацию.

В статистических отчетах (государственных, медицинских, финансовых) основная информация представлена в виде так называемых статистических таблиц1. Вне зависимости от национальной или корпоративной принадлежности такие таблицы обладают достаточно схожей структурой. Большинство таких отчетов доступно в электронном виде, где таблицы, как правило, являются машиночитаемым текстом, т. е. электронным текстом, который хранится в виде строк символов. Однако в литературе не представлены методы или системы извлечения табличной информации, которые с одной стороны являются комплексными, т. е. выполняют обнаружение, сегментацию, анализ функций ячеек и структурный анализ таблиц, а с другой стороны ориентированы на структуру и особенности статистических таблиц, в частности, публикуемых Росстатом. Таким образом, разработка комплексной технологии извлечения табличной информации, которая ориентирована на структуру и особенности статистических таблиц, представленных в виде машиночитаемого текста в электронных документах, является актуальной задачей.

Цель диссертационной работы состоит в создании технологии извле-

1 «Большая советская энциклопедия. Изд. 3-е» - М.: Советская энциклопедия. Т.25 «Струнино-Тихорецк». 1976. С. 161-162. http://slovari.yandeï.ru/dict/bse/article/00077/08800.h.to

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

Основные задачи диссертационной работы.

1. Анализ представления статистических таблиц в документах.

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

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

4. Разработка информационной системы извлечения табличной информации из электронных документов на основе предложенных методов.

5. Проверка созданной технологии на задачах автоматизации ввода больших объемов табличной информации из электронных статистических отчетов в базы данных.

Методы исследования: теория множеств, теория баз данных, методы машинной графики, объектно-ориентированное программирование.

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

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

представленных в виде машиночитаемого текста в электронных документах разных форматов. При этом данная технология позволяет снизить затраты и повысить качество формирования баз данных. Работа выполнена при поддержке РФФИ, грант 09-07-12017-офи_м.

Внедрение. Результаты диссертационной работы успешно использовались в Министерстве сельского хозяйства Иркутской области для ввода информации из электронных статистических отчетов Территориального органа федеральной службы государственной статистики по Иркутской области (Ир-кутскстата) в базу данных (БД) автоматизированной информационной системы (АИС) «Каскад». Предлагаемая технология внедрена в Институте систем энергетики им. Л.А. Мелентьева СО РАН, где используется при создании хранилища данных в составе информационной инфраструктуры исследований в энергетике.

Защищаемые положения.

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

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

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

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

ячеек и структурного анализа статистических таблиц; разработана информационная система для извлечения табличной информации из метафайлов EMF (Enhanced Metafiles); создана технология извлечения табличной информации из электронных документов разных форматов. В неделимом соавторстве с А.Е. Хмельновым получена модель структурного описания таблицы. В неделимом соавторстве с А.Е. Хмельновым, И.В. Бычковым и Г.М. Руж-никовым получено применение предлагаемой технологии для автоматизации ввода статистической информации в базу данных АИС «Каскад». В работах [2-4, 7, 8] автором лично предложен эвристический метод обнаружения таблиц и технология извлечения табличной информации из электронных документов разных форматов. В работах [5, 10-12] автором в неделимом соавторстве с А.Е. Хмельновым предложена модель структурного описания таблицы.

Представление работы. Основные результаты работы докладывались на научно-практических конференциях: Международной конференции «Математические и информационные технологии» (Будва, Черногория, 2009 г.); IX международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (Нижний Новгород, 2008 г.); XII, XIII и XIV всероссийской конференции «Информационные и математические технологии в науке и управлении» (Иркутск, 2007, 2008, 2009 гг.); Всероссийской конференции «Математическое моделирование и вычислителыго-ннфор-мационные технологии в междисциплинарных научных исследованиях» (Иркутск, 2009 г.); VI и IX школе-семинаре «Математическое моделирование и информационные технологии» (Иркутск, 2005, 2007 гг.); Школе-семинаре молодых ученых «Информационные технологии и моделирование социальных эколого-экономических систем» (Иркутск, 2008 г.); семинаре «Ляпуновские чтения и презентация информационных технологии» (Иркутск, 2007, 2008, 2009 гг.).

Публикации. По теме диссертации опубликовано 12 научных работ [1-12], в т. ч. 3 публикации [1-3] в изданиях, рекомендованных ВАК. Получено

4 свидетельства об официальной регистрации программ для ЭВМ в Роспатенте: Ж№ 2008614328, 2008614330, 2008614331, 2008614332 (2008 г.).

Структура и объем работы. Диссертация состоит из введения, 4-х глав, заключения, списка литературы, включающего 103 источника, и 4-х приложений. Основное содержание диссертации изложено на 132 страницах текста, общее количество страниц — 141.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении приводится общая характеристика работы.

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

Рассматривается разнообразие используемых в документах таблиц, а также структура и особенности статистических таблиц, Рис. 1. Обсуждаются форматы входных данных, которые используются в известных методах и системах извлечения табличной информации. Показано, что в основном в качестве входных данных применяются либо ASCII-текст без графического форматирования (не поддерживает всех возможностей современных текстовых и табличных процессоров), либо растровые изображения документов (требуют оптического распознавания текста), либо Web-страницы формата HTML (таблицы используются для компоновки Web-страниц).

В диссертации предлагается использовать в качестве входных данных метафайлы. Это позволяет извлекать табличную информацию, представленную в виде машиночитаемого текста в электронных документах разных форматов, например, DOC, XLS, PDF (с латиницей), HTML, ASCII-текст. Поскольку электронные документы таких форматов могут преобразовываться в метафайлы посредством виртуальной печати. При этом машиночитаемый текст исходных документов остается в метафайлах машиночитаемым. Следует отмстить, что в отличие от файлов форматов PostScript и PDF метафайлы могут интерпретироваться с номощыо GDI (Graphics Device Interface, части

ьазовая точка тела таблицы Шапка

Охватывающий заголовок, строки

Вложенный заголовок строки

Боковик

намолочено ¡намолочено

^ столбца

иркутская область Братский район Заларинский район Зиминский район иркутский район качугский район куйтунский район

иркутская область Братский район заларинский район

2004 : 2005 I 2004 ! 2005+j— ВЛОЖСННЫН

заголовок хозяйства всех категорий ~ столбца 7250 9334 30 640 97? 18 100 141 17 292 1309 25 799 942 16 61 98 20 414 722 19

20 16 13 28 1

J® УГело -Перерез

с/х предприятия 43221 5237 23 24 | 159 488 19 174-Элемент данных

56 121 18 22 I

Рис. 1. Пример статистической таблицы

Windows API). Также рассматриваются известные методы и системы извлечения табличной информации из документов. Обсуждаются их ограничения. На основе проведенного анализа предлагается технология извлечения табличной информации из электронных документов, основные компоненты и этапы которой приводятся на Рис. 2.

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

Описываются особенности и ограничения обрабатываемых таблиц, Рис. 1. Предлагается теоретико-множественная модель страницы документа, которая служит для представления данных обрабатываемой страницы. Основными объектами этой модели являются линейки (линии разграфки), текстовые элементы, текстовые блоки, строки, табличные регионы, табличные области, Рис. 3. Эти объекты формируются снизу вверх, Рис. 4. В предлагаемых методах используется анализ промежутков пустого места на странице (т. е. места, не занятого текстовыми блоками). Для этого предлагается алгоритм сегментации пустого места п выделение среди полученных сегментов вертикальных н горизонтальных промежутков, Рис. 5.

Описывается обработка и интерпретация метафайлов с помощью GDI, а также формирование из записей метафайлов текстовых элементов и лнне-

^Метафайлы—^

П\

EMF

EMF

Виртуальный ГМI принтер

ЭЛЕКТРОННЫЕ С ДОКУМЕНТЫ

_. FR\

Word (DOC)

HTML

ГОР

щъ,

Excel (XLS)

ASCII

Система извлечения табличной ииформацнн-из метафайлов_

Получение данных из метафайла

Страницы

(текст,

разграфка)

Обнаружение таблиц на странице

Ограничивающие

прямоугольники

таблиц

Анализ функций ячеек таблиц

х:

Таблицы (шапка, бококик, тело,перерезы)

7~

Сегментацня таблиц

Таблицы (линейки, ячейки)

Структурный анализ таблиц

_ЗАДАЧИ ПРЕДМЕТНЫХ_

/ ОБЛАСТЕЙ Ч

Интерпретаторы структурных описаний таблиц, ориентированные на решения задач предметных областей

^—Структурные описания таблиц-

хмь

хмь

Рис. 2. Технология извлечения табличной информации из электронных документов

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

Предлагается метод обнаружения таблиц на странице, т. е. поиска ограничивающих прямоугольников таблиц — табличных областей. Для этого текстовые элементы, близко расположенные в одной строке текста друг к другу и при этом не разделенные линейками, объединяются в текстовые блоки, Рис. 6. Близость расположения двух текстовых элементов вычисляется с помощью пх шрифтовых метрик. Для текстовых блоков вычисляются ограничивающие прямоугольники по вложенным в них текстовым элементам. Текстовые блоки группируются в строки. При этом если у двух текстовых бло-

б

жпт

рта

сшс

ГТИЧ

хзж

таедткй...........ГУ*

изхк

ЖКЙС

шак

ШИ

ют ша

Вертикальные промежутки

Ограничивающие прямоугольники

Офаничиваюшие ' прямоугольники строк

Рис. 3. Основные объекты страницы: текстовый элемент (а), текстовый блок (б), строки (б), табличный регион (г)

| Страница документа |

/

Табличная область

Табличная область

Табличный регион

Табличный регион

Строка

I Строка I

Текстовый блок

Текстовый блок

Текстовый I

\

Текстовый-]

ггг;

1_л

екстовыи элемент I

I Текстовый 1

Рис. 4. Порядок формирования объектов страницы документа снизу вверх

ков их проекции на ось У пересекаются, то они принадлежат одной строке. На странице среди всех строк выбираются строки табличного вида. Для этого используется ряд эвристик о составе строк табличного вида. Например, такая строка должна охватывать не менее двух текстовых блоков и иметь ширину пустого места относительно всей своей ширины не менее заданного порога. На странице выполняется поиск последовательностей подряд расположенных сверху вниз строк табличного вида, которые имеют схожее расположение проекций на ось X своих вертикальных промежутков. Каждая такая

Всего Ьа1 ¡200811гол

за Текстовые элементы

332 Текстовые

кЧЧ»МКЧЧЧЧ1'>')?МКЧЧ11'А<^ЖЧЧ1П 7'>>!к\\ЧМ| .?^'Ж\\ЧМ1»К\\\М1 »41КЧМ блоки

- —

^ Ы к

Ограничивающие прямоугольники текстовых блоков

Вертикальные сегменты пустого места

Вертикальные промежутки

Рис. 5. Сегментация пустого места (а) и выделение вертикальных промежутков (б) Текстовые элементы принадлежат

Ограничивающие прямоугольники текстовых блоков

Ограничивающие рямоугольники трок

Строки табличного вида принадлежат одному табличному региону

Текстовые элементы

Текстовые блоки

Рис. 6. Обнаружение таблиц на странице документа

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

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

Предлагается теоретико-множественная модель таблицы, которая представляет объекты, связанные с обрабатываемой таблицей. Формализованы ячейка и таблица, составленная из наборов текстовых блоков, строк, вертикальных и горизонтальных линеек, ячеек, базовой точки тела и ограничивающего прямоугольника. Обсуждается предобработка входных данных -табличной области и содержащихся внутри неё текстовых блоков и линеек,

Базовая точка -тела таблицы

Область поиска базовой точки / тела таблицы

N

'.jr .li/m ....

| | Ячейки с «Числами»

Рис. 7. Поиск базовой точки тела таблицы

по которым выполняется первоначальное формирование таблицы.

Описывается анализ функций ячеек таблицы. Функция (роль) ячейки зависит от её расположения относительно базовой точки тела таблицы. Эта точка делит таблицу на шапку, боковик и тело. Предлагаемый метод анализа функций ячеек строится, как поиск базовой точки табличного тела, Рис. 7. Для этого внутри таблицы определяется область поиска этой точки, которая начинается непосредственно под самым нижним охватывающим заголовком столбца. Эта область имеет «решёточную» структуру ячеек. Она сегментируется на отдельные ячейки с помощью вертикальных промежутков и ограничивающих прямоугольников строк таблицы. Данные, содержащиеся в теле статистической таблицы, являются числами или специальными обозначениями из ограниченного набора. С помощью заранее заданных регулярных выражений каждой непустой ячейке по её тексту сопоставляется один из следующих типов данных: «числа», «даты» или остальной «текст». По ячейкам, содержащим «числа», строится ограничивающий прямоугольник тела таблицы. Вершина в левом верхнем углу этого прямоугольника является базовой точкой тела таблицы. Если непосредственно над этой точкой располагаются табличные строки, включающие по одному текстовому блоку, то её »/-координата корректируется с помощью эвристик о расположении перерезов и заголовков. Кроме того, отдельно выделяются строки таблицы, содержащие перерезы.

Рассматривается сегментация таблицы. Статистические таблицы, как правило, имеют только частичную разграфку или не имеют её вовсе. Предла-

Ш Текстовые блоки • Базовая точка тела таблицы

КЗ Вертикальные промежутки / Вертикальные линейки

Горизонтальные промежутки / - -- Горизонтальные линейки

Рис. 8. Восстановление полной разграфки таблицы ^с* — Заголовки столбцов ^г,- — Заголовки строк Ь,0к— Перерезы — Элементы данных

14 722 19 20

б

Рис. 9. Компоненты структурного описания таблицы (а) и пример связывания элемента данных с заголовками (б)

гаемая сегментация таблицы выполняется, как восстановление полной разграфки таблицы, Рис. 8. По вертикальным промежуткам таблицы восстанавливаются вертикальные линейки. Далее, по горизонтальным промежуткам таблицы восстанавливаются горизонтальные линейки внутри её шапки. Горизонтальные линейки иод шапкой восстанавливаются по ограничивающим прямоугольникам табличных строк. Восстановленные линейки составляют полную табличную разграфку, которая корректируется с помощью исходной табличной разграфки при её наличии. С помощью своей полной разграфки таблица сегментируется на отдельные ячейки.

Предлагается теоретико-множественная модель структурного описания таблицы, которая служит для представления содержимого заголовков, эле-

ментов данных и связей между ними. Предлагаемое структурное описание таблицы включает в себя дерево заголовков столбцов, дерево заголовков строк, дерево перерезов и множество элементов данных, Рис. 9, а. Эти деревья соответствуют тем иерархиям вложенности, которые образуют заголовки (несмотря на то, что перерезы не имеют вложенности, их также удобнее рассматривать, как дерево). Вложенные заголовки являются в этих деревьях подузлами охватывающих заголовков. Корнями этих деревьев являются пустые узлы. Каждый элемент данных сопоставляется с одним заголовком столбца, одним заголовком строки и одним перерезом, Рис. 9, б.

Предлагается метод структурного анализа таблицы для формирования её структурного описания. Выполняется эвристический анализ компоновки ячеек таблицы. Из содержимого ячеек формируются: 1) дерево заголовков столбцов, 2) дерево заголовков строк, 3) дерево перерезов и 4) множество элементов данных. Выполняется связывание элементов данных с заголовками.

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

В главе 4 рассматривается применение созданной технологии.

Предлагается информационная система извлечения табличной информации из метафайлов, которая реализует предлагаемые методы. Эта система имеет графический пользовательский интерфейс, который визуализирует процесс извлечения табличной информации. На выбранной странице этот процесс выполняется поэтапно: 1) обнаружение, 2) анализ функций ячеек, 3) сегментация и 4) структурный анализ таблиц. При этом пользователь при необходимости может вручную корректировать результаты каждого из этих этапов. Данная система позволяет представить получаемые структурные описания таблиц в виде XML, Рис. 10, структура которого описана на языке XML Schema.

<columnHeader text-"JaronoRKn столбцов" id="0">

<columnHeader text="Намолочено зерна, всего" id=*"14581672">

ccolumnHeader text="2004" id="14581896"/> [...] </co1umnHeader> [...]

</coi umnHeader>_Дерево заголовков столбцов

<rowHeader text="3aronoat<n строк" id="0"> <rowNeader text="HpKyTCKafl область" id="14582344">

<rowHeader text="BpaTCKMfi район" id="1458240Q"/> [...] </rowNeader> [...] тт </rowHeader> _Дерево заголовков строк

<cutiпнeadeг гех1="перерезы" та="0">

<cut^пнeader 1ех1="Хозяйства всех категорий" 1'а="14582848"/> [...]

</ситтпнеадег>_Дерево перерезов

<ЗаН>

<аа1аЕ1ешеп1 гех1="7250" соИа="1458189б" гогаа-"14582344" сиГ1а="14582848"/> <йа1аЕ1етеп1 гехг="640" соШ="14581896" го»1а="14582400" а»:Й="14582848"/>

<д!ага> Множество элементов данных

</table>

Рис. 10. Фрагмент XML представления структурного описания таблицы

__Таблица 1. Экспериментальная оценка_

Обнаружение: таблиц базовых точек тел таблиц линеек Точность 84,5% 91,4% 86,2%

Полнота 91,7% X 82,5%

Приводится экспериментальная оценка данной системы, Таблица 1. Используется две оценки: 1) точность — процент количества корректно обнаруженных таблиц/базовых точек тел таблиц/линеек к общему количеству обнаруженных соответственно таблиц/базовых точек тел таблиц/линеек; 2) полнота — процент количества корректно обнаруженных таблиц/линеек к общему числу существующих соответственно таблиц/линеек. Экспериментальные данные были составлены из государственных статистических отчетов России, США, Евросоюза, Японии, а также из финансовых отчетов различных компаний. Они были представлены в форматах: PDF, DOC, XLS, HTML. Всего для оценки эффективности обнаружения таблиц/базовых точек тел таблиц было обработано 425 страниц, содержащих 518 таблиц. Для оценки эффективности обнаружения линеек из экспериментальных данных случайным образом было выбрано 44 страницы, содержащих 51 таблицу с 275 вертикальными и 1046 горизонтальными линейками.

Описывается автоматизация ввода статистической информации в БД АИС «Каскад» с помощью предлагаемой технологии. Неполнота представления статистической информации в базах данных Иркутскстата не позволяет организовать прямое преобразование необходимых данных в АИС «Каскад». Поэтому публикуемые электронные статистические отчеты Росстата являются основным источником необходимых данных. Эти отчеты представлены в форматах DOC, XLS, plain-text. При этом большинство таблиц в отчетах формата DOC являются включениями ASCII-текста, остальные являются табличными объектами Word. Каждое структурное описание извлеченной таблицы преобразуется в промежуточное представление, которое состоит из 1) таблицы формата СУБД «Paradox» (хранит в реляционном виде данные из статистической таблицы) и 2) текстового FNI (Field Name Information) файла (хранит информацию о структуре табличных заголовков и их связях с полями реляционного отношения). Для этого деревья заголовков структурного описания таблицы объединяются в одно дерево показателей. С помощью регулярных выражений в дереве показателей идентифицируются заголовки, обозначающие лексически «время» и «территории». Эти заголовки исключаются из дерева показателей и образуют два измерения — «время» и «территории». Также из дерева показателей исключаются игнорируемые заголовки, указывающие на вычислимые данные. Формируется реляционное отношение: элементы данных связанные с одним листом дерева показателей образуют поле, также два поля образуют соответственно значения измерений «время» и «территории». Формируется FNI файл, в котором каждой метке поля сопоставляется путь из дерева показателей. В БД АИС «Каскад» информация организована в виде дерева, узлами которого являются показатели из статистических отчетов. Для каждого промежуточного представления выполняется связывание со структурой БД АИС «Каскад», далее осуществляется автоматический ввод его данных.

Применение предлагаемой технологии для наполнения БД АИС «Кас-

кад» позволило снизить затраты и повысить качество при вводе в неё информации из электронных статистических отчетов.

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

Основные полученные результаты.

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

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

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

Список публикаций

[1] Шигаров А.О. Технология извлечения табличной информации из электронных документов разных форматов [Текст] / Шигаров А. О. // Современные технологии. Системный анализ. Моделирование. - 2009.

- № 3 (23). - С. 97-102.

[2] Бычков И.В. Эвристический метод обнаружения таблиц в разноформатных документах [Текст] / Бычков И.В., Ружников Г.М., Хмельнов А.Е., Шигаров А.О. // Вычислительные технологии. - 2009. - Т. 14, № 2.

- С. 58-73.

[3] Shigarov А.О. A method for table detection in metafiles [Текст] / Shigarov A.O., Bychkov I.V., Khmel'nov A.E., Ruzhnikov G.M. // Pattern Recognition and Image Analysis. - 2009. - Vol. 19, No 4. P. 693-697.

[4] Бычков И.В. Метод обнаружения таблиц в метафайлах [Текст] / Бычков И.В., Ружников P.M., Хмельнов А.Е., Шигаров А.О. // Современные технологии. Системный анализ. Моделирование. - 2008. - Спецвыпуск.

- С. 47-51.

[5] Хмельнов А.Е. Метод извлечения таблиц из неформатированного текста [Текст] / Хмельнов А.Е., Шигаров А.О. // Вычислительные технологии.

- 2008. - Т. 13, Спец. выпуск 1. - С. 93-101.

[6] Шигаров А.О. Автоматизированная система извлечения табличной информации из метафайлов [Текст] / Шигаров А.О. // Труды XIV Всероссийской конференции «Информационные и математические технологии в науке и управлении». - Иркутск, 2009. - Т. 2. - С. 218-224.

[7] Bychkov I.V. A method for table detection in metafiles [Текст] / Bychkov I.V., Hmelnov A.E., Ruzhnikov G.M., Shigarov A.O. //In Proc. 9th Int. Conf. on Pattern Recognition and Image Analysis: New Information Technologies. - Nizhni Novgorod, 2008. - Vol. 1. - P. 66-69.

[8] Хмельнов А.Е. Сегментация страницы документа для обнаружения таблиц [Текст] / Хмельнов А.Е., Шигаров А.О. // Труды XIII Всероссийской конференции Информационные и математические технологии в науке и управлении. - Иркутск, 2008. - Ч. 2. - С. 244-251.

[9] Шигаров А.О. Метод обнаружения таблиц в метафайлах [Текст] / Шигаров А.О. // Материалы Школы-семинара молодых ученых Информационные технологии и моделирование социальных эколого-экономических систем. - Иркутск, 2008. - С. 58-61.

[10[ Хмельнов А.Е. Метод извлечения статистических таблиц из неформатированного текста [Текст] / Хмельнов А.Е., Шигаров А.О. // Труды XII Всероссийской конференции Информационные и математические технологии в науке и управлении. - Иркутск, 2007. - Ч. 2. - С. 91-99.

п

[11] Хмельнов А.Е. Извлечение таблиц из неформатированного текста [Текст] / Хмельнов А.Е., Шигаров А.О. // Доклады 13-й Всероссийской конференции Математические методы распознавания образов (ММРО-13). - Зеленогорск, 2007. - С. 551-553.

[12] Хмельнов А.Е. Извлечение статистических таблиц из неформатированного текста [Текст] / Хмельнов А.Е., Шигаров А.О. // Материалы IX Школы-семинара Математическое моделирование и информационные технологии. - Иркутск, 2007. - С. 167-169.

Редакциокно-издательский отдел Учреждения Российской академии наук Института динамики систем и теории управления Сибирского отделения РАН 664033, Иркутск, ул. Лермонтова, 134 Подписано в печать 28.12.2009 Формат бумаги 60 х 84 1/16, объем 1,25 п.л. Заказ .V" 10. Тираж 100 экз. Отпечатано в ИДСТУ СО РАН

Условные обозначения

Введение

Глава 1. Анализ процесса извлечения табличной информации

1.1. Таблицы в документах

1.2. Статистические таблицы

1.3. Форматы входных данных

1.4. Метафайлы.

1.5. Известные методы и системы.

1.6. Технология извлечения табличной информации

Глава 2. Обработка страниц документов.

2.1. Обрабатываемые таблицы

2.2. Система координат

2.3. Модель страницы документа.

2.4. Выделение вертикальных промежутков.

2.5. Выделение горизонтальных промежутков

2.6. Обработка метафайлов

2.7. Предобработка страницы.

2.8. Обнаружение таблиц на странице документа.

Глава 3. Анализ и обработка таблиц

3.1. Модель таблицы.

3.2. Предобработка таблицы.

3.3. Анализ функций ячеек таблицы.

3.4. Сегментация таблицы.

3.5. Модель структурного описания таблицы

3.6. Структурный анализ таблицы

Глава 4. Практическое применение результатов.

4.1. Информационная система извлечения табличной информации

4.2. Представление структурных описаний таблицы в XML.

4.3. Экспериментальная оценка.

4.4. Автоматизация ввода информации в базу данных.

Актуальность исследования. Таблицы являются одним из наиболее используемых способов представления информации в документах. Часто такая табличная информация изначально представлена в базах данных. Однако базы данных не всегда доступны, открыты, содержат полную информацию. В связи с этим актуальность приобретают методы, системы и технологии извлечения табличной информации из документов, которые позволяют преобразовать её к требуемому виду, например, к отношениям в реляционных базах данных.

Актуальность данной проблематики подчеркивается в обзорах авторов Handley J.C. (1999) [17], Lopresti D. и Nagy G. (1999, 2000) [42, 43], Zanibbi R. (2004) [73, 74], Embley D.W. (2006) [10, 11], e Silva A.C. (2006) [9], Полевого Д. В. (2007) [84]. В литературе выделяется несколько задач связанных с извлечением табличной информации: 1) обнаружение — поиск на страницах документов областей, ограничивающих таблицы; 2) сегментация — разделение таблицы на отдельные ячейки, строки, столбцы; 3) анализ функций ячеек — определение того, какие функции выполняют отдельные ячейки таблицы (являются ли они заголовками или данными); 4) структурный анализ — определение связей между ячейками таблицы.

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

Автоматическое обнаружение и сегментация таблиц выполняется в некоторых системах оптического распознавания текста, например, «OmniPage» (Nuance Communications), «Cuneiform» (Cognitive Technologies), «FineReader» (ABBYY). Перечисленные системы ориентированы на «решёточную» структуру таблиц, характерную табличным процессорам, например, Excel. Это снижает их эффективность для обнаружения и сегментации таблиц со сложными структурами заголовков. Кроме того, оптическое распознавание символов выполняется с потерями информации. В системах «PDF2XL» (Cogniview) и «Solid Converter PDF» (Solid Documents), в частности, выполняется преобразование таблиц из документов PDF в файлы Excel/Word. Эти системы также ориентированы на «решёточную» структуру таблиц и выполняют только их обнаружение и сегментацию.

В статистических отчетах (государственных, медицинских, финансовых) основная информация представлена в виде так называемых статистических таблиц1. Вне зависимости от национальной или корпоративной принадлежности такие таблицы обладают достаточно схожей структурой. Большинство таких отчетов доступно в электронном виде, где таблицы, как правило, являются машиночитаемым текстом, т. е. электронным текстом, который хранится в виде строк символов. Однако в литературе не представлены методы или системы извлечения табличной информации, которые с одной стороны являются комплексными, т. е. выполняют обнаружение, сегментацию, анализ функций ячеек и структурный анализ таблиц, а с другой стороны ориентированы на структуру и особенности статистических таблиц, в частности, публикуемых Росстатом. Таким образом, разработка комплексной техноло

1 «Большая советская энциклопедия. Изд. 3-е» - М.: Советская энциклопедия. Т.25 «Струнино-Тихорецк». 1976. С. 161-162. http://slovari.yandex.ru/dict/bse/article/000T7/08800.htm гии извлечения табличной информации, которая ориентирована па структуру и особенности статистических таблиц, представленных в виде машиночитаемого текста в электронных документах, является актуальной задачей.

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

Основные задачи диссертационной работы.

1. Анализ представления статистических таблиц в документах.

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

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

4. Разработка информационной системы извлечения табличной информации из электронных документов на основе предложенных методов.

5. Проверка созданной технологии на задачах автоматизации ввода больших объемов табличной информации из электронных статистических отчетов в базы данных.

Методы исследования: теория множеств, теория баз данных, методы машинной графики, объектно-ориентированное программирование.

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

Практическая значимость. Результаты диссертационной работы могут использоваться в задачах извлечения информации и управления данными. В частности, предлагаемая технология может использоваться для автоматизации ввода в базы данных информации из статистических таблиц, представленных в виде машиночитаемого текста в электронных документах разных форматов. При этом данная технология позволяет снизить затраты и повысить качество формирования баз данных. Работа выполнена при поддержке РФФИ, грант 09-07-12017-офим.

Внедрение. Результаты диссертационной работы успешно использовались в Министерстве сельского хозяйства Иркутской области для ввода информации из электронных статистических отчетов Территориального органа федеральной службы государственной статистики по Иркутской области (Ир-кутскстата) в базу данных (БД) автоматизированной информационной системы (АИС) «Каскад». Предлагаемая технология внедрена в Институте систем энергетики им. JI.A. Мелентьева СО РАН, где используется при создании хранилища данных в составе информационной инфраструктуры исследований в энергетике.

Защищаемые положения.

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

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

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

Личный вклад автора. Основные результаты диссертационной работы получены автором лично, а именно: предложены модель страницы документа, эвристические методы обнаружения, сегментации, анализа функций ячеек и структурного анализа статистических таблиц; разработана информационная система для извлечения табличной информации из метафайлов EMF (Enhanced Metafiles); создана технология извлечения табличной информации из электронных документов разных форматов. В неделимом соавторстве с А.Е. Хмельновым получена модель структурного описания таблицы. В неделимом соавторстве с А.Е. Хмельновым, И.В. Бычковым и Г.М. Руж-никовым получено применение предлагаемой технологии для автоматизации ввода статистической информации в базу данных АИС «Каскад». В работах [89-91, 94, 95] автором лично предложен эвристический метод обнаружения таблиц и технология извлечения табличной информации из электронных документов разных форматов. В работах [92, 97-99] автором в неделимом соавторстве с А.Е. Хмельновым предложена модель структурного описания таблицы.

Представление работы. Основные результаты работы докладывались на научно-практических конференциях: Международной конференции «Математические и информационные технологии» (Будва, Черногория, 2009 г.); IX международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (Нижний Новгород, 2008 г.); XII, XIII и XIV всероссийской конференции «Информационные и математические технологии в науке и управлении» (Иркутск, 2007, 2008, 2009 гг.); Всероссийской конференции «Математическое моделирование и вычислительно-информационные технологии в междисциплинарных научных исследованиях» (Иркутск, 2009 г.); VI и IX школе-семинаре «Математическое моделирование и информационные технологии» (Иркутск, 2005, 2007 гг.); Школе-семинаре молодых ученых «Информационные технологии и моделирование социальных эколого-экономических систем» (Иркутск, 2008 г.); семинаре «Ляпуповские чтения и презентация информационных технологий» (Иркутск, 2007, 2008, 2009 гг.).

Публикации. По теме диссертации опубликовано 12 научных работ [88-99], в т.ч. 3 публикации [88-90] в изданиях, рекомендованных ВАК. Получено 4 свидетельства об официальной регистрации программ для ЭВМ в Роспатенте [100-103]: Ж№ 2008614328, 2008614330, 2008614331, 2008614332 (2008 г.).

Заключение

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

В рамках диссертационной работы получены следующие основные результаты.

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

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

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

Предлагаемая технология может развиваться в следующих направлениях.

1. Использование словаря словоформ русского языка для объединения частей одного слова (например, в тех случаях, когда в тексте таблицы используются переносы слов).

2. Использование словарей ключевых слов (заголовков таблиц специфичных для некоторой предметной области) для поиска заголовков столбцов, строк и перерезов таблиц.

3. Использование анализа разграфки таблиц в качестве дополнительного средства обнаружения таблиц.

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

1. Amano A., Asada N., Mukunoki M., Aoyama M. Table form document analysis based on the document structure grammar // 1.ternational Journal of Document Analysis. Springer-Verlag. 2006. Vol. 8, No 2-3. P. 201-213.

2. Amano A., Asada N. Graph Grammar Based Analysis System of Complex Table Form Document //In Proc. Tth International Conference on Document Analysis and Recognition. IEEE Computer Society. 2003. Vol. 2. P. 916-920.

3. Cesarini F., Marinai S., Sarti L., Soda G. Trainable table location document images //In Proc. 16th International Conference on Pattern Recognition (ICPR 02). IEEE Computer Society. 2002. Vol. 3. P. 236-240.

4. Chandran S., Kasturi R. Structural recognition of tabulated data //In Proc. 2nd International Conference on Document Analysis and Recognition (ICDAR 93). Japan. IEEE Computer Society. 1993, P. 516-519.

5. Cohen W.W., Hurst M., Jensen L.S. A flexible learning system for wrapping tables and lists in HTML documents //In Proc. 11th International World Wide Web Conference. USA. 2002. P. 232-241.

6. Douglas S., Hurst M., David Q. Using Natural Language Processing for Identifying and Interpreting Tables in Plain Text //In Proc. 4th Annual

7. Embley D.W., Hurst M., Lopresti D., Nagy G. Table-processing paradigms: a research survey // International Journal on Document Analysis and Recognition. Springer-Verlag. 2006. Vol. 8, No. 2. P. 66-86.

8. Embley D.W., Lopresti D., Nagy G. Notes on Contemporary Table Recognition //In Proc. 7th Int. Workshop on Document Analysis Systems. Springer-Verlag. 2006. P. 164-175.

9. Gatterbauer W., Bohunsky P., Herzog M., Krupl В., Pollak B. Towards domain independent information extraction from Web tables //In Proc. 16th International World Wide Web Conference. Canada. ACM. 2007. P. 71-80.

10. Gatterbauer W., Bohunsky P. Table extraction using spatial reasoning on the CSS2 visual box model // In Proc. 21st AAAI. AAAI Press. 2006. P. 1313-1318.

11. Green E., Krishnamoorthy M. Model-based analysis of printed tables // In Proc. 3rd International Conference on Document Analysis and Recognition (ICDAR 95). IEEE Computer Society. 1995. Vol. 1. P. 214-217.

12. Handley J.C. Document recognition // Electronic Imaging Technology. Chapter 8. IS&T/SPIE Optical Engineering Press. 1999. P. 289-316.

13. Handley J.C. Table analysis for multiline cell identification // In Proc. Document Recognition and Retrieval VIII. SPIE. Vol. 4307-04. P. 34-43.

14. Hassan Т., Baumgartner R. Table Recognition and Understanding from PDF Files // In Proc. 9th International Conference on Document Analysis and Recognition (ICDAR 2007). IEEE Computer Society. 2007. P. 1143-1147.

15. Hirayama Y. A method for table structure analysis using DP matching // In Proc. 3rd International Conference on Document Analysis and Recognition (ICDAR 95). Canada. IEEE Computer Society. 1995. P. 583-586.

16. Hori O., Doermann D.S. Robust table-form structure analysis based on box-driven reasoning //In Proc. 3rd International Conference on Document Analysis and Recognition. IEEE Computer Society. 1995. Vol. 1. P. 218-221.

17. HTML 4.01 Specification, http: //www. w3. org/TR/html4.

18. Hu J., Kashi R., Lopresti D., Wilfong G. Table Structure Recognition and its Evaluation //In Proc. Document Recognition and Retrieval VIII. USA. IS&T/SPIE Electronic Imaging. 2001. Vol. 4307 P. 44-55.

19. Hu J., Kashi R., Lopresti D., Wilfong G. Medium-Independent Table

20. Detection //In Proc. Document Recognition and Retrieval VII. USA. IS&T/SPIE Electronic Imaging. 2000. P. 291-302.

21. Hurst M. A constraint-based approach to table structure derivation // In Proc. 7th International Conference on Document Analysis and Recognition (ICDAR 2003). IEEE Computer Society. 2003. P. 911-915.

22. Hurst M. Layout and Language: An Efficient Algorithm for Text Block Detection based on Spatial and Linguistic Evidence // Document Recognition and Retrieval VIII. USA. SPIE. 2001. Vol. 4307. P. 55-67.

23. Hurst M. Layout and language: challenges for table understanding on the web //In Proc. First International Workshop on Web Document Analysis. Seattle. 2001. P. 27-30.

24. Hurst M., Douglas S. Layout and Language: Preliminary investigations in recognizing the structure of tables //In Proc. 4th International Conference on Document Analysis and Recognition (ICDAR 97). Germany. IEEE Computer Society. 1997. P. 1043-1047.

25. Itonori K. A table structure recongnition based on textblock arrangement and ruled line position //In Proc. 2nd International Conference on Document Analysis and Recognition (ICDAR 93). Japan. IEEE Computer Society. 1993. P. 765-768.

26. Kieninger T. Table structure recognition based on robust block segmentation // In Proc. Document Recognition V. USA. IS&T/SPIE Electronic Imaging. 1998. Vol. 3305. P. 22-32.

27. Kieninger Т., Dengel A. Applying the T-Recs table recognition system to the business letter domain //In Proc. 6th International Conference on Document

28. Analysis and Recognition (ICDAR 2001). IEEE Computer Society. 2001. R 518-522.

29. Kieninger Т., Dengel A. The T-Recs Table Recognition and Analysis System // Lecture Notes in Computer Science. Springer-Verlag. 1999. Vol. 1655. R 255-270.

30. Klein В., Gokkus S., Kieninger Т., Dengel A. Three Approaches to Industrial Table Spotting //In Proc. 6th International Conference on Document Analysis and Recognition (ICDAR 2001). USA. IEEE Computer Society. 2001. P. 513-517.

31. Kojima H., Akiyama Т., Table Recognition for Automated Document Entry System // SPIE Vol. 1384, High Speed Inspection Architectures, Barcoding, and Character Recognition. 1990. P. 285-292.

32. Kriipl В., Herzog M., Gatterbauer W. Using Visual Cues for Extraction of Tabular Data from Arbitrary HTML Documents // In Proc. 14th International Conference on World Wide Web. Japan. ACM. 2005. P. 1000-1001.

33. Kriipl В., Herzog M. Visually guided bottom-up table detection and segmentation in web documents //In Proc. 15th International Conference on World Wide Web. Scotland. ACM. 2006. P. 933-934.

34. Lang T.A., Secic M. «How to Report Statistics in Medicine: Annotated Guidelines for Authors, Editors, and Reviewers (2nd edition)». American College of Physicians, 2006. 490 c.

35. Lerman K., Getoor L., Minton S., Knoblock C. Using the structure of Web sites for automatic segmentation of tables //In Proc. 2004 ACM SIGMOD International Conference on Management of Data. ACM. 2004. P. 119-130.

36. Li J., Tang J., Song Q. Xu P. Table Detection from Plain Text Using Machine Learning and Document Structure // Lecture Notes in Computer Science. Springer-Verlag. 2006. Vol. 3841/2006. P. 818-823.

37. Liu Y., Bai K., Mitra P., Giles C. Searching for Tables in Digital Documents //In Proc. 9th International Conference on Document Analysis and Recognition. IEEE Computer Society. 2007. Vol. 2. P. 934-938.

38. Lopresti D., Nagy G. A tabular survey of automated table processing // Lecture Notes in Computer Science. Springer-Verlag. 2000. Vol. 1941. P. 93-120.

39. Lopresti D., Nagy G. Automated table processing: An (opinionated) survey // Third IAPR International Workshop on Graphics Recognition. India. 1999. P. 109-134.

40. Mandal S., Chowdhury S.P., Das A.K., Chanda B. A simple and effective table detection system from document images // International Journal on Document Analysis and Recognition. Springer-Verlag. 2006. Vol. 8, No. 2. P. 172-182.

41. Mandal S., Chowdhury S.P., Das A.K., Chanda B. A Complete System for Detection and Identification of Tabular Structures from Document Images // Lecture Notes in Computer Science. Springer-Verlag. 2004. Vol. 3212/2004. P. 217-225.

42. Microsoft Developer Network, http://msdn.microsoft.com.

43. Ng H.T., Lim C.Y., Li Teng Koo J. Learning to recognize tables in free text //In Proc. 37th Annual Meeting of the Association for Computational Linguistics. USA. 1999. P. 443-450.

44. Pyreddy P., Croft W.B. A System for Retrieval in Text Tables // Technical report. University of Massachusetts, USA. 1997.

45. Pyreddy P., Croft W.B. Tintin: a system for retrieval in text tables //In Proc. 2nd International Conference on Digital Libraries. USA. 1997. P. 193-200.

46. Ramel J.-Y., CrucianuM., Vincent N., FaureC. Detection, Extraction and Representation of Tables // In Proc. 7th International Conference on Document Analysis and Recognition (ICDAR 2003). IEEE Computer Society. 2003, Vol. 2. P. 374-379.

47. Rus D., Summers K. // Using White Space for Automated Document Structuring // Technical Report TR94-1452. Cornell University, USA. 1994. 33 c.

48. Shamillian J. H., Baird H.S., Wood T.L. A retargetable table reader // In Proc. 4th International Conference on Document Analysis and Recognition (ICDAR 97). IEEE Computer Society. 1997. P. 448-453.

49. Tengli A., Yang Y., Ma N.L. Learning table extraction from examples // In Proc. 20th International Conference on Computational Linguistics. Switzerland. Association for Computational Linguistics. 2004. P. 987-993.

50. Tersteegen W.T., Wenzel C. Scantab: Table recognition by reference tables // In Proc. 3rd IAPR Workshop on Document Analysis Systems (DAS 98). Japan. 1998. P. 356-365.

51. Tuerino Y. A., Embley D. W., Lonsdale D. W., Ding Y., Nagy G. Towards ontology generation from tables. // World Wide Web. Kluwer Academic Publishers. 2005. Vol. 8, No. 3. P. 261-285.

52. Tupaj S., Shi Z., Chang С. H., Alam H. Extracting Tabular Information From Text Files // EECS Department, Tufts University, Medford, USA. 1996. 18 c. (http://citeseer.nj .nec.com).

53. Wang Y. Document analysis: Table Structure Understanding and Zone Content Classification, Ph.D. thesis // University of Washington, USA. 2002. 179 c.

54. Wang Y., Hu J. A machine learning based approach for table detection on the web //In Proc. 11th International World Wide Web Conference. 2002. P. 242-250.

55. Wang Y., Hu J. Detecting tables in HTML documents // Lecture notes in computer science. Springer-Verlag. 2002. Vol. 2423. P. 249-260.

56. Wang Y., Phillips I.Т., Haralick R. Table detection via probability-optimization // Lecture Notes In Computer Science. Springer-Verlag. 2002. Vol. 2423. P. 272-282.

57. Wasserman H.C., Yukawa K, Sy B.K, Kwok K.-L., Phillips I.T. A Theoretical Foundation and a Method for Document Table Structure Extraction and Decompositon // Lecture Notes In Computer Science. Springer-Verlag. 2002. Vol. 2423. P. 291-294.

58. Watanabe Т., Quo Q.L., Sugie N. Layout recognition of multikinds of table-form documents // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1995. Vol. 17, No 4, P. 432-445.

59. Weizsacker L., Fiirnkranz J. On Table Extraction from Text Sources with Markups // Technical Report TUD-KE-2008-05. Knowledge Engineering group, Technical University Darmstadt, Germany. 2008. 22 c.

60. XHTML 1.0 The Extensible Hypertext Markup Language, Second Edition, http://www.w3.org/TR/xhtml1.

61. Xi D. Lee S.-W. Table Structure Extraction from Form Documents Based on Gradient-Wavelet Scheme // Lecture Notes in Computer Science. Springer-Verlag. 1999. Vol. 1655/1999. P. 240-254.

62. Yoshida M., Torisawa K., Tsujii J. A method to integrate tables of the World Wide Web //In Proc. 1st International Workshop on Web Document Analysis. USA. 2001. P. 31-34.

63. Zanibbi R. A Language for Specifying and Comparing Table Recognition Strategies, Ph.D. thesis // Queen's University Kingston, Canada. 2004. 236 c.

64. Zanibbi R., Blostein D., Cordy J. R. A survey of table recognition: Models, observations, transformations, and inferences // International Journal on Document Analysis and Recognition. Springer-Verlag. 2004. Vol. 7, No. 1. P. 1-16.

65. Вигдорчик В.А. «Ручной набор», М. 1985. 289 с.78. под ред. Бащинского С.Е., Власова В.В. «Рекомендации по подготовке научных медицинских публикаций: Сборник статей и документов». М. Медиа Сфера. 2006. 459 с.

66. Волкова JI.A. «Основы наборных процессов», М. 1986. 416 с.

67. ГОСТ 2.105-95 ЕСКД «Общие требования к текстовым документам» — М.: ИПК Издательство стандартов, 2001. 27 с.

68. Мильчин А.Э. «Издательский словарь-справочник» — М.: ОЛМА-Пресс, 2003. 560 с.

69. Мильчин А.Э., Чельцова JI.K. «Справочник издателя и автора. Редак-ционно-издательское оформление издания, 2-е издание», М. Олимп. 2003. 800 с.83. под ред. Мильчина А.Э. «Справочная книга редактора и корректора», М. 1985. 576 с.

70. Полевой Д.В. «Таблицы в системах обработки документов». М. ЛКИ, 2007. 48 с.

71. Полевой Д.В. Разработка моделей, методов и средств обработки табличных документов в информационных системах: Автореф. дис. канд. тех. наук. МФТИ, 2007. 21 с.

72. Хмелыюв А.Е. Язык FlexT для спецификации бинарных форматов данных. Дис. канд. тех. наук. Иркутск. 2000. 118 с.

73. Хмельнов А.Е. Свидетельство об официальной регистрации программы для ЭВМ № 2008614995 «Рабочие место администратора хранилища статистической информации (AttrTree)» / Бычков И.В., Ружников Г.М., Хмельнов А.Е., Шигаров А.О. // 2008.

74. Шигаров А.О. Технология извлечения табличной информации из электронных документов разных форматов Текст] / Шигаров А.О. // Современные технологии. Системный анализ. Моделирование. 2009. - N5 3 (23).- С. 97-102.

75. Бычков И.В. Эвристический метод обнаружения таблиц в разноформатных документах Текст] / Бычков И.В., Ружников Г.М., Хмельнов А.Е., Шигаров А.О. // Вычислительные технологии. 2009. - Т. 14, № 2.- С. 58-73.

76. Shigarov А.О. A method for table detection in metafiles Текст] / Shigarov A.O., Bychkov I.V., Khmel'nov A.E., Ruzhnikov G.M. // Pattern Recognition and Image Analysis. 2009. - Vol. 19, No 4. P. 693-697.

77. Бычков И.В. Метод обнаружения таблиц в метафайлах Текст] / Бычков И.В., Ружников Г.М., Хмелыюв А.Е., Шигаров А.О. // Современныетехнологии. Системный анализ. Моделирование. 2008. - Спецвыпуск. - С. 47-51.

78. Хмельнов А.Е. Метод извлечения таблиц из неформатированного текста Текст] / Хмельнов А.Е., Шигаров А.О. // Вычислительные технологии. 2008. - Т. 13, Спец. выпуск 1. - С. 93-101.

79. Шигаров А.О. Автоматизированная система извлечения табличной информации из метафайлов Текст] / Шигаров А.О. // Труды XIV Всероссийской конференции «Информационные и математические технологии в науке и управлении». Иркутск, 2009. - Т. 2. - С. 218-224.

80. Хмельнов А.Е. Сегментация страницы документа для обнаружения таблиц Текст] / Хмельнов А.Е., Шигаров А.О. // Труды XIII Всероссийской конференции Информационные и математические технологии в науке и управлении. Иркутск, 2008. - Ч. 2. - С. 244-251.

81. Шигаров А.О. Метод обнаружения таблиц в метафайлах Текст] / Шигаров А.О. // Материалы Школы-семинара молодых ученых Информационные технологии и моделирование социальных эколого-экономических систем. Иркутск, 2008. - С. 58-61.

82. Хмельнов А.Е. Извлечение таблиц из неформатированного текста Текст] / Хмелыюв А.Е., Шигаров А.О. // Доклады 13-й Всероссийской конференции Математические методы распознавания образов (ММРО-13). Зе-леногорск, 2007. - С. 551-553.

83. Хмелыюв А.Е. Извлечение статистических таблиц из неформатированного текста Текст] / Хмельнов А.Е., Шигаров А.О. // Материалы IX Школы-семинара Математическое моделирование и информационные технологии. Иркутск, 2007. - С. 167-169.

84. Бычков И.В. Свидетельство об официальной регистрации программы для ЭВМ № 2008614328 «Программное инструментальное средство обнаружения таблиц в документах (Tablocator)» / Бычков И.В., Ружников Г.М., Хмельнов А.Е., Шигаров А.О. // 2008.

85. Бычков И.В. Свидетельство об официальной регистрации программы для ЭВМ № 2008614332 «Программная система извлечения таблиц из электронных документов (Tabextractor)» / Бычков И.В., Ружников Г.М., Хмельнов А.Е., Шигаров А.О. // 2008.1. Примеры