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

0 概述

作為現(xiàn)代數(shù)學(xué)的一個(gè)重要研究課題,線性代數(shù)式廣泛應(yīng)用于各種科技文獻(xiàn),相對(duì)于普通公式和文本,線性代數(shù)式的結(jié)構(gòu)更復(fù)雜。目前主流的搜索引擎多數(shù)是針對(duì)文本而設(shè)計(jì),且部分針對(duì)數(shù)學(xué)公式設(shè)計(jì)的檢索系統(tǒng)也不能十分合理地完成線性代數(shù)式的搜索,因此,研究并設(shè)計(jì)具有線性代數(shù)式檢索功能的數(shù)學(xué)公式檢索系統(tǒng)具有重要意義。

目前,國(guó)內(nèi)外針對(duì)線性代數(shù)式檢索的研究并不多,而針對(duì)普通表達(dá)式的研究已取得一些成果,包括MathDex[1]、DLMF Search[2]、LeActiveMath[3-4]、EgoMath[5-7]、MathWebSearch[8-9]、Wikimirs[10-11]等。按照實(shí)現(xiàn)方法,可將上述成果分為改進(jìn)文本搜索的數(shù)學(xué)檢索系統(tǒng)和為數(shù)學(xué)公式建立專門索引的數(shù)學(xué)檢索系統(tǒng),前者不支持?jǐn)?shù)學(xué)公式內(nèi)容識(shí)別,而后者支持。隨著網(wǎng)絡(luò)數(shù)學(xué)資源的日漸豐富,用戶進(jìn)行檢索時(shí)往往會(huì)返回大量的檢索結(jié)果,如何按檢索結(jié)果與查詢公式的相似度由高到低將其進(jìn)行排序,以縮短查詢時(shí)間、提升工作效率,是實(shí)際應(yīng)用中面臨的挑戰(zhàn)。

文獻(xiàn)[12]將數(shù)學(xué)公式用五元組(s,n,r,p,b)表示,利用距離公式計(jì)算待查詢式和結(jié)果式的五元組距離,得出相似度進(jìn)而完成排序。文獻(xiàn)[13]提出一種基于結(jié)構(gòu)相似度的數(shù)學(xué)檢索方法,其將不同形式的數(shù)學(xué)公式統(tǒng)一成Presentation MathML格式,采用“樹編輯距離”方法計(jì)算公式之間的相似度。文獻(xiàn)[14-15]定義“數(shù)據(jù)類型層級(jí)”“查詢覆蓋度”“匹配深度”等特征,利用對(duì)查詢表達(dá)式和獲取目標(biāo)表達(dá)式的解析樹進(jìn)行遞歸的相似距離分析,計(jì)算其之間的相似度。文獻(xiàn)[16-17]設(shè)計(jì)并實(shí)現(xiàn)數(shù)學(xué)公式檢索系統(tǒng)MASE和Lattice-based Math Search,前者采用被動(dòng)攻擊的在線學(xué)習(xí)分類模型對(duì)檢索結(jié)果進(jìn)行排序,后者建立數(shù)學(xué)概念格,在格中完成數(shù)學(xué)公式的相關(guān)排序。文獻(xiàn)[10]改進(jìn)TF-IDF(Term Frequency-Inverse Document Frequency)算法,引入節(jié)點(diǎn)所處層次評(píng)價(jià)指標(biāo),計(jì)算每個(gè)節(jié)點(diǎn)的頻率和倒排公式頻率,完成相似度排序。文獻(xiàn)[11]改進(jìn)文獻(xiàn)[10]方法,引入結(jié)果表達(dá)式中包含的與待查詢式相同的節(jié)點(diǎn)數(shù)目占待查詢式節(jié)點(diǎn)總數(shù)的比例,用其作為評(píng)價(jià)指標(biāo),優(yōu)化排序結(jié)果。文獻(xiàn)[18]采用加權(quán)算法形成權(quán)值分配矩陣,利用快速排序和優(yōu)化排序?qū)?shù)學(xué)公式進(jìn)行相似度計(jì)算。

上述方法為線性代數(shù)式檢索結(jié)果排序提供了思路。由于線性代數(shù)式的結(jié)構(gòu)、語(yǔ)法和語(yǔ)義的復(fù)雜性,只有選擇合理的理論及模型,從多視角研究線性代數(shù)式的特征,才能完成線性代數(shù)式檢索結(jié)果的相似度排序。本文將猶豫模糊集理論應(yīng)用于線性代數(shù)式的相似度評(píng)價(jià)中,提出一種線性代數(shù)式檢索結(jié)果相似度排序方法。在線性代數(shù)式的局部屬性和整體屬性2個(gè)方面建立隸屬度函數(shù),應(yīng)用距離相似度公式計(jì)算猶豫模糊集之間的距離,完成待查詢線性代數(shù)式與檢索結(jié)果式的相似度計(jì)算,并最終得到排序結(jié)果。

1 線性代數(shù)式相似度評(píng)價(jià)特征

1.1 線性代數(shù)式檢索模式

線性代數(shù)式種類較多,其變形和計(jì)算十分豐富,在設(shè)計(jì)檢索系統(tǒng)時(shí),應(yīng)根據(jù)用戶的實(shí)際需求設(shè)計(jì)不同的匹配模式。

定義1線性代數(shù)式中按照行列規(guī)則排列,既相互獨(dú)立又互有聯(lián)系的子表達(dá)式稱為子公式。

定義2Eq為一個(gè)m行n列的線性代數(shù)查詢式,Eq(i,j)(i=1,2,…,m;j=1,2,…,n)為其子公式,Erqt(t=1,2,…,h)為檢索結(jié)果集合中的h個(gè)c行d列線性代數(shù)式,Erqt(k,l)(k=1,2,…,c;l=1,2,…,d)為其子公式。

線性代數(shù)式的檢索功能覆蓋了矩陣、行列式和方程組匹配3種模式,它們均是在子式匹配的基礎(chǔ)上做了相應(yīng)的改進(jìn)。由于在匹配算法的設(shè)計(jì)時(shí)考慮到線性代數(shù)式的語(yǔ)法和語(yǔ)義變換問題,因此矩陣匹配結(jié)果中除包含與待查詢矩陣精確一致,或部分子式包含待查詢矩陣子式的矩陣外,還會(huì)包含查詢式的轉(zhuǎn)置、逆矩陣、增廣矩陣和伴隨矩陣等變換結(jié)果。因此,在矩陣檢索結(jié)果的相似度評(píng)價(jià)中,也將查詢式的轉(zhuǎn)置、逆矩陣、增廣矩陣和伴隨矩陣作為相似度評(píng)價(jià)的因素。類似地,在行列式匹配中涉及轉(zhuǎn)置變換和求值運(yùn)算,而方程組匹配僅限于子式匹配。

子式匹配是將用戶輸入的待查詢式Eq的子式Eq(i,j)和檢索結(jié)果集Erqt的子式Erqt(k,l)看作一個(gè)獨(dú)立的數(shù)學(xué)公式,按行優(yōu)先原則遞歸地將Eq(i,j)和Erqt(k,l)進(jìn)行包含匹配,即要求Eq(i,j)是Erqt(k,l)的一部分或兩者完全相同,當(dāng)包含匹配成功時(shí),將該Erqt(k,l)所對(duì)應(yīng)的Erqt返回給用戶。子式匹配原理如圖1所示。

圖1 子式匹配原理

1.2 評(píng)價(jià)流程

對(duì)線性代數(shù)式進(jìn)行相似度評(píng)價(jià)的流程分為3個(gè)步驟:特征提取,隸屬度計(jì)算,相似度計(jì)算。

圖2 線性代數(shù)式評(píng)價(jià)原理

在圖2中,一級(jí)屬性為局部屬性{A1,A2,…,Am},二級(jí)屬性為整體屬性{Am+1,Am+2,…,An},每個(gè)屬性包含一組評(píng)價(jià)標(biāo)準(zhǔn),按每個(gè)屬性所對(duì)應(yīng)的評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行特征提取,首先提取局部屬性特征,并代入相應(yīng)的隸屬度函數(shù)進(jìn)行計(jì)算,再按相同的原理提取整體屬性特征,形成如圖2所示的局部猶豫模糊集和整體猶豫模糊集,最后根據(jù)針對(duì)線性代數(shù)式變型的廣義猶豫標(biāo)準(zhǔn)距離公式完成公式之間的相似度計(jì)算,該公式將在后文中給出詳細(xì)定義?；讵q豫模糊集的線性代數(shù)式評(píng)價(jià)流程如圖3所示。

圖3 線性代數(shù)式評(píng)價(jià)流程

1.3 評(píng)價(jià)屬性

本文從局部和整體2個(gè)部分進(jìn)行線性代數(shù)式的相似度評(píng)價(jià)。綜合考慮多種因素,定義線性代數(shù)式的評(píng)價(jià)屬性如表1所示,其中針對(duì)不同的匹配模式,將個(gè)別屬性設(shè)置為1來(lái)表示該屬性值對(duì)該匹配模式的屬性評(píng)價(jià)無(wú)影響。

表1 線性代數(shù)式評(píng)價(jià)屬性

定義3calla[a,b]表示a與b的相似度。其中a,b表示代數(shù)式。

1.3.1 局部屬性

線性代數(shù)式是多個(gè)子公式的組合,子公式的結(jié)構(gòu)、數(shù)量、位置和相對(duì)位置等都影響著線性代數(shù)式之間的相似程度。因此,進(jìn)行線性代數(shù)式相似度評(píng)價(jià)時(shí)需考慮如下屬性:

1)結(jié)構(gòu)屬性AF

(1)長(zhǎng)度標(biāo)準(zhǔn)indlen

按行優(yōu)先原則考察Eq(i,j)與每一個(gè)以其為子式的Erqt(k,l)所包含的運(yùn)算數(shù)和運(yùn)算符的數(shù)目,兩者的數(shù)目越接近,其相似度就越大。

calla[Eq(1,1),Erq1(1,1)]

(1)

(2)層次標(biāo)準(zhǔn)indlev

圖4 線性代數(shù)式層次與相似度關(guān)系

(3)位置標(biāo)準(zhǔn)indloc

calla[Eq(1,1),Erq1(1,1)]>calla[Eq(1,1),Erq2(2,1)]

(2)

(4)起始位標(biāo)準(zhǔn)indsta

圖5 線性代數(shù)式起始位與相似度關(guān)系

(5)標(biāo)志位標(biāo)準(zhǔn)indfla

圖6 線性代數(shù)式標(biāo)志位與相似度關(guān)系

2)運(yùn)算數(shù)屬性AO

按行優(yōu)先原則考察Eq(i,j)與以其為子式的Erqt(k,l)的運(yùn)算數(shù)信息,設(shè)Eq(i,j)中包含若干運(yùn)算數(shù){O1,O2,…,Os1},其中,s1表示Eq(i,j)所包含的運(yùn)算數(shù)個(gè)數(shù),考察Om(m=1,2,…,s1)在Erqt(k,l)中出現(xiàn)的次數(shù)及重要程度,將其作為一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)indopd。

3)運(yùn)算符屬性AR

按行優(yōu)先原則考察Eq(i,j)與以其為子式的Erqt(k,l)的運(yùn)算符信息,設(shè)Eq(i,j)中包含若干運(yùn)算符{R1,R2,…,Rs2},其中,s2表示Eq(i,j)所包含的運(yùn)算符個(gè)數(shù),考察Rn(n=1,2,…,s2)在Erqt(k,l)中出現(xiàn)的次數(shù)及重要程度,將其作為一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)indopr。

1.3.2 整體屬性

線性代數(shù)式在整體角度有其獨(dú)特的特征,因此,在考察線性代數(shù)式間的相似度時(shí)應(yīng)考慮其整體屬性,從而得出更準(zhǔn)確的測(cè)評(píng)結(jié)果。

1)矩陣變換屬性AJ

考慮矩陣A的4種變形:轉(zhuǎn)置變換AT,逆矩陣變換A-1,增廣矩陣變換和伴隨矩陣變換A*。將Eq和Erqt的矩陣變換信息作為評(píng)價(jià)標(biāo)準(zhǔn)indjuz?？紤]到待查詢矩陣與經(jīng)過(guò)上述4種變換后矩陣的相似性,規(guī)定相似度排序?yàn)?原矩陣>轉(zhuǎn)置矩陣>增廣矩陣>逆矩陣>伴隨矩陣>普通矩陣。

2)行列式變換屬性AD

根據(jù)行列式的性質(zhì)可知:D=DT,即行列式與其轉(zhuǎn)置行列式相等,將行列式是否與原查詢式互為轉(zhuǎn)置作為評(píng)價(jià)標(biāo)準(zhǔn)indhal。

3)行列式的值屬性AK

行列式可以進(jìn)行求值運(yùn)算,依據(jù)行列式的性質(zhì)進(jìn)行求值運(yùn)算時(shí),原行列式可能會(huì)發(fā)生變化,但其值不變,將行列式的值作為評(píng)價(jià)標(biāo)準(zhǔn)indkey。

4)規(guī)模屬性AS

calla(Eq,Erq1)>calla(Eq,Erq2)

(3)

5)相同子表達(dá)式數(shù)量屬性AN

設(shè)Eq中包含若干子表達(dá)式{N1,N2,…,Ns3},其中,s3為Eq所包含的子表達(dá)式個(gè)數(shù),將Erqt中每個(gè)子表達(dá)式Nd(d=1,2,…,s3)出現(xiàn)的個(gè)數(shù)及其所占的比例作為一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)indnsu。

1.4 猶豫模糊隸屬度定義及參數(shù)設(shè)置

1.4.1 猶豫模糊隸屬度定義

定義4長(zhǎng)度標(biāo)準(zhǔn)indlen的隸屬度函數(shù)為:

findlen[Eq(i,j),Erqt(k,l)]=lb(1+indlen)

(4)

定義5層次標(biāo)準(zhǔn)indlev的隸屬度函數(shù)為:

findlev[Eq(i,j),Erqt(k,l)]=eη·indlev

(5)

其中,indlev為子式Eq(i,j)在Erqt(k,l)中所處的層次,η為層次屬性權(quán)重系數(shù)。

定義6位置標(biāo)準(zhǔn)indloc的隸屬度函數(shù)為:

(6)

其中,rmin=min(i,k)表示Eq(i,j)和Erqt(k,l)所處行號(hào)中較小值,rmax=max(i,k),表示Eq(i,j)和Erqt(k,l)所處行號(hào)中較大值,cmin=min(j,l),表示Eq(i,j)和Erqt(k,l)所處列號(hào)中較小值,cmax=max(j,l),表示Eq(i,j)和Erqt(k,l)所處列號(hào)中較大值。

定義7起始位標(biāo)準(zhǔn)indsta的隸屬度函數(shù)為:

findsta[Eq(i,j),Erqt(k,l)]=e-μindsta

(7)

其中,indsta為子式Eq(i,j)在Erqt(k,l)中所處的水平位置(規(guī)定初始位置為0),μ為起始位屬性權(quán)重系數(shù)。

定義8標(biāo)志位標(biāo)準(zhǔn)indfla的隸屬度函數(shù)如表2所示。本文將標(biāo)志位信息內(nèi)部做了特殊處理,為區(qū)分各行,規(guī)定每行第1個(gè)子式的主基線標(biāo)志位為6i,其中,i=1,2,…,表示行號(hào)。每行非第1個(gè)子式的主基線標(biāo)志位為0。

表2 標(biāo)志位g隸屬度值

定義9運(yùn)算數(shù)標(biāo)準(zhǔn)indopd的隸屬度函數(shù)為:

(8)

定義10運(yùn)算符標(biāo)準(zhǔn)indopr的隸屬度函數(shù)為:

(9)

定義11矩陣變換標(biāo)準(zhǔn)indjuz的隸屬度函數(shù)如表3所示。

表3 矩陣不同變換形式的隸屬度值

定義12行列式變換標(biāo)準(zhǔn)indhal的隸屬度函數(shù)為:

(10)

定義13行列式的值標(biāo)準(zhǔn)indkey的隸屬度函數(shù)為:

(11)

定義14規(guī)模標(biāo)準(zhǔn)indsiz的隸屬度函數(shù)為:

(12)

其中,Rmin=min(m,c)表示Eq和Erqt的行數(shù)中較小值,Rmax=max(m,c)表示Eq和Erqt的行數(shù)中較大值,Cmin=min(n,d)表示Eq和Erqt的列數(shù)中較小值,Cmax=max(n,d)表示Eq和Erqt的列數(shù)中較大值。

定義15相同子表達(dá)式個(gè)數(shù)標(biāo)準(zhǔn)indnsu的隸屬度函數(shù)為:

findnsu[Eq(i,j),Erqt(k,l)]=

(13)

其中,D=m×n表示Eq包含的子式總數(shù),cntq(i,j)表示Eq(i,j)與Erqt(k,l)完全相同的次數(shù),cntrqt(k,l)表示Erqt的子公式總數(shù)。

1.4.2 參數(shù)設(shè)定

隸屬度函數(shù)參數(shù)設(shè)定說(shuō)明如下。

層次屬性權(quán)重系數(shù)η:通過(guò)統(tǒng)計(jì)數(shù)據(jù)庫(kù)中6 352個(gè)表達(dá)式的節(jié)點(diǎn)總數(shù)、層次信息以及處于該層的節(jié)點(diǎn)個(gè)數(shù),并將處于某層的節(jié)點(diǎn)個(gè)數(shù)歸一化,利用polyfit函數(shù)借助MATLAB軟件繪制圖像,最終確定η值為-0.113。

起始位屬性權(quán)重系數(shù)μ:通過(guò)統(tǒng)計(jì)數(shù)據(jù)庫(kù)中6 352個(gè)表達(dá)式的長(zhǎng)度信息,找出最小長(zhǎng)度、中間長(zhǎng)度、最大長(zhǎng)度和分布中心長(zhǎng)度,統(tǒng)計(jì)在[LEN,LEN+10](LEN=最小長(zhǎng)度,或中間長(zhǎng)度,或最大長(zhǎng)度,或分布中心長(zhǎng)度)范圍內(nèi)的表達(dá)式個(gè)數(shù)并進(jìn)行歸一化處理,將這4類長(zhǎng)度與其加10后的長(zhǎng)度進(jìn)行取平均值處理,利用polyfit函數(shù)借助MATLAB軟件繪制圖像,最終確定μ值為0.56。

根據(jù)統(tǒng)計(jì)數(shù)據(jù)庫(kù)中不同g值所對(duì)應(yīng)的表達(dá)式個(gè)數(shù)占表達(dá)式總數(shù)的比例,以及不同標(biāo)志位所代表的典型運(yùn)算的常見程度,進(jìn)行g(shù)隸屬度的取值設(shè)定。

綜合考慮用戶的檢索需求及幾種不同矩陣的常見性,進(jìn)行矩陣不同變換形式的隸屬度取值設(shè)定。

1.5 猶豫模糊集及線性代數(shù)式相似度計(jì)算

文獻(xiàn)[19]提出模糊集概念,之后一些學(xué)者又對(duì)其進(jìn)行擴(kuò)展,相繼提出直覺模糊集、Type2型模糊集、模糊多重集等,但在處理決策問題時(shí)其模糊不確定性方面存在缺陷,特別是在專家對(duì)某對(duì)象的某個(gè)屬性進(jìn)行評(píng)價(jià)時(shí)出現(xiàn)猶豫的情況。對(duì)此文獻(xiàn)[20]提出猶豫模糊集的概念,用一個(gè)集合的形式給出某一對(duì)象屬于模糊集的程度,該方法不再需要專家對(duì)屬性值給定一個(gè)誤差范圍或幾個(gè)可能值的分布,就可以對(duì)決策中的不確定性進(jìn)行有效刻畫,為數(shù)學(xué)公式檢索結(jié)果排序提供理論支撐。此后,區(qū)間值猶豫模糊集[21]及其相應(yīng)的一些關(guān)聯(lián)度、距離及相似性測(cè)度、算子和相應(yīng)的決策方法相繼被提出[22]。

1.5.1 猶豫模糊集相關(guān)概念

定義16設(shè)X是一個(gè)非空集合,則稱式(14)為猶豫模糊集。

E={|x∈X}

(14)

其中,hE(x)稱為猶豫模糊元素,是元素x對(duì)于集合E的幾個(gè)可能隸屬度的集合,該元素值在[0,1]區(qū)間內(nèi)分布[20]。

定義17設(shè)P和Q分別為非空集合X={x1,x2,…,xn}中的2個(gè)猶豫模糊集合,則P和Q的廣義猶豫標(biāo)準(zhǔn)距離表示為:

(15)

定義18P和Q的相似度表示為:

s(P,Q)=1-dghn(P,Q)

(16)

1.5.2 線性代數(shù)式相似度計(jì)算

線性代數(shù)式相似度計(jì)算分為3步:局部特征相似度計(jì)算,整體特征相似度計(jì)算和公式相似度計(jì)算。各步驟具體內(nèi)容如下:

步驟1設(shè)Eq(i,j)和Erqt(k,l)分別對(duì)應(yīng)猶豫模糊集合Hfq(i,j)和Hfrqt(k,l),這2個(gè)集合所對(duì)應(yīng)的猶豫模糊元素為Pq(i,j)(Aa)和Prqt(k,l)(Aa),其中Aa表示局部評(píng)價(jià)屬性,且a=1,2,3。根據(jù)式(15)得到局部特征猶豫模糊集合的廣義猶豫標(biāo)準(zhǔn)距離,再根據(jù)式(16)得出2個(gè)猶豫模糊集合的相似度。

s(Hfq(i,j),Hfrqt(k,l))=1-dghn(Hfq(i,j),Hfrqt(k,l))=

(17)

設(shè)srqt表示最終局部相似度,若同一個(gè)Erqt(k,l)有多個(gè)相似度值,就取最大值作為其相似度值。對(duì)同一個(gè)Erqt的每一個(gè)子式的最大相似度求平均值,即為Erqt的最終局部相似度。

(18)

步驟2設(shè)Eq和Erqt的整體評(píng)價(jià)屬性分別對(duì)應(yīng)的猶豫模糊集合為Hfq和Hfrqt,這2個(gè)集合所對(duì)應(yīng)的猶豫模糊元素為Pqw(Aw)和Prqwt(Aw),其中,Aw表示整體評(píng)價(jià)屬性,且w=1,2,3,4,5。考慮到用戶的實(shí)際需求,每個(gè)整體評(píng)價(jià)標(biāo)準(zhǔn)對(duì)檢索結(jié)果相似度排序的影響程度不同,將式(15)適當(dāng)變形,得出2個(gè)猶豫模糊集的相似度為:

s(Hfq,Hfrqt)=1-dghn(Hfq,Hfrqt)=

(19)

其中,在考慮大量用戶檢索需求的基礎(chǔ)上,經(jīng)過(guò)統(tǒng)計(jì)不同整體屬性所代表的典型線性代數(shù)式與待查詢式的邏輯相似性,進(jìn)而進(jìn)行θi值的設(shè)定(對(duì)不同匹配模式的相似度評(píng)價(jià)沒有影響的整體屬性對(duì)應(yīng)的θi值設(shè)置為0)。例如:當(dāng)用戶檢索式為某一矩陣時(shí),用戶更想查詢出原矩陣及其轉(zhuǎn)置矩陣、增廣矩陣、逆矩陣等。基于此,每種匹配模式的整體評(píng)價(jià)屬性所對(duì)應(yīng)的θi值如表4所示。

表4 各類匹配模式整體屬性所對(duì)應(yīng)θi值

步驟3將上述2部分相似度取平均值,即得到2個(gè)公式的相似度。

(20)

2 線性代數(shù)式排序算法

不同匹配模式的排序算法,其原理大致相同,算法步驟如下:

輸入LaTeX形式的線性代數(shù)查詢式

輸出LaTeX形式的線性代數(shù)結(jié)果式排序結(jié)果

1)初始化數(shù)據(jù)表LaForm、SubForm、Whole、NodeInf、OpInf、Rt_end。

2)將待查詢式子式的subid、文件名subnam和字符串substr存入表SubForm中,對(duì)其進(jìn)行解析,將特征存入表NodeInf、OpInf。

3)i=i+1,若i>待查詢線性代數(shù)式的子式總數(shù),執(zhí)行步驟5),否則執(zhí)行步驟4)。

4)查詢數(shù)據(jù)庫(kù)中SubForm表,若數(shù)據(jù)庫(kù)中表達(dá)式子式的字符串含有該查詢式的子式,則對(duì)其進(jìn)行解析,存入表NodeInf、OpInf、Whole,計(jì)算局部相似度,存入表NodeInf;否則,算法結(jié)束。

5)將待查詢式的Eqid、文件名Eqfnam和字符串Eqstr存入表LaForm,對(duì)其進(jìn)行解析,將特征存入表NodeInf、OpInf、Whole。

6)j=j+1,若j>數(shù)據(jù)庫(kù)中表達(dá)式總數(shù),執(zhí)行步驟8);否則,執(zhí)行步驟7)。

7)查詢數(shù)據(jù)庫(kù)中NodeInf表,并根據(jù)Formid在表達(dá)式表FORMULA中找到對(duì)應(yīng)表達(dá)式,對(duì)其進(jìn)行解析,并將特征存入表LaForm、SubForm、NodeInf、OpInf,計(jì)算整體屬性相似度,存入表Whole。

8)計(jì)算線性代數(shù)式的相似度并將最終結(jié)果寫入表Result_end,并把該表按s_end降序返回給用戶。

假設(shè)待查詢線性代數(shù)式的子公式總數(shù)為m1,數(shù)據(jù)庫(kù)中線性代數(shù)公式的總數(shù)為n,則數(shù)據(jù)庫(kù)中線性代數(shù)公式的子公式總數(shù)為m2×n,其中m2為數(shù)據(jù)庫(kù)中線性代數(shù)公式子公式個(gè)數(shù)的平均值。根據(jù)實(shí)驗(yàn)數(shù)據(jù)可知:1≤m1<

表5 檢索結(jié)果所對(duì)應(yīng)猶豫模糊集合

表6 結(jié)果表達(dá)式相似度計(jì)算結(jié)果

3 實(shí)驗(yàn)結(jié)果與分析

采用C#進(jìn)行編程,結(jié)合SQL2013,應(yīng)用猶豫模糊集理論進(jìn)行線性代數(shù)式檢索及結(jié)果排序。由于目前國(guó)內(nèi)外對(duì)此方面的研究并不多,相關(guān)數(shù)據(jù)集較少,因此本文選取線性代數(shù)課本和網(wǎng)絡(luò)上相關(guān)文獻(xiàn)的電子文檔,從中提取MathType格式的線性代數(shù)表達(dá)式并轉(zhuǎn)換成LaTeX形式,再通過(guò)解析程序?qū)⑵浯鎯?chǔ)于數(shù)據(jù)庫(kù)中,最終共得到6 352條用于實(shí)驗(yàn)的線性代數(shù)式數(shù)據(jù)集。因?yàn)楸疚南到y(tǒng)主要針對(duì)線性代數(shù)式,所以選擇與數(shù)學(xué)檢索系統(tǒng)SearchOnMath(http://searchonmath.com/,一個(gè)直接查詢數(shù)學(xué)內(nèi)容的搜索引擎,查詢結(jié)果包含給定數(shù)學(xué)公式的網(wǎng)頁(yè),并給出其不同的相似性)進(jìn)行對(duì)比,并引入斯皮爾曼秩次相關(guān)系數(shù)概念用以檢驗(yàn)檢索結(jié)果的合理性,斯皮爾曼秩次相關(guān)系數(shù)定義如下:

定義19斯皮爾曼秩次相關(guān)系數(shù)[24]是反映2組變量之間聯(lián)系密切程度的統(tǒng)計(jì)分析指標(biāo),適用于2組無(wú)序數(shù)列相關(guān)性大小的計(jì)算,其值越大,表示相關(guān)性越高。斯皮爾曼秩次相關(guān)系數(shù)計(jì)算公式為:

(21)

其中,di表示2組無(wú)序序列按遞增或遞減排序后,每個(gè)數(shù)列元素位置變化的差值,n表示2個(gè)序列的長(zhǎng)度。

表7 待查詢線性代數(shù)式

表8 排序結(jié)果對(duì)比

讓一組專家對(duì)表7中每個(gè)查詢表達(dá)式的檢索結(jié)果集合進(jìn)行人工排序,將該排序結(jié)果作為評(píng)價(jià)標(biāo)準(zhǔn),利用斯皮爾曼秩次相關(guān)系數(shù),分別計(jì)算本文方法和SearchOnMath方法的排序結(jié)果與人工排序結(jié)果的相關(guān)性,得到如圖7所示的相關(guān)性比較結(jié)果,其中,斯皮爾曼秩次相關(guān)系數(shù)越高,說(shuō)明排序結(jié)果越符合用戶需求。

圖7 2種方法與人工排序結(jié)果的相關(guān)性比較

由圖7可以看出,本文方法的排序結(jié)果與人工排序結(jié)果更接近,因此,本文方法更能滿足用戶的查詢需求。

4 結(jié)束語(yǔ)

針對(duì)線性代數(shù)式的檢索及結(jié)果排序,本文從多角度分析并歸納線性代數(shù)式的特征,利用猶豫模糊集的相關(guān)理論建立相應(yīng)的隸屬度函數(shù),對(duì)抽象的公式特征進(jìn)行數(shù)量化,從而實(shí)現(xiàn)線性代數(shù)式的相似度評(píng)價(jià),完成線性代數(shù)式檢索結(jié)果的合理排序。對(duì)比實(shí)驗(yàn)驗(yàn)證了該方法在線性代數(shù)式相似度評(píng)價(jià)上的合理性和有效性。但本文實(shí)驗(yàn)在線性代數(shù)式的特征選取上還不夠全面,評(píng)價(jià)函數(shù)涉及的參數(shù)選擇還需優(yōu)化,下一步將對(duì)此進(jìn)行研究。

[1] MINER R,MUNAVALLI R.An approach to mathematical search through query formulation and data normaliza-tion[C]//Proceedings of the 14th Symposium on Towards Mechanized Mathematical Assistants.Berlin,Germany:Springer,2007:342-355.

[2] 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.

[3] LIBBRECHT P,MELIS E.Semantic search in leactive-math[EB/OL].[2017-09-05].http://www.hoplahup.net/copy_left/Libbrecht-etal-Semant ic-Search-WebALT-06.pdf.

[4] LIBBRECHT P,MELIS E.Methods to access and retrieve mathematical content in active math[C]//Proceedings of 2006 Mathematical Software-ICMS.Berlin,Germany:Springer,2006:331-342.

[5] MISUTKA J,GALAMBOS L.Mathematical extension of full text search engine indexer[C]//Proceedings of the 3rd International Conference on Information and Communication Technologies.Washington D.C.,USA:IEEE Press,2008:1-6.

[7] MISUTKA J,GALAMBOS L.System description:EgoMath2 as a tool for mathematical searching on Wikipedia.org[C]//Proceedings of the 18th Calculemus and 10th International Conference on Intelligent Computer Mathematics.Berlin,Germany:Springer,2011:307-309.

[8] KOHLHASE M,SUCAN I.A search engine for mathematical formulae[C]//Proceedings of the 8th International Conference on Artificial Intelligence and Symbolic Computation.Berlin,Germany:Springer,2006:241-253.

[9] KOHLHASE M,ANCA S,JUCOVSCHI C,et al.MathWebSearch 0.4,a semantic search engine for mathematics[EB/OL].[2017-09-15].https://www.researchgate.net/publication/216797208_MathWebSearch_04_A_Semantic_Search_Engine_for_Mathematics.

[10] HU X,GAO L C,LIN X Y,et al.WikiMirs:a mathe-matical information retrieval system for Wikipedia[C]//Proceedings of the 13th ACM/IEEE-CS Joint Conference on Digital Libraries.New York,USA:ACM Press,2013:11-20.

[11] 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 and Development in Information Retrieval.New York,USA:ACM Press,2014:697-706.

[12] SCHELLENBERG T,YUAN B,ZANIBBI R.Layout-based substitution tree indexing and retrieval for mathematical expressions[J].Document Recognition and Retrieval XIX,2012,8297(2):263-271.

[13] KAMALI S,TOMPA F W.Structural similarity search for mathematics retrieval[C]//Proceedings of 2013 Inter-national Conference on Intelligent Computer Mathematics.Berlin,Germany:Springer,2013:246-262.

[14] ZHANG Q,YOUSSEF A.An approach to math-similarity search[C]//Proceedings of 2014 International Conference on Intelligent Computer Mathematics.Berlin,Germany:Springer,2014:404-418.

[15] 田學(xué)東,張凱歌,周 南,等.一種數(shù)學(xué)表達(dá)式檢索結(jié)果相關(guān)排序算法[J].計(jì)算機(jī)工程,2017,43(3):204-212.

[16] NGUYEN T T,CHANG K,HUI S C.A math-aware search engine for math question answering system[C]//Proceedings of the 21st ACM International Conference on Information and knowledge Management.New York,USA:ACM Press,2012:724-733.

[17] NGUYEN T T,HUI S C,CHANG K.A lattice-based approach for mathematical search using formal concept analysis[J].Expert Systems with Applications,2012,39(5):5820-5828.

[18] 馬惠娟.數(shù)學(xué)搜索中索引模型研究[D].蘭州:蘭州大學(xué),2013.

[19] ZADEH L A.Fuzzy sets[J].Information and Control,1965,8(3):338-353.

[20] TORRA V.Hesitant fuzzy sets[J].International Journal of Intelligent Systems,2010,25(6):529-539.

[21] 陳樹偉,蔡麗娜.區(qū)間值猶豫模糊集[J].模糊系統(tǒng)與數(shù)學(xué),2013,27(6):38-44.

[22] 蔡麗娜.區(qū)間值猶豫模糊集及其在決策中的應(yīng)用研究[D].鄭州:鄭州大學(xué),2013.

[23] XU Z S,XIA M M.Distant and similarity measures for hesitant fuzzy sets[J].Information Sciences,2011,181(11):2128-2138.

[24] KENDALL M,GIBBONS J D.Rank correlation methods[M].New York,USA:Oxford University Press,1990.