秦玉平 ，唐亞偉 ，倫淑嫻 ，王秀坤

1.渤海大學(xué) 工學(xué)院，遼寧 錦州 121000

2.渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院，遼寧 錦州 121000

3.渤海大學(xué) 新能源學(xué)院，遼寧 錦州 121000

4.大連理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧 大連 116024

1 引言

為保護(hù)知識產(chǎn)權(quán)，防止學(xué)術(shù)論文抄襲，論文查重檢測技術(shù)已成為信息檢索領(lǐng)域的一個研究熱點(diǎn)[1-2]，并取得了一些研究成果。如數(shù)字指紋法[3-4]、詞頻統(tǒng)計法[5-6]，篇章結(jié)構(gòu)相似度法[7]、段落相似度法[8]、句子相似度法[9]和局部詞頻指紋法[10]等。但這些方法都針對純文本內(nèi)容的檢測，對數(shù)學(xué)公式的抄襲檢測尚處于探索階段[11-13]，現(xiàn)有的抄襲檢測系統(tǒng)都不能對數(shù)學(xué)公式進(jìn)行檢測。但一篇學(xué)術(shù)論文，尤其是自然科學(xué)學(xué)術(shù)論文，其思想、觀點(diǎn)或創(chuàng)意等核心內(nèi)容往往體現(xiàn)在公式中，因此，對數(shù)學(xué)公式的抄襲檢測的研究具有十分重要的意義。

LaTeX軟件已被廣泛地用于制作科技論文、書籍、檔案、學(xué)位論文、手稿、私人信件以及各種復(fù)雜的符號公式等。另外，其他格式的文檔可轉(zhuǎn)化為LaTeX格式[14]。為此，本文提出了一種基于二叉樹結(jié)構(gòu)的LaTeX格式數(shù)學(xué)公式檢測算法，實(shí)現(xiàn)了對數(shù)學(xué)公式的抄襲檢測，并通過實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性。

2 數(shù)學(xué)公式的二叉樹表示

2.1 二叉樹構(gòu)造

在LaTeX文檔中，根據(jù)標(biāo)記提取用字符串形式表示的數(shù)學(xué)公式。由于LaTeX格式的數(shù)學(xué)公式具有較強(qiáng)的結(jié)構(gòu)特征，因此，可將一個復(fù)雜的數(shù)學(xué)公式分解為多個子式，再將每個子式分解成多個更小的子式[15]，如此反復(fù)，直到不能分解為止。分解后得到的最小子式稱為公式元素。

對于三目運(yùn)算符，如求和運(yùn)算“∑”，它與上、下、右都有聯(lián)系，通過增加一個“l(fā)ink”運(yùn)算符，將其與右面的子式結(jié)合起來。

從左向右遍歷增加了“l(fā)ink”運(yùn)算符后的字符串，生成公式元素的優(yōu)先級列表。依據(jù)結(jié)構(gòu)特征和優(yōu)先級列表可生成數(shù)學(xué)公式的二叉樹表示。二叉樹中結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如表1所示。

表1 二叉樹結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

由數(shù)學(xué)公式的公式元素串表示生成其二叉樹表示的方法是先建立根結(jié)點(diǎn)，根結(jié)點(diǎn)的公式元素是公式元素串中優(yōu)先級最低的公式元素，由于公式元素串中位于根結(jié)點(diǎn)公式元素之前的公式元素在根結(jié)點(diǎn)的左子樹，位于根結(jié)點(diǎn)公式元素之后的公式元素在根結(jié)點(diǎn)的右子樹，遞歸建立根結(jié)點(diǎn)的左右子樹。

每個結(jié)點(diǎn)的公式元素類別和結(jié)合方式根據(jù)公式元素確定。每個結(jié)點(diǎn)的高度根據(jù)公式（1）計算。每個結(jié)點(diǎn)的結(jié)構(gòu)碼在對樹形結(jié)構(gòu)作歸一化處理后生成。

其中，H(node)是結(jié)點(diǎn)node的高度，Hl是結(jié)點(diǎn)node左子樹的高度，Hr是結(jié)點(diǎn)node右子樹的高度。

圖1 數(shù)學(xué)公式的二叉樹表示

2.2 歸一化處理

由于一些運(yùn)算符的操作數(shù)具有可交換屬性，即交換前后數(shù)學(xué)公式的含義不變，但它們對應(yīng)的二叉樹樹形結(jié)構(gòu)可能不同，因此，必須對二叉樹樹形結(jié)構(gòu)作歸一化處理。樹形結(jié)構(gòu)歸一化處理的方法是先序遍歷二叉樹，若當(dāng)前結(jié)點(diǎn)公式元素類別為OPS且其左子樹的高度大于右子樹的高度，則交換其左右子樹。例如，對圖1作歸一化處理后的二叉樹如圖2所示。

圖2 樹形結(jié)構(gòu)歸一化后的二叉樹

對樹形結(jié)構(gòu)作歸一化后處理后，后序遍歷二叉樹，根據(jù)式（2）生成各結(jié)點(diǎn)的結(jié)構(gòu)碼，最終得到根結(jié)點(diǎn)的結(jié)構(gòu)碼，即二叉樹的結(jié)構(gòu)碼。

其中，C(node)是結(jié)點(diǎn)node的結(jié)構(gòu)碼，Cl是結(jié)點(diǎn)node左子樹根結(jié)點(diǎn)的結(jié)構(gòu)碼，Cr是結(jié)點(diǎn)node右子樹根結(jié)點(diǎn)的結(jié)構(gòu)碼。

另外，數(shù)學(xué)公式中的變量名與公式含義無關(guān)。對于一個樹形結(jié)構(gòu)確定的二叉樹，為使按給定的遍歷方式遍歷后得到的公式元素序列唯一，必須對序列中的變量名作歸一化處理。對變量名作歸一化處理的方法是按從左到右的順序，用固定的變量名序列依次替換遍歷序列中公式元素類別為VAR的公式元素。

3 公式檢測數(shù)據(jù)庫設(shè)計

公式檢測數(shù)據(jù)庫包含論文信息表和數(shù)學(xué)公式信息表兩種表。論文信息表的結(jié)構(gòu)見表2，數(shù)學(xué)公式信息表結(jié)構(gòu)見表3。數(shù)學(xué)公式信息表以結(jié)構(gòu)碼命名，即結(jié)構(gòu)碼相同的數(shù)學(xué)公式信息存儲在同一個表中。

表2 論文信息表結(jié)構(gòu)

表3 數(shù)學(xué)公式信息表結(jié)構(gòu)

4 數(shù)學(xué)公式檢測算法

步驟1對于待檢測文檔，提取所有數(shù)學(xué)公式，得到數(shù)學(xué)公式集Formula={f1，f2，…，fn}。

步驟2若數(shù)學(xué)公式集Formula非空，則從Formula中取出一個數(shù)學(xué)公式fi，生成fi的二叉樹表示并對二叉樹結(jié)構(gòu)作歸一化處理，得到fi的二叉樹表示Ti及其結(jié)構(gòu)碼fcode，轉(zhuǎn)步驟3；否則，轉(zhuǎn)步驟7。

步驟3查找文件名為fcode的數(shù)據(jù)表，若該文件存在，轉(zhuǎn)步驟4；否則，轉(zhuǎn)步驟2。

步驟4在數(shù)據(jù)表fcode中，查找與二叉樹Ti根結(jié)點(diǎn)的公式元素相等的記錄，若存在，轉(zhuǎn)步驟5；否則，轉(zhuǎn)步驟2。

步驟5對二叉樹Ti中的公式元素類別為OPS且左、右子樹高度相同的結(jié)點(diǎn)（設(shè)有k個），交換這類結(jié)點(diǎn)的左右子樹，得到2k-1棵樹形結(jié)構(gòu)與Ti相同的二叉樹，分別先序遍歷這2k棵二叉樹，得到相應(yīng)二叉樹的公式元素遍歷序列，對序列中的變量名作歸一化處理，公式元素序列相同的只保留一個，得到公式元素序列集L={L1，L2，…，Lm}，轉(zhuǎn)步驟6。

步驟6在數(shù)據(jù)表fcode中，查找與L中的公式元素序列相同的記錄，若存在，輸出數(shù)學(xué)公式fi所在的論文名和發(fā)表信息，轉(zhuǎn)步驟2。

步驟7檢測結(jié)束。

5 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證算法的性能，從258篇公開發(fā)表的學(xué)術(shù)論文中選取1 000個含義和結(jié)構(gòu)互不相同的數(shù)學(xué)公式，預(yù)處理后存入公式檢測數(shù)據(jù)庫。

實(shí)驗(yàn)環(huán)境為CPU Pentium 2.0 GHz，內(nèi)存2 GB，操作系統(tǒng)Windows XP SP3，數(shù)據(jù)庫ACCESS 2007。

實(shí)驗(yàn)中采用準(zhǔn)確率P、召回率R和F1值作為評價標(biāo)準(zhǔn)。

其中，A是檢測結(jié)果中語義相同且實(shí)際相同的表達(dá)式數(shù)，B是檢測結(jié)果中未出現(xiàn)但實(shí)際語義相同的表達(dá)式數(shù)，C是檢測結(jié)果中語義相同但實(shí)際不相同的表達(dá)式數(shù)。

數(shù)學(xué)公式抄襲的手段主要有原樣復(fù)制，修改變量名稱和交換可交換運(yùn)算符兩邊子式的位置等。根據(jù)抄襲手段的不同，對公式檢測數(shù)據(jù)庫中的公式人工修改后進(jìn)行檢測，具體的修改方式如表4所示。

表4 修改方式的種類

實(shí)驗(yàn)中，根據(jù)數(shù)學(xué)公式抄襲的手段，對選取的258篇論文中的數(shù)學(xué)公式按表4中的修改方式作相應(yīng)的修改后，分別對這些論文進(jìn)行檢測。共進(jìn)行2 000次數(shù)學(xué)公式檢測，檢測的準(zhǔn)確率和召回率都為100%，檢測檢測時間為421 ms。

從實(shí)驗(yàn)結(jié)果可以看出，該算法對公式未作修改，修改其變量名稱及交換其可交換運(yùn)算符兩邊子表達(dá)式的情況都實(shí)現(xiàn)了精準(zhǔn)檢測。其原因是對源公式和目標(biāo)公式的樹形結(jié)構(gòu)作歸一化處理后，源公式和目標(biāo)公式的樹形結(jié)構(gòu)相同，雖然與源公式樹形結(jié)構(gòu)形同的目標(biāo)公式二叉樹可能有多種，但在對所有的先序遍歷序列的變量名稱作歸一化處理后，目標(biāo)公式的遍歷序列中至少存在一個與源公式遍歷序列完全相同的遍歷序列，使修改后的目標(biāo)公式恢復(fù)原形。該算法檢測速度比較快。數(shù)學(xué)公式的檢測過程包括數(shù)學(xué)公式提取、轉(zhuǎn)換和查找。由于LaTeX格式文檔中的數(shù)學(xué)公式有開始和結(jié)束標(biāo)記，所以根據(jù)標(biāo)記能快速識別并提取數(shù)學(xué)公式。由LaTeX格式表示的數(shù)學(xué)公式轉(zhuǎn)換成其對應(yīng)二叉樹表示時，其主要操作是遍歷公式元素串。遍歷串長為n的公式元素串的時間復(fù)雜度為nlbn。由于公式元素串的串長較小且操作簡單，所以用時較少。查找時，先檢查與結(jié)構(gòu)碼同名的數(shù)據(jù)表是否存在，若不存在，檢測結(jié)束，否則，先在數(shù)據(jù)表中查找與根結(jié)點(diǎn)公式元素相等的記錄，若有滿足條件的記錄，再在滿足條件的記錄中查找與變量名歸一化后的先序遍歷公式元素序列相等的記錄。

6 結(jié)束語

基于數(shù)學(xué)公式的二叉樹表示，提出了一種LaTeX格式的數(shù)學(xué)公式檢測算法。本文方法對未作修改的公式檢測，對修改變量名稱的公式檢測和對交換可交換運(yùn)算符兩邊子表達(dá)式的公式的檢測都十分精確，且具有較高的檢測速度，有效地解決了論文抄襲檢測中數(shù)學(xué)公式檢測問題，彌補(bǔ)了現(xiàn)有的檢測系統(tǒng)中不能對數(shù)學(xué)公式進(jìn)行檢測的缺陷。

[1]史彥軍，滕弘飛，金博，等.抄襲論文識別研究與進(jìn)展[J].大連理工大學(xué)學(xué)報，2005，45（1）：50-57.

[2]Song Q B，Shen J Y.On illegal Coping and Distrib uting Detection Mechanism for Digital Goods[J].Journal of Computer Research and Development，2001，38（1）：121-125.

[3]Hoad T，Zobel J.Methods for identifying versioned and plagiarism documents[J].Journal of the American Society for Information Science and Technology，2002，54（3）：203-215.

[4]Chowdhury A，F(xiàn)rieder O.Collection Statistics for Fast Duplicate Document Detection[J].ACM Transactions on Information System，2002，20（2）：171-191.

[5]Zobel J，Moffat A.Exploring the similarity space[J].ACM SIGIR Forum，1998，32（1）：18-34.

[6]Antonio S，Leong H V.A document plagiarism detection system[C]//Proceedingsofthe1997 ACM Symposium for Applied Computing.San Jose：ACM Press，1997：70-77.

[7]金博，史彥軍.基于篇章結(jié)構(gòu)相似度的復(fù)制檢測算法[J].大連理工大學(xué)學(xué)報，2007，47（1）：125-130.

[8]趙俊杰，胡學(xué)鋼.一種基于段落詞頻統(tǒng)計的論文抄襲判定算法[J]，計算機(jī)技術(shù)與發(fā)展，2009，19（4）：231-233.

[9]秦新國.基于句子相似度的文檔復(fù)制檢測算法研究[J].現(xiàn)代圖書情報技術(shù)，2007（11）：63-66.

[10]秦玉平，冷強(qiáng)奎，王秀坤，等.基于局部詞頻指紋的論文抄襲檢測算法[J].計算機(jī)工程，2011，37（6）：193-194.

[11]Lee H，Wang J.Design of a mathematical expression recognition system[J].Pattern Recogniton Letters，1997，18（8）：289-298.

[12]陳國俊，唐勇智.基于基準(zhǔn)線的多候選數(shù)學(xué)公式識別[J].計算機(jī)工程與應(yīng)用，2013，49（1）：206-209.

[13]陳康，許婷.基于Web的全文搜索引擎的設(shè)計與實(shí)現(xiàn)[J].計算機(jī)工程，2005，31（10）：51-53.

[14]靳簡明，江紅英，王慶人.數(shù)學(xué)公式識別系統(tǒng)：MatheReader[J].計算機(jī)學(xué)報，2006，29（11）：2018-2026.

[15]郭育生，黃磊，劉昌平.基于多候選的數(shù)學(xué)公式識別系統(tǒng)[J].計算機(jī)研究與發(fā)展，2007，44（7）：1144-1150.