郝保水

（北京信息科技大學(xué)計(jì)算機(jī)學(xué)院，北京 100101）

數(shù)學(xué)公式檢索與匹配技術(shù)研究

郝保水

（北京信息科技大學(xué)計(jì)算機(jī)學(xué)院，北京 100101）

數(shù)學(xué)公式是科技文檔不可或缺的重要組成部分，具有復(fù)雜的二維結(jié)構(gòu)和嵌套結(jié)構(gòu)。數(shù)學(xué)文檔有多種格式，包括Word、PDF、MathML、TexLaTex等，如何對(duì)文檔中的公式進(jìn)行檢索，如何判定兩個(gè)公式匹配則成為一個(gè)難題。公式匹配包括精確匹配、語(yǔ)義匹配和結(jié)構(gòu)匹配等，如果簡(jiǎn)單地使用字符串匹配技術(shù)，則無(wú)法實(shí)現(xiàn)公式的匹配，因此必須針對(duì)數(shù)學(xué)公式特點(diǎn)，研究出相應(yīng)公式匹配方法。首先對(duì)文檔進(jìn)行歸一化，然后對(duì)公式進(jìn)行匹配。如果有多個(gè)文檔或網(wǎng)絡(luò)檢索的話(huà)，則為了加快速度，需要構(gòu)建索引等結(jié)構(gòu)。

數(shù)學(xué)公式；公式匹配；公式檢索

（一）引言

科學(xué)離不開(kāi)數(shù)學(xué)，數(shù)學(xué)是科學(xué)的工具，而數(shù)學(xué)是借助數(shù)學(xué)公式來(lái)進(jìn)行描述和表現(xiàn)的。在各種科技文檔中，包含著大量的數(shù)學(xué)公式。如何對(duì)這些公式進(jìn)行檢索，則日益成為一個(gè)重要的問(wèn)題。

在將各種文檔電子化之前，只能使用人工對(duì)數(shù)學(xué)公式進(jìn)行檢索，考校的主要是記憶力和理解力，存在速度慢、范圍窄、有遺漏等問(wèn)題?，F(xiàn)在信息技術(shù)飛速發(fā)展，互聯(lián)網(wǎng)上包含數(shù)學(xué)公式的資源愈來(lái)愈多，加之?dāng)?shù)字圖書(shū)館的不斷發(fā)展壯大，人們希望能夠利用計(jì)算機(jī)來(lái)對(duì)數(shù)學(xué)公式進(jìn)行檢索。

數(shù)學(xué)公式檢索和匹配定義為在特定的文檔集合中是否包含指定的數(shù)學(xué)公式，文檔集合可能為單個(gè)文檔、多個(gè)文檔或網(wǎng)絡(luò)資源等，而包含的含義是指某公式同文檔集合中的某些公式或其子公式是匹配的。公式匹配包括下面幾種：

（1）精確匹配：兩個(gè)公式從表現(xiàn)形式和語(yǔ)義上完全相同，在這種情況下，ab+和ba+ 顯然不能匹配。

（2）語(yǔ)義匹配：兩個(gè)公式數(shù)學(xué)語(yǔ)義是相同的，但是表現(xiàn)形式可能不同。ab+ 和ba+ 是匹配的，他們僅是順序不同；也是匹配的，其數(shù)學(xué)含義完全相同。

當(dāng)前文本檢索和匹配相對(duì)成熟，如Google、百度等公司的搜索引擎技術(shù)已經(jīng)比較先進(jìn)。但是這些技術(shù)主要是針對(duì)字符串文本而言的。而數(shù)學(xué)公式有其自身特點(diǎn)：

1.數(shù)學(xué)公式結(jié)構(gòu)復(fù)雜，不同于文本的一維線(xiàn)型結(jié)構(gòu)，而是復(fù)雜的二維結(jié)構(gòu)。例如對(duì)于貝葉斯公式而言，包含了上下標(biāo)、分式等結(jié)構(gòu)。

2.數(shù)學(xué)符號(hào)眾多，不僅有英文和數(shù)字，還有希臘字母等。

3.除了數(shù)學(xué)顯示外，數(shù)學(xué)還包含了語(yǔ)義。

數(shù)學(xué)公式檢索和匹配必須考慮數(shù)學(xué)公式的這些特點(diǎn)。

數(shù)學(xué)公式的檢索對(duì)于信息交流和共享有著重要意義，在科學(xué)研究、工程開(kāi)發(fā)、教育教育等方面有著重要應(yīng)用。目前，數(shù)學(xué)公式的搜索已經(jīng)漸漸成為研究熱點(diǎn)，國(guó)內(nèi)國(guó)外許多機(jī)構(gòu)或人員開(kāi)展了相關(guān)研究，出現(xiàn)了以一些數(shù)學(xué)搜索印前或相關(guān)論文等。例如MathDex、DLMF Search、LeActiveMath、EgoMath等，國(guó)內(nèi)也有相關(guān)論文等。總體而言，數(shù)學(xué)公式的搜索目前還處在探索階段。

下面對(duì)單個(gè)文檔、多個(gè)文檔或網(wǎng)絡(luò)數(shù)學(xué)公式的檢索和匹配等技術(shù)進(jìn)行簡(jiǎn)單分析。

（二）單個(gè)文檔的公式檢索和匹配

如果對(duì)單獨(dú)文檔中的字符串文本進(jìn)行匹配查找，無(wú)論是單模式串還是多模式串，其搜索有多種經(jīng)典方法，包括KMP、BM、BDM、Wu-Manber等算法，主要理論基礎(chǔ)是自動(dòng)機(jī)技術(shù)，但是這些算法處理對(duì)象均是字符串。但是對(duì)于數(shù)學(xué)公式則沒(méi)有那么簡(jiǎn)單，除了在上節(jié)所闡述的數(shù)學(xué)公式的特點(diǎn)外，還包括下面困難：

1.文檔來(lái)源多種多樣，可能包括 PDF、Word、包含TexLaTex的文檔、包含MathML的網(wǎng)頁(yè)和包含數(shù)學(xué)公式的圖片網(wǎng)頁(yè)等。

2.如何確定兩個(gè)公式匹配。例如ab+ 和ba+ ，數(shù)學(xué)語(yǔ)義是相同的，但是表示形式不同。

為了解決這些問(wèn)題，可以首先對(duì)文檔進(jìn)行歸一化，然后在進(jìn)行公式檢索和匹配。

（1）文檔歸一化

由于存在多種多樣格式的文檔，包括 Word、PDF、TexLaTex、網(wǎng)頁(yè)(包含MathML或圖片等)或其他文檔格式等。為了方便公式的匹配與檢索，必須對(duì)各種文檔進(jìn)行預(yù)處理，以相同的格式表示數(shù)學(xué)公式，即歸一化。這里均以 MathDoc格式保存，這樣所有的數(shù)學(xué)公式在形式上和邏輯上統(tǒng)一起來(lái)了。

下面簡(jiǎn)單分析各種文檔的處理方法。

對(duì)于Word文檔，由于Word文檔中主要公式為OLE對(duì)象（其中大部分為公式編輯器所產(chǎn)生的MathType對(duì)象）等，因此可以借助于OLE技術(shù)對(duì)其進(jìn)行分析和處理。

對(duì)于PDF文檔，由于PDF文檔是基于PS語(yǔ)言的電子文檔格式，其中的數(shù)學(xué)公式可以為字符或圖像。對(duì)于字符而言，一般經(jīng)過(guò)符號(hào)提取、數(shù)學(xué)表達(dá)式提取等幾個(gè)階段；對(duì)于圖像而言，則使用模式識(shí)別技術(shù)進(jìn)行分析提取。

如果是Tex、LaTex文檔，由于TexLaTex主要是用來(lái)排版的命令語(yǔ)言或宏命令等，其公式查詢(xún)通過(guò)處理后可以采用基于文本技術(shù)的檢索。這里為了方便，也對(duì)其進(jìn)行歸一化，采用MathDoc格式。

如果網(wǎng)頁(yè)中包含 MathML等，則需要對(duì) MathML解析，MathML主要包含表現(xiàn)形式和表義形式等兩種，然后轉(zhuǎn)換成MathDoc格式。

如果網(wǎng)頁(yè)中包含數(shù)學(xué)公式圖片等，則需要采用模式識(shí)別技術(shù)進(jìn)行分析提取。圖像中包含的公式一般分為印刷體和（脫機(jī)）手寫(xiě)體，其識(shí)別一般包括圖像預(yù)處理、符號(hào)識(shí)別和結(jié)構(gòu)分析等幾個(gè)階段。

MathDoc為自定義的數(shù)學(xué)公式歸一化后的格式。由于數(shù)學(xué)公式存在明顯的嵌套結(jié)構(gòu)，因此數(shù)學(xué)公式文檔格式在邏輯上必須是樹(shù)的形式。

（2）公式的檢索

字符串的匹配查找有多種經(jīng)典方法，包括KMP、BM、BDM、Wu-Manber等算法，但是這些算法處理對(duì)象均是字符串。正如前面的討論，數(shù)學(xué)公式不適合采用傳統(tǒng)的這些方法，但可供我們借鑒。如果要求公式精確匹配，則我們可以首先公式文本序列化，然后采用字符串匹配的方法進(jìn)行查找。這種查找方法有其優(yōu)點(diǎn)：速度快、簡(jiǎn)單。但是缺點(diǎn)也是很明顯的，數(shù)學(xué)公式匹配不僅僅是表現(xiàn)的匹配，還包括語(yǔ)義的匹配和結(jié)構(gòu)的匹配等。

對(duì)于語(yǔ)義匹配，則首先將公式按照某種形式重新構(gòu)建。公式需要轉(zhuǎn)換為樹(shù)的形式，在樹(shù)中，按照某種形式重新排列其元素。例如a+ b和b + a ，經(jīng)過(guò)分析后發(fā)現(xiàn)為兩個(gè)符號(hào)的加法運(yùn)算，由于加法滿(mǎn)足交換律，因此可以按照字母順序重新排列，則這倆個(gè)公式重新排列后形式就完全一樣，即全部為a+b。然后按照樹(shù)匹配的算法進(jìn)行匹配查找。對(duì)于兩個(gè)表達(dá)式為減法、乘法等可以以此方式進(jìn)行匹配。

對(duì)于結(jié)構(gòu)匹配而言，則需要檢驗(yàn)兩個(gè)公式是否具有相同的二維結(jié)構(gòu)，例如是否均為分式等。這樣和 0.5雖然語(yǔ)義相同，但是結(jié)構(gòu)并不相同。

（3）輸入與輸出

數(shù)學(xué)公式檢索自然離不開(kāi)數(shù)學(xué)公式的輸入和輸出，但是數(shù)學(xué)公式由于自身復(fù)雜的二維結(jié)構(gòu)，其顯示和編輯均比較困難。目前人們可以借助插件或其他技術(shù)等實(shí)現(xiàn)在網(wǎng)頁(yè)上的顯示和編輯，例如在IE中，可以使用MathPlayer等插件進(jìn)行公示顯示等。同時(shí)，必須指定匹配方式。

（三）多個(gè)文檔或網(wǎng)絡(luò)資源的公式檢索與匹配

如果需要對(duì)多個(gè)文檔進(jìn)行公式檢索，當(dāng)文檔數(shù)目不太多的情況，則可以逐個(gè)文檔按照上節(jié)方法進(jìn)行查找。當(dāng)文檔數(shù)目比較多時(shí)，則宜采用網(wǎng)絡(luò)數(shù)學(xué)公式查找方法。由于網(wǎng)絡(luò)數(shù)學(xué)資源多種多樣，既有各種Word或PDF文檔，又有包含MathML等網(wǎng)頁(yè)，因此需要首先對(duì)文檔進(jìn)行預(yù)處理，即如果文檔中包含數(shù)學(xué)公式的話(huà)，則該文檔進(jìn)行歸一化。其次為了加快查詢(xún)速度，必須構(gòu)建索引，例如倒排索引等。在構(gòu)建索引時(shí)，需要考慮數(shù)學(xué)公式特點(diǎn)，可以以子公式的結(jié)構(gòu)和語(yǔ)義等為關(guān)鍵詞構(gòu)建索引。

（四）小結(jié)

數(shù)學(xué)公式的檢索對(duì)于科研教育、工程開(kāi)發(fā)等多個(gè)領(lǐng)域具重要意義，公式匹配則不同于字符串匹配。本文討論了數(shù)學(xué)公式的特點(diǎn)，并給出了針對(duì)單個(gè)文檔、多個(gè)文檔和網(wǎng)絡(luò)公示檢索匹配的實(shí)現(xiàn)方法，一般首先需要對(duì)文檔進(jìn)行歸一化預(yù)處理，然后針對(duì)不同匹配要求采用不同方法，為了加快速度，針對(duì)多文檔或網(wǎng)絡(luò)資源查找，需要建立索引結(jié)構(gòu)。

[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]張志偉.數(shù)學(xué)表達(dá)式數(shù)字化處理中關(guān)鍵技術(shù)的研究[D].2007.

TP391

A

1008-1151(2011)05-0058-02

2011-02-16

2010年度科研水平提高項(xiàng)目資助（5028123400）

郝保水（1976－），男，河北衡水人，北京信息科技大學(xué)計(jì)算機(jī)學(xué)院講師，碩士，研究方向?yàn)橛?jì)算機(jī)應(yīng)用。