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

郝保水

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

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

郝保水

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

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

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

（一）引言

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

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

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

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

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

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

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

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

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

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

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

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

（二）單個文檔的公式檢索和匹配

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

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

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

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

（1）文檔歸一化

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

下面簡單分析各種文檔的處理方法。

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

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

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

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

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

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

（2）公式的檢索

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

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

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

（3）輸入與輸出

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

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

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

（四）小結(jié)

數(shù)學(xué)公式的檢索對于科研教育、工程開發(fā)等多個領(lǐng)域具重要意義，公式匹配則不同于字符串匹配。本文討論了數(shù)學(xué)公式的特點，并給出了針對單個文檔、多個文檔和網(wǎng)絡(luò)公示檢索匹配的實現(xiàn)方法，一般首先需要對文檔進行歸一化預(yù)處理，然后針對不同匹配要求采用不同方法，為了加快速度，針對多文檔或網(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é)表達式數(shù)字化處理中關(guān)鍵技術(shù)的研究[D].2007.

TP391

A

1008-1151(2011)05-0058-02

2011-02-16

2010年度科研水平提高項目資助（5028123400）

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