一种文本数据集成方法的研究与实现

陈飞彦，胡　亮

(吉林大学计算机科学与技术学院，吉林 长春 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