重復(fù)記錄檢測(cè)綜述

1、書(shū)《現(xiàn)代圖書(shū)情報(bào)技術(shù)》版權(quán)所有，歡迎下載引用！請(qǐng)注明引用地址：相似重復(fù)記錄清理方法研究綜述［Ｊ］，現(xiàn)代圖書(shū)情報(bào)技術(shù)，２０１０（９）：５６－６６５６現(xiàn)代圖書(shū)情報(bào)技術(shù)相似重復(fù)記錄清理方法研究綜述葉煥倬吳迪（中南財(cái)經(jīng)政法大學(xué)信息與安全工程學(xué)院信息系武漢４３００７３）【摘要】介紹相似重復(fù)數(shù)據(jù)清理的步驟、框架和衡量標(biāo)準(zhǔn)。重點(diǎn)對(duì)檢測(cè)和清除算法按照算法類型及相關(guān)改進(jìn)思路進(jìn)行分類綜述，給出算法的適用范圍和優(yōu)缺點(diǎn)，概括現(xiàn)有的數(shù)據(jù)清理工具（如Ｍｅｒｇｅ／

2、Ｐｕｒｇｅ）。對(duì)相似重復(fù)記錄清理領(lǐng)域的研究問(wèn)題進(jìn)行展望，將知識(shí)和語(yǔ)義的概念引入到數(shù)據(jù)清理框架中是未來(lái)重要的發(fā)展趨勢(shì)?！娟P(guān)鍵詞】相似重復(fù)記錄數(shù)據(jù)清洗檢測(cè)算法清除算法【分類號(hào)】Ｇ２０２ＴＰ３９１１ＡＳｕｒｖｅｙｏｆＡｐｐｒｏｘｉｍａｔｅｌｙＤｕｐｌｉｃａｔｅＤａｔａＣｌｅａｎｉｎｇＭｅｔｈｏｄＹｅＨｕａｎｚｈｕｏＷｕＤｉ（ＤｅｐａｒｔｍｅｎｔｏｆＩｎｆｏｒｍａｔｉｏｎ，ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎａｎｄＳａｆｅｔｙＥｎｇｉｎｅｅｒ

3、ｉｎｇ，ＺｈｏｎｇｎａｎＵｎｉｖｅｒｓｉｔｙｏｆＥｃｏｎｏｍｉｃｓａｎｄＬａｗ，Ｗｕｈａｎ４３００７３，Ｃｈｉｎａ）【Ａｂｓｔｒａｃｔ】Ｔｈｉｓｐａｐｅｒｉｎｔｒｏｄｕｃｅｓｔｈｅｓｔｅｐｓ，ｆｒａｍｅｗｏｒｋｓａｎｄｍｅｔｒｉｃｓｏｆａｐｐｒｏｘｉｍａｔｅｌｙｄｕｐｌｉｃａｔｅｄａｔａｃｌｅａｎｉｎｇＴｈｅｎ，ｔｈｅｄｅｔｅｃｔａｌｇｏｒｉｔｈｍｓａｎｄｔｈｅｅｌｉｍｉｎａｔｉｏｎａｌｇｏｒｉｔｈｍｓａｒｅｓｕｒｖｅｙｅｄｅｓｓｅｎｔ

4、ｉａｌｌｙ，ａｃｃｏｒｄｉｎｇｔｏｔｙｐｅａｎｄｔｈｅｉｒｉｍｐｒｏｖｅｍｅｎｔｍｅｔｈｏｄｓ，ａｎｄｔｈｅａｌｇｏｒｉｔｈｍｓｕｓａｇｅｓｃｏｐｅａｎｄｔｈｅｉｒａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓａｒｅｇｉｖｅｎＭａｎｙｄａｔａｃｌｅａｎｉｎｇｔｏｏｌｓａｒｅｐｒｅｓｅｎｔｅｄ，ｓｕｃｈａｓＭｅｒｇｅ／ＰｕｒｇｅＦｉｎａｌｙ，ｉｔｄｉｓｃｕｓｓｅｓｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｔｏｐｉｃｓｉｎｄａｔａｃｌｅａｎｉ

5、ｎｇａｎｄｐｏｉｎｔｓｏｕｔｔｈａｔｔｈｅｃｏｎｃｅｐｔｏｆｋｎｏｗｌｅｄｇｅａｎｄｓｅｍａｎｔｉｃｕｓｅｄｉｎｔｈｅｆｒａｍｅｗｏｒｋｏｆｄａｔａｃｌｅａｎｉｎｇｗｉｌｌｂｅａｎｉｍｐｏｒｔａｎｔｔｒｅｎｄ【Ｋｅｙｗｏｒｄｓ】ＡｐｐｒｏｘｉｍａｔｅｌｙｄｕｐｌｉｃａｔｅｄａｔａＤａｔａｃｌｅａｎｉｎｇＤｅｔｅｃｔａｌｇｏｒｉｔｈｍＥｌｉｍｉｎａｔｅａｌｇｏｒｉｔｈｍ收稿日期：２０１０－０７－１２收修改稿日期：２０１０－０８－１８本文

6、系國(guó)家自然科學(xué)基金資助項(xiàng)目“持續(xù)審計(jì)中智能數(shù)據(jù)處理及其應(yīng)用框架研究”（項(xiàng)目編號(hào)：７０９７２１３８）和湖北省教育廳人文社會(huì)科學(xué)基金項(xiàng)目“基于ＳＯＡ和ＭＡＳ的金融監(jiān)管信息系統(tǒng)總體框架研究”（項(xiàng)目編號(hào)：２００９ｂ０８０）的研究成果之一。１引言隨著信息技術(shù)的不斷發(fā)展和信息化建設(shè)的不斷深入，企事業(yè)單位、圖書(shū)館等在進(jìn)行信息系統(tǒng)集成和重構(gòu)時(shí)，數(shù)據(jù)庫(kù)中積累了大量的臟數(shù)據(jù)。如何將臟數(shù)據(jù)有效轉(zhuǎn)化成高質(zhì)量的干凈數(shù)據(jù)是系統(tǒng)要解決的首要問(wèn)題，這涉及到數(shù)據(jù)清理的技

7、術(shù)。數(shù)據(jù)清理（ＤａｔａＣｌｅａｎｉｎｇ，ＤａｔａＣｌｅａｎｓｉｎｇ或ＤａｔａＳｃｒｕｂｂｉｎｇ）也稱為數(shù)據(jù)清洗，目的是檢測(cè)數(shù)據(jù)中存在的錯(cuò)誤和不一致，剔除或者改正它們，以提高數(shù)據(jù)的質(zhì)量［１］。臟數(shù)據(jù)按其不同的表現(xiàn)形式可具體概括為不完整數(shù)據(jù)、相似重復(fù)數(shù)據(jù)和錯(cuò)誤數(shù)據(jù)三種類型［１，２］。其中多數(shù)據(jù)源合并造成的信息重復(fù)是最關(guān)鍵的問(wèn)題，因此重復(fù)信息的檢測(cè)和清除成為一個(gè)研究的熱點(diǎn)［３，４］。２相似重復(fù)記錄清理概述２１數(shù)據(jù)質(zhì)量問(wèn)題的分類進(jìn)行數(shù)據(jù)清理的最

8、終目的是提高數(shù)據(jù)的質(zhì)量，數(shù)據(jù)質(zhì)量問(wèn)題在微觀層面分為單數(shù)據(jù)源（Ｓｉｎｇｌｅ－Ｓｏｕｒｃｅ）和多情報(bào)分析與研究５８現(xiàn)代圖書(shū)情報(bào)技術(shù)－Ｇｒａｍｓ算法（Ｎ－ＧｒａｍＡｌｇｏｒｉｔｈｍ）、對(duì)ＸＭＬ數(shù)據(jù)的匹配算法（ＭａｔｃｈｉｎｇＡｌｇｏｒｉｔｈｍｆｏｒＸＭＬ）等。３１字段匹配算法字段匹配是用來(lái)確定兩個(gè)字段值是否表示同一個(gè)語(yǔ)義實(shí)體的句法上的可替換者，是記錄匹配的基礎(chǔ)?；镜淖侄纹ヅ渌惴ê瓦f歸的字段匹配算法是兩種最基礎(chǔ)的字段匹配算法?；镜淖侄纹ヅ渌?/p>

9、法利用兩個(gè)分詞串中順序匹配的分詞個(gè)數(shù)除以它們平均的所有的分詞個(gè)數(shù)，以此來(lái)計(jì)算匹配度。如表１中兩個(gè)地址字段，在Ａ中有ｋ＝６個(gè)單詞（Ｃｏｍｐｕｔ、Ｓｃｉ、Ｕｎｉｖｅｒｓｉｔｙ、Ｃａｌｉｆｏｒｎｉａ、Ｓａｎ、Ｄｉｅｇｏ）與Ｂ中的單詞匹配，則匹配度為ｋ／［（｜Ａ｜＋｜Ｂ｜）／２］＝０８，其中：｜Ａ｜表示Ａ中分詞的個(gè)數(shù)，為８；｜Ｂ｜＝７。遞歸的字段匹配算法使用典型文本字段的遞歸結(jié)構(gòu)，基本的情況是如果Ａ和Ｂ是相同的字符串或一個(gè)是另一個(gè)的縮寫(xiě)，匹配

10、度就是１０，否則是００。每一個(gè)Ａ的子字符串與Ｂ的子字符串進(jìn)行匹配，記錄子字符串匹配得分最高的情形。Ａ和Ｂ的匹配度計(jì)算如公式（２）所示。文獻(xiàn)［１８］－［２０］對(duì)這兩種算法思想進(jìn)行了詳細(xì)的描述，并用實(shí)驗(yàn)對(duì)它們的性能進(jìn)行了驗(yàn)證。ｍａｔｃｈ（Ａ，Ｂ）＝１｜Ａ｜∑｜Ａ｜ｉ＝１ｍａｘ｜Ｂ｜ｊ＝１ｍａｔｃｈ（Ａｉ，Ｂｊ）（２）Ｓｍｉｔｈ和Ｗａｔｅｒｍａｎ在１９８１年提出了著名的Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ算法［２１］，這是一種動(dòng)態(tài)編程的方法。引入間隙

11、或空位（Ｇａｐ）以及罰值（Ｐｅｎａｌｔｙ）的概念，確定兩個(gè)字符串的匹配程度。文獻(xiàn)［１９］介紹了一種將遞歸的字段匹配算法與Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ算法相結(jié)合的改進(jìn)的Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ算法（Ｒ－Ｓ－Ｗ），該算法既能識(shí)別拼寫(xiě)錯(cuò)誤，又能識(shí)別子串的顛倒和縮寫(xiě)。文獻(xiàn)［２２］和［２３］對(duì)Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ算法進(jìn)行了改進(jìn)，分別加入了擴(kuò)大的遞歸變量和并行處理的概念，極大地提高了運(yùn)行效率。文獻(xiàn)［２４］將Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ算

12、法與編輯距離（Ｌｅｖｅｎｓｈｔｅｉｎ距離）結(jié)合來(lái)處理實(shí)際檢測(cè)問(wèn)題，可以將檢測(cè)誤識(shí)別率從５５６％降低到３４８％，極大地提高了檢測(cè)準(zhǔn)確度。其中矩陣值范圍Ｓｉｊ定義的關(guān)系式如下所示：Ｓｉｊ＝Ｓｉ－１，ｊ－１＋１，ｉｆＡ（ｉ）＝Ｂ（ｊ）ｍａｘ（０，Ｓｉ－１，ｊ－１，Ｓｉ，ｊ－１－１，Ｓｉ－１，ｊ－１－１），ｏｔｈｅｒｗｉｓｅ（３）基于以上的算法都無(wú)法直接應(yīng)用在中文中，文獻(xiàn)［１９］提出基于編輯距離的中文縮寫(xiě)發(fā)現(xiàn)算法，文獻(xiàn)［２０］給出了一個(gè)中文字段

13、匹配框架，描述了簡(jiǎn)單中文字段匹配算法、遞歸的中文字段匹配算法、漢語(yǔ)同音字字段匹配算法三種中文字符型字段匹配算法。常用字段匹配算法的比較情況，如表２所示：表２常用字段匹配算法的比較算法時(shí)間復(fù)雜度優(yōu)點(diǎn)缺點(diǎn)基本的字段匹配算法［７，１８－２０］Ｏ（ｎｌｏｇｎ），ｎ是兩個(gè)字段中原子字符串的數(shù)目的最大值算法直觀，處理速度較快不能處理不是前綴的縮寫(xiě)情況，也不能應(yīng)用有關(guān)子字段排序的信息遞歸的字段匹配算法［７，１８－２０］Ｏ（ｎ２），ｎ是子串的個(gè)數(shù)算法簡(jiǎn)

14、單直觀，能處理子串順序顛倒及縮寫(xiě)等的匹配情況。時(shí)間復(fù)雜度較高，與具體的應(yīng)用領(lǐng)域密切相關(guān)，匹配規(guī)則復(fù)雜，效率較低，此外還不能處理包含錯(cuò)誤的字符串Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ算法［７，２１］Ｏ（ｍｎ），ｍ、ｎ為參與比較的兩個(gè)字符串的長(zhǎng)度不依賴領(lǐng)域知識(shí)，可以識(shí)別字符串縮寫(xiě)、字符串拼寫(xiě)錯(cuò)誤的情形不能處理子串順序顛倒的情況改進(jìn)的Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ算法（Ｒ－Ｓ－Ｗ）［１９］Ｏ（ｍｎｍａｘ（ｍ，ｎ）），ｍ、ｎ為參與比較的兩個(gè)字符串的

15、長(zhǎng)度既能識(shí)別拼寫(xiě)錯(cuò)誤，又能識(shí)別子串的顛倒和縮寫(xiě)無(wú)法直接應(yīng)用于中文中基于編輯距離的縮寫(xiě)發(fā)現(xiàn)算法［１９］—可以發(fā)現(xiàn)所有可能的縮寫(xiě)模式為了提高準(zhǔn)確性需要在專業(yè)領(lǐng)域內(nèi)應(yīng)用啟發(fā)式規(guī)則或知識(shí)庫(kù)來(lái)選擇真正的縮寫(xiě)形式３２編輯距離算法編輯距離是用來(lái)計(jì)算從原串（ｓ）轉(zhuǎn)換到目標(biāo)串（ｔ）所需要的最少的插入、刪除和替換的數(shù)目，首先由俄國(guó)科學(xué)家Ｌｅｖｅｎｓｈｔｅｉｎ在１９６５年提出，故又叫Ｌｅｖｅｎｓｈｔｅｉｎ距離［２５］。如圖１（ａ）顯示了“愛(ài)看期刊”和“喜歡看

16、雜志”之間的編輯距離為４。圖１編輯距離與改進(jìn)編輯距離的比較Ｍｏｎｇｅ等使用一種可調(diào)節(jié)的編輯距離計(jì)算方法來(lái)識(shí)別重復(fù)記錄［２６］。文獻(xiàn)［２７］提出一種應(yīng)用子串進(jìn)行相似度計(jì)量的編輯距離方法。文獻(xiàn)［２８］在文獻(xiàn)［２５］的理論基礎(chǔ)上提出一種基于ＮＦＡ（ＮｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃＦｉｎｉｔｅｓｔａｔｅＡｕｔｏｍａｔｉｏｎ）的編輯距離方法。將匹配字符串看作是一個(gè)查找樹(shù)，通過(guò)建立一個(gè)查找樹(shù)索引，從而有效地提高了識(shí)別準(zhǔn)確率。以發(fā)現(xiàn)１００萬(wàn)條記錄中