数学公式检索与匹配技术研究

郝保水

（北京信息科技大学计算机学院，北京 100101）

数学公式检索与匹配技术研究

郝保水

（北京信息科技大学计算机学院，北京 100101）

数学公式是科技文档不可或缺的重要组成部分，具有复杂的二维结构和嵌套结构。数学文档有多种格式，包括Word、PDF、MathML、TexLaTex等，如何对文档中的公式进行检索，如何判定两个公式匹配则成为一个难题。公式匹配包括精确匹配、语义匹配和结构匹配等，如果简单地使用字符串匹配技术，则无法实现公式的匹配，因此必须针对数学公式特点，研究出相应公式匹配方法。首先对文档进行归一化，然后对公式进行匹配。如果有多个文档或网络检索的话，则为了加快速度，需要构建索引等结构。

数学公式；公式匹配；公式检索

（一）引言

科学离不开数学，数学是科学的工具，而数学是借助数学公式来进行描述和表现的。在各种科技文档中，包含着大量的数学公式。如何对这些公式进行检索，则日益成为一个重要的问题。

在将各种文档电子化之前，只能使用人工对数学公式进行检索，考校的主要是记忆力和理解力，存在速度慢、范围窄、有遗漏等问题。现在信息技术飞速发展，互联网上包含数学公式的资源愈来愈多，加之数字图书馆的不断发展壮大，人们希望能够利用计算机来对数学公式进行检索。

数学公式检索和匹配定义为在特定的文档集合中是否包含指定的数学公式，文档集合可能为单个文档、多个文档或网络资源等，而包含的含义是指某公式同文档集合中的某些公式或其子公式是匹配的。公式匹配包括下面几种：

（1）精确匹配：两个公式从表现形式和语义上完全相同，在这种情况下，ab+和ba+ 显然不能匹配。

（2）语义匹配：两个公式数学语义是相同的，但是表现形式可能不同。ab+ 和ba+ 是匹配的，他们仅是顺序不同；也是匹配的，其数学含义完全相同。

当前文本检索和匹配相对成熟，如Google、百度等公司的搜索引擎技术已经比较先进。但是这些技术主要是针对字符串文本而言的。而数学公式有其自身特点：

1.数学公式结构复杂，不同于文本的一维线型结构，而是复杂的二维结构。例如对于贝叶斯公式而言，包含了上下标、分式等结构。

2.数学符号众多，不仅有英文和数字，还有希腊字母等。

3.除了数学显示外，数学还包含了语义。

数学公式检索和匹配必须考虑数学公式的这些特点。

数学公式的检索对于信息交流和共享有着重要意义，在科学研究、工程开发、教育教育等方面有着重要应用。目前，数学公式的搜索已经渐渐成为研究热点，国内国外许多机构或人员开展了相关研究，出现了以一些数学搜索印前或相关论文等。例如MathDex、DLMF Search、LeActiveMath、EgoMath等，国内也有相关论文等。总体而言，数学公式的搜索目前还处在探索阶段。

下面对单个文档、多个文档或网络数学公式的检索和匹配等技术进行简单分析。

（二）单个文档的公式检索和匹配

如果对单独文档中的字符串文本进行匹配查找，无论是单模式串还是多模式串，其搜索有多种经典方法，包括KMP、BM、BDM、Wu-Manber等算法，主要理论基础是自动机技术，但是这些算法处理对象均是字符串。但是对于数学公式则没有那么简单，除了在上节所阐述的数学公式的特点外，还包括下面困难：

1.文档来源多种多样，可能包括 PDF、Word、包含TexLaTex的文档、包含MathML的网页和包含数学公式的图片网页等。

2.如何确定两个公式匹配。例如ab+ 和ba+ ，数学语义是相同的，但是表示形式不同。

为了解决这些问题，可以首先对文档进行归一化，然后在进行公式检索和匹配。

（1）文档归一化

由于存在多种多样格式的文档，包括 Word、PDF、TexLaTex、网页(包含MathML或图片等)或其他文档格式等。为了方便公式的匹配与检索，必须对各种文档进行预处理，以相同的格式表示数学公式，即归一化。这里均以 MathDoc格式保存，这样所有的数学公式在形式上和逻辑上统一起来了。

下面简单分析各种文档的处理方法。

对于Word文档，由于Word文档中主要公式为OLE对象（其中大部分为公式编辑器所产生的MathType对象）等，因此可以借助于OLE技术对其进行分析和处理。

对于PDF文档，由于PDF文档是基于PS语言的电子文档格式，其中的数学公式可以为字符或图像。对于字符而言，一般经过符号提取、数学表达式提取等几个阶段；对于图像而言，则使用模式识别技术进行分析提取。

如果是Tex、LaTex文档，由于TexLaTex主要是用来排版的命令语言或宏命令等，其公式查询通过处理后可以采用基于文本技术的检索。这里为了方便，也对其进行归一化，采用MathDoc格式。

如果网页中包含 MathML等，则需要对 MathML解析，MathML主要包含表现形式和表义形式等两种，然后转换成MathDoc格式。

如果网页中包含数学公式图片等，则需要采用模式识别技术进行分析提取。图像中包含的公式一般分为印刷体和（脱机）手写体，其识别一般包括图像预处理、符号识别和结构分析等几个阶段。

MathDoc为自定义的数学公式归一化后的格式。由于数学公式存在明显的嵌套结构，因此数学公式文档格式在逻辑上必须是树的形式。

（2）公式的检索

字符串的匹配查找有多种经典方法，包括KMP、BM、BDM、Wu-Manber等算法，但是这些算法处理对象均是字符串。正如前面的讨论，数学公式不适合采用传统的这些方法，但可供我们借鉴。如果要求公式精确匹配，则我们可以首先公式文本序列化，然后采用字符串匹配的方法进行查找。这种查找方法有其优点：速度快、简单。但是缺点也是很明显的，数学公式匹配不仅仅是表现的匹配，还包括语义的匹配和结构的匹配等。

对于语义匹配，则首先将公式按照某种形式重新构建。公式需要转换为树的形式，在树中，按照某种形式重新排列其元素。例如a+ b和b + a ，经过分析后发现为两个符号的加法运算，由于加法满足交换律，因此可以按照字母顺序重新排列，则这俩个公式重新排列后形式就完全一样，即全部为a+b。然后按照树匹配的算法进行匹配查找。对于两个表达式为减法、乘法等可以以此方式进行匹配。

对于结构匹配而言，则需要检验两个公式是否具有相同的二维结构，例如是否均为分式等。这样和 0.5虽然语义相同，但是结构并不相同。

（3）输入与输出

数学公式检索自然离不开数学公式的输入和输出，但是数学公式由于自身复杂的二维结构，其显示和编辑均比较困难。目前人们可以借助插件或其他技术等实现在网页上的显示和编辑，例如在IE中，可以使用MathPlayer等插件进行公示显示等。同时，必须指定匹配方式。

（三）多个文档或网络资源的公式检索与匹配

如果需要对多个文档进行公式检索，当文档数目不太多的情况，则可以逐个文档按照上节方法进行查找。当文档数目比较多时，则宜采用网络数学公式查找方法。由于网络数学资源多种多样，既有各种Word或PDF文档，又有包含MathML等网页，因此需要首先对文档进行预处理，即如果文档中包含数学公式的话，则该文档进行归一化。其次为了加快查询速度，必须构建索引，例如倒排索引等。在构建索引时，需要考虑数学公式特点，可以以子公式的结构和语义等为关键词构建索引。

（四）小结

数学公式的检索对于科研教育、工程开发等多个领域具重要意义，公式匹配则不同于字符串匹配。本文讨论了数学公式的特点，并给出了针对单个文档、多个文档和网络公示检索匹配的实现方法，一般首先需要对文档进行归一化预处理，然后针对不同匹配要求采用不同方法，为了加快速度，针对多文档或网络资源查找，需要建立索引结构。

[1] MathDex Search tool[EB/OL]. http://www.ima.umn.edu/2006-2007/SW12.8-9.06/activities/Miner-Robert/ind ex.html.

[2] DLMF Search[EB/OL].dlmf.nist.gov/help/search.

[3] LeActiveMath[EB/OL]. http://www.leactivemath.org/

[4] EgoMath[EB/OL]. http://egomath.cythres.cz/.

[5]张志伟.数学表达式数字化处理中关键技术的研究[D].2007.

TP391

A

1008-1151(2011)05-0058-02

2011-02-16

2010年度科研水平提高项目资助（5028123400）

郝保水（1976－），男，河北衡水人，北京信息科技大学计算机学院讲师，硕士，研究方向为计算机应用。