基于數(shù)學(xué)表達(dá)式特征的科技文檔檢索模型

田學(xué)東，崔曉娟

(河北大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，河北 保定 071002)

基于數(shù)學(xué)表達(dá)式特征的科技文檔檢索模型

田學(xué)東，崔曉娟

(河北大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，河北 保定 071002)

現(xiàn)有全文檢索技術(shù)多是以文本信息為處理對象，對于以數(shù)學(xué)表達(dá)式為主要成分的科技文檔檢索還處在探索階段.為了使用戶可以方便地以數(shù)學(xué)公式作為查詢語言對科技文檔進行檢索，提出了一種基于數(shù)學(xué)表達(dá)式特征的科技文檔檢索模型.首先通過將公式解析為二叉樹得到數(shù)學(xué)表達(dá)式的子式信息，利用數(shù)學(xué)表達(dá)式及子式構(gòu)造檢索特征向量；在索引階段，利用所提取的文檔特征向量構(gòu)建分層結(jié)構(gòu)的索引表；在匹配階段，對文檔向量采用tf-idf進行加權(quán)操作，利用余弦相似度對檢索向量和文檔向量進行相似度計算，得到一個有序的文檔檢索結(jié)果.實驗選取了來自不同領(lǐng)域的期刊、學(xué)術(shù)網(wǎng)站以及公共數(shù)據(jù)集的5 017篇科技文檔，其中包含了96 362條數(shù)學(xué)公式，平均檢索時間為0.428 s，表明該模型達(dá)到了實現(xiàn)較高效率科技文檔檢索的目標(biāo).

科技文檔；數(shù)學(xué)表達(dá)式；檢索；索引；匹配；二叉樹；特征

數(shù)學(xué)表達(dá)式是科技文獻(xiàn)的重要組成部分，以數(shù)學(xué)表達(dá)式為線索獲取文檔信息，對于科技工作者來說，是較為理想的科技信息獲取方式之一.目前，全文信息檢索技術(shù)已較為成熟，而以數(shù)學(xué)表達(dá)式檢索為核心的科技文檔信息檢索還處于研究階段.國內(nèi)外針對數(shù)學(xué)表達(dá)式檢索的研究已經(jīng)取得了一定的成果，其中MathDex[1]、LetAciveMath[2,3]、EgoMath[4]、MathSearch[5-7]、MIas[8]、DLMFSearch[9-11]、WikiMirs[17]等是已經(jīng)出現(xiàn)的具備數(shù)學(xué)檢索功能的方法和原型系統(tǒng).

DLMFSearch[9-11]是基于DLMF(Digital Library of Mathematical Functions)構(gòu)建的數(shù)學(xué)表達(dá)式檢索系統(tǒng),以TeX/LaTeX格式的數(shù)學(xué)內(nèi)容作為檢索對象，采用由Shatnawi和Youssef提出的Parse-tree作為索引結(jié)構(gòu)，將特殊字符和數(shù)學(xué)符號與字母表中字母相對應(yīng)，使數(shù)學(xué)對象線性化、定界，并序列化，即按順序?qū)⒏鞅磉_(dá)式元素轉(zhuǎn)換為標(biāo)準(zhǔn)形式；然后利用傳統(tǒng)的全文搜索引擎實現(xiàn)面向數(shù)學(xué)表達(dá)式的檢索.Lí?ka等[12]采用擴展傳統(tǒng)文本檢索方法實現(xiàn)數(shù)學(xué)信息檢索的策略，提出了一種將文本信息和表達(dá)式信息進行混合查詢的方法.這種方法采用查詢分解策略，判斷構(gòu)成一次完整查詢的查詢項的個數(shù)，若查詢項較多，則對所有查詢項進行歸類并建立子查詢組，然后對所有子查詢組進行處理.對于各查詢組的檢索結(jié)果，則需要進行權(quán)重分配，通過有效的權(quán)重計算算法將各組結(jié)果進行合并處理.孫凈等[13]利用Trie樹構(gòu)建索引，實現(xiàn)了對數(shù)學(xué)表達(dá)式的結(jié)構(gòu)檢索.盧托等[14]提出一種基于表達(dá)式分層索引的方法通過抽象出表達(dá)式的關(guān)鍵特征，實現(xiàn)了子結(jié)構(gòu)查詢和語義相似性查詢.在數(shù)學(xué)表達(dá)式相似度計算方面，Kamali和Tompa[15]提出了一種基于結(jié)構(gòu)相似度的數(shù)學(xué)檢索方法，采用“樹編輯距離”計算Presentation MathML格式的數(shù)學(xué)表達(dá)式的相似度，并設(shè)計了top-k選擇算法和索引算法來減少查詢處理時間.Zanibbi和Yuan[16]將傳統(tǒng)的面向文檔排序的TF-IDF算法應(yīng)用到數(shù)學(xué)表達(dá)式相似度計算中，將每一個表達(dá)式視為一個單獨的文檔建立索引，這一方法在進行數(shù)學(xué)表達(dá)式相似度計算時避免了由文本和相似公式導(dǎo)致的噪聲.Hu等[17]采取改進的TF-IDF算法計算數(shù)學(xué)表達(dá)式相似度，將表達(dá)式轉(zhuǎn)化為樹并進行正規(guī)化，結(jié)合該關(guān)鍵詞的層次與是否正規(guī)化等信息，計算得出表達(dá)式間的相似度.Lin等[18]在該方法的基礎(chǔ)上，考慮查詢表達(dá)式被匹配表達(dá)式匹配到的關(guān)鍵字?jǐn)?shù)目與查詢表達(dá)式中關(guān)鍵字總數(shù)的比例，對表達(dá)式相似度計算方法進行了改進.Schellenberg[19]用五元組表示數(shù)學(xué)表達(dá)式，通過計算表達(dá)式所對應(yīng)的五元組的距離作為相似度.

國內(nèi)外專家學(xué)者對于文檔檢索以及數(shù)學(xué)公式檢索的理論和方法進行了有益的嘗試，但目前以數(shù)學(xué)表達(dá)式為基礎(chǔ)的科技信息檢索尚處于發(fā)展階段，還沒有成熟、實用的數(shù)學(xué)表達(dá)式檢索系統(tǒng)和搜索引擎問世.通過對數(shù)學(xué)表達(dá)式檢索和文檔檢索的研究，提出一種基于向量空間模型、以數(shù)學(xué)公式特征為查詢依據(jù)的科技文檔檢索模型，以滿足科技工作者對科技文檔的檢索需求.

1 科技文檔檢索模型

根據(jù)科技文獻(xiàn)中數(shù)學(xué)公式的特點以及向量空間模型理論，構(gòu)建科技文檔的檢索模型如圖1所示.

1)文檔特征抽取

針對科技文檔的特征，確定檢索特征及相應(yīng)的提取算法.包括由文檔特征構(gòu)建的文檔信息表和文檔中包含的數(shù)學(xué)公式特征組織構(gòu)建的公式信息表.

2)索引構(gòu)建

根據(jù)所提取的特征構(gòu)成科技文檔檢索的特征向量.借助分層索引模型[21]的方法構(gòu)建數(shù)學(xué)索引.

圖1 科技文檔檢索模型Fig.1 Scientific document retrieval model

3)文檔檢索匹配與結(jié)果排序

解析輸入的LaTeX格式的數(shù)學(xué)表達(dá)式得到公式的檢索特征向量，設(shè)計匹配算法，得到符合查詢需求的所有文檔，依據(jù)相似度計算結(jié)果得到符合用戶需求的文檔排序.

2 檢索特征的提取及數(shù)學(xué)特征向量的構(gòu)建

從科技文檔中抽取的信息包括2部分：一部分是以文檔屬性構(gòu)造的文檔信息表，方便用戶查詢到更多的科技文檔信息；另一部分是公式屬性構(gòu)造的公式信息表，用于構(gòu)建索引檢索科技文檔，如表1、表2所示.文檔信息表和公式信息表的組織結(jié)構(gòu)如圖2所示.

表1 文檔信息表結(jié)構(gòu)

表2 公式信息表結(jié)構(gòu)

圖2 文檔信息組織結(jié)構(gòu)Fig.2 Document information organization structure

數(shù)學(xué)表達(dá)式在互聯(lián)網(wǎng)上的格式有MathML、OpenMath、LaTeX、圖像等[7]，由于多數(shù)格式都可以方便地轉(zhuǎn)換為目前主流的數(shù)學(xué)文檔描述語言LaTeX，故采用LaTeX格式數(shù)學(xué)表達(dá)式作為系統(tǒng)的查詢輸入形式，利用數(shù)學(xué)表達(dá)式特有的二維結(jié)構(gòu)特征及運算符和運算數(shù)屬性對其進行解析.

LaTeX描述的數(shù)學(xué)表達(dá)式解析生成二叉樹的遞歸算法如表3所示.

表3 算法 1 數(shù)學(xué)公式解析算法

圖3 數(shù)學(xué)表達(dá)式的解析過程Fig.3 Analytical process of mathematical expressions

圖4 表達(dá)式(1)的二叉樹結(jié)構(gòu)Fig.4 Binary tree structure of expression(1)

通過上述一系列操作得到數(shù)學(xué)表達(dá)式的二叉樹表示形式，利用隊列先進先出的特點，進行二叉樹結(jié)點入隊和出隊的操作，層次化遍歷二叉樹，得到二叉樹的所有節(jié)點信息.首先，將二叉樹的根結(jié)點進行入隊操作，然后進行隊列的出隊操作，得到根節(jié)點的左子樹結(jié)點和右子樹結(jié)點的所有節(jié)點信息，將得到的信息保存到List表中.上述操作遞歸進行，可以得到數(shù)學(xué)表達(dá)式的所有子式信息.

表4 表達(dá)式的子式信息

定義1對查詢公式Q的子式qn-1,…，q0進行劃分，構(gòu)造查詢公式的檢索向量F(fn-1,…，f0)，其中，n表示查詢公式的子式個數(shù)，fi為子式qi對應(yīng)的檢索特征.

文獻(xiàn)[20]對數(shù)學(xué)公式的子式劃分做了一定的研究，提出了對數(shù)學(xué)公式的N-grams劃分，研究得到對N值的選擇，將N值的下界定義為2-gram，上界定義為15-gram，即N∈[2,15]，這樣索引表的規(guī)模將大大減小.在本文中對提取到公式的所有子式，除去其中的1-gram的子公式，這樣將大大降低檢索特征向量的維度.

降維后的檢索特征向量為

q(FN-gram,FN-1-gram,…，F(xiàn)2-gram)(N=2,3,…，n).

定義2通過檢索向量F檢索得到的文檔向量為dj(DFn,DFn-1,…，DF1)(n=1,2,…，m)(j=0,1,…，i)，其中，DFn表示查詢公式在科技文檔中的特征信息，DFn-1,…，DF1表示查詢公式子式在科技文檔中的特征信息.文檔向量的維度由檢索向量的維度決定.檢索向量降維后，通過檢索得到降維后的文檔向量為

dj(DFN-gram,DFN-1-gram,…，DF2-gram)，

其中(N=2,3,…，n)(j=1,2,…，i).由此可以通過一個查詢公式構(gòu)造的檢索向量q檢索出多篇科技文檔d1,d2,…，dn.

3 科技文檔索引的構(gòu)建

表5 數(shù)學(xué)表達(dá)式的特征編碼

圖5 科技文檔索引結(jié)構(gòu)示例Fig.5 An example of scientific document indexing structure

f索引結(jié)構(gòu)f1d1(Code(f1))，d1(Code(f1))→d2(Code(f1)，d2(Code(f1)))→…→dn(Code(f1)，dn(Code(f1)))…fnd5(Code(fn)，d5(Code(fn)))→d6(Code(fn)，d6(Code(fn)))→…→dm(Code(fn)，dm(Code(fn)))

4 科技文檔檢索的匹配過程及結(jié)果排序

4.1 檢索特征向量的構(gòu)建

根據(jù)查詢公式構(gòu)造的檢索向量中的公式及子式的特征信息,檢索出包含其特征的所有文檔向量構(gòu)成文檔向量集.匹配過程如圖6所示.

圖6 基于數(shù)學(xué)向量的科技文檔的匹配過程Fig.6 Matching process of scientific documents based on mathematical vector

圖6中，Root表示的是根節(jié)點，Leftsubtree表示的是左子樹節(jié)點，Rightsubtree表示的是右子樹節(jié)點，Leafnode表示的是葉子節(jié)點.Key(X)(X表示R、L1等)表示生成的關(guān)鍵碼.Formulan(n=1，2,…，N)表示檢索出的公式集，Documentj(j= 1，2,…，M)表示檢索出的文檔集.

圖7 科技文檔匹配過程示例Fig.7 Examples of scientific document matching process

以上述方式匹配可能會出現(xiàn)檢索文檔結(jié)果重復(fù)的問題，其解決方法如表7所示.

表7 算法2 科技文檔去重算法

4.2 科技文檔檢索結(jié)果的排序

計算文檔相關(guān)度常用的模型主要包括向量空間模型和集合運算模型等，集合運算模型的局限性比較大，所以最常用的還是向量空間模型.對TF-IDF加權(quán)賦予新的含義.

(1)

其中，fi代表的是所要查詢的特征公式在所在文檔中出現(xiàn)的頻率，∑f代表的是特征公式所在文檔的所有公式出現(xiàn)的頻率.

(2)

其中，|D|代表的是文檔集中所有文檔的個數(shù)，{f∈di}表示的是所要查詢的數(shù)學(xué)公式在文檔集中出現(xiàn)的文檔個數(shù).

TF-IDF=tf-idfi=tfi×idfi.

(3)

由此得到文檔向量中每個分量的加權(quán)值.

利用文檔向量中每個特征公式DFi計算出其TF-IDF，并利用TF-IDF對其特征項加權(quán)，可以得到文檔向量中每個特征分量加權(quán)后的向量表示.最后，利用余弦相似度公式得到結(jié)果.

(4)

其中dj(j=0,1,2,…，n-1).計算出檢索向量與文檔向量之間的相似度.公式(4)中q表示的是查詢公式的特征構(gòu)成的檢索向量，dj表示的是科技文檔的特征構(gòu)成的文檔向量.通過上述計算，可以得到與查詢公式相似度較高的文檔集.根據(jù)相似度大小進行文檔排序.

表8 dm文檔向量tf-idf加權(quán)操作表

表9 dn文檔向量tf-idf加權(quán)操作表

計算出每篇文檔向量中每個分量的TF-IDF.然后根據(jù)余弦相似度，計算文檔的相似度，如文檔dm=0.829 39比文檔dn=0.820 27更相似,從表中分析可以看出,文檔dm包含查詢公式子式的個數(shù)雖然不多，但包含有公式本身的信息，dn文檔中雖然查詢公式的子式較多，但沒包含公式本身信息，dm確實更為接近檢索結(jié)果，所以把檢索到的文檔dm排在靠前的位置，而把文檔dn排在靠后的位置.

5 實驗結(jié)果及分析

實驗在Microsoft Visual Studio 2013平臺上實現(xiàn)，在瀏覽器/服務(wù)器模式下，利用.NET平臺和C#語言以及MVC框架進行操作.實驗環(huán)境：Intel Corei5-4 570，IIS服務(wù)，CPU 3.20GHz，RAM 8.00 GB,系統(tǒng)環(huán)境為64位Windows 7操作系統(tǒng).

本文用于實驗的數(shù)據(jù)來自公共數(shù)據(jù)集(如NTCIR數(shù)據(jù)集等)以及不同領(lǐng)域期刊(如知網(wǎng)等)與學(xué)術(shù)網(wǎng)站(如科學(xué)空間網(wǎng)站以及英文預(yù)出版網(wǎng)站arxiv等)，共5 017篇文檔，96 362條測試數(shù)據(jù)，對其進行以數(shù)學(xué)公式為檢索詞的科技文檔檢索.

本文與文獻(xiàn)[18]的索引文件情況如表10、表11所示.

表10 本方法實驗數(shù)據(jù)

表11 文獻(xiàn)[18]方法實驗數(shù)據(jù)

可見本方法索引文件占用空間較小.

隨機選取121條公式進行檢索效率實驗，結(jié)果如表12所示.文獻(xiàn)[18]方法的檢索效率如表13所示.

表12 本方法檢索效率

表13 文獻(xiàn)[18]方法檢索效率

可以看出檢索文檔的時間隨著文檔及公式數(shù)量增加而增加，但增幅相對平穩(wěn).

采用基于數(shù)學(xué)公式特征向量的科技文檔檢索模型，在相同數(shù)據(jù)集的情況下，選取20個數(shù)學(xué)公式(表14),與查詢公式直接檢索科技文檔的方法進行對比，結(jié)果如圖8所示.

表14 查詢表達(dá)式

圖8 向量檢索與公式檢索結(jié)果對比Fig.8 Compare results of vector retrieval and formula retrieval

由圖8可以看出，本方法擴展了以數(shù)學(xué)公式為線索對科技文檔進行檢索的范圍.

6 結(jié)論

本文利用向量空間模型構(gòu)建了以數(shù)學(xué)公式為線索的科技文檔索引與匹配方法，實現(xiàn)了依據(jù)公式信息的科技文檔檢索.通過實驗驗證了利用運算符優(yōu)先級將LaTeX描述的數(shù)學(xué)表達(dá)式構(gòu)造成二叉樹的解析方法和基于數(shù)學(xué)表達(dá)式特征的科技文檔檢索方法的有效性.但是，還存在一些不足之處，實驗中的科技文檔數(shù)量較少；同時，檢索向量的特征還不夠充分.下一步的工作是進一步完善檢索特征，豐富實驗樣本，使檢索系統(tǒng)能夠更好地滿足用戶的檢索需求；并設(shè)計與本文檢索對象相適應(yīng)的相似度計算函數(shù)，使科技文檔的檢索結(jié)果更準(zhǔn)確、合理.

[1] MINER R，MUNAVALLI R.An approach to mathematical search through query formulation and data normalization[M] //Towards Mechanized Mathematical Assistants，Springer Berlin Heidelberg，2007: 342-355.DOI:10.1007/978-3-540-73086-6_27.

[2] LIBBRECHT P，MELIS E.Methods to access and retrieve mathematical content in activemath[M] // Mathematical Software-ICMS 2006，Springer Berlin Heidelberg，2006: 331-342.DOI: 10.1007/11832225_33.

[3] LIBBRECHT P，MELIS E.Semantic search in leactivemath[C] //Proceedings of the First WebALT Conference and Exhibition.Eindhoven，Holland，Jan.2006: 97-109.

[5] 景珂.網(wǎng)絡(luò)數(shù)學(xué)搜索中的數(shù)學(xué)查詢語言與索引的研究[D].蘭州：蘭州大學(xué)，2009.

JING K.Research on math query language and index in web-based math search[D].Lanzhou: Lanzhou University of Technology,2011.

[6] GUO W，SU W，LI L，et al.MQL: A mathematical formula query language for mathematical search [C]// Proceedings of the IEEE Conference on Computational Science and Engineering，Dalian，China: IEEE Press，2011: 245-250.DOI :10.1109/CSE.2011.52.

[7] 劉志偉.數(shù)學(xué)搜索引擎研究[D].蘭州: 蘭州大學(xué)，2011.

LIU Z W.The Research on mathematics search[D].Lanzhou: Lanzhou University of Technology,2011.

[9] YOUSSEF A.Methods of relevance ranking and hit-content generation in math search [M] // Towards Mechanized Mathematical Assistants，Springer Berlin Heidelberg，2007: 393-406.DOI:10.1007/978-3-540-73086-6_31.

[10] SHATNAWI M，YOUSSEF A.Equivalence detection using parse-tree normalization for math search [C]// Proceedings of the 2nd International Conference on Digital Information Management，Lyon，F(xiàn)rance：IEEE Press，2007，2: 643-648.DOI: 10.1109/ICDIM.2007.4444297.

[11] MILLER B，YOUSSEF A.Technical aspects of the digital library of mathematical functions[J].Annals of Mathematics and Artificial Intelligence，2003，38(1): 121-136.DOI: 10.1023/A:1022967814992.

[13] 孫凈.基于Trie樹的數(shù)學(xué)表達(dá)式運算結(jié)構(gòu)檢索[D].保定: 河北大學(xué)，2015.

SUN J.Operation structural retrieval of mathematical expressions based on trie tree[D].Baoding: Hebei University,2015.

[14] 盧托.科技文檔中數(shù)學(xué)公式的描述與檢索[D].武漢: 華中科技大學(xué)，2007.

LU T.The description and retrieval of math formulas in scientific documents[D].Wuhan: Huazhong University of Science and Technology,2007.

[15] KAMALI S，TOMPA F.Structural similarity search for mathematics retrieval [M].Intelligent Computer Mathematics，Springer Berlin Heidelberg，2013: 246-262.DOI:10.1007/978-3-642-39320-4_16.

[16] ZANIBBI R，YUAN B.Keyword and image-based retrieval for mathematical expressions[C]// Proceedings of the SPIE 7874 Conference on Document Recognition and Retrieval XVIII，California，USA: SPIE，2011，7874(6): 993-1004.DOI: 10.1117/12.873312.

[17] HU X，GAO L C，LIN X Y，et al.WikiMirs: A mathematical information retrieval system for wikipedia[C].Proceedings of the 13th ACM/IEEE-CS Joint Conference on Digital libraries.ACM，2013: 11-20.DOI:10.1145/2467696.2467699.

[18] LIN X Y，GAO L C，HU X，et al.A mathematics retrieval system for formulae in layout presentations [C]// Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval，Gold Coast，Australia: ACM，2014: 697-706.DOI:10.1145/2600428.2609611.

[19] SCHELLENBERG T，YUAN B，ZANIBBI R.Layout-based substitution tree indexing and retrieval for mathematical expressions [C]// Proceedings of the SPIE 7874 Conference on Document Recognition and Retrieval XIX，California，USA: SPIE，2012，8297(2): 263-271.DOI:10.1117/12.912502.

[20] 徐月霞.面向語義的數(shù)學(xué)公式N-grams索引結(jié)構(gòu)研究[D].蘭州: 蘭州大學(xué)，2015.

XU Y X.N-gram index structure for semantic based mathematical formulas[D].Lanzhou: Lanzhou University of Technology,2015.

[21] 周南.LaTeX數(shù)學(xué)表達(dá)式解析與索引方法[J].計算機應(yīng)用,2016,36(3):833-836,842.

ZHOU N.Analyzing and indexing method on LaTeX formulae[J].Journal of Computer Applications, 2016,36(3):833-836,842.DOI:10.11772/j.issn.1001-9081.2016.03.833.DOI:10.11772/j.issn.1001-9081.2016.03.833.

Aretrievalmodelofscientificdocumentsbasedonmathematicalexpressionfeatures

TIANXuedong，CUIXiaojuan

(College of Computer Science and Technology，Hebei University，Baoding 071002，China)

The existing full-text retrieval techniques are mostly targeting the text information.While the retrieval of the scientific documents with mathematical expressions as the main components is still in the exploration stage.In order to make the users can easily use the mathematical formula as the query language to retrieve the scientific and technical documents，a new scientific document retrieval model based on mathematical expression features was proposed.Firstly，the formulas were resolved into the subformulas forming the binary trees，which are used to generate the retrieval feature vectors.In the index phase，the index table with the hierarchical structure was constructed using the extracted document feature vectors.In the retrieval phase，the document vectors were weighted by tf-idf.The similarity between the retrieval vector and the document vector was calculated by using the cosine similarity，and an ordered document retrieval result was obtained.The experiment data was selected from different journals，academic website and public data set of 5 017 science and technology documents which contain 96 362 mathematical formulas.The average retrieval time was 0.428 s，which indicates that the proposed model achieved the goal of realizing mathematical expression retrieval with high efficiency.

scientific documents; mathematical expressions; retrieval; indexing; matching; binary tree; features

10.3969/j.issn.1000-1565.2017.06.013

2017-09-18

國家自然科學(xué)基金資助項目(61375075)；河北省教育廳河北省高等學(xué)校科學(xué)技術(shù)研究重點項目(ZD2017208)

田學(xué)東(1963—)，男，天津人，河北大學(xué)教授，博士，主要從事模式識別、信息檢索的研究.

E-mail：xuedong_tian@126.com

TP391

A

1000-1565(2017)06-0652-10

孟素蘭)