數學公式檢索與匹配技術研究

郝保水

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

數學公式檢索與匹配技術研究

郝保水

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

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

數學公式；公式匹配；公式檢索

（一）引言

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

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

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

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

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

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

1.數學公式結構復雜，不同于文本的一維線型結構，而是復雜的二維結構。例如對于貝葉斯公式而言，包含了上下標、分式等結構。

2.數學符號眾多，不僅有英文和數字，還有希臘字母等。

3.除了數學顯示外，數學還包含了語義。

數學公式檢索和匹配必須考慮數學公式的這些特點。

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

下面對單個文檔、多個文檔或網絡數學公式的檢索和匹配等技術進行簡單分析。

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

如果對單獨文檔中的字符串文本進行匹配查找，無論是單模式串還是多模式串，其搜索有多種經典方法，包括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－），男，河北衡水人，北京信息科技大學計算機學院講師，碩士，研究方向為計算機應用。