相似度技術(shù)在資料信息化中的應(yīng)用研究

張德龍，楊 鵬

（內(nèi)蒙古氣象信息中心 內(nèi)蒙古 呼和浩特 010051）

我國有器測(cè)以來，積累了大量的觀測(cè)氣象資料，是氣候研究、決策規(guī)劃的珍貴資源。其大部分以紙質(zhì)形式記錄，大量觀測(cè)資料均存儲(chǔ)在各類報(bào)表或自記紙上。為了對(duì)歷史資料的進(jìn)一步應(yīng)用，需要把報(bào)表上的資料錄入成電子數(shù)據(jù)。然而在錄入過程中可能存在同一臺(tái)站不同年代，或不同臺(tái)站間數(shù)據(jù)相互拷貝的情況。在這種情況下，如果能通過計(jì)算機(jī)自動(dòng)、快速地在大量錄入文件中檢查哪些部分是相同的，就時(shí)間而言可完成人工幾乎不可能完成的任務(wù)，然后在選出的文件中再進(jìn)行人工參與，大大的減少了審核人員的工作量。

目前，內(nèi)容相似度度量的技術(shù)主要有：屬性計(jì)數(shù)技術(shù)和結(jié)構(gòu)度量技術(shù)。由于屬性計(jì)數(shù)技術(shù)沒有考慮文件的結(jié)構(gòu)，只是統(tǒng)計(jì)了文件中一些屬性信息，所以隨著文件復(fù)制種類的不斷提高（如從不同文件中各選一些組合成文件），其度量結(jié)果的準(zhǔn)確性就會(huì)下降。1976年，Halstead[1]首先提出了用屬性計(jì)數(shù)的方法檢測(cè)文件的拷貝問題，1977年，Ottenstein[2]使用Halstead的方法設(shè)計(jì)了最早的自動(dòng)文件拷貝檢測(cè)系統(tǒng)。結(jié)構(gòu)度量技術(shù)考慮了文件的結(jié)構(gòu)特征，度量結(jié)果比較真實(shí)地反映了文件之間的相似性。 Plague[3]，Sim[4]，YAP3[5]等拷貝檢測(cè)系統(tǒng)無一例外的都使用了結(jié)構(gòu)度量技術(shù)。由于國外大部分成功的拷貝檢查系統(tǒng)都采用了結(jié)構(gòu)度量技術(shù)，所以本研究結(jié)構(gòu)度量技術(shù)。首先對(duì)文件作預(yù)處理，去掉對(duì)相似度度量結(jié)果沒有影響的部分，接著掃描經(jīng)預(yù)處理后的文件，并對(duì)其作簡(jiǎn)單的語法分析，將其轉(zhuǎn)換為表示文件結(jié)構(gòu)的標(biāo)記字符串，再通過特定的匹配算法對(duì)得到的字符串作比較，并給出它們之間匹配程度的數(shù)值表示，以此作為文件數(shù)據(jù)相似度的度量值。該值越大說明文件數(shù)據(jù)越相似，存在拷貝的可能性也越高。

1 相關(guān)算法及技術(shù)介紹

文件相似度度量技術(shù)中，結(jié)構(gòu)度量技術(shù)是通過比較文件的結(jié)構(gòu)來度量文件數(shù)據(jù)間的相似度。結(jié)構(gòu)度量技術(shù)中，首先將源文件轉(zhuǎn)換為標(biāo)記串序列，然后通過字符串匹配算法比較得到的標(biāo)記串，并根據(jù)匹配結(jié)果給出文件數(shù)據(jù)相似度的數(shù)值表示。這里用到的字符串匹配算法稱為結(jié)構(gòu)比較算法，本研究也將采用該算法來匹配表示文件結(jié)構(gòu)的標(biāo)記串。在討論Running Karp-Rabin Greedy String Tiling算法。算法中用到的幾個(gè)基本概念：1）文本串（也稱主串），指要在其中查找子字符串的較長的字符串，用T表示；2）模式串（也稱模式），指需要在文本串T中查找的字符串，用P表示。通常，文本串T是較長的字符串，而模式串P是較短的字符串。

1.1 Running Karp-Rabin Greedy String Tiling

1.1.1 算法描述和偽代碼

Running Karp-Rabin Greedy String Tiling算法是基于非常有名的字符串匹配算法Karp-Rabin[6]。受基于映射（散列）排序技術(shù)的啟發(fā)，1987年圖靈獎(jiǎng)獲得者Karp教授和著名學(xué)者Rabin教授合作，在IBM研究與發(fā)展雜志上介紹了一種直觀、快速的Karp-Rabin串匹配隨機(jī)算法（簡(jiǎn)稱KR算法）。算法十分簡(jiǎn)單，但是卻非常有效。該算法的基本思想是把長度為m的模式串看作是一個(gè)鍵（key），而把文本串中每m個(gè)字符也看作是一個(gè)鍵。如果能夠定義一個(gè)散列函數(shù)把這些鍵都映射為它們對(duì)應(yīng)的散列值，那么顯然只有那些與模式串具有相同散列值的文本字段才有可能與模式串匹配，這是一個(gè)必要條件。Karp和Rabin給出了在線性時(shí)間內(nèi)計(jì)算散列函數(shù)的有效方法。

通過以下方法修改字符串匹配算法KR，RKR-GST算法擴(kuò)展了原來的GST[7]算法：

不對(duì)整個(gè)模式串計(jì)算一個(gè)單獨(dú)的散列值，而是對(duì)每一個(gè)長度為w從Pw到Pm+w-1未作記號(hào)的模式串的子串計(jì)算一個(gè)散列值。同樣，計(jì)算未作記號(hào)從Tn到Tn+w-1文本串子串的散列值。前面已經(jīng)提到，該計(jì)算可以在線性時(shí)間內(nèi)完成。

比較上一步得出的每一個(gè)模式串和文本串的散列值。如果相等，表明兩個(gè)子串可能匹配，接著通過逐個(gè)比較每一個(gè)標(biāo)記來檢查是否匹配。這樣，利用映射表通過散列值的比較將時(shí)間復(fù)雜度從O（n2）減少到了一個(gè)常量時(shí)間。

這里的參數(shù)w被稱為搜索長度，且在算法的每一次循環(huán)后將逐步減少，直到等于最小匹配長度。

以下給出了RKR-GST算法的最高層偽代碼。該算法很簡(jiǎn)單，因?yàn)樗腔贕ST算法的，所以類似于Greedy String Tiling算法。算法的主要不同是scanpattern步驟，RKR-GST是在確定的大小上找到所有的最大匹配。

在RKR-GST最高層算法中，首先是給搜索長度賦了一個(gè)初值，這是該算法與GST算法之間的另一個(gè)不同點(diǎn)。算法的主要循環(huán)從scanpattern過程開始，這個(gè)過程返回w的一個(gè)新值。如果找到了一個(gè)較長的最大匹配，算法自動(dòng)從一個(gè)等于新長度的搜索長度重新開始。否則，算法接著開始執(zhí)行這樣一個(gè)過程，該過程為找到的最大匹配中所有未作記號(hào)的標(biāo)記作記號(hào)。這個(gè)作記號(hào)的過程是通過markstrings過程完成的。作記號(hào)過程結(jié)束后，如果w的值被更新為比最小匹配長度更小的新值，算法就結(jié)束了。否則，算法從w的這個(gè)新值開始繼續(xù)執(zhí)行。

以上是scanpattern過程的偽代碼，這個(gè)過程的主要部分就是散列過程。scanpattern過程掃描文本文檔中從Tn到Tn+w-1的文本串中未作記號(hào)的字符串并為其產(chǎn)生散列值。當(dāng)這個(gè)過程執(zhí)行完成后，會(huì)生成所有未作記號(hào)的標(biāo)記的映射表，所有未作記號(hào)的子串的長度都等于w。隨后，為每一個(gè)從Pm到Pm+w-1的模式串生成散列值，并將其與文本串的散列值作比較，即在前一步中產(chǎn)生的映射表中查找每一個(gè)模式串的散列值，如果找到了一個(gè)相等的，算法就試圖擴(kuò)展這個(gè)匹配。相等的子串（有相同散列值的標(biāo)記串）的檢測(cè)過程從模式掃描過程延期到了算法標(biāo)記過程。推論結(jié)果顯示，KR的散列過程很少發(fā)生沖突，且算法標(biāo)記過程中逐個(gè)元素的匹配也很有效。這個(gè)過程返回找到的最大匹配的長度。

用于記錄最大匹配的數(shù)據(jù)結(jié)構(gòu)是雙向隊(duì)列。每個(gè)隊(duì)列記錄相同長度的最大匹配，隊(duì)列列表的次序是按匹配長度遞減排列。每個(gè)隊(duì)列里用一個(gè)指針指向最近添加的最大匹配，因?yàn)楹苡锌赡芟乱粋€(gè)最大匹配的匹配長度與最后一個(gè)記錄的相同或相近，因此可以很方便地被記錄到該隊(duì)列的最后或接近該隊(duì)列的隊(duì)列里。

以下描述了markstrings過程的偽代碼。除了使用了一個(gè)比線性鏈表更合適的隊(duì)列外，該算法使用了和GST算法相同的結(jié)構(gòu)。此外，像前面討論的一樣，該過程中也作了相等字符串的測(cè)試。為了檢查散列值相等的那些子串是否真正的相等，文件從scanpattern過程進(jìn)入到了markstring過程，此外，散列值相等的子串通過逐個(gè)元素的比較后也不一定能保證是相等的字符串。

只要子串相等，算法就為屬于它們的所有標(biāo)記作上記號(hào)。與GST算法相比較，如果出現(xiàn)了封閉，則最大匹配的未作記號(hào)部分就被定義了。如果這個(gè)未作記號(hào)的部分大于等于搜索長度，則被記錄進(jìn)最大匹配列表里。這樣做是為了確保未作記號(hào)的部分在markstrings過程中被選擇并被作上記號(hào)。

1.1.2 KR散列值的計(jì)算

像前面討論中多次提到的一樣，散列值的計(jì)算能在常量時(shí)間內(nèi)完成。Karp-Rabin算法是這樣定義散列函數(shù)的[8-9]：假設(shè)文本串T與模式串P中出現(xiàn)的字符集合為Σ，設(shè)集合的大小為s，那么可以把字符串看作是一個(gè)s進(jìn)制的數(shù)，也就是說，當(dāng)模式串P=p1p2p3…pm時(shí)，則P可以數(shù)值化為：

此時(shí)，可以找到一個(gè)較大的素?cái)?shù)q，定義P的散列函數(shù)為：

Hash（P′）=mod（P′，q）=mod（p1×sm-1+p2×sm-2+…+pm，q） （2）同理，對(duì)于文本串，也可以對(duì)其中長為m的一段執(zhí)行上述操作，如果假設(shè)文本串為T=t1t2t3…tn，可以在其中找到一個(gè)整數(shù) k，取 T 其中的 T（k）=tk+1tk+2tk+3…tk+m，對(duì)于這一段進(jìn)行 s進(jìn)制的數(shù)值化為：

同理如果往后移動(dòng)一個(gè)位置，則有：

顯然，T′（k+1）與 T′（k）滿足這樣的關(guān)系：

所以如果求得了 Hash（T′（k）），根據(jù)求模運(yùn)算的性質(zhì)，則右移一位得到的字符串子段滿足：

上面式子通?？梢杂霉?Hash （T′（k）-tk+1*sm-1）*s+tk+m+1計(jì)算得到，如果得到的值比q大，那么只需要再做一次取模運(yùn)算就可以了。同時(shí)，由于Hash（sm）在比較中常常用到，所以可以先對(duì)其進(jìn)行預(yù)處理，在需要的時(shí)候直接調(diào)用即可。

假設(shè)X=xr，xr+1，…，xr+n是從r開始的 n+1個(gè)字符組成的字符串，而且，假設(shè)d是標(biāo)記字母表的基，q是一個(gè)大的素?cái)?shù)，則散列值Xy按下列公式計(jì)算：

到此為止，計(jì)算散列值的過程H的時(shí)間復(fù)雜度也沒有太多的改善。然而，Xr+1的散列值則可按如下公式求出：

如果散列值H（Xr）存在的話，式（8）就可在常量時(shí)間內(nèi)計(jì)算出來。

1.1.3 RKR-GST時(shí)間復(fù)雜度分析

像前面討論的一樣，最壞情況下，RKR-GST算法的時(shí)間復(fù)雜度和GST算法一樣，仍然是O（n3）。然而，算法的平均時(shí)間復(fù)雜度卻在O（n）和O（n2）之間。使用曲線擬合法，Wise經(jīng)實(shí)驗(yàn)得出的平均復(fù)雜度為O（n1.12），非常接近線性時(shí)間。因此，實(shí)際上RKR-GST算法改善了算法的時(shí)間復(fù)雜度。

2.2 對(duì)RKR-GST算法的一點(diǎn)改進(jìn)

通過前面的分析可知，當(dāng)兩個(gè)標(biāo)記串的KR散列值相同時(shí)，再通過逐個(gè)字符的比較來判斷兩個(gè)標(biāo)記串是否匹配。很顯然，這是使用的蠻力（Brute Force）字符串匹配算法（簡(jiǎn)稱BF算法），最壞情況下該算法的時(shí)間復(fù)雜度為O（mn）。為了改進(jìn)[10-11]其時(shí)間復(fù)雜度，所以考慮使用KMP算法[11-12]，KMP算法的時(shí)間復(fù)雜度為O（m+n），這里m和n分別為模式串和文本串的長度。下面簡(jiǎn)單介紹一下KMP算法。

KMP（Knuth-Morris-Pratt）算法是 BF的一種改進(jìn)算法，其核心思想是：在發(fā)生失配時(shí)，文本串不需要回溯，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式串向右“滑動(dòng)”盡可能遠(yuǎn)的距離，繼續(xù)進(jìn)行比較。這里要強(qiáng)調(diào)的是，模式串不一定向右移動(dòng)一個(gè)字符的位置，右移也不一定必須從模式串起點(diǎn)處重新試匹配，即模式串一次可以右移多個(gè)字符的位置，右移后可以從模式串起點(diǎn)后的某處開始試匹配。

假設(shè)發(fā)生失配時(shí)，P[i]≠T[j]，1≤i≤m，1≤j≤n。 則下一輪比較時(shí)，P[i]應(yīng)與T[next[j]]對(duì)齊往后比較：

根據(jù)j的取值可以得到next[i]的結(jié)果，從而獲得向右滑動(dòng)的距離。

2 實(shí)際問題處理

利用相似度技術(shù)對(duì)內(nèi)蒙古全區(qū)119個(gè)臺(tái)站從建站到2010年的地面歷史資料所有要素進(jìn)行同站間不同年代數(shù)據(jù)，相鄰臺(tái)站各年代數(shù)據(jù)進(jìn)行控制，如下例

|1969-02-02|A054***.F69|54***.F79|1979-02-12|水汽壓|13天|

表示54***站1969年2月2日開始有13天的水汽壓記錄和1979年2月22日開始的13天記錄完全相同，需要核對(duì)報(bào)表，確認(rèn)是否存在錄入拷貝的問題。

|1998-12-09|A05****.D98|54***|2001-12-05|A054***.D01|氣壓|12 天|

|2001-01-12|A05****.J01|54102|2004-01-21|A054***.J04|水汽壓|2天|

|1984-12-13|A054***.D84|55***|1984-12-16||A055***.D84溫度|12天|

表示不同臺(tái)站在某些年月存在連續(xù)若干天記錄相同的問題，通過核對(duì)原始報(bào)表確認(rèn)其錄入的數(shù)據(jù)是否正確。

3 結(jié) 論

通過全內(nèi)蒙古全區(qū)119個(gè)臺(tái)站從建站到2010年約6 000個(gè)站月資料數(shù)字化文件臺(tái)站參數(shù)、要素方式位、要素等方面相似度的檢查，我區(qū)臺(tái)站參數(shù)檢測(cè)疑誤1 970條，方式位疑誤檢測(cè)53 852條，要素檢測(cè)疑誤1 6991條。存在的問題主要是要素02時(shí)與08時(shí)整月要素值相同；要素缺少記錄；定時(shí)風(fēng)風(fēng)速個(gè)位非零和風(fēng)向8方位；方式位變化的問題和臺(tái)站參數(shù)變化的問題。通過自動(dòng)度量不僅可以幫助審核人員節(jié)省大量的工作時(shí)間，也減輕了工作量，同時(shí)對(duì)其他行業(yè)的數(shù)字化工作也具有重要的借鑒意義。

[1]Halstead M H.Elements of software science[M].North Holland，New York，1977（17）:5-7.

[2]Ottenstein K J.An algorithmic approach to the detection and prevention of plagiarism[J].ACM SIGCSE Bulletin，1976，8（4）:30-41.

[3]Whale G.Identification of program similarity in large populations[J].The Computer Journal，1990，33（2）:140-146.

[4]Gitchell D，Tran N.Sim:A utility for detecting similarity in computer programs[C]//In Proceedings of the 30th SIGCSE Technical Symposium，March 1999.

[5]Wise，Michael J.YAP3:Improved Detection of Similarities in Computer Program and other Texts[M].Department of Computer Science， University of Sydney， 2003.

[6]張文典，任冬偉.程序拷貝判定系統(tǒng)[J].小型微型計(jì)算機(jī)系統(tǒng)，1988，9（10）：34-39.

ZHANG Wen-dian，REN Dong-wei.The judgment system of program copies[J].Journal of Chinese Computer System，1988，9（10）：34-39.

[7]于海英.字符串相似度度量中LCS和GST算法比較[J].電子科技，2011（3）：101-103，124.

YU Hai-ying.The comparison of the LCS algorithm with the GST algorithm in strings similarity metrics[J].Electronic Science and Technology，2011（3）：101-103，124.

[8]Faidhi，J A W，Robinson S K.An empirical approach for detecting program similarity within a university programming environment[J].Computers and Education，1987，11（1）:11-19.

[9]Grier，Sam.A Tool that Detects Plagiarism in Pascal Programs.Twelfth SIGCSE Technical Symposium[J].St Louis， Missouri，1981:15-20.

[10]Verco K L，Wise M J.Software for detecting suspected plagiarism:comparing structure and attribute-counting systems[J].Computer Science， University of Sydney，1996:3-5.

[11]Donaldson，John L，LancasterA M，etal.A Plagiarism Detection System[M].Twelfth SIGCSE Technical Symposium，St Louis，Missouri，1981:21-25.

[12]黨紅云，蔣品群，何婷婷.一種改進(jìn)的KMP算法在不良網(wǎng)站信息過濾中的應(yīng)用[J].現(xiàn)代電子技術(shù)，2012（1）：110-112，116.

DANG Hong-yun，JIANG Pin-qun，HE Ting-ting.Application of an improved KMP algorithm in bad website information filtering[J].Modern Electronics Technique，2012（1）：110-112，116.