（计算机应用技术专业论文）数学公式语法关系规则库的设计与应用.pdf

中文摘要 中文摘要 数学公式图像处理是一个具有相当难度的前沿课题，该问题的解决能够为 科研工作和学习提供巨大的便利，具有重要的意义。其中数学公式的分析与理 解是该问题的难点，而建立完整的数学公式语法关系规则辅助公式结构分析， 是该问题的核心。 本文基于对前人研究成果的总结，系统地总结了数学公式的先验知识与语 法规则，对其进行了良好的归类并建立了完整的语法关系规则库，以规范的二 进制文件格式进行存储，设计方便的资源调用接口，为数学公式的分析提供灵 活高效的语法属性查询，完成与版面关系的交互，实现了数学公式结构的准确 分析。 本文在数学公式的语法关系规则的设计上，借鉴了产生式及关系数据库表 示方法的优点，为数学公式的语法结构分析提供强大的支持；并采用了数据驱 动和目标驱动相结合的混合推理控制策略实现公式的分析、理解与检验，保证 系统推理分析的完整和高效。 本文提出的语法关系规则设计方法具有通用性，适用于各种特殊文档的语 法关系规则的设计。 关键字 数学公式图像处理语法结构分析语法关系规则语法关系版面关系知 识表示智能推理 a b s t r a c t a b s t r a c t p r o c e s s i n go fm a t h e m a t i c a le x p r e s s i o n si m a g ei sav e r yd i 币c u l tt a s k ，e s p e c i a l l y a n a l y s i s a i l d u n d e r s t a l l d i n go fm a t h e m a t i c a le x p r e s s i o n s a n db u i l d i n gc o m p i e t e s ”t a c t i cm l e so fm a t h e m a t i c a le x p r e s s i o nf b ri t sa i l a l y s i sa i l du n d e r s t a l l d i n gi sm # m o s ti m p o n a n t i tw o u l do f f e rh u g ec o n v e l l i e n c ef o ro i l rr e s e a r c ha i l ds t u d yi fi t s u c c e s s e s ： t h i sp 印e rs u m m 撕z e sm a 血e m a t i c a lt y p e s e n i n gm l e sa i l ds ”t a c t i cm l e sb a s e d o nk n o w l e d g ea n de x p e e n c e ，b l l i l d su pac o m p l e t ea n da c c u r a t es ”t a c t i cm l eb a s e w h i c hi ss a v e da sn o n n a t i v eb i n a r yf i l e ，d e s i g n se f ! i c c t i v ei n t e r f a c e ，s ot h a ts y s t e mc 耳驻 e a s i l yi m p l e m e n ta 1 1 d a c c e s sm es ”t a c n ca t m b u t ee 伍c i e n t l y ，a i l da j l a l y z e 出e s t r u c t u r eo fm a t h e m a t i c a le x p r e s s i o na c c u r a t e l yv i am ei n t c r a c t i o nw i t hi t s1 a y o u t i n f o m a n o n i nt h ed e s i g no fs ”t a c t i cn l l e so fm a t h e m a t i c a le x p r e s s i o n ，t h i sp a p e rd r a w s 1 e s s o n sf m mt h e k n o w l e d g eo fp r o d u c t i o na n dr e l a t i o nd a t a b a s e t h em l eb a s e s u p p o r t st h es y n t a c t i ca n a l y s i s o fm a t t l e m a t i c a le x p r e s s i o ns n d n g l yt h es y s t e l t 三 a d o p t s1 1 1 i x e dr e a s o n i n gs t i a t e g yo fd a t a 血v e na n dt a r g e t 血v e nf o rt h ea n a l y s i s ： u n d e r s t a l l d i n 昌a n dc h e c l ( i n go ft h ee x p r e s s i o n t h e s eg u a r a n t e ef o rt h ec o m p l e t ea n d e 币c i e n tr e a s o n i n go fm ea r i a l y s i ss y s t e m t h ed e s i g n i n gm e t h o do fs ”t a c t i cm l e si nt h i sp 印e ri so fg o o dg e n e r a l i t y ，a n di t c o u l db eu s e di nm a n yo t h e rs y n t a c t i cr u l e s d e s i g n i n go fv 撕o u sd o c u m e n t sw n h s d e c i a ls t m c t u r e k e y w o r d m a t h e m a t i c a le x p r e s s i o ni m a g ep m c e s s i n g ，m a t h e m a t i c a le x p r e s s i o ns y 矗t a c t j c s t r u c t u r ea n a l y s i s ，s y n t a c t i cr u l e ，s y n t a c t i cr e l a t i o n ，l a y o u tr e l a 石o n ，k n o w l e d g t ， r e p r e s e n t a t i o n ，i n t e l l j g e n tr e a s o n i n g i i 内容目录 图目录 图1 1 计算机模拟人类理解数学公式的过程： 图1 2 公式分析中的知识表示与智能推理3 图1 3 数学公式三个分析层次的关系4 图1 4 数学公式语法关系在语法分析中的作用5 图2 1 字符集分类与子表达式。1 0 图2 2 数学公式语法结构模型四元组之间的关系1 1 图2 3 数学公式示例1 l 图2 4 子表达式层次结构及各层操作符优先级1 2 图2 5 公式版面关系 图2 6 数学公式的子表达式树1 3 图2 7 数学公式语法分析系统的结构1 4 图2 8 数学公式结构分析流程1 5 图2 9 文法示例( 英文语法) 。1 6 图2 1 0 数学公式字符集1 8 图2 n 操作符所属最小范围子表达式2 4 v i 内容目录 图2 1 2 专家系统架构图2 5 图2 1 3 数学公式语法结构分析系统架构图2 5 图3 1 语法关系与版面关系在公式结构分析中的交互。2 9 图3 2 数学符号的l i n i b o u n d 3 0 图3 3 数学符号骨干线抽取3 l 图3 一操作符优先级层次3 1 图3 5 子表达式拆解3 2 图3 6 操作符子表达式范围限定3 2 图3 7 符号二义性判断3 3 图3 8 语法关系对字符识别的辅助作用3 4 图5 1 语法关系规则设计流程4 3 v i i 菌蠹自曝o 。 表目录 。 矗。矗。 t 一。茹，篡鬣。乏”量二釜毒。：一ui 一* 峨砖a “，“。， 表2 1 数学公式语法结构模型四元组。j 9 表2 2 数学公式语法关系期则的组成 1 7 表2 - 3 数学公式操作符优先级规则表一2 3 。 t 表3 1 数学公式语法关系规则的组成。- 2 8 v i i i 第一章前言 第一章前言 第一节数学公式图像处理概述 数学，是地球上最古老的科学之一，它博大精深，渗透于我们生活的各个 领域。数学语言是“唯一的国际科学语言”，准确、严密而且简明，是表达科学 思想的通用语言和数学思维的最佳载体。数学公式是数学语言的主要表现形式， 大量包含于各类科技文献中，通常经扫描后以图像的形式存入计算机。随着网 络技术的迅猛发展，信息资源的电子化成为至关重要的问题。数学公式是许多 科技文献的核心，但它的图片存在形式对于数学公式的重用、编辑、查找以及 网络传输都带来极大的不便。因此，识别文献中的数学公式图像，理解它的结 构含义，获取公式中包含的信息，能够使信息的储存和使用变得更加容易，更 好地实现信息的交流和共享，具有非常重要的现实意义。 数学公式由于具有庞大的符号集，使用繁多的特殊符号；具有复杂的二维 嵌套结构，排版格式复杂多变：并且公式的符号含义具有多样性，这使得现有 成熟的文档图像处理( d 口：d o c u m 即ti m a g ep r o c e s s ) 【1 3 】技术无法适用于数学公 式的处理。因此，数学公式图像处理已经成为d 领域的个研究热点。印刷 体数学公式识别系统主要包括三个组成部分：公式图像的提取、识别、分析和 公式重构。其中，公式的提取已有比较成熟的技术可以采用，公式的识别也有 大量前人的研究基础做借鉴，而公式的分析与理解由于其复杂性和创新性，成 为这一领域的一个研究难点。 科技文献中的数学公式，如果我们能够对它们进行搜索、编辑、重用，这 对于研究人员来说具有很大的意义，这将节省大量的时间，免去许多重复操作， 大大提高研究人员有效工作的比重。要达到这些目标，就必须做到数学公式图 像的信息化、电子化，就必须对数学公式进行结构分析与理解，使计算机能够 像人一样真正认识数学公式，理解它的结构、含义，达到真正的可编辑、可检 索、可重用、易存储、易传输。在数学公式的结构分析方面，以往的研究人员 做了大量的工作，并且在近年，前人创造性地提出了语法结构分析的概念【2 ”， 开创了数学公式分析的新的局面。本文正是在前人研究的基础上，结合大量的 事实观察，对数学公式语法结构分析方法进行深入研究。 第l 页 第一章。前言 第二节数学公式结构分析与理解 “数学公式就是由数字、代数符号、运算符号等符号构成，表示数量、变 量、运算、数学规律的一个或一组符号。”【捌这个定义突出了数学公式的语法结 构描述，将其拆解，我们就得到数学公式的组成结构：符号集数字、代数 符号、运算符号等，语法规则表示数量、变量、运算、数学规律的符号及 符号的组合。识别出公式中的符号，理解其语法关系和运算含义，这就达到了 数学公式分析的目的。人类阅读数学公式正是这样的一个过程：首先通过视觉 形成公式图像，而后基于人理解数学公式的先验规则及数学公式的组成规则， 经过大脑思维的分析与理解最终获得公式所表达和计算的含义，即经过一个从 版式结构到语法结构再到语义含义的过程。本文的研究重点，正是计算机如何 模拟人类已有的数学公式语法规则及先验知识，并利用这些规则模拟人类理解 数学公式的过程。 圆 影乡 霪 。 图1 1 计算机模拟人类理解数学公式的过程 图1 1 显示了人在获得数学公式的图像信息后，基于人理解数学公式的先验 规则及数学公式的组成规则，经过大脑思维的分析与理解最终获得公式的具体 内容和意义。作为计算机，则是获取公式图像经识别后的信息，包括公式类型、 公式的组成符号、符号的大小及相互位置关系等，然后通过读取数学公式语法 规则库及先验规则库，再经过复杂的处理流程和算法模拟人脑的分析过程，最 终获得公式的语法结构信息。这些信息包括操作符、操作数及相互间操作关系、 表达式结构等。 将数学公式先验规则及语法规则的知识表示出来，使计算机利用这些规贝| j 第2 页 第一章前言 进行智能推理，分析出数学公式的语法结构，同时对版式结构的识别结构进行 验证和纠错，这个分析过程类似于专家系统的推理过程，而知识表示和推理方 法正是专家系统中至关重要的两个方面，二者密切相关，相辅相成。知识表示 的形式要有利于推理方法的顺利进行，推理方法的采用必须以知识表示为基础， 二者相互配合，以达到准确高效的处理目裂矧，如图1 2 所示。 图1 2 公式分析中的知识表示与智能推理 数学经过几千年的沉淀与发展，形成了一套非常严谨而稳定的规则体系。 它使用最精确最简洁的形式，却表达着最丰富的数学含义。要准确理解这丰富 的数学含义，就必须充分掌握这套规则体系。人类通过知识的传承来掌握这些 知识，而对于计算机，就必须以计算机可理解的方式来表示知识使之理解，这 就需要用到知识表示技术。所谓知识表示技术【2 3 1 ，就是研究在计算机中如何使 用最合适的形式对系统中所需要的各种知识进行组织，目标是最适合于该问题 的推理与计算，它与问题的性质和推理控制策略有着密切的联系。通过对这些 知识规则的学习，使计算机对数学公式进行分析，并得出结果，这就是推理。 推理是指依据一定的原则从已有的事实推出结论的过程，该原则是推理的核心。 数学公式分析系统的推理是知识推理，是在计算机或智能机器中，在知识表示 的基础上，进行机器思维，求解问题，实现知识推理的智能操作过程。知识推 理的实现有赖于分析系统各个模块的协调与实现。 传统的知识表示及推理大多只能表示确定的、精确的知识，且在此基础上 进行正向的、精确的推理。推理是人类的思维过程，它是从已知事实出发，通 过运用相关的知识逐步推出某个结论的过程。数学公式是数学理论精简准确的 表达方式，它的版式结构变化多样，其语义在不同情况下含义也不相同，表现 形式非常灵活，造成公式信息的不精确性。并且，由公式图像出发分析公式结 构是一个逆向的推理过程，逆向过程必然造成不确定推理。所谓不确定性推理 第3 页 第一章前言 就是从不确定性初始证据出发，通过运用不确定性的知识，最终推出具有一定 程度的不确定性但却是合理或者近乎合理的结论的思维过程。因此，我们需要 寻求一种新的表示机制和方法，以实现人类阅读并理解公式这一过程的模拟。 本文中，我们借鉴了产生式及关系数据库表示方法的优点，设计和实现了数学 公式的语法知识规则，采用语法关系与版面关系相结合的处理方式，数据驱动 和目标驱动相结合的混合推理控制策略实现公式的分析、理解与检验。 第三节数学公式语法结构分析 1 3 1 数学公式语法结构分析的作用和意义 数学公式的分析根据其处理目标和处理层次的不同，可分为版式结构分析、 语法结构分析与语义结构分析三类。图1 3 描述了在数学公式分析中，三个分析 层次之间的关系。通过对数学公式图像中各符号空问位置关系的识别，可以得 出公式的版式结构，它包括组成数学公式的各个符号的内容，以及每个符号各 自的空间位置信息。通过版式结构提供的这些信息，借助于相应数学语法规则， 就可以得到公式的语法结构；反过来，又可以利用数学公式的语法限定规则来 检验公式的版式结构。在获取了公式的语法结构之后，依据操作符的运算规则， 可以得到公式的语义含义；操作符的计算含义又反过来约束公式的语法结构。 通过这样的层层推进与反馈，最终能够实现语法结构与语义含义对数学公式不 同层次的重现。重现后的数学公式包含了丰富的语法或语义信息，已经不等同 于最初简单的公式图像，此时，我们可以方便地对公式进行编辑、存储、检索 以及传输等等，达到我们数学公式图像处理的实际目的。 空间位置 一 计算含义、 运算烈则 尽蠛绩鹈一 落滋拍譬 图1 3 数学公式三个分析层次的关系 什么是数学公式的语法结构? “符号语言的语法就是指这个标记系统的组 第4 页 黪匿缎褥虿熟激 第一章前言 织方法。”数学是一种符号语言，数学公式的语法结构就是指，在数学的符号 系统中，各种数学符号构成合法数学公式的组织方式。数学公式由各种数学符 号组成，这些符号各自具有某种特性，在组织构成数学公式时扮演着不同的角 色。它们都有哪些特性，在组织方式上又有什么联系和约束，这些都是数学公 式语法结构必须涉及的问题。 在这里，我们使用“语法关系”的概念，它囊括数学公式系统中所有与之 相关的规律和法则，包括数学符号的分类、特性，以及符号间的排列组合规律 等等。语法关系作为一个抽象的概念，是这些规律与法则的统称，而我们在分 析过程中使用的一条一条的语法规则则是数学语法关系的表现形式，它在公式 语法结构分析的过程中从头至尾都起着非常关键的作用。如图1 4 所示，数学公 式要利用数学规则自项向下地进行子表达式分解，同时又以自底向上的方式， 利用数学规则进行公式的合法性检验，数学规则在分析中的作用是显而易见的。 图1 4 数学公式语法关系在语法分析中的作用 自 底 l 叫 卜 以往的研究证明，单纯针对数学公式版式结构的处理，由于基于非常有限 的版面信息，无法对公式的完整性、合法性及二义性进行判断和处理；而单纯 针对数学公式深层语义的分析，通常使用文法分析的方法，相对数学公式千变 万化的形式，以及大量具有二义性的数学符号，可分析的公式类型极其有限， 而且会造成公式处理的复杂化，难以进行系统实现。数学公式语法结构通过数 学语法规则的辅助作用，很好地承接了版式结构分析与语义结构分析这两个层 第5 页 利数学规则进行合法性检验 自刚蛳1引别篓捌叫粥到纠蛳划种 第一章前言 次，通过语法规则约束数学公式的版式结构，对其合法性及完整性进行检验；。 对符号二义性进行判断，进一步获取公式的语义信息，通过公式的计算含义约 束其语法结构。解决了单纯依靠个方面带来的分析不准确或者分析范围狭窄 的状况，以及两个分析层次差距太大造成的无法衔接的矛盾，是数学公式结构 分析中非常重要的一个环节。 1 3 2 数学公式语法结构分析中的重点与难点 由于数学公式结构复杂多样，语义上具有二义性，使得它的语法结构分析 存在一定的难度，主要有以下几个方面： 夺数学公式符号种类繁多j 格式变化多样，给统计与分类工作都带来不便。 数学公式集合了数字、英文字母、希腊字母等多种类型符号，使得符号集 非常庞大，并且具有多种字体，风格不一，使得符号的统计与分类工作量巨 大，导致符号的识别困难，直接影响后期的结构分析。 夺数学公式组合关系复杂多样，含义多变，给公式的识别造成困难。 公式组合关系形成了一系列的组合规则，复杂的组合关系不仅使得公式的 版面结构变得多样，对公式的识别造成困难，同时公式的语法结构也复杂得 难以被计算机所理解。 夺数学公式结构复杂，难以描述和表示，给公式语法结构的自动分析造成困难。 数学公式形式简单，却蕴含着很大的信息量，原因是其语法结构复杂而叉 灵活，在计算机上不易表示，让计算机理解就更加困难。 而克服这些困难的根本就是建立完整准确的数学公式语法关系规则体系， 使得数学符号的分类清晰，其组合关系与结构描述都有据可依。在数学公式的 结构分析过程中，依靠版面位置信息，根据语法规则对公式进行拆解，同时由 语法规则限定公式的版面结构，语法规则起着必要的指导作用。公式的语法结 构分析过程，其实就是数学公式的版面关系与语法关系交互作用的过程。如何 利用公式的版面关系与语法关系交互作用进行公式的结构分析与拆解，这正是 数学公式语法结构分析中的重点。 数学语法关系规则是否准确、完整，对于公式结构分析是否能够进行，结 构是否准确都有着直接的关系。因此，如何从大量的数学公式中抽取语法规则， 建立完整、准确的语法关系规则体系，并以适当的形式存储和展现，成为数学 第6 页 第一章前言 公式语法结构分析问题的难点，同时也是本文研究的重点。后面的章节，我们 将主要围绕这两点进行分析和论述，并提出本文的方法和观点。 第四节本文主要内容及结构 本文在前人对数学公式图像处理的研究基础上，通过对大量数学公式的观 察，对数学领域公式组织和书写的经验规则进行总结和统计，与智能推理相结 合，实现数学公式的语法结构分析。本文借鉴了产生式及关系数据库表示方法 的优点，设计和实现了数学公式的语法知识规则，为数学公式的语法结构分析 提供强大的支持；并采用了数据驱动和目标驱动相结合的混合推理控制策略实 现公式的分析、理解与检验，推动数学公式的图像处理问题向前发展。 本文的内容与结构分布如下： 第一章简单介绍了数学公式图像处理的现状，当前数学公式图像处理中的 热点以及难点，引出本文研究的重点数学公式语法关系规则，提出以知识 推理的思想进行公式分析。 第二章阐述了数学公式语法关系描述模型的定义和作用，以产生式的形式 对公式语法关系规则进行了详细的分类和描述，详细分析了如何利用语法关系 规则进行数学公式语法结构的分析。 第三章重点讲述了数学公式语法关系规则的设计、实现与存储，详细分析 了语法关系与版面关系如何交互作用实现公式结构的分析，并对公式结构分析 中的几个关键方法进行了分析和说明。 第四章研究了数学公式语法关系规则的性能评价。提出了语法关系规则的 完整性、适用性及鲁棒性三个性能评价标准，并通过定性分析的方法，给出了 本文中数学公式语法关系规则基于这三方面的评价结果。 第五章对数学公式语法关系规则的设计方法，以及公式结构分析方法的设 计进行了总结，并对未来的研究工作提出建议和展望。 7 第7 页 第二章数学公式语法关系描述和分析 第二章数学公式语法关系描述和分析 第一节数学公式语法结构描述 本文关于数学公式分析问题的知识表示及推理方法是在前人提出的数学公 式语法结构描述模型基础上进行的，因此有必要先了解该结构模型，后面才能 更好地理解基于语法知识的推理。我们将在本小节解释数学公式语法结构模型， 并简要介绍基于语法关系的数学公式结构分析方法。 2 1 1 数学公式语法结构描述模型 我们的数学公式语法结构描述模型为一个四元组： 数学公式语法结构= ( 字符集，子表达式树，语法关系，版面关系) ；【2 2 1 我们通过表格的形式来展现这个四元组，表2 1 清晰地描述了数学公式语法 结构模型四元组的定义、作用、以及所包含的信息。 表2 1 数学公式语法结构模型四元组 名称定义作用包含信息 j 组成一个数学公式的所是构成数学公式的基 字符集分为操作符和操作数 有符号 本单元 数学公式在子表达式拆反映了数学公式及其表达式之间的从属关 子表达式树 解过程中形成的由子表子表达式之间组合与系及各个子表达式的 达式组成的树状结构 被组合的关系具体信息 数学公式必须遵循的数限定数学公式的版面 包括符号间的组合关 语法关系学领域所规定的一系列结构，为结构分析提供 系、操作符之间的优先 级限定、各种子表达式 规则依据和指导 的阅读顺序等 包括构成公式的所有 组成一个数学公式的各为公式的语法结构分 符号的内容、字体、字 版面关系 个字符的版式信息 析提供输入信息号，以及符号之间的空 间位置关系 第9 页 第二章数学公式语法关系描述和分析 其中，字符集和语法关系是数学公式的基本组成结构。字符集包括操作符和 操作数。操作符是指运算符、函数名及某些特殊符号，表示对一个或多个操作 数的某种操作关系，或某种特殊数学规律。操作数是指由数字、英文字母、希 腊字母等代数符号构成的，表示数量、变量等含义的数学符号，如图2 1 a 中所 示。子表达式树由子表达式构成，每个子表达式在构成某个子表达式的一部分 的同时，又可能同时由多个子表达式构成，如图2 1 b 所示。子表达式树反映了 数学公式及其子表达式之间组合与被组合的关系，子表达式的拆解过程其实就 是数学公式语法结构的分析过程。 二= 囡e 园团圆+ 口一撵依敏。一操作待 ( a ) 固予岌达式 ( b ) 图2 1 字符集分类与子表达式 对于数学公式的语法结构来说，这个四元组中的每一个成员都是必不可少 的，它们之间有着密不可分的关系，并且在公式语法分析的不同阶段起着不同 的重要作用。图2 2 描述了数学公式语法结构模型中四元组之间的关系：罕符集 对应于数学公式图像经识别后的字符流，包括操作符和操作数；版面关系则包 含了符号所能获得的全部版面信息，包括符号的字体、大小及空间位置关系。 二者一起作为语法结构分析系统的原始输入数据，利用数学公式语法关系，经 过系统的分析决策，对表达式进行层层拆解，最终得到公式的子表达式树，完 成公式的语法结构分析。 第1 0 页 第二章数学公式语法关系描述和分析 图2 2 数学公式语法结构模型四元组之间的关系 下面我们通过一个例子来展示数学公式语法结构模型，以使我们对这个模型 有更为直观和清晰的认识。 d zz p z 一1 c o s p 丌 图2 3 数学公式示例 根据我们的语法结构描述模型，可以得到如下各项信息 字符集： 夺操作符：、一( 分数线) 、一( 减号) 、d 、= 、c o s 夺操作数：x 、l 、p 、兀 语法关系： 冷操作符属性：目数、子表达式方位、操作符类型等 夺操作数属性：操作数类型、是否拥有角标等 第1 1 页 一 一、一第三章数势公式语法慕暴瞄述和分杯 夺操作符层次及优先级： 子表达式层次结构 各层次操作符优先级比较 版面关系： 图2 4 子表达式层次结构及各层操作符优先级 图2 5 公式版面关系 子表达式树： 在获取该公式的字符集后，依据语法关系规则提取当前层次优先级最高的 操作符，并以它为基点，再依据其语法属性及公式版面关系进行子表达式的拆 第1 2 页 一 、 、 婚 第二章数学公式语法关系描述和分析 解；再对拆解后得到的子表达式进行同样的分析过程，层层迭代，最终形成图 2 6 显示的树状结构，即生成子表达式树。这是前面三部分综合作用产生的结果。 上一层表达式的子表达式 o 上一层表达式的核心操作符 图2 6 数学公式的子表达式树 子表达式的拆解是一个单调有穷的过程，由上面的分析可以看出，在这种 描述机制下，公式的分析是可以在有限的操作步骤中完成的，并且因为语法关 系因素的加入，使得这种描述结构能够满足可编辑、可检索的要求。在版式结 构信息的指导下，我们可以进行一些数学公式的结构分析与判断，若止于此， 则由于各种原因造成的文档识别错误将无法被纠正，而依靠语法分析我们就能 够检查并纠正大量识别错误，提高数学公式的识别率，因此，这种描述结构是 具有可判别性的。这种描述方法结构简单，具有一定的容错性和扩展性，便于 处理系统的实现、维护与升级，具备相当的鲁棒性和简洁性，能够满足处理大 量普通文档中数学公式的应用需求。 第1 3 页 第二章数学公式语法关系描述和分析 2 1 2 数学公式语法结构分析流程 数学公式语法结构模型描述的并不仅仅是几个静态的信息集合，它同时反映 了一种动态的处理过程。它定义了分析系统的输入信息公式字符集和版面 信息；系统的处理目标完成子表达式拆解，生成子表达式树；系统的数据 依赖语法关系规则。于是，根据上一小节的语法结构模型，我们很容易得 到系统的大致结构如图2 7 所示。 图2 7 数学公式语法分析系统的结构 由系统结构图2 7 我们可以看出，公式的分析系统可分为五个模块。其中， 预处理模块对系统的输入信息进行一些必要的操作，即针对识别结果进行函数 名合并，定界符配对，去除帽子符号生成语法单元等操作。后处理模块主要负 责结构分析之后的一些后续工作，包括帽子符号的添加，差错校验及分析结果 的输出等工作。中间的语法分析模块是分析系统的主体和核心，它通过与语法 规则库模块和版面信息处理模块进行交互实现数学公式结构的分析，并将结果 输出给后处理模块，得出最终所需的结果。 数学公式的结构分析流程如图2 8 所示，其语法结构分析是一个循环迭代的 过程。用虚线框圈起的几个部分，它们在操作的时候都使用了数学公式的语法 关系规则，包括查询符号的操作属性、比较操作符优先级、查询操作符的语法 属性及相关子表达式属性等等。包括在预处理与后处理阶段，帽子符号以及定 界符的处理也需要进行一些符号属性的查询操作。可以说，数学公式语法关系 规则贯穿着语法结构分析过程的始终，它串起了语法结构分析系统的整个流程。 第1 4 页 第二章数学公式语法关系描述和分析 广识目石；藉集台 l 一一 j 1 分析预处雕( 函最名台井、定l ，进行操作符骨干线抽取，得到 l ：界符配对、皓除幅子符号替) i卑谢层姿的撩作椅列毒 | | 通历市询母节符号的操作j e | l j比较操作符倥先强得到最高 i 。性生成撵作梅与操作数链袭： ，+ 1 优先缱姆作张、+ il i i 商t 嘴殊操作蒋，i 赧掘女版币l 蠢柳吾法规则库簸取该操作符 l ，1 i 静征捌分 i 獭自i 二- 的柏关语法届性；尊、 “、 # t + 生成谈操作符予裘选式树结构 一 ， 。螺蹶藩南， l t 驾黪! 藕群? 剽 巳受目巳苎鲺 图2 8 数学公式结构分析流程 2 1 3 数学公式语法关系规则 我们前面提到，数学公式语法分析过程构成一个典型的专家系统。专家系 统主要由知识库和智能推理两部分组成。知识按其含义，大体上可分为事实和 规则。事实是指人类对客观事物的属性的值的描述，是确定的，无二义性的； 规则指可以分解为前提和结论两部分的那种能够表达因果关系的知识，是有条 件的2 2 1 。根据这两类知识的划分，知识库可相应地分为信息库和规则库。 数学公式语法关系是一个抽象的概念，指数学公式遵循的一些规律和法则， 其具体表现形式为我们在分析过程中使用的一条一条的数学语法规则。这些语 法规则的集合构成了我们这个系统的规则库。它们在公式语法结构分析的整个 流程中，从头至尾都起着非常重要的作用。那么，如何从无穷无尽地数学公式 第1 5 页 第二章数学公式语法关系描述和分析 中提炼出这些规则，如何把它们表现出来，它们应以何种方式存储在计算机里， 公式在结构分析过程中又如何使用它们? 这些问题显然成为我们必须面对和解 决的问题。 就如同学者们研究语言语法，通过大量的生活体验，对语言的反复观察和 分析才归纳总结出来的，对于数学语法也是一样。无论是人类交往使用的自然 语言，还是计算机使用的程序语言，它们都只使用有限多个基本符号，然而由 这些基本符号却能够组成成千上万各式各样的语句，表达着丰富多彩的含义。 对于数学语言也是一样，并且，数学语言因其准确精炼的特点，成为表达科学 思想的“唯一的国际科学语言”，成为世界上最伟大的科学。不过，这些语言的 符号组合并不是任意的，对于一个有意义的句子或是一个合法的程序，符号的 组织是必须遵循一定的规则的。数学公式，作为数学语言的表现形式，正是 些数学符号遵循相应的数学语法规则组合而成的。这些语法规则伴随着数学这 门古老学科的诞生与发展，经过于年的沉淀，我们则通过对大量数学公式的观 察与分析，进而将它归纳总结出来。 数学语言之所以具有准确、严密且简明的特点，也正是得益于其语法规则 的稳定性与严谨性。这种规则就是文法( 也即语法) 。瞳1 在文法理论中，文法有 很多种类型，其限定范围与适用范围均有所不同。图2 6 是一种比较简单的形式 文法，它描述了英文的语法规则构成，定义了英文语句。 一 d e r e 锄i n e r ) t h e ia a p p l e i c a l i m a n i v e r b e a t s id r ；n k i 兀i n s 图2 9 文法示例( 英文语法) 我们将借用类似图2 6 中文法的形式对数学公式语法规则进行表示，为它的 实现提供理论指导( 深入的文法知识请参见 2 7 】) 。同时，由于有些数学公式具 有特殊的二维结构，因此，必要时，我们将设计一种二维的形式文法来定义相 应类型的公式结构。 第1 6 页 第二章数学公式语法关系描述和分析 第二节数学公式语法关系规则的组成 通过对大量数学公式的观察与分析，我们根据在数学公式结构分析过程中 语法规则所起的不同作用，将其分为四个大类：数学符号的属性规则、数学符 号及表达式相对位置规则、数学符号及表达式的语法约束规则和公式分析过程 中操作符的优先级规则。它们的定义、在公式结构分析中的作用、及其知识库 分类如下表所示。 表2 2 数学公式语法关系规则的组成 类型定义作用知识库分类 组成数学公式的符号的自身 获取符号属性之后，才能 符号属性规则属性，包括其内码、图像、类信息库 够进行公式结构分析 别等 子表达式在版面结构上应遵 用于查找子表达式，同时 公式排版规则检验公式的版面结构是规则库 循的排列格式 否合法 子表达式在类型等语法方面用于分析表达式类型，同 语法约束规则的条件约束，以及一些具二义时检验表达式的语法结规则库 性的操作符的条件约束等构是否合法 在结构分析过程中，对数学符 决定语法结构分析中每 优先级规则一次子表达式分解的关信息库 号进行分析的先后顺序 键符号 下面我们使用独立的小节，具体介绍每一类数学语法规则的原理和文法定 义，以及它们在数学公式结构分桁中的应用。 2 2 1 符号属性规则 我们在进行数学公式语法结构分析时，是假定已经得到公式的初步识别结 果，即公式的版式结构，包括组成公式的所有符号的列表，以及各个符号的空 间位置信息。分析的第一步，我们需要了解各个符号的语法属性，以便找出公 式分析的关键符号。因此，我们需要对数学符号进行分类，依照上文，我们将 之分为操作数与操作符两个大的类别。于是，我们这样定义数学符号： 第1 7 页 第二章数学公式语法关系描述和分析 一 ( s ：s y m b o l ；s c ：s y m b o lc o n t e n t ；s i ：s y m b o l t y p e ) ， i ( o p ：o p e r a t o r ；o d ：o p e r a n d ) 这两条文法表示：一个数学符号( s ) 由它的符号类型( s t ) 与它的具体内 容( s c ) 所构成，而数学符号的类型又分为操作符( o p ) 和操作数( 0 d ) 。奠 仅依靠这样的粗分类来进行公式结构分析，是远远不够的。数学符号的分类标 准有很多，为了结构分析的方便，我们还需要对它们进行细分类。图2 7 是前人 总结的数学公式中可能出现的字符的集合，在本文中，我们暂不考虑那些生僻 少见的数学符号，只研究其中在数学公式中大量出现的那些符号。 a bc de f g h i jk l m n o p qrs tuv 霄x yz abcdef g h ij k l m n o p q r s t u v w x yz 46c dc ，口 t j 七f mno 尹qrj q zf ： a8c d ef ch fjkl mno p q r s t u v 、x yz 0 12 3 4 5 b 78 口 ，：；! ? ”榉s 西+ 一，= ( ) 】 ) i8 【j 1 ( ) 口口1 6c fc 叶口毋 卢p f f 口，p 口cr v 毋妒x 母埘r e a 三r r e t 4 雪n 士寻x t n u 出n u v o 0 0 v 日 l o e o o o l 士竺c ) x 垒v 暑 譬j 饯w j 卜卜s 匕 j i 辞 r tj p 琥9 ，口vv ，口t 上v 3 - 4 # 0 9 ，n u n u u v 0 0 0 日 一一 = = i 一= ：= - 一t e j 一一一_ 1n l4 i8 图2 1 0 数学公式字符集 我们从属性比较简单的操作数开始。由于语法结构分析与符号的字体等无 关，因此我们在这里不区分符号正体与斜体。由此，我们对操作数进行如下劳 类定义： 一 i ( n i ( i ( l ：l e t t e i j n ：n u m b e r ；i ：i n f i n i t y ) 一 i ( u l ：u p p e r c a s el e t t e r ；l l ：l o w e r c a s el e t t e r ) + 1 ( u c l ：u p p e r c a s ec o m m o nl e t t er u g l ：u p p e r c a s e g r e e k1 e t t e n 第1 8 页 第二章数学公式语法关系描述和分析 l 1 ( l l = a ，b ，c ，z ) l 2 m 2 = ( r 1 ， ，q ) di 一 id 向l 皿c l ：l o w e r c a s ec o m m o n1 e t t e r ；u g l 1 0 w e r c a s e g r e e kl e t t e n l 3 ( l 3 = a ，b ，c ，z ) 一 i d i + 科勾：n o n - z e md i 百t ；d ： d i 百t ；+ 表示无限循环) n 1 ( n 1 = l ，2 ，3 ，9 ) 一o o 一 操作符作为我们分析数学公式的关键因素，它拥有非常复杂的语法规则， 我们按照由易至难由面到点的方式分析它的属性，尽可能做到全面和完整。根 据操作符不同方面的性质，可以对它进行不同的分类： 夺按版面特征可分为帽子符号、定界符、大操作符、箭头、关系操作符、二目 运算符、普通操作符、特殊操作符以及功能函数( 由于其具有操作符的某些 性质，因此将其作为整体当作操作符处理) ： ( l o a o 娘o 娟o d o ( c o ： a c c e n to p e r a t o r ；d o ：d e l i i l l i t c ro p e r a t o r ；l o ：l a r g eo p e m t o r ；a 0 ：a r r o wo p e r a t o r ； r o ：r e l a t i o no p e r a t o r ；b 0 ：b i n a r yo p e r a t o r ；m 0 ：c o m m o no p e r a t o r ；s 0 ：s p e c i a l o p e r a t o r ；n j n c ：f u n c t i o n ) 夺按照符号的语法特性却只需分为帽子符号、定界符、大操作符、关系操作符、 运算操作符、功能函数、其它特殊符号七类： - ( c o ：a c c e n to p e m t o r d o ：d e l i i i l i t e ro p e r a t o r ；l o ：l a 唱eo p e r a t o r ；r 0 ：r e l a t i o no p e r a t o r ；u o ：s u m o p e m t o r ；f u n c ：f u n c t i o n ；s o ：s p e c i a lo p e r a t o r ) 夺对于功能函数可根据其上，下限的是否必需进行分类： 删c 一心1 ) l 妤n i l 栅l 叮。：f u n c t i o n w i t h1 i m i t ；f n l ：f u n c t i o n w i t hn ol i r l l i t ；f e l ：f u n c t i o nw i t he i t h e rl i m i t0 rn o t ) 夺按目类型可分为单目、双目及多目操作符： 一 lo y a o i 心压u l o ( m o n o ：m o n a d i c 叩e r a t o r ； 第1 9 页 1 第二章数学公式语法关系描述和分析 d y a o ：d y a m co p e r a t o r ；m u i d ：m u m 础m e n s l o no p e r a t o r ) 夺按符号所属知识类别可分为代数类、几何类、集合类、逻辑类操作符： 一 i l id d g o ( a l g ：a l g e b mo p e m t o r ； g e 0 ：g e o m e 仃yo p e m t o r ；s e r ：s e to p e m t o cl o g ：l o 百co p e r a t o r ) 操作符的特性有很多，所以它的分类标准也多种多样，每一种分类方式并 不一定能够覆盖到所有的数学符号，但每一个符号却能够同时拥有许多种类别 属性，分的种类越多越细，对于我们的结构分析就能够提供越多的信息。在此， 各种分类就不一一列举。 2 2 2 公式排版规则 前面提到，版面信息除了提供符号内容信息外，还提供了符号的空间位置 信息。然而目前的识别系统都不能够达到百分之百的正确率，因此，如果符号 出现识别错误的话，仅仅依靠版面信息无法进行校验，这时就需要相对位置规 则。相对位置包括符号之间、子表达式之间、以及符号与子表达式之间的相对 位置。其具体内容包含符号或子表达式的外接矩形的大