摘要：從排序屬性的選擇、匹配方法、相似度計算、檢測和處理相似重複記錄以及實驗結果幾個方面，闡述了一種有效檢測漢語相似重複記錄的方法。
關鍵詞：相似重複記錄;匹配;排序屬性
Web系統、數據挖掘系統、決策支援系統都離不開高質量的數據。由於系統所需數據常常來自不同數據源中的Web檔案、各種格式文檔檔案和數據庫檔案，而集成這些檔案中的數據極易產生包括相似重複記錄在內的各種質量問題。重複記錄是指描述同一個對象的記錄，而相似記錄是指不完全相同但相似度超過了給定閾值的記錄。產生相似重複記錄出現的原因很多，包括輸入錯誤、縮寫、計量單位不同、字元串分割錯誤、模式轉換錯誤等。相似重複記錄的存在不僅浪費系統的存儲資源，而且還會造成系統得到有偏差的、甚至是錯誤的結果。因此，檢測和消除相似重複記錄是保證系統性能的一項重要工作。檢測重複記錄的方法很多：在記錄層次，有機器學習方法、領域知識方法和基於距離的方法;在屬性層次，則有基於字元相似度、基於標記相似度、基於語音相似度和基於數值相似度等方法[1]。在大型數據庫中檢測相似重複記錄，排序—比較—處理是一個有效的方法[2]。
排序的目的是將相似或重複記錄儘可能聚集在一起，以便縮小記錄之間的比較範圍，縮短檢測時間，而用於排序的屬性一般是關鍵屬性或權重值大的屬性[3-4]。比較是檢測數據庫中相似重複記錄的過程，它需要逐個比較記錄的各個屬性，最後根據各個屬性總的匹配程度判斷兩個記錄是否是重複記錄或相似記錄。處理是對檢查出的重複記錄或相似記錄進行處理，對重複記錄一般刪除，對相似記錄則可以選擇保留、合併或刪除。在排序—比較—處理方法中，核心工作是字元串之間的匹配，無論是英文還是中文字元串，基於距離的匹配是常用方法[5-6]。
本文提出了一種新的排序—比較—處理方法，實驗結果表明，該方法的查準率和執行時間均優於目前已有的方法。
1排序屬性的選擇
檢測數據庫中的相似重複記錄時，如果不限制比較範圍，每條記錄從自己的下一條記錄開始進行比較直到最後一條記錄爲止。如果數據庫有N條記錄，總共需要比較(N-1)!次。如果先排序再比較，則由於具有相同或相似屬性值的記錄聚集在相近位置，每個記錄只需要比較臨近的少量記錄，這樣可以大大降低每條記錄的比較次數。設屬性Ai值的種類分別有δi種，則用Ai排序後，記錄比較的範圍是N/δi+ε(ε<
2匹配方法
在排序屬性的選擇、記錄排序和檢測記錄是否是相似重複記錄過程中，都需要進行漢字匹配。漢字字元串匹配、比較時要考慮以下3種情況：一是省略，如“東華大學”和“上海東華大學”相比，省略了“上海”2個字;二是縮寫，如“中科大”是“中國科技大學”的縮寫;三是輸入錯誤，輸入同音、近音字或字形相似的字。
對於前兩種情況，透過查找子串算法解決;對於第三種情況，則透過查找相似漢字表解決。相似漢字表選用GB 2312—80中的常用字，按讀音對它們進行編碼，每個漢字有唯一的區位碼。而當滿足下面條件之一時，兩個漢字被認爲是相似的：(1)區碼相同，位碼差值的絕對值小於8;
(2)區碼不同，但屬緊鄰的區，且位碼差值的絕對值小於8。
字元串S和T的匹配方法如下，Ω存放S和T中相同字元個數：步驟1：計算字元串長度|S|和|T|。
步驟2：如果|S|≥|T|，則指針i指向T的第1個字元，指針j指向S的第1個字元;否則相反。
步驟3：儲存j的值到變量head作爲下次比較開始位置。如果i和j所指字元相同，Ω加1，i和j的值加1，使其指向下一個待比較字元。如果i的值大於Min(|S|，|T)|，匹配束;如果不相同，則查詢同音字表;如果在表中的相似度等於0，則j的值增1，否則λ加1，i和j的值加1，使其指向下一個待比較字元。
步驟4：如果j的值等於Max(|S|，|T|)，則將head中的值賦給j作爲下次匹配起始位置，返回步驟3。
3相似度計算
對有n個屬性的記錄M和N，它們的相似度用公式(1)計算：Sim(M，N)=α1ma(tMi，N)i+α2ma(tMj，N)j+nk=1，k≠i，jΣ1-α1-α2n-2ma(tMk，Nk)(1)(α1>0，α2>0，α1+α2<1)式(1)中，ma(tMi，N)i是記錄M和N屬性Ai的匹配值，α1,α2分別是Ai，Aj匹配結果的權重，越重要的屬性權重值越大。
屬性值匹配用公式(2)計算：
ma(tMi，N)i=Min(|Mi|，|Ni)|k=1ΣΩk(|Mi|，|Ni)|/2(2)式(2)中，|Mi|和|Ni|分別表示記錄M和N的.第i個屬性的字元個數，ΣΩ表示相同字元數。
4檢測和處理相似重複記錄
檢測相似重複記錄的步驟如下：(1)數據庫中記錄數是N，則從中抽樣εN的記錄。N越大，ε就越小，反之越大，原則是抽樣記錄要能夠比較真實地反映整體數據庫記錄的情況。
(2)統計記錄中前5個屬性值的種類數，選擇種類數最多的屬性作爲第1次排序的屬性。如果Ai是第1排序屬性，則統計屬性Ai+A(jAj是其他4個屬性)值的種類數，選擇種類數最多的屬性Aj作爲第2排序屬性;當屬性值的匹配值大於0.8時認爲相等。
(3)先用Ai然後用Aj對數據庫排序。
(4)初始化時i指向第1個記錄。
(5)指針j指向下1個記錄。
(6)計算第i個和第j個記錄中屬性的ma(t)，如果值小於0.80，則將j+1的值賦給i，轉到步驟(5);如果大於0.80，則計算屬性Aj的ma(t);如果均值大於0.90，則繼續比較後續的屬性，最後計算Sim()，其中Ai和Aj的權重分別是0.3和0.2。如果Sim小於0.90，則將j+1的值賦給i，轉到步驟(5);如果Sim大於0.90，則認定它們是相似或重複記錄;如果Sim在0.90和0.95之間，則它們之間認定爲相似記錄，將其複製到檔案表中由人工判斷;如果大於0.95，則它們是重複記錄，轉向(5)。
5實驗結果
實驗環境是Pentium Dual-Core CPU，3.20 GHz，2.00 GB聯想電腦。實驗數據來源於學校圖書館蒐集的漢語文獻，其中包含大約8%的相似或重複記錄。同時，實驗比較了文獻[6]中的方法一和本文提出的方法二得到的查準率和執行時間，如圖1和圖2所示。從中可以看出，本文提出的方法是有所改進的。6結語在當今資訊社會，資訊的來源和種類越來越多，而將資訊集成到一起不可避免地會產生相似重複記錄。而如何消除相似重複記錄，是人們必須面對的問題，因此也是一個值得研究的問題。