Применение регулярных выражений в распознавании математических текстов

 pdf (189K)

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

Ключевые слова: регулярные множества, регулярные выражения, регулярные операции.
Цитата: Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2012, вып. 2, с. 63-73
DOI: 10.20537/vm120206

Regular expressions in the mathematical text recognition problem

The work is devoted to use of regular expressions at recognition of hand-written mathematic texts. The main problem in handwritten mathematical formula recognition is that these texts mainly consist of a large number of small fragments, arranged in accordance with some strict rules. Despite the fact that formal definition of syntax of mathematic texts can involve context-free grammars and even more complicated constructions, it frequently suffices definition of mathematical language on the base of regular expressions for successful recognition. Since some constructions can occur in mathematic texts frequently than other, we introduce the concept of the weighed regular expression. The weights determine preference of some constructions before other ones. In the work, mathematical tools for use of such expressions at recognition is introduced. Theorems about intersection of weighed sets defined by such regular expressions are proved. Some estimations are given to complexity of algorithms work using such regular expressions for recognition.

Keywords: regular sets, regular expressions, regular operations.
Citation in English: Bulletin of Udmurt University. Mathematics, Mechanics, Computer Science, 2012, issue 2, pp. 63-73

Журнал индексируется в Web of Science (Emerging Sources Citation Index)

Журнал индексируется в Scopus

Журнал входит в базы данных zbMATH, MathSciNet

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Журнал включен в перечень ВАК.

Электронная версия журнала на Общероссийском математическом портале Math-Net.Ru.

Журнал включен в Crossref