Синтаксические методы контекстной обработки в задачах распознавания текста тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Шоломов, Дмитрий Львович

• Шоломов, Дмитрий Львович
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Шоломов, Дмитрий Львович

ВВЕДЕНИЕ.

Актуальность темы исследования.

Предмет работы.

Цель работы.

Методы исследования.

Практическая ценность и апробация работы.

Публикации.

Структура и объем работы.

1. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ КОНТЕКСТНОЙ ОБРАБОТКИ.

1.1. N-граммы.

1.2. Динамическое программирование.

1.2.1. Дискретный процесс управления.

1.2.2. Метод динамического программирования.

1.2.3. Алгоритм Левенштейна.

1.2.4. Обзор работ.

1.3. Скрытые марковские модели.

1.3.1. Определение СММ.

1.3.2. Обзор работ.

1.4. Нейронные сети.

1.5. Методы коррекции и валидации текстов.

1.5.1. Словарные методы.

1.5.2. Вероятностные методы.

1.5.3. Техника похожих ключей.

1.5.4. Сравнение методов.

1.6. Классификационные методы.

1.7. Методы синтаксического анализа.

1.7.1. Формальные языки. Компилирование.

1.7.2. Естественные языки. Компьютерная лингвистика.

1.8. Выводы.

2. СИНТАКСИЧЕСКИЕ МЕТОДЫ КОНТЕКСТНОЙ ОБРАБОТКИ.

2.1. Представление результатов распознавания. AP-сеть, АР-цепь, АР-матрица.

2.2. Формальные языки и грамматики, синтаксические диаграммы.

2.2.1. Язык.

2.2.2. Понятие грамматики. ГрамматикаХомского.

2.2.3. Нотация Бэкуса-Наура.

2.2.4. Синтаксические диаграммы.

2.2.5. PDS грамматика.

2.3. Классификация типов полей на формах.

2.3.1. Словарное поле.

2.3.2. Текст на естественном языке.

2.3.3. Поле с заданным синтаксисом.

2.3.4. Поле, описываемое синтаксисом частично.

2.3.5. Поле с нефиксированным текстовым представлением.

2.3.6. Поля со специальными ограничениями.

2.4. Постановка задачи контекстной обработки.

2.4.1. Восстановление текстового значения.

2.4.2. Классификация т екстового значения.

2.4.3. Приведение распознанного значения к нормальной форме.

2.4.4. Оценка степени надежности распознанного значения.

2.4.5. Локализация ненадежных фрагментов.

2.4.6. Нахождение опорных фрагментов.

2.5. Поиск заданного текстового фрагмента в АР-цепи. Алгоритм MCHSR.

2.5.1. Структура результатов распознавания.

2.5.2. Описание алгоритма MCHSR.

2.6. Синтаксический подход.

2.6.1. О подходе.

2.6.2. Основная алгоритмическая схема.

2.6.3. ОП-процедура.

2.6.4. Эксперименты и результаты.

2.7. Подход с использованием частично-определенного синтаксиса.

2.7.1. Предпосылки создания.

2.7.2. Схема алгоритма.

2.7.3. Эксперименты и результаты.

2.7.4. Выводы.

2.8. Классификация полей с нефиксированным текстовым представлением.

2.8.1. Признаки и функции выделения признаков.

2.8.2. Построение первичного классификатора.

2.8.3. Сравнение функций выделения признаков.

2.8.4. Задача с неизвестными классами.

2.8.5. Сглаживание.

2.8.6. Проблема зависимости признаков.

2.8.7. Реализация и выводы.

2.9. Выводы.

3. ВНЕДРЕНИЯ И ОСОБЕННОСТИ ТЕХНИЧЕСКОЙ РЕАЛИЗАЦИИ.

3.1. Система массового ввода структурированных документов.

3.1.1. Обзор системы.

3.1.2. Стадии технологической цепочки ввода документов.

3.1.3. Основные компоненты системы.

3.2. Подсистема контекстной обработки.

3.2.1. Назначение подсистемы.

3.2.2. Структура подсистемы.

3.2.3. Процесс создания функций контекстной обработки.

3.3. Внедренные проекты и особенности технической реализации.

3.3.1. Ввод документов пенсионного страхования.

3.3.2. Ввод анкет школьников и студентов.

3.3.3. Ввод банковских документов.

3.3.4. Ввод отгрузочныхразнадядок в ОАО "Сибнефть ".

3.3.5. Ввод счетов-фактур в Магнитогорском Металлургическом Комбинате.

Введение диссертации (часть автореферата) на тему «Синтаксические методы контекстной обработки в задачах распознавания текста»

Актуальность темы исследования

В настоящее время системы распознавания и идентификации структурированных документов и форм широко используются в сфере информационных технологий. В рамках проч цесса распознавания и автоматизированной обработки современных деловых документов контекстная обработка является одним из ключевых этапов. Обработка документа подразумевает его ввод с бумажного носителя, сортировку, маршрутизацию и т.п. Программы оптического распознавания текста (OCR), ставшие за последние время необходимой частью офисного программного обеспечения, успешно решают задачу ввода текстовой информации. При этом если в 80-х или начале 90-х годов основные усилия разработчиков были направлены на повышение точности распознавания "гладкого" текста, то в последние годы все более актуальным свойством систем автоматизированного ввода информации с отсканированного графического образа документа становится возможность "понимания" структуры бумажного документа и создания адекватной электронной модели. В частности, важным элементом задания структуры документа является задание синтаксических ограничений при описании полей ввода.

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

Основной качественной характеристикой при вводе документов с бумажного носителя является скорость ввода. В промышленных системах доля автоматически вводимых полей составляет 70-90%. Более высокий процент достигается редко - реальные документы, как правило, имеют дефекты, привнесенные при печати и сканировании, помарки при ручном заполнении полей. Для профессионального оператора среднее время, затрачиваемое на проверку поля обычно в 1.5-2 раза больше чем при последовательном чтении и вводе текстового значения. В связи с этим, если для подтверждения предъявляется более 50% полей, скорость автоматизированного ввода сравнима с вариантом ручного ввода. Учитывая, что вариант автоматизированного ввода использует более дорогостоящие технические средства, системы с долей автоматической обработки менее 60-70% обычно становятся неэффективными. Априорное знание синтаксической структуры поля позволяет существенно сократить количество ошибок распознавания, а также уменьшить число правильно распознанных полей с признаком сомнительности, тем самым увеличивая скорость. Таким образом, синтаксические методы контекстной обработки в целом могут существенно повысить эффективность промышленных систем ввода деловых документов, а задача разработки таких методов является весьма актуальной.

Предмет работы

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

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

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

• автоматической коррекции результатов распознавания с учетом синтаксической и семантической структуры поля,

• автоматического определения достоверности результатов распознавания полей на структурированных документах в задачах ввода стандартных форм,

• локализации недостоверных фрагментов распознанного поля,

• нормализации распознанного значения,

• классификации значений полей ввода на формах,

• практической реализации алгоритмов контекстной обработки в рамках систем автоматизированного ввода деловой информации.

Цель работы

Целью диссертации является разработка универсальных синтаксических методов и алгоритмов контекстной обработки полей ввода на структурированных документах и анализ их качественных характеристик. Также целью является комплексное рассмотрение задачи контекстной обработки - классификация типов полей ввода, изучение, построение и сравнение методов, пригодных для улучшения качества их распознавания. Практическая цель работы заключается в реализации подсистемы контекстной обработки, использующей алгоритмы и методы, предложенные в работе, к решению практических задач автоматизированного ввода деловой информации в рамках системы Cognitive Forms [АПШ02], далее по тексту - Системы.

Методы исследования

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

Научная новизна

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

Разработан специальный метаязык синтаксического описания множества допустимых текстовых значений на основе предложенной автором PDS-грамматики, определяемой при помощи нотации Бэкуса-Наура. Это позволило в рамках единой алгоритмической схемы обрабатывать широкий спектр полей с учетом специфики их структуры. При этом, несмотря на независимость алгоритмического ядра от особенностей конкретных полей ввода, обеспечена возможность использования специальных знаний, что существенно улучшает качество контекстной обработки. Кроме того, в диссертации задача контекстной обработки полей ввода рассмотрена комплексно - приведена математическая постановка задачи, описана классификация типов полей, встречаемых на формах, и приведен обзор алгоритмов для обработки указанных классов полей.

Практическая ценность и апробация работы

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

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

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

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

• ввод документов персонифицированного учета в Московском и Санкт-петербургском отделениях Пенсионного фонда России,

• ввод платежных документов в Сбербанке РФ и других коммерческих банках,

• ввод отгрузочных разнарядок в ОАО "Сибнефть",

• ввод анкет школьников и студентов, анкет-заявок на изготовление "Социальной карты москвича",

• ввод счетов-фактур, договоров, актов, накладных и товаросопроводительных документов в Магнитогорском металлургическом комбинате.

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

• 6-ая Международная конференции «Распознавание образов и анализ изображений: новые информационные технологии». Великий Новгород, 2002;

• The International Conference on Machine Learning, Technologies and Applications (MLMTA'03), 2003, USA;

• 6th German-Russian Workshop on Pattern Recognition and Image Understanding (OGRW-6), 2003;

• The International Conference on Machine Learning, Technologies and Applications (MLMTA'04), 2004, USA.

Кроме того, подходы, отраженные в работе, неоднократно представлялись на семинарах Института системного анализа РАН и Института проблем информатики РАН.

Публикации

По теме диссертации автором опубликовано одиннадцать работ. Шесть из них опубликованы в рецензируемых научных изданиях, рекомендуемых ВАК.

Структура и объем работы

Диссертация состоит из трех глав, введения, заключения и списка литературы. Работа изложена на 121 странице машинописного текста, содержит 42 иллюстрации и 9 таблиц. Список литературы включает 136 наименований. Работа организована следующим образом:

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

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

В главе "Синтаксические методы контекстной обработки" представлены основные результаты работы - ряд новых методов контекстной обработки полей ввода. Глава состоит из двух частей. В первой приведена математическая постановка задачи контекстной обработки - вводится описание структуры результатов распознавания, варианты возникающих подзадач. Вводится понятие языка, грамматики и способов ее описания, определяется PDS-грамматика, используемая в синтаксическом методе основанных на частичном описании структуры поля. Также глава содержит классификацию типов полей встречаемых на формах с точки зрения контекстной обработки, указаны методы их обработки. Во второй части главы приводятся новые методы контекстной обработки полей, структура которых задается при помощи грамматик в виде синтаксических диаграмм либо посредством PDS-грамматики, указаны алгоритмы решения, приведены их качественные характеристики.

Глава "Внедрения и особенности технической реализации" посвящена обзору системы массового ввода документов Cognitive Forms, в рамках которой были реализованы и апробированы описанные в работе алгоритмы и методы. Приводится краткий обзор системы, рассматривается подсистема контекстной обработки. Приводятся реализованные на базе системы и внедренные проекты по массовому вводу документов. Рассматриваются особенности документов и технологии ввода, а также тонкости технической реализации.

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Шоломов, Дмитрий Львович

Основные результаты, изложенные в диссертации, опубликованы в работах [АПШ02], [Шол02], [PSM03], [Sho03a], [Sho03b], [PS04], [ПМШ04], [Шол04], [ШПМ05], [Шол07а], [Шол07Ь]. В период с 2002 по 2007 годы результаты неоднократно докладывались и обсуждались на международных научных конференциях в России и за рубежом. Помимо этого методы синтаксической обработки были представлены автором на ряде семинаров Института Системного Анализа РАН и Института Проблем Информатики РАН.

Заключение. Выводы.

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

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

2. Предложены методы описания полей ввода при помощи порождающих КС-грамматик Хомского в виде синтаксических диаграмм. Предложен метаязык синтаксического описания (PDS-грамматика), применимый для описания полей, структура которых определена частично.

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Шоломов, Дмитрий Львович, 2007 год

1. АВ95. J.C. Anigbogu and A. Belaid, Hidden Markov Models in Text Recognition, HIJPRAI, Vol.9, No.6, pp. 925-958,1995

2. Arn94. D.J. Arnold, Lorna Balkan, Siety Meijer, R.Lee Humphreys and Louisa Sadler Machine Translation: an Introductory Guide. HBlackwells-NCC, London

3. ASU86. Aho A., Sethi R., Ullman J. Compilers: principles, techniques and tools, //N.Y., Addison-Wesley, 1986.

4. BDS92. Peter F. Brown and Vincent J. Delia Pietra and Peter V. deSouza and Jennifer C. Lai and Robert L. Mercer. Class-Based n-gram Models of Natural Language. I I Computational Linguistics, vol. 18, no. 4, pp. 467-479,1992.

5. BGS97. Djamel Bouchaffra and Venu Govindaraju and Sargur N. Srihari. Postprocessing of Recognized Strings Using Nonstationary Markovian Models. I/IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21 no. 10, pp. 990-999,1997.

6. BGS98. D. Bouchaffra and V. Govindaraju and S. Srihari A Methodology for Determining Probability of Correctness of Recognizer Scores UProc. IEEE Conf. Computer Vision and Pattern Recognition, Santa Barbara, Calif., June 1998

7. Bis95. Christopher M. Bishop Neural Networks for Pattern Recognition // Oxford University Press (1995).

8. BJG03. Steven Beitzel, Eric Jensen and David Grossman. A Survey of Retrieval Strategies for OCR Text Collections. UProc. of2003 Symposium on Document Image Understanding Technology, April 2003

9. Blul. Michael Blumenstein and Brijesh Verma. A Neural Network for Real-World Postal Address Recognition.

10. BRR02. Anja Brakensiek, Jorg Rottland and Gerhald Rigoll. Handwritten Address Recognition with Open Vocabulary Using Character N-grams. UProc. of 8th International Workshop on Frontiers in Handwriting Recognition (IWFHR), 2002.

11. CC95. C.L.A. Clarke and G.V. Cormack. On the use of regular expressions for searching text. //Technical Report CS-95-07, Department of Computer Science, University of Waterloo, February 1995

12. CDD97. C. Cracknell, A. C. Downton, L. Du. An Object-Oriented form Description Language and Approach to Handwritten Form Processing. H4th International Conference Document Analysis and Recognition (ICDAR '97) Volume I and Volume II. 1997. pp. 180.

13. CFM92. Casey, D. Ferguson, K. Mohiuddin, and E. Walach, "Intelligent forms processing system," Machine Vision and Applications, vol. 5, no. 3 pp. 1443-1455,1992

14. CG98. Stanley F. Chen, Joshua Goodman. An empirical study of smoothing techniques for language modeling //Technical Report TR-10-98, Computer Science Group, Harvard University, 1998

15. CGM+98. F. Cesarini, M. Gori, S. Marinai, and G. Soda, "INFORMys: A Flexible InvoiceLike Form-Reader System" //IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 7, pp. 730-745, July 1998

16. СКР92. Doug Cutting, Julian Kupiec, Jan Pedersen, Penelope Sibun, A practical part-of-speech tagger, HProc. of the third conference on Applied natural language processing, March 31-April 03,1992, Trento, Italy

17. CMM99. David Y. Chen, Jianchang Mao, K. Mohiuddin. An Efficient Algorithm for Matching a Lexicon with a Segmentation Graph. //Fifth International Conference on Document Analysis and Recognition, India, September 1999.

18. CV89. Cherkassky, V., and Vassilas, N. Back propagation networks for spelling correction. //Neural Networks 1, 3 (July), 166-173,1989

19. Dam90. Damerau. F. J. Evaluating computer-generated domain-oriented vocabularies. //Inf. Process. Manage. 26, 6, pp 791-801.1990

20. Dav62. Davidson, L. Retrieval of misspelled names in an airline passenger record system. //Community A CM 5,169-171,1962

21. DEG90. Deffiier, R, Eder, K, and Geiger, H. Word recognition as a first step towards natural language processing with artificial neural nets. //In Proceedings of KONNAI-90. 1990

22. DHS01. R. 0. Duda, P. E. Hart and D. G. Stork, Pattern Classification (2nd ed.), //John Wiley and Sons, 2001

23. Doul. Shona Douglas. Customising Grammar and Style Checker Rules //Centre for Cognitive Science University of Edinburgh

24. Elt88. Elliot, R. J. 1988. Annotating spelling list words with affixation classes. //AT&T Bell Labs Int. Mem. Dec. 14.

25. ESS96. Emelyanov N.E., Solovyev A.V., Schelkacheva I.V. Classification of Structured Data Representations ПProceedings of the Third International Worbhop on Advances in Databases and Information Systems./ MEPhI Publishing, Vol. 2,1996

26. For73. G. D. Forney. The Viterbi algorithm. //Proceedings of the IEEE 61(3):268-278, March 1973

27. FYBOO. C.O. de Almendra Freitas, A. El Yacoubi, F. Bortolozzi, R. Sabourin. Brazilian

28. Bank Check Handwritten Legal Amount Recognition. HProc. of the XIII Brazilian Symposium on Computer Graphics and Image Processing.

29. GI01. Luis Gravano, Panagiotis G. Ipeirotis and oth. Using q-grams in a {DBMS} for Approximate String Processing //IEEE Data Engineering Bulletin, Vol.24 No.3 pp. 2834, 2001

30. GMW97. Dafydd Gibbon, Roger Moore, Richard Winski. Spoken Language System Assessment (Handbook of Stnadards and Resources for Spoken Language Systems) HMouton de Gruyter, 1997.

31. Har72. Harmon L.D. Automatic recognition of print and script. HProc. IEEE 60, (Oct.), p.p.l165-1176,1972.

32. HHS91. Т. К. Ho and J. J. Hull and S. N. Srihari. Word Recognition with Multi-Level Contextual Knowledge. HProc. of the lstlnt'l Conference on Document Analysis and Recognition, October 1991, pp. 905-915.

33. HPR1. Young-Sook Hwang, Bong-Rae Park, Hae-Chang Rim. A Contextual Postprocessing Model for Korean OCR using Synthesized Statistical Information

34. HS82. Hull J. J., Srihari S. N. Experiments in text recognition with binary n-gram and Viterbi algorithms. //IEEE Trans. Patt. Anal. Machzne Intell. PAMI-4, 5 (Sept.), pp.520-530,1982

35. Hul92. J. Hull, "A Hidden Markov Model for Language Syntax in Text Recognition,"

36. HI 1th IAPR Int 7 Conf. Pattern Recognition, The Hague, The Netherlands, 1992, pp. 124-127.

37. Hul96. Incorporating Language Syntax in Visual Text Recognition with a Statistical Model //IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 18, No. 12, 1996

38. JDM02. Anil K. Jain and Robert P. W. Duin and Jianchang Mao. Statistical Pattern Recognition: A Review. //IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 1, pp. 4-37, 2002.

39. Kem93. Kempe, A. (1993). A stochastic Tagger and an Analysis of Tagging Errors.

40. HInternal paper. Institute for Computational Linguistics, University of Stuttgart.

41. Kim99. Dong Kyue Kim. Efficient Algorithms for Approximate String Matching with Swaps HJ. Complexity Vol.15 pp. 128-147,1999

42. KMC95. Andras Kornai, K.M. Mohiuddin, Scott D. Connell. An HMM-Based Legal Amount Field OCR System for Checks HIEEE International Conference on Systems, Man and Cybernetics, Vancouver ВС, October 1995, 2800-2805,1995

43. KPB87. Kahan, S , Pavlidis, T, Baird. H. S. On the recognition of characters of any font size. //IEEE Trans Patt. Anal. Machine Intell. PAMI-93 9, 274-287,1987

44. Kuk88. Kukich, K. Variations on a back-propagation name recognition net. //In Proceedings of the Advanced Technology Conference, vol 2

45. Kuk92. Kukich K. Techniques for automatically Correcting Words in Text. IIACM computing survey Computational Linguistics, vol. 24, no. 4, pp. 377-439,1992

46. S95. V.V. Lam, L. Javanbakht, and S. X. Srihari, "Anatomy of a form reader," Proc. 2nd Int'l Conf. on Document Analysis and Recognition, pp. 287-292,1995

47. G95. E. Lethelier, M. Leroux, and M. Gilloux, "An Automatic Reading System for

48. Handwritten Numeral Amounts on French Checks," UProc. Third Int 7 Conf. Document Analysis and Recognition, pp. 92-97,1995.

49. Lowrance, R., Wagner, R. 1975. An extension of the strmg-to-strmg correction problem. HJ. ACM22, 2 (Apr.), 177-183.

50. Mai97. Michael H. Mailburg. Comparative Evaluation of Techniques for Word Recognition Improvement by Incorporation of Syntactic Information. H4th International Conference Document Analysis and Recognition (ICDAR '97) August 1997, pp784.

51. Mis99. Misyurev A.V., Hand-Printed Character Recognition by Neural Networks. UProc. of the 5th German-Russian Workshop on Pattern Recognition and Image Understanding (GRWS98), 1999.

52. MM89. E. W. Myers and W. Miller. Approximate matching of regular expressions. HBulletin of Mathematical Biology, pages 7-37,1989.

53. MNROO. Andrew K. McCallum and Kamal Nigam and Jason Rennie and Kristie Seymore Automating the Construction of Internet Portals with Machine Learning HJ. Information Retrieval vol.3 no.2pp. 127-163, 2000

54. МР43. McCulloch, W. S. and Pitts, W. H. A logical calculus of the ideas immanent in nervous activity. //Bulletin of Mathematical Biophysics, 5:115-133,1943.

55. MS99. C. D. Manning, H. Schutze. Foundations of Statistical Natural Language //Processing. MIT Press, 1999

56. Mye95. E. W. Myers. Approximately Matching Context-Free Languages //Proceedings of the 2nd South American Workshop on String Processing pp. 38-52,1995

57. NavOl. Gonzalo Navarro. A Guided Tour to Approximate String Matching. ПАСМ Computing Surveys, Volume 33, Issue 1, Pages: 31-88, 2001

58. Neu75. D. Neuhoff. The viterbi algorithm as an aid in text recognition. I/IEEE Trans. Information Theory, 21:222-226,1975.

59. Nik03. Nikolaev D.P. Segmentation-based binarization method for color document images. //Proceedings of 6th Open Russian-German Workshop on Pattern Recognition and Image Understanding, Novosibirsk 2003, pp. 190-193.

60. NSG96. D. Niyogi, S.N. Srihari, and V. Govindaraju. Analysis of printed forms. HH.Bunke and P.S.P. Wang, editors, Handbook on Optical Character Recognition and Document Image Analysis. World Scientific Publishing Co., Singapore, 1996.

61. Oku76. Okuda, Т., Tanaka, E., Kasai, T. A method of correction of garbled words based on the Levenshtein metric. I/IEEE Trans. Comput., 1976.

62. Pos99. Postnikov V.V., Flexible forms identification. HProc. of the 5th German-Russian Workshop on Pattern Recognition and Image Understanding (GRWS98), 1999.

63. PSM03. Postnikov V.V., Sholomov D.L., Marchenko A.E. FlexiDocs: The Template Driven Document Recognition Technology. //Proceedings of the 6th German-Russian Workshop on Pattern Recognition and Image Understanding (OGRW-6), 2003.

64. PZ83. Pollock J. J., Zamora A. Collection and characterization of spelling errors in scientific and scholarly text. HJ. Amer. Sot. Inf. Sci. 34,1, 51-58,1983

65. Rab89. L. R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. //Proceedings of the IEEE 77(2):257-286, February 1989.

66. RenOl. J. Rennie Improving multi-class text classification with naive bayes. //Master's thesis, Massachusetts Institute of Technology, 2001

67. RH74. E. Riseman and A. Hanson. A contextual postprocessing system for error correction using binary n-grams. I/IEEE Trans. Computer, 23:480-493,1974.

68. RHW86. Rumelhart D. E., Hinton G. E., Williams R. J. Learning representations by back-propagating errors //Nature (London). N323. p. 533-536., 1986

69. RJ86. L. Rabiner and B. Juang. An Introduction to Hidden Markov Models. IIIEEE ASSP Magazine, pages 4-16,1986.

70. Ros58. Rosenblatt, F. The perceptron: A propabilistic model for information storage and organization in the brain. I I Psychological Review 65,1958

71. SA93. Gerard Salton and James Allan. Selective Text Utilization and Text Traversal. //Hypertext'93 Proceedings, November 14-18,1993, Seattle, Washington, USA

72. Sch78. J. Schuermann. A Multifont Word Recognition System for Postal Address Reading. UIEEE Transactions on Computers, C-27, 8, August 1978, 721-732. 9.

73. Sch94. Helmut Schmid. Part-of-speech tagging with neural networks //Proceedings of the 15th conference on Computational linguistics Vol. 1 pp. 172-176,1994

74. Seb99. Fabrizio Sebastiani Machine learning in automated text categorisation: a survey. //Pisa, IT, 1999

75. Seg03. Ilya Segalovich. A fast morphological algorithm with unknown word guessing induced by a dictionary for a web search engine. HMLMTA- 2003. Las Vegas, 2003

76. Sho03a. Sholomov D.L. Syntactical Approach to Post-Processing of Fuzzy recognized Text. UProc. of The International Conference on Machine Learning, Technologies and Applications, CSREA Press, pp. 115-121. June 2003, USA

77. Sho03b. Sholomov D.L., Interpreting the Indistinctly Recognized Textual Constructions. 11 Pattern Recognition and Image Analysis, 2003, vol. 13, no. 2, pp. 353-355.

78. Sit61. Sitar E.J. Machine recognition of cursive script: The use of context for error detection and correction. I'/Bell Labs Tech. Mem, 1961.

79. SK83. Sankoff, D., Kruskal, J. B. Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. HAddison-Wesley, Reading, Mass. 1983.

80. SN98. M. SchuJ31er and H. Niemann. A HMM-based System for Recognition of Handwritten Adress Words. Uln 6th Int. Workshop on Frontiers in Handwriting Recognition (IWFHR), pages 505-514, Taejon, Korea, 1998.

81. SRG04. Speech Recognition Grammar Specification Version 1.0 W3C Recommendation 16 March 2004 http://www.w3.org/rR/2004/REC-speech-grammar-20040316/

82. Sri97. Sargur N. Srihari. Document image understanding. UProc. of1986fall joint computer conference on Fall joint computer conference, November 1997. pp. 87-96

83. SS02. Sari, Т.; Sellami, M. MOrpho-LEXical analysis for correcting OCR-generated Arabic words (MOLEX) //Frontiers in Handwriting Recognition, 2002. Proceedings. Pp. 461-466

84. SSR1. Sargur Srihari and Yong-Chul Shin and Vemulapati Ramanaprasad and Dar-Shyang Lee. A System to Read Names and Addresses on Tax Forms.

85. St90. L. Stringa. "A New Set of Constraint-Free Character Recognition Grammars"

86. EE Transactions on Pattern Analysis and Machine Intelligence. December 1990 (Vol. 12, No. 12)pp.: 1210-1217.

87. TC96. Teahan. W. J. & Cleary, J.G. The entropy of English using PPM based models. UProc. Data Compression Conference. IEEE Society Press, 53- 62,1996.

88. TIC98. Teahan, W.J., Inglis, S., Cleary, J.G. & Holmes, G. Correcting English text using PPM models //In Proceedings DCC'98, edited by Storer, J.A. & Cohn, M., IEEE Computer Society Press, 1998.

89. TJ05. Huihsin Tseng, Daniel Jurafsky, Christopher Manning. Morphological features help POS tagging of unknown words across language varieties. //Fourth SIGHAN Workshop on Chinese Language Processing, 2005.

90. Tou78. Toussaint, G. T. The use of context in pattern recognition I I Pattern Recognition 10, pp. 189-204,1978

91. Tru99. A. Trujillo, Engines: Translation Engines: Techniques for Machine Translation l/Springer-Verlag, London, 1999.

92. Ueb93. Joerg P. Ueberla. The Generalized NPOS Language Model for Speech Recognition, IICMPTTR 93-09,1993.

93. Vit67. Andrew J. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. HIEEE Transactions on Information Theory 13(2):260~ 269, April 1967.

94. Vou03. Atro Voutilainen (2003): "Part-of-speech tagging". Hln: Ruslan Mitkov, editor: "The Oxford Handbook of Computational Linguistics", pp. 219- 232. Oxford University Press.

95. Wag74. Wagner, R. A. Order-n correction for regular languages. I I Community ACM 17, 5 (May), 265-268,1974.

96. WCh76. Wong, С. K. Cnandra, A. K. Bounds for the string editing problem. HJ. ACM23,1 (Nov.), 13-16,1976.

97. Web99. A. Webb, Statistical pattern recognition, HOxford University Press Inc., New York, 1999

98. WF74. Wagner, R. A., Fisher, M.J. The string-to-string correction problem. HJ. ACM21, l(Jan.), 168-178,1974.

99. WHD95. Lars WiedenhGfer Hans-Giinther Hein Andreas Dengel. Post-Processing of OCR Results for Automatic Indexing I/ICDAR Proceedings of the Third International Conference on Document Analysis and Recognition Vol. 2 p. 592,1995

100. WHS92. P. K. Wong and Т. К. Ho and S. N. Srihari. Firm Name Recognition for Automatic Address Interpretation. UProc. of the 5th {USPS} Advanced Technology Conference, November 1992pp. pp. 757-770.

101. XF03. XForms 1.0, W3C Recommendation 14 October 2003. http://www.w3.org/TR/2003/REC-xforms-20031014/

102. АБМ05. Андреев A.M., Березкин Д.В., Морозов B.B., Симаков K.B. Автоматическая классификация текстовых документов с использованием нейросетевых алгоритмов и семантического анализа. НИнтелтек изд-во, 2005.

103. АЕ02. Арлазаров В. Л., Емельянов Н. Е.Системы обработки документов. Основные компоненты. Направление информационными потоками" Сборник трудов Института системного анализа РАН/ М., УРСС. 2002 г.

104. AKC00. Арлазаров В. JL, Куратов П. А., Славин О. А. Распознавание строк печатных текстов. "Методы и средства работы с документами". //Сборник трудов Института системного анализа РАН/М., УРСС. 2000 г.

105. АПШ02. Арлазаров В.В, Постников В.В., Шоломов Д.Л. Cognitive Forms система массового ввода структурированных документов. ИВ сб. «Управление информационными потоками», Москва, Едиториал УРСС, 2002. стр. 35-46

106. Арл02. Арлазаров В. В. Управление информационными потоками в системе автоматического ввода документов. I/"Управление информационными потоками", Сборник трудов Института системного анализа РАН./М., УРСС, 2002 г.

107. АС96. Арлазаров B.JL, Славин О.А. Алгоритмы распознавания и технологии ввода текстов в ЭВМ. IIИнформационные технологии и вычислительные системы 1996, No 1., стр. 48-54.

108. АУ78. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. ИМ.: Мир, 1978

109. БЕОЗ. Богачева А.Е., Емельянов Н.Е. Семантическая Модель документа.

110. ПСистемные исследования. Ежегодник/ М„ УРСС. 2003 г. с.:360-375.

111. БелбО. Беллман Р. Динамическое программирование. ИМ.: Изд-во иностранной литературы, I960.

112. ГМ06. М.В. Губин А.Б. Морозов. Влияние морфологического анализа на качество информационного поиска IIТруды RCDL'2006, Суздаль 2006

113. Еме88. Емельянов Н.Е. Виды представления структурированных данных.

114. Теоретические основы информационной технологии. Сб. тр. Вып. 22. -М.-.ВНИИСИ, 1988

115. Зал80. Зализняк А.А. Грамматический словарь русского языка. ИМосква, Русский язык, 1980

116. Кар02. Ю.Г.Карпов. Методы построения трансляторов. 2002 г

117. ККС02. Кляцкин В. М., Котович Н. В., Славин О. А. Многопроходная схема распознавания документов с обучением. //"Управление информационными потоками" Сборник трудов Института системного анализа РАН М., УРСС. 2002 г.

118. Кну78. Д.Кнут. Искусство программирования для ЭВМ. Том 3. Сортировка и поиск. Перевод с англ. ИМ: Изд. "Мир", 1978.

119. Кул87. Кулагина О.С. Об автоматическом синтаксическом анализе русских текстов. //Препринт ИПМ им. М.В. Келдыша, АН СССР, № 205,1987 г.

120. Лев65а. Левенштейн В.И., Двоичные коды с исправлением выпадений, вставок и замещений символов, //Докл. АН СССР, 163, 4,1965, 845-848.

121. Лев65Ь. В.И.Левенштейн, Двоичные коды с исправлением выпадений и вставок символа \,//Пробл. перед, информ., 1,1,1965,12-25.

122. Мер05. Мерков А.Б. Основные методы, применяемые для распознавания рукописного текста. http://fornit2005 .narod.ru/papers/methods.ps

123. МерОб. Мерков А.Б.О статистическом обучении.http://www.recognition.mccme.ru/pub/RecognitionLab.html/slt.pdf

124. Пен04. Пентус А. Е., Пентус М. Р. Теория формальных языков: Учебное пособие. ИМ.: Изд-во ЦП И при механико-математическом ф-те МГУ, 2004

125. ПМШ04. Постников В.В. Марченко А.Е. Шоломов Д.Л. Разбор структурированного документа в модели с нечеткой логикой ИСб. тр. ИСА РАН "Документооборот. Концепции и инструментарий.", Москва, Едиториал УРСС, 2004, стр. 71-82.

126. Пос01. Постников В.В., Автоматическая идентификация и распознавание структурированных документов ПДисс. На соискание уч. степ. Канд. Технич. наук, Москва, 2001.

127. Пос98. Постников В.В., Разработка методов наложения формы на графическое изображение документа. ИВ сб. «Интеллектуальные технологии ввода и обработки информации», Москва, 1998

128. Пос99а. Постников В.В., Формальный подход к задаче идентификации графическихобразов структурированных документов, ИВ сб. «Развитие безбумажных технологий в организационных системах», Москва, 1999

129. СКБ99. Славин О.А., Корольков Г.В., Болотин П.В. Методы распознавания грубых объектов. И В сб. "Развитие безбумажных технологий в организациях", 1999, с. 290-311

130. Уос92. Ф.Уоссермен, "Нейрокомпьютерная техника.", ИМ.: Мир, 1992

131. ФрОЗ. Дж. Фридл. Регулярные выражения. IIИздательство Питер, 2003 г., 464 стр.

132. Хай05. Хайкин С. Нейронные сети, полный курс, //Изд. "Вильяме, 2005

133. Хол1. А.Б. Холоденко. О построении статистических языковых моделей для систем распознавания русской речи //Журнал Интеллектуальные системы

134. Чер98. Черноусько Ф.Л. Динамическое программирование ИСОЖ, 1998, No 2, с. 139144.

135. Шенбб. Шеннон К. Работы по теории информации. ИМ.: Изд-во иностранной литературы, 1966.

136. Шол02. Шоломов Д.Л. Интерпретация нечетко распознанных текстовых конструкций. И Сборник трудов 6-ой Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии». Великий Новгород, 2002.

137. Шол07а. Шоломов Д.Л. Коррекция распознанного текста с использованием методов классификации. И Сб. трудов ИСА РАН, 2007, Том 17, стр. 352-366

138. Шол07Ь. Шоломов Д.Л. Постников В.В. Никольский Н.Н. Рынок систем обработки деловых документов. Перспективы и направления развития. И Сб. трудов ИСА РАН, 2007, Том 17, стр. 181-191.

139. Шол04. Шоломов Д.Л. Синтаксический подход к пост-обработке нечетко распознанного текста. НСб. трудов ИСА РАН "Документооборот. Концепции и инструментарий. ", Москва, Едиториал УРСС, 2004, стр. 193-207