一種基于二叉樹(shù)的數(shù)學(xué)公式抄襲檢測(cè)算法

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

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

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

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

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

1 引言

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

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

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

2.1 二叉樹(shù)構(gòu)造

在LaTeX文檔中，根據(jù)標(biāo)記提取用字符串形式表示的數(shù)學(xué)公式。由于LaTeX格式的數(shù)學(xué)公式具有較強(qiáng)的結(jié)構(gòu)特征，因此，可將一個(gè)復(fù)雜的數(shù)學(xué)公式分解為多個(gè)子式，再將每個(gè)子式分解成多個(gè)更小的子式[15]，如此反復(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所示。

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

由數(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(node)是結(jié)點(diǎn)node的高度，Hl是結(jié)點(diǎn)node左子樹(shù)的高度，Hr是結(jié)點(diǎn)node右子樹(shù)的高度。

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

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所示。

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

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

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

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

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

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

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

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

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

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

步驟2若數(shù)學(xué)公式集Formula非空，則從Formula中取出一個(gè)數(shù)學(xué)公式fi，生成fi的二叉樹(shù)表示并對(duì)二叉樹(shù)結(jié)構(gòu)作歸一化處理，得到fi的二叉樹(shù)表示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中，查找與二叉樹(shù)Ti根結(jié)點(diǎn)的公式元素相等的記錄，若存在，轉(zhuǎn)步驟5；否則，轉(zhuǎn)步驟2。

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

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

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

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

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

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

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

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

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

表4 修改方式的種類

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

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

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

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

[1]史彥軍，滕弘飛，金博，等.抄襲論文識(shí)別研究與進(jìn)展[J].大連理工大學(xué)學(xué)報(bào)，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ù)制檢測(cè)算法[J].大連理工大學(xué)學(xué)報(bào)，2007，47（1）：125-130.

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

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

[10]秦玉平，冷強(qiáng)奎，王秀坤，等.基于局部詞頻指紋的論文抄襲檢測(cè)算法[J].計(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]陳國(guó)俊，唐勇智.基于基準(zhǔn)線的多候選數(shù)學(xué)公式識(shí)別[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（1）：206-209.

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

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

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