一種文本數(shù)據(jù)集成方法的研究與實現(xiàn)

陳飛彥，胡　亮

(吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院，吉林 長春 130012)

?

一種文本數(shù)據(jù)集成方法的研究與實現(xiàn)

陳飛彥，胡亮

(吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院，吉林 長春 130012)

[摘要]針對數(shù)據(jù)預(yù)處理中文本數(shù)據(jù)集成涉及文本比較和查找耗時問題，提出一種基于hash技術(shù)的方法.通過hash運算，將查找過程中文本比較轉(zhuǎn)化為整數(shù)比較，并同時使用2種hash函數(shù)，解決hash沖突問題.建立hash表或者B-樹索引，加快了查找速度.實驗結(jié)果表明:hash算法與hash表的結(jié)合使用，相對于常規(guī)集成方法，極大地提高了數(shù)據(jù)預(yù)處理的速度，數(shù)據(jù)量較大時，優(yōu)勢尤其顯著；而相對于B-樹方法，hash表方法實現(xiàn)簡單，并且比B-樹處理速度快.

[關(guān)鍵詞]hash算法；hash表；數(shù)據(jù)集成；B-樹；數(shù)據(jù)預(yù)處理

在數(shù)據(jù)采集時，由于每個樣本有多個指標(biāo)需要檢測，一般根據(jù)指標(biāo)分別進(jìn)行采集相關(guān)數(shù)據(jù)，因此會產(chǎn)生多個數(shù)據(jù)源文件.需要將多個數(shù)據(jù)源的數(shù)據(jù)進(jìn)行合并，將其轉(zhuǎn)換或統(tǒng)一成適合于數(shù)據(jù)挖掘[1]的形式，如將同一樣本對象的多個特征屬性統(tǒng)一在一起，使其滿足文本分類[2]模型的輸入格式，這一過程在數(shù)據(jù)預(yù)處理中稱為集成.

文本數(shù)據(jù)的合并一直沒有較好的算法[3]，目前字符串合并算法的時間復(fù)雜度為O(n2)[4].在對樣本進(jìn)行特征合并過程中，需要不斷對其結(jié)果集進(jìn)行檢索，如果結(jié)果集存在，則合并特征值，如果不存在，則作為新樣本添加到結(jié)果集中.合并過程是文本字符串檢索(文本比較和查找)的過程，在數(shù)據(jù)量較大時，常規(guī)的檢索方法消耗時間是巨大的，因此需要尋找能夠縮短文本字符串比較時間和加快查找速度的方法來降低時間消耗.通過對文本求散列值，將文本查找轉(zhuǎn)化為整數(shù)查找，明顯縮短比較時間，建立hash表或者B-樹索引能夠加快查找速度.實驗表明，對文本進(jìn)行hash求值，再使用hash表或者B-樹查找，能夠明顯提高文本數(shù)據(jù)集成效率，減少時間消耗.而hash表方法比B-樹方法實現(xiàn)簡單，在空間開銷相當(dāng)?shù)那闆r下，能夠取得比B-樹更好的處理速度.

1相關(guān)知識

1.1hash函數(shù)

hash函數(shù)是一個公開的函數(shù)，用于將任意長度的消息M映射成為較短的、固定長度的一個值(比特串)[5].由于hash函數(shù)具備抗碰撞性、hash值長度固定等特點[6]，常用于快速檢索、無線傳感器網(wǎng)絡(luò)等領(lǐng)域，如X.C.Liu等[7]將其與B+樹算法結(jié)合，用于快速查找[8]，黃錦旺等[9]將hash算法應(yīng)用于無線傳感器網(wǎng)絡(luò)中.hash表也能夠?qū)崿F(xiàn)快速定位查找，常用于查找效率要求較高的場景，如Ruiqing Wang等[10]將hash表用于IPv6地址的快速查找.常見的hash算法根據(jù)單向函數(shù)的構(gòu)造方法可以分為加法hash、位運算hash、 乘法hash、除法hash、查表hash、混合hash等.對于不同的應(yīng)用要求，結(jié)合各種hash算法自身的特點，往往會使用不同的hash函數(shù)，如密碼學(xué)中抗碰撞性較強的MD5[11]和SHA-1(secure hash algorithm)[12]等算法用于保證消息的完整性，應(yīng)用hash算法進(jìn)行查找往往希望具有較高的效率.

hash表是一種能夠根據(jù)關(guān)鍵碼值(key value)而進(jìn)行直接訪問的數(shù)據(jù)結(jié)構(gòu).通過將關(guān)鍵碼值映射到表中的一個位置來訪問記錄，以實現(xiàn)加快查找速度的目的，其中使用的映射函數(shù)就是hash函數(shù).hash表中hash函數(shù)必須滿足如下條件：(1)便于快速計算；(2)沒有或者極少沖突.

由于hash函數(shù)不能完全避免沖突，尋求較好的解決沖突的方法成為十分重要的問題.解決沖突(Collision Resolution)也稱為“溢出”處理技術(shù).常用的沖突解決方法有拉鏈方法(chaining)和開地址法(open addressing)[13]，本文采用開地址法中的線性探查法，解決了沖突問題，另外盡可能增大空間利用率.

1.2B-樹

B-樹又叫平衡多路查找樹.由于其本身特性，常被用于快速查找場景，例如，王立濤等[14]使用B-樹進(jìn)行IPv6路由查找，一顆m階的B-樹具有如下性質(zhì)：

(1) 樹的每個節(jié)點至多有m棵子樹；

(2) 根節(jié)點至少有2棵子樹；

(3) 除根節(jié)點外所有非葉子節(jié)點至少有sup(m/2)棵子樹；

(4) 所有葉子節(jié)點在同一層上，B-樹的葉節(jié)點可以看做是一種外部節(jié)點；

(5) 若非葉子節(jié)點有k個孩子，則其恰好有k-1個關(guān)鍵碼，關(guān)鍵碼按遞增次序排列.

本文使用hash表方法和B-樹方法在實驗中進(jìn)行了比較，二者使用的關(guān)鍵碼的格式保持一致，在進(jìn)行動態(tài)插入和查找時，B-樹方法實現(xiàn)起來相對比較復(fù)雜.

2基于hash的文本數(shù)據(jù)集成方法

2.1算法數(shù)據(jù)結(jié)構(gòu)

圖1　數(shù)據(jù)結(jié)構(gòu)關(guān)系

本文用到索引集合和結(jié)果集合2個數(shù)組，二者的元素結(jié)構(gòu)和相互關(guān)系如圖1所示.結(jié)果集合用于存儲文本數(shù)據(jù)的集成結(jié)果，包括一個用于樣本區(qū)分的屬性文本(稱為固有屬性)和多個樣本指標(biāo)及對應(yīng)值(即特征屬性)；索引集合是一個存儲hash表或者B-樹中元素的集合，其中HASH1和HASH2是樣本固有屬性使用不同hash函數(shù)所求得的值.在hash表方法中，使用HASH1計算其在hash表結(jié)構(gòu)中的位置，HASH1和HASH2共同解決文本hash沖突的問題，即當(dāng)且僅當(dāng)文本的HASH1和HASH2均相等時才認(rèn)為二者是同一文本，元素中index指向樣本在結(jié)果集合中的位置.本文B-樹索引結(jié)構(gòu)和hash表結(jié)構(gòu)使用的元素結(jié)構(gòu)相同.

本文hash表索引結(jié)構(gòu)中，使用的線性探查法元素查找過程的描述如下:

Step1:計算元素e在hash表中的位置k；

Step2:若element[k].used=-1表示該位置沒有元素，返回空；否則轉(zhuǎn)Step3；

Step3:從k位置開始查找，直到滿足如下條件之一結(jié)束.

(1) element[k].used=-1.

(2) 對當(dāng)前k位置中的元素e′計算在hash表中地址和e計算在hash表中地址相同.

如果滿足條件(1)，返回空，如果滿足條件(2)，轉(zhuǎn)Step4；

Step4:若element[k].used≥0，直到element[k].used=k的位置被查找過，按下面步驟進(jìn)行.

(1) 若element[k]=e，找到，返回element[k].value.

(2) 否則，k←element[k]，繼續(xù)Step4.

Step5:找到滿足element[k].used=k，若element[k]=e，返回element[k].value，否則，返回空.

上述過程中標(biāo)記元素used=-1表示該位置沒有元素.在元素查找過程中若返回值為空則表明hash表中沒有該元素，需要將該元素插入到hash表中.針對Step1和Step5 2種返回空值的情況，具體插入操作將在“元素插入過程”中給出具體描述.另外，當(dāng)used≥0時，used的作用相當(dāng)于一個鏈表指針，該指針指向下一個在hash表中為鏈表頭所在位置的元素，used等于當(dāng)前位置時，即表示到達(dá)鏈尾.另外本文使用HASH1和HASH2是否同時相等來判斷2個元素相等與否.

關(guān)于本文使用的線性探查法元素插入過程的描述如下：

Step1:如果e對應(yīng)位置k滿足element[k].used=-1，將元素e添加到這一位置，令element[k].used←k，結(jié)束.否則轉(zhuǎn)Step2.

Step2:查找新元素e是否在hash表中，若在，結(jié)束，否則轉(zhuǎn)Step3.

Step3:獲得hash表中滿足element[k].used=k的k值，在hash表中k后順序查找到下一個used=-1的位置p，將元素e添加到這一位置，令element[k].used←k，如果hash表元素快裝滿，擴展hash表容積，結(jié)束.

當(dāng)B-樹索引為其常規(guī)的插入和查找方法時，在這里不做具體描述.

2.2算法及流程

本文hash表索引方法的流程如圖2所示.首先對數(shù)據(jù)的固有屬性A進(jìn)行關(guān)鍵詞提取，再對提取的字符串使用2種hash函數(shù)計算hash值，記為H1(A)和H2(A)，然后使用H1(A)的值來計算該數(shù)據(jù)在hash表中的位置，同時比較H1(A)和H2(A)來確定該數(shù)據(jù)和hash表中指定位置的數(shù)據(jù)是否屬于同一樣本，另外使用一次hash函數(shù)將H1(A)作為參數(shù)計算hash表地址，求2次hash值主要為了實現(xiàn)以下目的：

(1) 將字符串?dāng)?shù)組比較轉(zhuǎn)換為數(shù)值比較，以節(jié)省字符串比較所消耗的時間；

(2) 使結(jié)果盡可能均勻分布在hash表中，以減少地址沖突，提高查找速度；

(3) 將因hash沖突導(dǎo)致的合并錯誤(2條不同數(shù)據(jù)因hash值相同被認(rèn)為是一條數(shù)據(jù)而合并在一起)的概率降至極低(甚至不可能發(fā)生).

圖2　本文算法流程

將長字符串映射成hash值時，對于hash函數(shù)HASH1應(yīng)該保證其hash值盡可能地均勻分布，極少產(chǎn)生hash沖突，且具有較好的計算性能；對于HASH2應(yīng)當(dāng)保證其極少產(chǎn)生hash沖突，具有較快的計算速度.在hash表中使結(jié)果盡可能均勻分配，有利于減少用于解決hash表沖突所帶來的開銷.本文方法可以分為2個部分，即在hashTable中進(jìn)行檢索返回索引值Index和在結(jié)果集Table中根據(jù)Index值進(jìn)行合并，重點部分在于前者.

若定義本文中對觀察樣本的固有屬性關(guān)鍵字符串?dāng)?shù)組比較其所消耗的平均時間為ta，2個長整型hash值比較的平均時間為tb，數(shù)據(jù)總數(shù)為N，Table中最終數(shù)據(jù)條數(shù)為n，則有如下結(jié)論:如果使用前文所述常用合并方法，每條數(shù)據(jù)在遍歷查找時都需要進(jìn)行字符串?dāng)?shù)組比較，N的每條數(shù)據(jù)在合并到結(jié)果集中前都遍歷了結(jié)果集中的已有數(shù)據(jù)集，易知常用合并方法的時間復(fù)雜度為O(N×n)，于是常規(guī)合并方法的時間可以表示為T=γ(N×n)ta(γ為一個常數(shù)值).如果使用本文方法進(jìn)行合并，由于hash表能夠直接定位，所以每條數(shù)據(jù)查找的時間復(fù)雜度為O(1)，整個合并過程的時間復(fù)雜度應(yīng)為O(N)，因此，本文方法的時間可以表示為T′ =δNtb(δ為一個常數(shù)值).

另外，B-樹索引方法中除檢索部分外流程完全與hash表方法一致，因此不再做重復(fù)說明.

3實驗部分

3.1實驗環(huán)境和數(shù)據(jù)

本文實驗的軟硬件環(huán)境：CPU為AMD A6-3400M 1.4 Ghz(4核心)，內(nèi)存為DDR3 1 333 MHz 4 G，操作系統(tǒng)為Windows 7旗艦版(64位)，算法運行平臺為VC++2013(64位).

實驗使用的數(shù)據(jù)為2011年吉林省全地區(qū)對各類食品進(jìn)行微生物和化學(xué)指標(biāo)的檢測結(jié)果，共16 383條數(shù)據(jù)，數(shù)據(jù)類型為文本數(shù)據(jù)，每條數(shù)據(jù)包含26個屬性，其中前18個屬性包括采樣地區(qū)、采樣時間、樣本名稱和采樣方法等對應(yīng)上文提出的固有屬性，關(guān)鍵字提取后用于判斷是否為同一樣本，剩余指標(biāo)包括檢測指標(biāo)、檢測值和參考標(biāo)準(zhǔn)等.

3.2實驗驗證

目前常用于字符串的hash函數(shù)有dbj2_hash、sdbm_hash、rs_hash、js_hash以及bkdr等hash算法，這些hash算法能夠保證極少發(fā)生沖突，或者不發(fā)生沖突.通過實驗分析，最終選擇bkdr算法作為HASH1的函數(shù)，選擇djb2算法作為HASH2的函數(shù).為了簡化計算，在求hashTable中的地址時，對HASH1的值進(jìn)行取模運算，將其映射在hash表空間范圍內(nèi).

通過實驗，得出在使用本文hash表方法、常規(guī)方法、無索引方法(對文本求散列值但不建立索引方法)和B-樹方法(元素的結(jié)構(gòu)與hash表元素結(jié)構(gòu)相同)的耗時情況(排除文件讀取時的耗時)，在數(shù)據(jù)總數(shù)依次為4 000，6 000，8 000，10 000，12 000，14 000，16 383條時，其耗時情況和集成后結(jié)果見表1和2.

表1　各類方法數(shù)據(jù)預(yù)處理耗時情況　ms

由表1可見，使用hash表和B-樹方法進(jìn)行文本數(shù)據(jù)集成的效率遠(yuǎn)遠(yuǎn)超出常規(guī)方法，尤其是隨著數(shù)據(jù)量的增加，這種優(yōu)勢更加明顯，當(dāng)數(shù)據(jù)總數(shù)為4 000條時，常規(guī)方法耗時是hash表和B-樹方法的5倍，當(dāng)數(shù)據(jù)總數(shù)增加到16 383條時，這個差距分別增加到了18倍和16倍，原先需要19 084 ms才能完成的分類工作，現(xiàn)在只需要1 023 ms，大大提高了文本數(shù)據(jù)集成的效率，節(jié)省了計算資源.另外，通過比較，發(fā)現(xiàn)hash技術(shù)很好地解決了長文本耗時問題，本文方法采用的hash表(開地址法)和B-樹方法所使用的輔助空間開銷基本一致(后者大約是前者的90%)，但hash表方法實現(xiàn)相對容易，并且在數(shù)據(jù)動態(tài)增加的情況下，性能要好于B-樹方法(16 383條時，約10%).

表2　各類方法數(shù)據(jù)預(yù)處理集成數(shù)　條

由表2可以看出，4種方法的集成結(jié)果完全一致，說明使用2種hash函數(shù)求值的方法很好地解決了hash沖突帶來的合并錯誤問題.

長字符串的比較是文本檢索操作耗時的主要因素，而本文通過兩類hash函數(shù)求值很好地解決了這一問題，同時使用hash表索引結(jié)構(gòu)大大減少了搜索的時間消耗，提高了集成效率.相對于常規(guī)方法hash表和B-樹方法建立索引結(jié)構(gòu)增加了少量的空間開銷，但相對于原始數(shù)據(jù)空間以及性能的提升來說，這樣的空間開銷是可以接受的.

4種方法隨著數(shù)據(jù)總數(shù)的增加其耗時情況見圖3.從圖3可以看出，本文方法隨著數(shù)據(jù)的增加消耗時間基本上呈線性增加，而常規(guī)方法和無hash表方法則呈現(xiàn)拋物線增長，一方面驗證了本文關(guān)于時間復(fù)雜性分析的算法時間復(fù)雜度為O(αN)，而常用歸類方法時間復(fù)雜度為O(N×n)的結(jié)論；另一方面，隨著數(shù)據(jù)量繼續(xù)增加，常規(guī)方法和無索引方法耗時不斷增加，尤其是常規(guī)集成方法增加到不可容忍的程度，而使得數(shù)據(jù)集成工作無法進(jìn)行.因此本文算法具有更加明顯的優(yōu)勢.

圖3　各類方法耗時情況

4結(jié)束語

本文提出的基于hash技術(shù)和索引結(jié)構(gòu)的文本數(shù)據(jù)集成方法，在相同條件下，數(shù)據(jù)集成速度遠(yuǎn)遠(yuǎn)超過常規(guī)方法.實驗表明：hash表方法相對于B-樹方法來說，具有實現(xiàn)簡單的優(yōu)勢，算法性能也有所提升；對文本數(shù)據(jù)使用散列算法求值，將耗時較大的字符串?dāng)?shù)組比較(尤其是文本字符串較大時)轉(zhuǎn)換為速度更快的整數(shù)比較；使用hash表的方法，將遍歷查找O(n)的時間復(fù)雜性減小到O(1)級別.提出對文本數(shù)據(jù)使用2種hash函數(shù)求值，解決了使用hash方法引入的hash沖突問題.另外，常規(guī)查找方法的時間復(fù)雜度與數(shù)據(jù)的分布情況有關(guān)，而hash表方法不受其影響，因此本文方法為大量數(shù)據(jù)的預(yù)處理提供了一種性能較好的參考依據(jù).

[參考文獻(xiàn)]

[1]HAN J W，KAMBER M，PEI J. Data mining concepts and techniques[M].San Francisco：Morgan Kaufmann Publishers，2011:5-42.

[2]高潔，吉根林.文本分類技術(shù)研究[J].計算機應(yīng)用軟件，2004(7):28-30.

[3]吳立德.大規(guī)模中文文本處理[M].上海:復(fù)旦大學(xué)出版社，1997:1-7.

[4]韓客松，王永成，陳桂林.無詞典高頻字串快速提取和統(tǒng)計算法研究[J].中文信息學(xué)報，2001，15(2):23-30.

[5]MERKLE R.One way hash functions and DES[C]. Berlin:Springer-Verlag，1989:428-446.

[6]PRENEEL B. The first 30 years of cryptographic hash functions and the NIST SHA-3 competition[M].Berlin:Springer-Verlag，2010:1-14.

[7]長孫妮妮，張毅坤.一種基于B+樹的混合索引結(jié)構(gòu)[J].計算機工程，2012，38(14):35-40.

[8]LIU X C，WANG J L，ZHU M.An effective directory index framework taking advantages of hash table and B+-tree[J].Journal of Xi’an Jiaotong University，2013，47(4):105-111.

[9]黃錦旺，胡志輝.一種無線傳感器網(wǎng)絡(luò)的混沌Hash算法[J].計算機科學(xué)，2013，40(6):49-51.

[10]WANG RUIQING，DU HUIMIN. Proceeding of the 2012 international conference on computer applications and system modeling[C]//A design and implementation of a high performance IPv6 lookup algorithm based on hash and cam，F(xiàn)rance：Atlantis Press，2012:0299-0303.

[11]RIVEST R.The MD5 Message-Digest Algorithm[J/OL].RFC Editor，1992.

[12]WANG XIAOYUN，YIN YIQUN，YU HONGBO. Finding collisions in the full SHA-1[M].Berlin:Springer-Verlag，2005:17-36.

[13]劉大有，虞強源，楊博.數(shù)據(jù)結(jié)構(gòu)(第2版) [M].北京:高等教育出版社，2010:277-284.

[14]杜飛，董治國，苗琳，等.基于無沖突哈希表和多比特樹的兩級IPv6路由查找算法[J].計算機應(yīng)用，2013，33(5):1194-1196，1202.

(責(zé)任編輯：石紹慶)

Research and implementation of an integrated method for text data

CHEN Fei-yan，HU Liang

(College of Computer Science and Technology，Jilin University，Changchun 130012，China)

Abstract:In data preprocessing，the text data integration involves comparison and search two steps，both of them are time-consuming processes. In view of this，this article proposes a method based on hash technology，by using hash algorithm，the text comparison is transformed to integer comparison，and through simultaneously using two kinds of hash algorithm，hash collision problems are solved. This article uses hash table or B-tree index to improve search efficiency. Experiments show that，use hash algorithm and hash table，comparing to the common integration method，greatly improves the search speed，especially when the amount of data is huge，the advantage is obvious. Comparing to the B-tree method，hash method is easier for implementation，and can get better processing speed.

Keywords:hash algorithm；hash table；data integration；B-tree；data preprocessing

[中圖分類號]TP 393[學(xué)科代碼]520·3040

[文獻(xiàn)標(biāo)志碼]A

[作者簡介]陳飛彥(1990—)，男，碩士研究生；通訊作者：胡亮(1968—) 男，教授，博士研究生導(dǎo)師，主要從事分布式系統(tǒng)和網(wǎng)絡(luò)與信息安全研究.

[基金項目]國家自然科學(xué)基金資助項目(61103197，61073009)；國家高技術(shù)研究發(fā)展計劃項目(2011AA010101).

[收稿日期]2014-03-06

[文章編號]1000-1832(2016)01-0078-06

[DOI]10.16163/j.cnki.22-1123/n.2016.01.017