徐以聰,田學東,左麗娜

(河北大學 網(wǎng)絡空間安全與計算機學院,河北 保定 071002)

0 概述

在目前搜索引擎已經(jīng)具備快速準確檢索文本的功能,同時關于文本相似度檢測的研究也較為成熟[1-3]的背景下,數(shù)學公式相似度的檢索問題被廣泛關注[4-6]。然而,數(shù)學表達式具有復雜的二維結(jié)構(gòu)特征,傳統(tǒng)面向一維文本的檢索方法難以滿足其檢索需要。

關于數(shù)學表達式的檢索,國內(nèi)外研究者取得了較多研究成果,但由于數(shù)學表達式的種類繁多且結(jié)構(gòu)復雜,在其索引結(jié)構(gòu)的建立與匹配方面仍有待研究?？紤]到?jīng)Q定數(shù)學表達式含義的往往不是運算數(shù),而是由運算符構(gòu)成的表達式結(jié)構(gòu),本文設計一種基于運算符信息的數(shù)學表達式檢索方法,提取數(shù)學表達式中的運算符作為骨架并建立索引,在此基礎上尋找與目標表達式相似的數(shù)學表達式。

1 相關研究

目前,國內(nèi)外學者已針對數(shù)學表達式檢索的問題提出了多種方法和模型。MCAT search system[7]采用基于路徑與基于哈希散列相結(jié)合的編碼方法對數(shù)學表達式進行編碼,從數(shù)學表達式、段落、文檔3個層面提取文本信息,并參與了NTCIR-12 MathIR任務[8]。文獻[9]設計的語義檢索系統(tǒng)支持盲人用戶進行數(shù)學學習,其先將數(shù)據(jù)庫中的數(shù)學表達式轉(zhuǎn)換為MathML編碼的表達式,再對MathML表達式中的公式進行語義分析,構(gòu)造每個公式的樹狀子結(jié)構(gòu),通過該樹狀子結(jié)構(gòu)以特征向量的形式提取特征。MathPD[10]通過定義表達式符號特征、特征描述符和粒度,運用粒度比較、特征比較、相似度度量的方法來判定2個文檔的相似度。VMEXT[11]是一款數(shù)學表達式可視化工具,其同時將表示元素和數(shù)學表達式的語義結(jié)構(gòu)可視化,使用戶能夠快速發(fā)現(xiàn)MathML標記中不影響表達式表示的缺陷。文獻[12]針對數(shù)字數(shù)學圖書館設計和開發(fā)的Web用戶界面WebMIaS,允許用戶將文本自動生成的標準關鍵字與LaTeX或MathML格式的數(shù)學公式形式的關鍵字組合在一起,通過Web界面進行查詢操作。Min[13]是一個多模態(tài)的數(shù)學搜索界面,可以在臺式機以及平板電腦等設備的標準Web瀏覽器中運行,并通過外部Web服務實現(xiàn)數(shù)學符號的識別與解析功能。

文獻[14]提出一種基于2個索引的數(shù)學公式局部匹配檢索系統(tǒng),其中一個索引將公式視為表達式樹,以每個節(jié)點到根節(jié)點的路徑構(gòu)造反向索引,另一個索引是一個表,用于存儲表達式樹中每個節(jié)點的父節(jié)點和文本字符串。文獻[15]提出的數(shù)學表達式檢索和索引方法,索引中的每個鍵都是一對符號以及它們在表達式中的相對距離和垂直距離,可以解決部分匹配問題。文獻[16]設計的一種MathML格式的數(shù)學公式匹配算法,將數(shù)學公式表示為二叉樹,層次遍歷二叉樹得到結(jié)構(gòu)碼,根據(jù)先序遍歷序列與中序遍歷序列是否相同判斷2個數(shù)學公式是否匹配。文獻[17]提出一種基于Ontology的數(shù)學表達式檢索方法,運用Ontology建立數(shù)學表達式及其概念之間的聯(lián)系并構(gòu)建數(shù)學表達式語義本體庫,以達到輸入關鍵詞、概念、短語和數(shù)學名詞即可檢索數(shù)學表達式語義相關文獻的目的。

文獻[18-19]將數(shù)學表達式轉(zhuǎn)化為自底向上等價的樹結(jié)構(gòu)用以解答數(shù)學應用題,首先構(gòu)造具有不同結(jié)構(gòu)和內(nèi)部節(jié)點的候選樹,然后通過定義評分函數(shù)選擇最佳的候選樹。文獻[20]提出一種多方程數(shù)學表達式問題的求解方法,設計了語義表示語言DOL,用來表示自然語言文本的結(jié)構(gòu)語義,其通過語義分析器將文本轉(zhuǎn)換為DOL樹,根據(jù)得分函數(shù)選擇得分最高的DOL樹。

文獻[21]提出一種基于協(xié)同過濾的數(shù)學表達式推薦方法,通過在數(shù)學表達式查詢輸入端加入數(shù)學表達式子式位置選擇模式,使檢索結(jié)果初步貼近用戶偏好。在此基礎上,采用模糊集方法以多特征指標對用戶偏好進行建模,并依據(jù)用戶行為的隸屬度函數(shù)構(gòu)造用戶對數(shù)學表達式的評分矩陣。最后根據(jù)協(xié)同過濾算法的思想,通過設置閾值產(chǎn)生數(shù)學表達式的推薦列表,實現(xiàn)數(shù)學表達式的協(xié)同過濾推薦。

文獻[22]提出一種基于semi-operator樹生成子樹的層次泛化方法,該方法支持子結(jié)構(gòu)匹配和模糊匹配,其在索引階段構(gòu)建2個索引文件計算查詢公式與文檔的混合相似度得分,提高了在線查詢效率。文獻[23]在文獻[22]方法的基礎上設計改進的數(shù)學信息檢索系統(tǒng),增加了表達式周圍的文本信息屬性,提高了查詢結(jié)果的合理性。

為使用戶可以方便地以數(shù)學公式作為查詢語言對科技文檔進行檢索,文獻[24]提出了一種基于數(shù)學表達式特征的科技文檔檢索模型。首先通過將公式解析為二叉樹得到數(shù)學表達式的子式信息,利用數(shù)學表達式及子式構(gòu)造檢索特征向量;在索引階段,利用所提取的文檔特征向量構(gòu)建分層結(jié)構(gòu)的索引表;在匹配階段,對文檔向量采用tf-idf進行加權(quán)操作,利用余弦相似度對檢索向量和文檔向量進行相似度計算,從而得到一個有序的文檔檢索結(jié)果。

文獻[25]提出一個能夠在維基百科中檢索數(shù)學公式的工具WikiMirs,基于文本和空間相似性搜索相似的數(shù)學公式。該文提出一種從數(shù)學公式表示樹生成子樹的層次泛化方法,并根據(jù)這些樹在不同層次上的匹配程度計算相似度。

文獻[26]提出MIaS,設計了一個基于MathML表示樹的索引結(jié)構(gòu)來檢索數(shù)學表達式,其利用tf-idf權(quán)重法對表達式進行排序。文獻[27]則針對線性代數(shù)表達式,設計了一種線性代數(shù)表達式的索引與匹配方法,根據(jù)線性代數(shù)表達式的種類對其進行分類,并定義相應的擴充運算,據(jù)此構(gòu)建索引文件,設計線性代數(shù)表達式匹配算法,實現(xiàn)靈活的檢索模式,提高檢索結(jié)果的相關性。

2 數(shù)學表達式骨架提取

公式描述結(jié)構(gòu)[28-30](Formula Description Structure,FDS)用于對數(shù)學表達式的描述,更便于建立數(shù)學表達式索引和實現(xiàn)數(shù)學檢索。因此,本文利用改進的FDS解析算法對LaTeX格式數(shù)學表達式進行分析,并提取數(shù)學表達式的結(jié)構(gòu)信息。

2.1 FDS提取算法

數(shù)學表達式每個節(jié)點上的信息存儲在FDS向量(Symbol,Level,Operator,Flag)中,其中:Symbol為表達式的當前符號;Level表示當前符號所在的層次信息,主基線層次為0,其余層次在上一層次的基礎上加1;Operator表示當前符號是否為運算符,如果是運算符,值為1,否則為0;Flag表示當前符號的空間位置,對應over、superscript、subscript、under、inclusion、upper left(ul) 和lower left(ll)7種情況,Fcode為Flag的值,分別對應1、2、3、4、5、6、7。部分表達式符號空間位置關系如表1所示。

表1 部分表達式符號空間位置關系

例如,LaTeX公式“[x=frac{{-bpmsqrt{{b^2} -4ac}}} {{2a}} ]” 對應的原型公式為:

(1)

其FDS解析數(shù)據(jù)見表2。當Fcode為0時,表示該節(jié)點位于主基線層。

表2 式(1)的FDS信息

由于本文設計的索引結(jié)構(gòu)不需要存儲表達式的所有節(jié)點信息,因此有必要對原有的FDS算法進行修改,如算法1所示。

算法1FDS解析算法

輸入LaTeX數(shù)學表達式

輸出數(shù)學表達式的FDS信息

步驟1將隱式運算符關鍵字添加到現(xiàn)有運算符字典中。

步驟2遞歸遍歷LaTeX表達式,查找運算符字典,確定每個關鍵字節(jié)點長度,并為每個節(jié)點分配Level編號。

步驟3依次分析每個關鍵字節(jié)點,并記錄該節(jié)點的Level、Operator和Fcode信息。

步驟4如果Operator為1,則保留該節(jié)點,否則舍棄。保留的節(jié)點構(gòu)成了表達式的FDS信息表。

上述算法的主要過程是線性掃描LaTeX格式的數(shù)學表達式,以一層循環(huán)為主,循環(huán)體內(nèi)包含選擇語句對每個關鍵字進行判斷,若為運算數(shù)則返回循環(huán)條件對下一個關鍵字進行判斷;若為運算符則提取其信息。對一個長度為n的LaTeX表達式,共需執(zhí)行n次元操作,算法的時間復雜度為O(n)。

除了存儲關鍵字本身,字典還存儲關鍵字的類型,這些類型之間用“#”分隔。根據(jù)關鍵字的類型,可以判斷當前關鍵字是否為運算符,然后由運算符判斷當前關鍵字的層次信息。算法修改后獲取的式(1)的FDS信息如表3所示?？梢钥闯?原有信息表中Operator字段值為1的節(jié)點全部保留,為0的全部舍棄。此外,將隱含的指數(shù)符號“^”視為運算符添加進來,層次與標志位均與其指數(shù)位相同?！癪”作為一種隱含符號,與層次的變化有關,其他像“ab”中的乘法將不包括在內(nèi),因為它不會導致左右2個節(jié)點的層次變化。

表3 算法修改后式(1)的FDS信息

2.2 公式骨架提取

數(shù)學表達式的結(jié)構(gòu)由運算符組成,運算符決定了數(shù)學表達式的基本運算含義。考慮以下2個公式:

a2+b2=c2

(2)

x2+y2=z2

(3)

雖然構(gòu)成上述2個表達式的運算數(shù)不同,但結(jié)構(gòu)與含義實際上是完全相同的,其一般形式如下:

i*+j*=k*

(4)

其中,“*”表示指數(shù),不限于等于2。為便于觀察,將式(2)和式(3)以二叉樹的形式描述并提取它們的骨架,分別如圖1～圖3所示。顯然,式(2)和式(3)除了構(gòu)成表達式的運算數(shù)不同以外,運算符及其所在層次是相同的,2個表達式具有完全相同的結(jié)構(gòu)。因此,式(2)和式(3)互為相似表達式。

圖1 式(2)的二叉樹

圖2 式(3)的二叉樹

圖3 式(2)和式(3)的骨架樹

本文的研究目標是檢索出具有完全相同或是部分相同結(jié)構(gòu)的相似表達式,其中部分相同是指2個表達式的結(jié)構(gòu)至少具有一個在同一層次相同的運算符。

3 數(shù)學表達式索引結(jié)構(gòu)設計與匹配

3.1 運算符與骨架存儲結(jié)構(gòu)設計

在對數(shù)學表達式的結(jié)構(gòu)(以下簡稱為骨架)建立索引之前,首先對單個運算符進行結(jié)構(gòu)化設計,除了考慮構(gòu)成骨架的運算符本身以外,還需要考慮運算符在表達式中的層次。

定義1每個運算符與其層次組成一個S-L對(S:Symbol,L:Level),其中,Symbol表示當前運算符本身的符號,Level表示當前運算符的層次。單個運算符的存儲結(jié)構(gòu)如圖4所示。

圖4 單個運算符的存儲結(jié)構(gòu)

對于一個完整的表達式,假設共有N個操作符,將表達式所有的單個操作符存儲結(jié)構(gòu)連接起來即可得到表達式的完整骨架存儲結(jié)構(gòu),如圖5所示。由于N的取值不同,因此不同表達式的完整骨架結(jié)構(gòu)是不等長的。

圖5 完整骨架存儲結(jié)構(gòu)

3.2 數(shù)學表達式索引結(jié)構(gòu)

定義2一個完整的數(shù)學表達式具有如下形式的索引結(jié)構(gòu):expIndex:{expId,fileId,expCode,expInfo},其中,expId為表達式的序號,fileId為當前表達式所在文檔的編號,expCode為表達式的骨架結(jié)構(gòu)編碼,expInfo為LaTeX形式的表達式本身。

定義3含有表達式的文檔索引結(jié)構(gòu)形式為fileIndex:{fileId,fileName},其中,fileId為文檔的編號,fileName為當前文檔的名稱。在檢索時,首先提取待檢索表達式的expCode,然后在數(shù)據(jù)庫中檢索是否有相同或相似的expCode與之匹配,若匹配結(jié)果不為空,即可根據(jù)檢索結(jié)果表達式中的fileId找到對應的fileName。

3.3 數(shù)學表達式匹配算法

定義4設O為任意表達式F的所有S-L對的集合,sl1,sl2,…,sln為O的元素,記為O={sl1,sl2,…,sln},其中,sli(1≤i≤n)分別為F的第i個S-L對,n為S-L對的個數(shù)。

設S為數(shù)據(jù)集中全部表達式S-L對的集合,O1,O2,…,Om為S的元素,S={O1,O2,…,Om},其中,m為表達式的個數(shù),S的子集記為Si(1≤i≤n)。

算法的執(zhí)行步驟數(shù)與目標表達式的長度成正比,表達式的長度越長,骨架結(jié)構(gòu)就越長,從而n也就越大,執(zhí)行的步驟也越多。如圖6所示,可見式(1)的骨架結(jié)構(gòu)為(=/0)+(frac/0)+(-/1)+(pm/1)+(sqrt/1)+(^/3)+(-/2)。

圖6 式(1)檢索過程

數(shù)學表達式匹配算法描述如下:

算法2數(shù)學表達式匹配算法

輸入LaTeX數(shù)學表達式

輸出與目標表達式相似的表達式集合

步驟1輸入待檢索的目標表達式F,利用算法1獲得F的所有S-L對的集合O。

步驟2從O中提取sl1,并在S中檢索出所有包含sl1的表達式,構(gòu)成集合S1。

步驟3從O中提取sl2,并在S1中檢索出所有包含sl2的表達式,構(gòu)成集合S2。

……

步驟n+1從O中提取sln,并在Sn-1中檢索出所有包含sln的表達式,構(gòu)成集合Sn,即與目標表達式相似的表達式集合。

算法步驟1的時間復雜度為O(n),步驟2是第1次從S中提取運算符,因此,復雜度為O(m),從步驟2到步驟n+1,因為集合Si逐漸變小,所以每步的復雜度均小于O(m),又因為n遠小于m,所以算法的總時間復雜度小于O(n)+nO(m),即小于nO(m)。

4 實驗結(jié)果與分析

4.1 實驗數(shù)據(jù)與環(huán)境

本文實驗從ntcir_12_mathir_wikipedia_corpus數(shù)據(jù)集中獲得31 742個文檔,其中包含519 588個數(shù)學表達式。編程語言為C#,采用C/S模式,實驗環(huán)境為Intel(R) Core(TM) i7-7700 CPU,3.6 GHz,內(nèi)存為8 GB。操作系統(tǒng)是Microsoft Windows [version 10.0.17134.407]。

4.2 索引大小與查詢響應時間

表4、表5分別列出了本文實驗索引文件以及文獻[25]索引文件的大小,圖7顯示了隨著公式數(shù)量的增加索引文件大小的變化情況。

表4 本文實驗索引數(shù)據(jù)

表5 文獻[25]索引數(shù)據(jù)

圖7 索引大小與公式個數(shù)的關系

隨著文檔和公式數(shù)量的增加,文檔和公式索引的大小逐漸增大,但增速較低。本文方法只對運算符建立索引,放棄了運算數(shù),大幅減小了索引文件的大小,節(jié)省了存儲空間。與表5所示的文獻[25]索引相比,本文索引較為節(jié)省空間。同時由圖7可知,最初公式索引和總索引2條曲線幾乎重合。文檔索引曲線一直在水平軸附近,與其他2條曲線不同,變化緩慢,公式個數(shù)則與3個索引曲線之間存在線性函數(shù)關系。

對不同結(jié)構(gòu)的表達式進行檢索實驗,結(jié)果如表6所示,其中平均檢索時間是指10次檢索時間的平均值,均在可接受范圍內(nèi)。

表6 部分表達式檢索情況

由表6可以看出:目標表達式結(jié)構(gòu)越簡單,骨架結(jié)構(gòu)越簡單,結(jié)果表達式越多,時間開銷越低;目標表達式的結(jié)構(gòu)越復雜,結(jié)果表達式就越少,所需的時間也就越長。

4.3 個例研究

對式(1)的部分檢索結(jié)果如表7所示。由于查詢結(jié)果數(shù)量較多,表中只列出前15個查詢結(jié)果(本文排序方法的第一步是找到最接近目標公式長度的公式。如果有2個長度相同的結(jié)果公式,則ID較小的排在前面)?？梢钥闯?除了能夠檢索出與目標表達式完全相同的表達式外,本文方法還可以檢索出具有相同結(jié)構(gòu)但運算數(shù)不同的表達式,例如第68 421個和第248 575個表達式,這樣即可消除一般運算數(shù)的影響。

表7 式(1)部分檢索結(jié)果

4.4 對比實驗

表8給出了WikiMirs 和本文系統(tǒng)檢索結(jié)果的前5個查詢結(jié)果。

表8 2種方法的Top-5查詢結(jié)果

5 結(jié)束語

本文通過引入公式描述結(jié)構(gòu),提出一種基于運算符信息的數(shù)學檢索方法,其由FDS分析、索引和匹配3個主要步驟組成。將數(shù)學表達式輸入到FDS程序中獲得運算符信息,在此基礎上建立數(shù)學表達式索引,并通過匹配算法找出與目標表達式相似的數(shù)學表達式。實驗結(jié)果表明,該方法能夠檢索相似的表達式,具有較高的檢索效率,并且不受一般運算數(shù)的影響。由于本文方法主要面向表達式,未考慮表達式在文檔中的重要性,因此下一步將在表達式和文檔之間添加關系屬性,以檢索出滿足用戶需求的文檔。此外,還將優(yōu)化其索引結(jié)構(gòu),加快檢索速度。