- 相關(guān)推薦
一種有效檢測漢語相似重復(fù)記錄的方法文學(xué)論文
摘要：從排序?qū)傩缘倪x擇、匹配方法、相似度計(jì)算、檢測和處理相似重復(fù)記錄以及實(shí)驗(yàn)結(jié)果幾個(gè)方面，闡述了一種有效檢測漢語相似重復(fù)記錄的方法。
關(guān)鍵詞：相似重復(fù)記錄;匹配;排序?qū)傩?/p>
Web系統(tǒng)、數(shù)據(jù)挖掘系統(tǒng)、決策支持系統(tǒng)都離不開高質(zhì)量的數(shù)據(jù)。由于系統(tǒng)所需數(shù)據(jù)常常來自不同數(shù)據(jù)源中的Web文件、各種格式文檔文件和數(shù)據(jù)庫文件，而集成這些文件中的數(shù)據(jù)極易產(chǎn)生包括相似重復(fù)記錄在內(nèi)的各種質(zhì)量問題。重復(fù)記錄是指描述同一個(gè)對象的記錄，而相似記錄是指不完全相同但相似度超過了給定閾值的記錄。產(chǎn)生相似重復(fù)記錄出現(xiàn)的原因很多，包括輸入錯(cuò)誤、縮寫、計(jì)量單位不同、字符串分割錯(cuò)誤、模式轉(zhuǎn)換錯(cuò)誤等。相似重復(fù)記錄的存在不僅浪費(fèi)系統(tǒng)的存儲(chǔ)資源，而且還會(huì)造成系統(tǒng)得到有偏差的、甚至是錯(cuò)誤的結(jié)果。因此，檢測和消除相似重復(fù)記錄是保證系統(tǒng)性能的一項(xiàng)重要工作。檢測重復(fù)記錄的方法很多：在記錄層次，有機(jī)器學(xué)習(xí)方法、領(lǐng)域知識方法和基于距離的方法;在屬性層次，則有基于字符相似度、基于標(biāo)記相似度、基于語音相似度和基于數(shù)值相似度等方法[1]。在大型數(shù)據(jù)庫中檢測相似重復(fù)記錄，排序—比較—處理是一個(gè)有效的方法[2]。
排序的目的是將相似或重復(fù)記錄盡可能聚集在一起，以便縮小記錄之間的比較范圍，縮短檢測時(shí)間，而用于排序的屬性一般是關(guān)鍵屬性或權(quán)重值大的屬性[3-4]。比較是檢測數(shù)據(jù)庫中相似重復(fù)記錄的過程，它需要逐個(gè)比較記錄的各個(gè)屬性，最后根據(jù)各個(gè)屬性總的匹配程度判斷兩個(gè)記錄是否是重復(fù)記錄或相似記錄。處理是對檢查出的重復(fù)記錄或相似記錄進(jìn)行處理，對重復(fù)記錄一般刪除，對相似記錄則可以選擇保留、合并或刪除。在排序—比較—處理方法中，核心工作是字符串之間的匹配，無論是英文還是中文字符串，基于距離的匹配是常用方法[5-6]。
本文提出了一種新的排序—比較—處理方法，實(shí)驗(yàn)結(jié)果表明，該方法的查準(zhǔn)率和運(yùn)行時(shí)間均優(yōu)于目前已有的方法。
1排序?qū)傩缘倪x擇
檢測數(shù)據(jù)庫中的相似重復(fù)記錄時(shí)，如果不限制比較范圍，每條記錄從自己的下一條記錄開始進(jìn)行比較直到最后一條記錄為止。如果數(shù)據(jù)庫有N條記錄，總共需要比較(N-1)!次。如果先排序再比較，則由于具有相同或相似屬性值的記錄聚集在相近位置，每個(gè)記錄只需要比較臨近的少量記錄，這樣可以大大降低每條記錄的比較次數(shù)。設(shè)屬性Ai值的種類分別有δi種，則用Ai排序后，記錄比較的范圍是N/δi+ε(ε<
2匹配方法
在排序?qū)傩缘倪x擇、記錄排序和檢測記錄是否是相似重復(fù)記錄過程中，都需要進(jìn)行漢字匹配。漢字字符串匹配、比較時(shí)要考慮以下3種情況：一是省略，如“東華大學(xué)”和“上海東華大學(xué)”相比，省略了“上海”2個(gè)字;二是縮寫，如“中科大”是“中國科技大學(xué)”的縮寫;三是輸入錯(cuò)誤，輸入同音、近音字或字形相似的字。
對于前兩種情況，通過查找子串算法解決;對于第三種情況，則通過查找相似漢字表解決。相似漢字表選用GB 2312—80中的常用字，按讀音對它們進(jìn)行編碼，每個(gè)漢字有唯一的區(qū)位碼。而當(dāng)滿足下面條件之一時(shí)，兩個(gè)漢字被認(rèn)為是相似的：(1)區(qū)碼相同，位碼差值的絕對值小于8;
(2)區(qū)碼不同，但屬緊鄰的區(qū)，且位碼差值的絕對值小于8。
字符串S和T的匹配方法如下，Ω存放S和T中相同字符個(gè)數(shù)：步驟1：計(jì)算字符串長度|S|和|T|。
步驟2：如果|S|≥|T|，則指針i指向T的第1個(gè)字符，指針j指向S的第1個(gè)字符;否則相反。
步驟3：保存j的值到變量head作為下次比較開始位置。如果i和j所指字符相同，Ω加1，i和j的值加1，使其指向下一個(gè)待比較字符。如果i的值大于Min(|S|，|T)|，匹配束;如果不相同，則查詢同音字表;如果在表中的相似度等于0，則j的值增1，否則λ加1，i和j的值加1，使其指向下一個(gè)待比較字符。
步驟4：如果j的值等于Max(|S|，|T|)，則將head中的值賦給j作為下次匹配起始位置，返回步驟3。
3相似度計(jì)算
對有n個(gè)屬性的記錄M和N，它們的相似度用公式(1)計(jì)算：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匹配結(jié)果的權(quán)重，越重要的屬性權(quán)重值越大。
屬性值匹配用公式(2)計(jì)算：
ma(tMi，N)i=Min(|Mi|，|Ni)|k=1ΣΩk(|Mi|，|Ni)|/2(2)式(2)中，|Mi|和|Ni|分別表示記錄M和N的第i個(gè)屬性的字符個(gè)數(shù)，ΣΩ表示相同字符數(shù)。
4檢測和處理相似重復(fù)記錄
檢測相似重復(fù)記錄的步驟如下：(1)數(shù)據(jù)庫中記錄數(shù)是N，則從中抽樣εN的記錄。N越大，ε就越小，反之越大，原則是抽樣記錄要能夠比較真實(shí)地反映整體數(shù)據(jù)庫記錄的情況。
(2)統(tǒng)計(jì)記錄中前5個(gè)屬性值的種類數(shù)，選擇種類數(shù)最多的屬性作為第1次排序的屬性。如果Ai是第1排序?qū)傩�，則統(tǒng)計(jì)屬性Ai+A(jAj是其他4個(gè)屬性)值的種類數(shù)，選擇種類數(shù)最多的屬性Aj作為第2排序?qū)傩?當(dāng)屬性值的匹配值大于0.8時(shí)認(rèn)為相等。
(3)先用Ai然后用Aj對數(shù)據(jù)庫排序。
(4)初始化時(shí)i指向第1個(gè)記錄。
(5)指針j指向下1個(gè)記錄。
(6)計(jì)算第i個(gè)和第j個(gè)記錄中屬性的ma(t)，如果值小于0.80，則將j+1的值賦給i，轉(zhuǎn)到步驟(5);如果大于0.80，則計(jì)算屬性Aj的ma(t);如果均值大于0.90，則繼續(xù)比較后續(xù)的屬性，最后計(jì)算Sim()，其中Ai和Aj的權(quán)重分別是0.3和0.2。如果Sim小于0.90，則將j+1的值賦給i，轉(zhuǎn)到步驟(5);如果Sim大于0.90，則認(rèn)定它們是相似或重復(fù)記錄;如果Sim在0.90和0.95之間，則它們之間認(rèn)定為相似記錄，將其復(fù)制到文件表中由人工判斷;如果大于0.95，則它們是重復(fù)記錄，轉(zhuǎn)向(5)。
5實(shí)驗(yàn)結(jié)果
實(shí)驗(yàn)環(huán)境是Pentium Dual-Core CPU，3.20 GHz，2.00 GB聯(lián)想電腦。實(shí)驗(yàn)數(shù)據(jù)來源于學(xué)校圖書館搜集的漢語文獻(xiàn)，其中包含大約8%的相似或重復(fù)記錄。同時(shí)，實(shí)驗(yàn)比較了文獻(xiàn)[6]中的方法一和本文提出的方法二得到的查準(zhǔn)率和運(yùn)行時(shí)間，如圖1和圖2所示。從中可以看出，本文提出的方法是有所改進(jìn)的。6結(jié)語在當(dāng)今信息社會(huì)，信息的來源和種類越來越多，而將信息集成到一起不可避免地會(huì)產(chǎn)生相似重復(fù)記錄。而如何消除相似重復(fù)記錄，是人們必須面對的問題，因此也是一個(gè)值得研究的問題。
【一種有效檢測漢語相似重復(fù)記錄的方法文學(xué)論文】相關(guān)文章：
漢語言文學(xué)論文05-24
漢語言文學(xué)論文10-23
漢語言文學(xué)論文提綱06-28
精選漢語言文學(xué)論文提綱05-30
漢語言文學(xué)專業(yè)論文05-15
高職漢語言文學(xué)論文10-08
漢語言文學(xué)專業(yè)論文08-01
漢語語言文學(xué)畢業(yè)論文08-25