基于數學表達式特征的科技文檔檢索模型

田學東，崔曉娟

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

基于數學表達式特征的科技文檔檢索模型

田學東，崔曉娟

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

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

科技文檔；數學表達式；檢索；索引；匹配；二叉樹；特征

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

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

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

1 科技文檔檢索模型

根據科技文獻中數學公式的特點以及向量空間模型理論，構建科技文檔的檢索模型如圖1所示.

1)文檔特征抽取

針對科技文檔的特征，確定檢索特征及相應的提取算法.包括由文檔特征構建的文檔信息表和文檔中包含的數學公式特征組織構建的公式信息表.

2)索引構建

根據所提取的特征構成科技文檔檢索的特征向量.借助分層索引模型[21]的方法構建數學索引.

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

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

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

2 檢索特征的提取及數學特征向量的構建

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

表1 文檔信息表結構

表2 公式信息表結構

圖2 文檔信息組織結構Fig.2 Document information organization structure

數學表達式在互聯網上的格式有MathML、OpenMath、LaTeX、圖像等[7]，由于多數格式都可以方便地轉換為目前主流的數學文檔描述語言LaTeX，故采用LaTeX格式數學表達式作為系統的查詢輸入形式，利用數學表達式特有的二維結構特征及運算符和運算數屬性對其進行解析.

LaTeX描述的數學表達式解析生成二叉樹的遞歸算法如表3所示.

表3 算法 1 數學公式解析算法

圖3 數學表達式的解析過程Fig.3 Analytical process of mathematical expressions

圖4 表達式(1)的二叉樹結構Fig.4 Binary tree structure of expression(1)

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

表4 表達式的子式信息

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

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

降維后的檢索特征向量為

q(FN-gram,FN-1-gram,…，F2-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).由此可以通過一個查詢公式構造的檢索向量q檢索出多篇科技文檔d1,d2,…，dn.

3 科技文檔索引的構建

表5 數學表達式的特征編碼

圖5 科技文檔索引結構示例Fig.5 An example of scientific document indexing structure

f索引結構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 科技文檔檢索的匹配過程及結果排序

4.1 檢索特征向量的構建

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

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

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

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

以上述方式匹配可能會出現檢索文檔結果重復的問題，其解決方法如表7所示.

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

4.2 科技文檔檢索結果的排序

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

(1)

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

(2)

其中，|D|代表的是文檔集中所有文檔的個數，{f∈di}表示的是所要查詢的數學公式在文檔集中出現的文檔個數.

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

(3)

由此得到文檔向量中每個分量的加權值.

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

(4)

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

表8 dm文檔向量tf-idf加權操作表

表9 dn文檔向量tf-idf加權操作表

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

5 實驗結果及分析

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

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

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

表10 本方法實驗數據

表11 文獻[18]方法實驗數據

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

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

表12 本方法檢索效率

表13 文獻[18]方法檢索效率

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

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

表14 查詢表達式

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

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

6 結論

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

[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] 景珂.網絡數學搜索中的數學查詢語言與索引的研究[D].蘭州：蘭州大學，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] 劉志偉.數學搜索引擎研究[D].蘭州: 蘭州大學，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，France：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樹的數學表達式運算結構檢索[D].保定: 河北大學，2015.

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

[14] 盧托.科技文檔中數學公式的描述與檢索[D].武漢: 華中科技大學，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] 徐月霞.面向語義的數學公式N-grams索引結構研究[D].蘭州: 蘭州大學，2015.

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

[21] 周南.LaTeX數學表達式解析與索引方法[J].計算機應用,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

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

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

E-mail：xuedong_tian@126.com

TP391

A

1000-1565(2017)06-0652-10

孟素蘭)