基于N-Gram算法的數(shù)據(jù)清洗技術(shù)*

馬平全， 宋 凱， 紀(jì)建偉

(1. 沈陽農(nóng)業(yè)大學(xué) 信息與電氣工程學(xué)院， 沈陽 110866； 2. 沈陽理工大學(xué) 自動(dòng)化與電氣工程學(xué)院， 沈陽 110159)

基于N-Gram算法的數(shù)據(jù)清洗技術(shù)*

馬平全1，2， 宋 凱1，2， 紀(jì)建偉1

(1. 沈陽農(nóng)業(yè)大學(xué) 信息與電氣工程學(xué)院， 沈陽 110866； 2. 沈陽理工大學(xué) 自動(dòng)化與電氣工程學(xué)院， 沈陽 110159)

針對(duì)數(shù)據(jù)庫中存在的大量相似重復(fù)數(shù)據(jù)，對(duì)相似重復(fù)記錄的屬性結(jié)構(gòu)以及產(chǎn)生原因進(jìn)行了分析，采用N-Gram算法對(duì)數(shù)據(jù)記錄進(jìn)行計(jì)算，得到代表每條記錄屬性的鍵值，即N-Gram值.依據(jù)該鍵值將數(shù)據(jù)庫中的數(shù)據(jù)記錄進(jìn)行排序處理，建立有序的數(shù)據(jù)庫，并對(duì)其中的數(shù)據(jù)記錄進(jìn)行相似度計(jì)算.運(yùn)用排列合并的清洗思想對(duì)識(shí)別出來的相似重復(fù)數(shù)據(jù)記錄進(jìn)行清洗，實(shí)驗(yàn)結(jié)果表明，N-Gram算法有效提高了相似重復(fù)數(shù)據(jù)記錄的查全率和查準(zhǔn)率.

相似度； 相似重復(fù)記錄； 屬性； 排序； 合并； 數(shù)據(jù)清洗； 查全率； 查準(zhǔn)率

在第二次世界大戰(zhàn)期間，信息傳遞給戰(zhàn)爭雙方帶來了極大的便利，在戰(zhàn)爭進(jìn)行過程中，人們漸漸地發(fā)現(xiàn)信息的重要性，各方都在不斷地更新自己的信息處理機(jī)制，加速信息的獲取.這種形式促進(jìn)了電子計(jì)算機(jī)的產(chǎn)生，并在戰(zhàn)爭中起到了舉足輕重的作用.戰(zhàn)爭結(jié)束以后，電子計(jì)算機(jī)作為一種新的技術(shù)被保留下來，并且不斷地被開發(fā)，漸漸走進(jìn)了人們的生活，人類逐漸進(jìn)入了信息化時(shí)代，信息技術(shù)成為每一位新時(shí)代人所必備的技術(shù).

但隨著信息技術(shù)的不斷發(fā)展，數(shù)據(jù)量不斷增加，大量的錯(cuò)誤數(shù)據(jù)充斥其中，相似數(shù)據(jù)、重復(fù)數(shù)據(jù)和字段缺失數(shù)據(jù)等，這些垃圾數(shù)據(jù)的出現(xiàn)給人們帶來了很大的不便，甚至?xí)o一些企業(yè)機(jī)關(guān)單位帶來嚴(yán)重的后果[1-3].因此，針對(duì)這些數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗變得迫在眉睫.

1 相似重復(fù)數(shù)據(jù)產(chǎn)生的原因

相似重復(fù)記錄是指在合并數(shù)據(jù)集的過程中，同一目標(biāo)實(shí)體往往有著多條記錄，這些記錄之間雖然在形式上有所不同，但其所描述的目標(biāo)卻是相同的一個(gè).通常造成這種結(jié)果的原因是由于數(shù)據(jù)錄入時(shí)錯(cuò)誤的拼寫、對(duì)名詞的縮寫以及不同的存儲(chǔ)類型，導(dǎo)致同一記錄實(shí)體有著多種不同表現(xiàn)形式，但這些記錄往往本意上都是表現(xiàn)同一條數(shù)據(jù)記錄[4-5].由于這種特殊原因，造成了其數(shù)據(jù)特征并不明顯，這對(duì)相似重復(fù)記錄的識(shí)別以及對(duì)其進(jìn)行數(shù)據(jù)清洗造成了很大的困難.因此，清除數(shù)據(jù)庫中的相似重復(fù)記錄是提高數(shù)據(jù)庫使用率、降低消耗、提高數(shù)據(jù)質(zhì)量的一個(gè)重要途徑[6-7].

本文將相似重復(fù)記錄大致分為以下兩大類：

1) 完全重復(fù)記錄.這類記錄在數(shù)據(jù)庫中無論是字符還是數(shù)值，在屬性和表現(xiàn)形式上都是完全相同的.

2) 相似重復(fù)記錄.這類記錄是指在數(shù)據(jù)庫中部分屬性字段相同或者相似，但卻是同一記錄實(shí)體的不同表現(xiàn)形式[8-9].

2 數(shù)據(jù)清洗

數(shù)據(jù)清洗是指通過某種方式來清除數(shù)據(jù)集中“臟數(shù)據(jù)”的技術(shù)，經(jīng)常作為提高數(shù)據(jù)使用率的一種途徑.到目前為止，數(shù)據(jù)清洗仍是一個(gè)模糊的概念，研究人員對(duì)數(shù)據(jù)清洗沒有給出一個(gè)標(biāo)準(zhǔn)定義，對(duì)數(shù)據(jù)清洗技術(shù)的理解仍是從字面意思上解釋的，比較通用的說法是數(shù)據(jù)清洗就是把數(shù)據(jù)庫中“臟”的數(shù)據(jù)記錄清洗掉，保留下“干凈”的數(shù)據(jù)記錄[10-11].

數(shù)據(jù)清洗的步驟與一般數(shù)據(jù)處理過程類似，主要內(nèi)容包括如下幾個(gè)方面.

1) 數(shù)據(jù)分析.數(shù)據(jù)分析基本上是所有數(shù)據(jù)處理過程的首要步驟，通過詳細(xì)分析源數(shù)據(jù)庫，檢測源數(shù)據(jù)庫中的錯(cuò)誤數(shù)據(jù)和不一致數(shù)據(jù)的情況，從而來判定數(shù)據(jù)質(zhì)量上的問題.然而，如何準(zhǔn)確了解數(shù)據(jù)集中的質(zhì)量問題是個(gè)難點(diǎn)，而這個(gè)問題僅依靠既有的元數(shù)據(jù)并不能達(dá)到預(yù)期目的.這便需要對(duì)具體的數(shù)據(jù)實(shí)例進(jìn)行數(shù)據(jù)分析，從中提取出能夠代表整條記錄的元數(shù)據(jù)，這些元數(shù)據(jù)能夠自動(dòng)改變數(shù)據(jù)之間的屬性，本文稱之為依附性，然后重點(diǎn)對(duì)這些實(shí)例的屬性進(jìn)行分析，才能發(fā)現(xiàn)其中的數(shù)據(jù)質(zhì)量問題[12].

數(shù)據(jù)派生和數(shù)據(jù)挖掘都能夠較好地完成數(shù)據(jù)分析的任務(wù)，但兩者主要應(yīng)用在不同的數(shù)據(jù)庫中.首先兩者最大的不同是作用范圍，數(shù)據(jù)派生主要是作用在單獨(dú)的屬性上，通過對(duì)單獨(dú)的屬性實(shí)例進(jìn)行分析，從而得到大量的屬性信息，包括數(shù)據(jù)類型、數(shù)據(jù)單位、屬性沖突的次數(shù)和缺失信息的頻率等.而數(shù)據(jù)挖掘恰好與其相反，其主要應(yīng)用在大型數(shù)據(jù)中心，通過對(duì)大型數(shù)據(jù)中心的海量信息進(jìn)行分析，挖掘出屬性之間依賴關(guān)系和約束關(guān)系，這些關(guān)系往往是后期對(duì)多數(shù)據(jù)源中相似重復(fù)記錄進(jìn)行數(shù)據(jù)清洗的一個(gè)重要依據(jù)，根據(jù)這些關(guān)系能夠較為完善地解決存在的問題[13-14].

2) 確定數(shù)據(jù)轉(zhuǎn)換規(guī)則和工作流.通過數(shù)據(jù)分析可得到一些信息，包括數(shù)據(jù)源的個(gè)數(shù)、錯(cuò)誤數(shù)據(jù)的多少以及“臟數(shù)據(jù)”的主要類型等，通過這些信息建立合適的清洗步驟、轉(zhuǎn)換算法、查詢語句以及檢測算法等，從而確定主句轉(zhuǎn)換規(guī)則和工作流.

3) 數(shù)據(jù)驗(yàn)證.在確定數(shù)據(jù)轉(zhuǎn)換規(guī)則和工作流之后，需要對(duì)其進(jìn)行驗(yàn)證，避免出現(xiàn)效率低下等問題.從數(shù)據(jù)源中抽出一部分?jǐn)?shù)據(jù)當(dāng)作樣本數(shù)據(jù)，然后利用上一步確定的數(shù)據(jù)轉(zhuǎn)換規(guī)則和工作流對(duì)抽出來的樣本進(jìn)行驗(yàn)證，并對(duì)驗(yàn)證結(jié)果進(jìn)行分析，對(duì)工作流和轉(zhuǎn)換規(guī)則進(jìn)行相應(yīng)的調(diào)整和改進(jìn)[15-16].數(shù)據(jù)驗(yàn)證這一過程往往需要進(jìn)行多次，以達(dá)到盡可能高的效率以及高精度地進(jìn)行數(shù)據(jù)清洗.

4) 數(shù)據(jù)清洗.在數(shù)據(jù)驗(yàn)證過程中，對(duì)選擇的清洗策略進(jìn)行了驗(yàn)證，確定其可行性，并利用該策略進(jìn)行數(shù)據(jù)清洗操作，數(shù)據(jù)清洗的流程如圖1所示.

圖1 數(shù)據(jù)清洗流程Fig.1 Flow chart of data cleaning

3 N-Gram算法

N-Gram算法是一種大詞匯連續(xù)語音識(shí)別中常用的語言模型，它遵循的思想是每一條數(shù)據(jù)的出現(xiàn)都有一定的概率，通過假設(shè)數(shù)據(jù)中所有詞的出現(xiàn)都會(huì)影響其之后的詞，但對(duì)已出現(xiàn)的詞并沒有任何影響.通過這種思想可以認(rèn)為整條記錄的出現(xiàn)都有一定的概率，與記錄中的每一個(gè)詞均有關(guān)系.因此，本文根據(jù)每個(gè)詞出現(xiàn)的概率，給每條記錄計(jì)算出一個(gè)鍵值，即N-Gram值，該值在一定程度上代表了該條記錄的屬性，屬性越相近，相似程度越高，該值在數(shù)值上就越接近.根據(jù)這種特性對(duì)數(shù)據(jù)源中所有的數(shù)據(jù)進(jìn)行排序能夠?qū)⑾嗨浦貜?fù)數(shù)據(jù)放到一起.

當(dāng)某條記錄中第N個(gè)詞的出現(xiàn)概率并不是隨機(jī)出現(xiàn)時(shí)，而是與這條記錄的前N-1個(gè)詞息息相關(guān)，并且僅與這N-1個(gè)詞有關(guān)，與第N個(gè)詞后面的詞都沒有關(guān)系，每個(gè)詞出現(xiàn)的概率相乘，便得到整條數(shù)據(jù)記錄出現(xiàn)的概率，而每個(gè)詞出現(xiàn)的概率都可以直接從所有數(shù)據(jù)記錄的語料庫和重復(fù)矩陣中計(jì)算得到，這便是N-Gram算法模型.

統(tǒng)計(jì)語言模型的數(shù)學(xué)模型表達(dá)式為

(1)

(2)

式(2)即為“馬爾可夫假設(shè)”.二元的Bigram認(rèn)為，每條語句中的所有詞僅和其前面最相近的那個(gè)詞有關(guān)，與其他任何詞都無關(guān)，則其概率表達(dá)式為

P(S)=P(w1w2…wn)=

(3)

三元的Trigram假設(shè)下一個(gè)詞的出現(xiàn)僅依賴于其前面的兩個(gè)詞，則其概率表達(dá)式為

(4)

算法過程描述如下.

1) 數(shù)據(jù)預(yù)處理.在進(jìn)行數(shù)據(jù)清洗之前，首先對(duì)待清洗的數(shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理，將其中無法識(shí)別的字符串或者帶有標(biāo)識(shí)性含義的標(biāo)點(diǎn)進(jìn)行處理，例如銀行系統(tǒng)中常用的“￥”和“＄”符號(hào)，以及處于對(duì)數(shù)據(jù)保密的原因所進(jìn)行的加密處理符號(hào)“*”，這些字符串在后期進(jìn)行數(shù)據(jù)清洗的時(shí)候，由于其具有相似性，會(huì)對(duì)清洗結(jié)果的準(zhǔn)確性產(chǎn)生很大的影響.

例如，待清洗的數(shù)據(jù)庫中有如下5條數(shù)據(jù)：

①Johnny·Depp，California，PrincetonUniversity，Computer

②Tom·Hanks，Districtofcolumbia，HarvardUniversity，philosophy

③Tom·Hanks，Districtcolumbia，HarvardUniversity，philosophy

④Adam·Sandler，Alabamas，UniversityofCaliforniaBerkeley，PhysicalScience

⑤Leonardo·Dicaprio，Connecticut，UniversityofSou-thernCalifornia，Biology

對(duì)它們進(jìn)行預(yù)處理之后的結(jié)果如下：

① s1=johnnydeppcaliforniaprincetonuniversityco-mputer

② s2=tomhanksdistrictofcolumbiaharvardunivers-ityphilosophy

③ s3=tomhanksdistrictcolumbiaharvarduniversit-yphilosophy

④ s4=adamsandleralabamasuniversityofcaliforni-aberkeleyphysicalscience

⑤ s5=leonardodicaprioconnecticutuniversityofs-outherncaliforniabiology

2) 建立語料庫.掃描整個(gè)待清洗數(shù)據(jù)庫，根據(jù)N-Gram算法精度建立語料庫.當(dāng)N值為2時(shí)，語料庫中每一個(gè)元素字符串的長度則為1，建立上述5條待清洗記錄的語料庫，如表1所示.

3) 分 割數(shù)據(jù)記錄，計(jì)算重復(fù)矩陣.按照N-Gram算法將這5條字符串分割成元字符串，例如，當(dāng)N值為2時(shí)，這5條字符串經(jīng)過N-Gram算法分割后得到的字符串?dāng)?shù)組如下：

S1={“jo”，“oh”，“hn”，“nn”，…，“ut”，“te”，“er”}

S2={“to”，“om”，“mh”，“ha”，…，“op”，“ph”，“hy”}

S3={“to”，“om”，“mh”，“ha”，…，“op”，“ph”，“hy”}

S4={“ad”，“da”，“am”，“ms”，…，“en”，“nc”，“ce”}

表1 待清洗記錄語料庫
Tab.1 Corpus of records to be cleaned

名稱數(shù)量a24b5c16d9名稱數(shù)量e17f6g1h11名稱數(shù)量i31j1k3l13名稱數(shù)量m7n20o24p10名稱數(shù)量q0r21s16t16名稱數(shù)量u10v7w0x0名稱數(shù)量y11z0

S5={“l(fā)e”，“eo”，“on”，“na”，…，“l(fā)o”，“og”，“gy”}

對(duì)這些字符串?dāng)?shù)組建立重復(fù)矩陣M.在重復(fù)矩陣中，M(a，b)代表“ab”在整個(gè)數(shù)據(jù)庫中的數(shù)量，則有

4) 計(jì)算N-Gram值.根據(jù)式(4)及語料庫和重復(fù)矩陣，對(duì)這5條待清洗數(shù)據(jù)記錄進(jìn)行計(jì)算，得到它們的N-Gram值，即

(p(jo)/p(o))(p(oh)/p(h))(p(hn)/p(n))…(p(er)/p(r))=

4.9×10-37

(5)

P(S2)=7.411×10-36

(6)

P(S3)=4.447×10-35

(7)

P(S4)=1.9e×10-51

(8)

P(S5)=3.7×10-50

(9)

5) 對(duì)數(shù)據(jù)進(jìn)行清洗.根據(jù)步驟4)所得到的N-Gram值對(duì)待清洗數(shù)據(jù)記錄進(jìn)行排序，對(duì)所得到的排序結(jié)果采用基本的字段匹配算法計(jì)算數(shù)據(jù)記錄之間的相似度，當(dāng)相似度低于規(guī)定的閾值時(shí)，則判定兩者為相似重復(fù)記錄.

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

本文根據(jù)上述算法設(shè)計(jì)了一個(gè)基于N-Gram算法的相似重復(fù)記錄數(shù)據(jù)清洗流程，通過查全率、查準(zhǔn)率和運(yùn)行速度3個(gè)因素對(duì)數(shù)據(jù)清洗過程和基于S-W算法的數(shù)據(jù)清洗技術(shù)進(jìn)行對(duì)比.

查全率是評(píng)判數(shù)據(jù)清洗技術(shù)好壞的一個(gè)重要指標(biāo)，查全率越高，代表所檢查出來的相似重復(fù)記錄越多，在一定程度上能夠代表數(shù)據(jù)清洗技術(shù)的性能.圖2為查全率曲線圖.從圖2中可以看出，在查全率方面，本文提出的算法較S-W算法有較大的優(yōu)勢，且隨著數(shù)據(jù)量的不斷增加，兩種算法的查全率都在不斷遞增.

圖2 查全率Fig.2 Recall ratio

查準(zhǔn)率是評(píng)判數(shù)據(jù)清洗技術(shù)好壞的重要指標(biāo)，是指所檢測出來的相似重復(fù)記錄中確實(shí)為相似重復(fù)記錄的比例，能夠真實(shí)地反映出一個(gè)算法的好壞.圖3為查準(zhǔn)率曲線圖.從圖3中可以看出，本文提出的算法較S-W算法有較大優(yōu)勢，雖然隨著數(shù)據(jù)量的不斷增加，該優(yōu)勢有所減緩，但結(jié)合查全率的優(yōu)勢可以看出本文算法的優(yōu)點(diǎn).

圖3 查準(zhǔn)率Fig.3 Precision ratio

隨著信息的不斷發(fā)展，數(shù)據(jù)記錄的不斷增多，運(yùn)行時(shí)間也作為評(píng)判一個(gè)算法好壞的標(biāo)準(zhǔn)，本文對(duì)兩種算法的運(yùn)行時(shí)間進(jìn)行了對(duì)比，結(jié)果如圖4所示.從圖4中可以看出，數(shù)量級(jí)較低時(shí)，S-W算法較本文算法具有較大優(yōu)勢，隨著數(shù)量級(jí)的不斷增多，S-W算法的運(yùn)行時(shí)間增長迅速，超過本文算法所提出的數(shù)據(jù)清洗算法運(yùn)行時(shí)間.

圖4 運(yùn)行時(shí)間對(duì)比Fig.4 Runtime comparison

5 結(jié) 論

通過對(duì)相似重復(fù)數(shù)據(jù)記錄的結(jié)構(gòu)及產(chǎn)生原因進(jìn)行分析，提出了一種基于N-Gram算法的相似重復(fù)記錄的數(shù)據(jù)清洗技術(shù).該方法通過計(jì)算數(shù)據(jù)記錄之間的N-Gram值，將待清洗記錄進(jìn)行排序，并對(duì)排序后的結(jié)果進(jìn)行相似度檢測，從而提高了相似重復(fù)記錄的查全率和查準(zhǔn)率，且隨著數(shù)量級(jí)的不斷增加，本文算法的運(yùn)行時(shí)間優(yōu)于其他算法.

[1]楊東華，李寧寧，王宏志，等.基于任務(wù)合并的并行大數(shù)據(jù)清洗過程優(yōu)化 [J].計(jì)算機(jī)學(xué)報(bào)，2016，39(1)：97-108.

(YANG Dong-hua，LI Ning-ning，WANG Hong-zhi，et al.The optimization of the big data cleaning based on task merging [J].Chinese Journal of Computers，2016，39(1)：97-108.)

[2]羅景峰，劉艷秋，許開立.基于均勻設(shè)計(jì)與灰局勢決策的智能算法參數(shù)設(shè)定 [J].沈陽工業(yè)大學(xué)學(xué)報(bào)，2010，32(1)：84-89.

(LUO Jing-feng，LIU Yan-qiu，XU Kai-li.Parameter establishment of intelligent algorithm based on uniform design and grey situation decision [J].Journal of Shenyang University of Technology，2010，32(1)：84-89.)

[3]陳明.大數(shù)據(jù)分析 [J].計(jì)算機(jī)教育，2014(5)：122-126.

(CHEN Ming.Big data analysis [J].Computer Education，2014(5)：122-126.)

[4]吳斐，唐雁，補(bǔ)嘉.基于N-Gram的VB源代碼抄襲檢測算法 [J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2012，26(2)：86-91.

(WU Fei，TANG Yan，BU Jia.A VB source code plagiarism detection method based onN-Gram [J].Journal of Chongqing University of Technology (Natural Science)，2012，26(2)：86-91.)

[5]邵林，黃芝平，唐貴林，等.并行緩存結(jié)構(gòu)在高速海量數(shù)據(jù)記錄系統(tǒng)中的應(yīng)用 [J].計(jì)算機(jī)測量與控制，2008，16(4)：527-529.

(SHAO Lin，HUANG Zhi-ping，TANG Gui-lin，et al.Application of parallel cache structure in high-speed mass data recording system [J].Computer Measurement and Control，2008，16(4)：527-529.)

[6]周典瑞，周蓮英.海量數(shù)據(jù)的相似重復(fù)記錄檢測算法 [J].計(jì)算機(jī)應(yīng)用，2013，33(8)：2208-2211.

(ZHOU Dian-rui，ZHOU Lian-ying.Algorithm for detecting approximate duplicate records in massive data [J].Journal of Computer Applications，2013，33(8)：2208-2211.)

[7]付印金，肖儂，劉芳.重復(fù)數(shù)據(jù)刪除關(guān)鍵技術(shù)研究進(jìn)展 [J].計(jì)算機(jī)研究與發(fā)展，2012，49(1)：12-20.

(FU Yin-jin，XIAO Nong，LIU Fang.Research and development on key techniques of data deduplication [J].Journal of Computer Research and Development，2012，49(1)：12-20.)

[8]Lillibridge M，Eshghi K，Bhagwat D.Improving restore speed for backup systems that use inline chunk-based deduplication [C]//Proceedings of the 11th USENIX Conference on File and Storage Technologies.New York，USA，2013：183-197.

[9]朱燦，曹健.實(shí)體解析技術(shù)綜述與展望 [J].計(jì)算機(jī)科學(xué)，2015，42(3)：8-12.

(ZHU Can，CAO Jian.Summary and prospect on entity resolution [J].Computer Science，2015，42(3)：8-12.)

[10]王琛.Web數(shù)據(jù)清洗及其系統(tǒng)框架研究 [J].計(jì)算機(jī)時(shí)代，2014(12)：42-44.

(WANG Chen.Research on Webdata cleaning and its system framework [J].Computer Era，2014(12)：42-44.)

[11]Geerts F，Mecca G，Papotti P，et al.The LLUNATIC data-cleaning framework [J].VLDB Endowment，2013，6(9)：625-636.

[12]Tan Y J，Jiang H，Sha H M，et al.SAFE：a source deduplication framework for efficient cloud backup ser-vices [J].Journal of Signal Processing Systems，2013，72(3)：209-228.

[13]殷秀葉.大數(shù)據(jù)環(huán)境下的相似重復(fù)記錄檢測方法 [J].武漢工程大學(xué)學(xué)報(bào)，2014，36(3)：66-69.

(YIN Xiu-ye.Method for detecting approximately duplicate database records in big data environment [J].Journal of Wuhan Institute of Technology，2014，36(3)：66-69.)

[14]Nguyen T T，Hui S C，Chang K.A lattice-based approach for mathematical search using formal concept analysis [J].Expert Systems with Applications，2012，39(5)：5820-5828.

[15]黨小超，高琪，郝占軍.基于小波變換的分布式WSN數(shù)據(jù)融合模型研究 [J].計(jì)算機(jī)工程與應(yīng)用，2014，50(22)：97-101.

(DANG Xiao-chao，GAO Qi，HAO Zhan-jun.Research on model of distributed date aggregation in WSN based on wavelet transform [J].Computer Engineering and Applications，2014，50(22)：97-101.)

[16]譚霜，何力，陳志坤，等.云存儲(chǔ)中一致基于格的數(shù)據(jù)完整性驗(yàn)證方法 [J].計(jì)算機(jī)研究與發(fā)展，2015，52(8)：1862-1872.

(TAN Shuang，HE Li，CHEN Zhi-kun，et al.A method of provable data integrity based on lattice in cloud storage [J].Journal of Computer Research and Deve-lopment，2015，52(8)：1862-1872.)

(責(zé)任編輯：鐘 媛 英文審校：尹淑英)

Data cleaning technology based onN-Gram algorithm

MA Ping-quan1,2, SONG Kai1,2, JI Jian-wei1

(1. College of Information and Electrical Engineering, Shenyang Agricultural University, Shenyang 110866, China; 2. School of Automation and Electrical Engineering, Shenyang Ligong University, Shenyang 110159, China)

Aiming at the plentiful approximately duplicate data in the database, the attribute structure of approximately duplicate records and the causing reason were analyzed. The data records were calculated with theN-Gram algorithm to get the key values, namelyN-Gram values, which represented the attribute of every record. According to the key values, the data records in the database were ordered so as to form a well-organized database. In addition, the similarity of data records in the database was calculated. The identified approximately duplicate records were cleaned by applying the arranged combination cleaning idea. The experimental results show that theN-Gram algorithm effectively increases the recall ratio and precision ratio of approximately duplicate data records.

similarity; approximately duplicate record; attribute; ordering; combination; data cleaning; recall ratio; precision ratio

2016-06-28.

遼寧省教育廳科學(xué)研究項(xiàng)目(LG201610).

馬平全(1975-)，男，遼寧丹東人，講師，博士生，主要從事信號(hào)檢測與處理等方面的研究.

17∶40在中國知網(wǎng)優(yōu)先數(shù)字出版.

http：∥www.cnki.net/kcms/detail/21.1189.T.20161222.1740.040.html

10.7688/j.issn.1000-1646.2017.01.13

TP 311.11

A

1000-1646(2017)01-0067-06