一種文本數據集成方法的研究與實現

陳飛彥，胡　亮

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

?

一種文本數據集成方法的研究與實現

陳飛彥，胡亮

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

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

[關鍵詞]hash算法；hash表；數據集成；B-樹；數據預處理

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

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

1相關知識

1.1hash函數

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

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

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

1.2B-樹

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

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

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

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

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

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

本文使用hash表方法和B-樹方法在實驗中進行了比較，二者使用的關鍵碼的格式保持一致，在進行動態插入和查找時，B-樹方法實現起來相對比較復雜.

2基于hash的文本數據集成方法

2.1算法數據結構

圖1　數據結構關系

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step1:如果e對應位置k滿足element[k].used=-1，將元素e添加到這一位置，令element[k].used←k，結束.否則轉Step2.

Step2:查找新元素e是否在hash表中，若在，結束，否則轉Step3.

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

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

2.2算法及流程

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

(1) 將字符串數組比較轉換為數值比較，以節省字符串比較所消耗的時間；

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

(3) 將因hash沖突導致的合并錯誤(2條不同數據因hash值相同被認為是一條數據而合并在一起)的概率降至極低(甚至不可能發生).

圖2　本文算法流程

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

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

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

3實驗部分

3.1實驗環境和數據

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

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

3.2實驗驗證

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

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

表1　各類方法數據預處理耗時情況　ms

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

表2　各類方法數據預處理集成數　條

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

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

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

圖3　各類方法耗時情況

4結束語

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

[參考文獻]

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

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

[3]吳立德.大規模中文文本處理[M].上海:復旦大學出版社，1997:1-7.

[4]韓客松，王永成，陳桂林.無詞典高頻字串快速提取和統計算法研究[J].中文信息學報，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+樹的混合索引結構[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]黃錦旺，胡志輝.一種無線傳感器網絡的混沌Hash算法[J].計算機科學，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，France：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]劉大有，虞強源，楊博.數據結構(第2版) [M].北京:高等教育出版社，2010:277-284.

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

(責任編輯：石紹慶)

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[學科代碼]520·3040

[文獻標志碼]A

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

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

[收稿日期]2014-03-06

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

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