一種laex格式數(shù)學(xué)公式匹配算法

一種laex格式數(shù)學(xué)公式匹配算法

1基于二叉樹(shù)的數(shù)學(xué)公式匹配檢測(cè)為了保護(hù)知識(shí)產(chǎn)權(quán)，防止學(xué)術(shù)交流被剽竊，重新期刊檢驗(yàn)技術(shù)已成為研究領(lǐng)域的熱點(diǎn)，并取得了一些研究成果。針對(duì)英文學(xué)術(shù)論文的檢測(cè)主要有數(shù)字指紋法和詞頻統(tǒng)計(jì)方法,針對(duì)中文學(xué)術(shù)論文的檢測(cè)主要有篇章結(jié)構(gòu)相似度法、段落結(jié)構(gòu)相似度法和句子相似度法,但這些方法都只適用于純文本內(nèi)容的檢測(cè)。目前,對(duì)數(shù)學(xué)公式的識(shí)別已取得了一些研究成果,但對(duì)數(shù)學(xué)公式的抄襲檢測(cè)尚處于探索階段。一篇學(xué)術(shù)論文,尤其是自然科學(xué)學(xué)術(shù)論文,其思想、觀點(diǎn)或創(chuàng)意等核心內(nèi)容往往主要體現(xiàn)在公式中,因此,在學(xué)術(shù)論文抄襲檢測(cè)中,對(duì)數(shù)學(xué)公式的匹配檢測(cè)具有十分重要的意義。LATEX軟件被廣泛地用于制作科技論文、書(shū)籍、檔案、學(xué)位論文、手稿、私人信件以及各種復(fù)雜的符號(hào)公式等。另外,其他格式的文檔可轉(zhuǎn)化為L(zhǎng)aTeX格式,為此,本文提出了一種基于二叉樹(shù)結(jié)構(gòu)的LaTeX格式數(shù)學(xué)公式匹配算法。首先在LaTeX格式文檔中提取用字符串表示的數(shù)學(xué)公式,通過(guò)詞法和結(jié)構(gòu)分析,生成其二叉樹(shù)表示,并對(duì)二叉樹(shù)的樹(shù)形結(jié)構(gòu)作歸一化處理,然后先序遍歷二叉樹(shù),得到公式元素的先序遍歷序列,并對(duì)變量名作歸一化處理,最后根據(jù)序列中對(duì)應(yīng)位相同的公式元素?cái)?shù)計(jì)算兩個(gè)公式的相似度。本文第2節(jié)介紹了由數(shù)學(xué)公式的LaTeX格式生成其二叉樹(shù)表示的方法;第3節(jié)詳細(xì)闡述了基于二叉樹(shù)的數(shù)學(xué)公式匹配算法;第4節(jié)給出了對(duì)數(shù)學(xué)公式進(jìn)行不同修改的實(shí)驗(yàn)結(jié)果;最后得出結(jié)論。2數(shù)學(xué)公式的交叉樹(shù)代表2.1以“k”運(yùn)算符生成二叉樹(shù)表示在LaTeX文檔中,根據(jù)標(biāo)記提取用字符串形式表示的數(shù)學(xué)公式。由于LaTeX格式的數(shù)學(xué)公式具有較強(qiáng)的結(jié)構(gòu)特征,因此,可將一個(gè)復(fù)雜的數(shù)學(xué)公式分解為多個(gè)子式,再將每個(gè)子式分解成多個(gè)更小的子式,如此反復(fù),直到不能分解為止。分解后得到的最小子式稱為公式元素。對(duì)于三目運(yùn)算符,如求和運(yùn)算“∑”,它與上、下、右都有聯(lián)系,通過(guò)增加一個(gè)“l(fā)ink”運(yùn)算符,將其與右面的子式結(jié)合起來(lái)。從左向右遍歷增加了“l(fā)ink”運(yùn)算符后的字符串,生成了公式元素的優(yōu)先級(jí)列表。依據(jù)結(jié)構(gòu)特征和優(yōu)先級(jí)列表可生成數(shù)學(xué)公式的二叉樹(shù)表示。二叉樹(shù)中結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如表1所列。由數(shù)學(xué)公式的公式元素串表示生成其二叉樹(shù)表示的方法是:先建立根結(jié)點(diǎn),根結(jié)點(diǎn)的公式元素是公式元素串中優(yōu)先級(jí)最低的公式元素,由于公式串中位于根結(jié)點(diǎn)公式元素之前的公式元素在根結(jié)點(diǎn)的左子樹(shù),位于根結(jié)點(diǎn)公式元素之后的公式元素在根結(jié)點(diǎn)的右子樹(shù),因此遞歸建立根結(jié)點(diǎn)的左右子樹(shù)。每個(gè)結(jié)點(diǎn)的公式元素類別和結(jié)合方式根據(jù)公式元素確定。每個(gè)結(jié)點(diǎn)的高度根據(jù)式(1)計(jì)算。每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)碼在對(duì)樹(shù)形結(jié)構(gòu)作歸一化處理后生成。H=Hr>Hl?Hr:Hl+1(1)式中,Hl是左子樹(shù)高度,Hr是右子樹(shù)高度。例如,數(shù)學(xué)公式(∑i=110ai+x×y×z)×(x×y+y×z)(∑i=110ai+x×y×z)×(x×y+y×z)的LaTeX格式為“(\sum_{i=1}∧{10}a∧i+x imesy imesz) imes(x imesy+y imesz)”,其對(duì)應(yīng)二叉樹(shù)表示如圖1所示。2.2尾類整合式及其歸一化由于一些運(yùn)算符的操作數(shù)具有可交換屬性,即交換前后數(shù)學(xué)公式的含義不變,但它們對(duì)應(yīng)的二叉樹(shù)樹(shù)形結(jié)構(gòu)可能不同,因此,必須對(duì)二叉樹(shù)樹(shù)形結(jié)構(gòu)作歸一化處理。樹(shù)形結(jié)構(gòu)歸一化處理的方法是先序遍歷二叉樹(shù),若當(dāng)前結(jié)點(diǎn)公式元素類別為OPS且其左子樹(shù)的高度大于右子樹(shù)的高度,則交換其左右子樹(shù)。例如,對(duì)圖1作歸一化處理后的二叉樹(shù)如圖2所示。對(duì)樹(shù)形結(jié)構(gòu)作歸一化處理后,通過(guò)后序遍歷二叉樹(shù)生成各結(jié)點(diǎn)的結(jié)構(gòu)碼。其中,葉子結(jié)點(diǎn)的結(jié)構(gòu)碼為1,非葉子結(jié)點(diǎn)的結(jié)構(gòu)碼為“左子樹(shù)根結(jié)點(diǎn)結(jié)構(gòu)碼”+“結(jié)點(diǎn)高度”+“右子樹(shù)根結(jié)點(diǎn)結(jié)構(gòu)碼”。另外,數(shù)學(xué)公式中的變量名與公式含義無(wú)關(guān)。對(duì)于一個(gè)樹(shù)形確定的二叉樹(shù),為使按給定的遍歷方式遍歷后得到的公式元素序列唯一,必須對(duì)序列中的變量名作歸一化處理。對(duì)變量名作歸一化處理的方法是按從左到右的順序,用固定的變量名序列依次替換遍歷序列中公式元素類別為VAR的公式元素。3t1、s1,s1e結(jié)構(gòu)碼的相似度設(shè)E1和E2是兩個(gè)LaTeX格式的數(shù)學(xué)公式,其中,E1是源公式,E2是目標(biāo)公式,其具體匹配算法描述如下:步驟1生成E1的二叉樹(shù)表示并對(duì)樹(shù)形結(jié)構(gòu)作歸一化處理,得二叉樹(shù)T1。先序遍歷二叉樹(shù)T1,得公式元素序列,對(duì)序列中的變量名作歸一化處理,得歸一化后的公式元素序列L1;步驟2生成E2的二叉樹(shù)表示并對(duì)樹(shù)形結(jié)構(gòu)作歸一化處理,得二叉樹(shù)T2。先序遍歷二叉樹(shù)T2,得公式元素序列,對(duì)序列中的變量名作歸一化處理,得歸一化的公式元素序列L2,若T1和T2根結(jié)點(diǎn)的結(jié)構(gòu)碼不相同,則根據(jù)式(2)計(jì)算E1和E2的相似度,轉(zhuǎn)步驟5,否則轉(zhuǎn)步驟3;sim(E1,E2)=sim(L1,L2)=2*matnum(L1,L2)strlen(L1)+strlen(L2)(2)sim(E1,E2)=sim(L1,L2)=2*matnum(L1,L2)strlen(L1)+strlen(L2)(2)式中,matnum(s,t)為公式元素序列s和t中對(duì)應(yīng)位相同的公式元素個(gè)數(shù),strlen(s)為公式元素序列s中的公式元素個(gè)數(shù);步驟3若T2中不存在公式元素類別為OPS且左、右子樹(shù)高度相同的結(jié)點(diǎn),則根據(jù)式(2)計(jì)算E1和E2的相似度,轉(zhuǎn)步驟5,否則轉(zhuǎn)步驟4;步驟4對(duì)T2中公式元素類別為OPS且左、右子樹(shù)高度相同的結(jié)點(diǎn)(設(shè)有n個(gè)),交換這類結(jié)點(diǎn)的左右子樹(shù),可得到2n-1棵樹(shù)形結(jié)構(gòu)與T2相同的二叉樹(shù)序列T1221,T2222,…,T2n?1222n-1,分別先序遍歷這2n-1棵二叉樹(shù),得到相應(yīng)的公式元素序列,分別對(duì)每個(gè)公式元素序列中的變量名作歸一化處理,得到2n-1個(gè)歸一化后的公式元素序列L1221,L2222,…,L2n?1222n-1,先根據(jù)式(2)計(jì)算L1與Li22i(i=1,2,…,2n-1)的相似度,再根據(jù)式(3)計(jì)算E1和E2的相似度,轉(zhuǎn)步驟5;sim(E1,E2)=max(sim(L1,L2),sim(L1,L1221),sim(L1,L2222,…,sim(L1,L2n?1222n-1))(3)步驟5結(jié)束。4所列變量所列數(shù)學(xué)公式抄襲的手段主要有原樣復(fù)制、修改變量名稱和交換可交換運(yùn)算符兩邊子式的位置等。為了驗(yàn)證算法的性能,本文實(shí)驗(yàn)從已公開(kāi)發(fā)表的學(xué)術(shù)論文中選取50個(gè)含義和結(jié)構(gòu)互不同的數(shù)學(xué)公式進(jìn)行測(cè)試。根據(jù)抄襲手段的不同,人工對(duì)這些公式進(jìn)行修改,具體的修改方式如表2所列。實(shí)驗(yàn)中,按表2的修改方式修改每個(gè)公式,并分別計(jì)算源公式與修改后的目標(biāo)公式的相似度,每一種修改方式的平均相似度如表3所列。從實(shí)驗(yàn)結(jié)果可以看出,未作修改的公式、修改變量名稱的公式以及交換可交換運(yùn)算符兩邊子表達(dá)式的公式,其相似度都為100%,這是因?yàn)閷?duì)源公式和目標(biāo)公式的樹(shù)形結(jié)構(gòu)作歸一化處理后,源公式和目標(biāo)公式的樹(shù)形結(jié)構(gòu)相同,雖然與源公式樹(shù)形結(jié)構(gòu)形同的目標(biāo)公式二叉樹(shù)可能有多種,但在對(duì)所有的先序遍歷序列中變量名稱作歸一化處理后,目標(biāo)公式的遍歷序列中至少存在一個(gè)與源公式遍歷序列完全相同的遍歷序列,使修改后的目標(biāo)公式恢復(fù)原形。修改常量值時(shí)的相似度較低,這是因?yàn)樾薷墓街械某Ａ亢?公式的含義在一定程度上與源表達(dá)式不同,即源表達(dá)式和目標(biāo)表達(dá)式是兩個(gè)不完全相同的表達(dá)式。例如,∑i=110i2∑i=110i2和∑i=1020i3∑i=1020i3是兩個(gè)含義不相同的數(shù)學(xué)表達(dá)式。另外,算法中用結(jié)構(gòu)碼標(biāo)識(shí)樹(shù)形結(jié)構(gòu),并且字符串匹配過(guò)程是以公式元素為單位,匹配速度較快。結(jié)束語(yǔ)基于