２０１７年第７期 文章编号：１００６－２４７５（２０１７）０７－００３８－０４ 计算机与现代化 ＪＩＳＵＡＮＪＩ ＹＵ ＸＩＡＮＤＡＩＨＵＡ 总第２６３期 基于Ｓｉｍｈａｓｈ的大数据去重改进算法 周春晖 （上海交通大学软件学院，上海２０１１００） 摘要：数据去重是大数据预处理过程中最主要的一个步骤。为了提升大数据去重的效率，以及优化其在较差情况下的表 现，本文以中文微博的原始数据为基础，在传统的Ｓｉｍｈａｓｈ方法的基础上，改进计算相似度的公式，将文本重复率纳入考 虑，并在检索步骤中采用桶排序的思想，进行多次多级的线程分配以提高效率。实验结果表明，改进后的算法可以显著 提升传统算法的效率和准确率。 关键词：微博；大数据；去重；Ｓｉｍｈａｓｈ；多线程 中图分类号：ＴＰ３１１ 文献标识码：Ａ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００６—２４７５．２０１７．０７．００７ Ａ Ｂｉｇ Ｄａｔａ Ｄｅｄｕｐｌｉｃａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｓｉｍｈａｓｈ ＺＨ０Ｕ Ｃｈｕｎ．ｈｕｉ （Ｓｃｈｏｏｌ ｏｆ Ｓｏｆｔｗａｒｅ，Ｓｈａｎｇｈａｉ Ｊｉａｏ Ｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２０１１００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｄａｔａ ｄｅｄｕｐｌｉｃａｔｉｏｎ ｉｓ ａ ｍａｉｎ ｓｔｅｐ ｉｎ ｂｉｇ ｄａｔａ ｐｒｅｐｒｏｃｅｓｓ．Ｔｏ ｉｍｐｒｏｖｅ ｅｆｉｃｉｆｅｎｃｙ ｉｎ ｄｅｄｕｐｌｉｃａｔｉｏｎ ａｎｄ ｏｐｔｉｍｉｚｅ ｐｅｒｆｏｒｍ－ ａｎｃｅ ｉｎ ｔｅｒｒｉｂｌｅ ｃｏｎｄｉｔｉｏｎ ｏｆ ｃｌａｓｓｉｃ ａｌｇｏｒｉｔｈｍ，ｔｈｉｓ ｐａｐｅｒ ＵＳｅＳ Ｃｈｉｎｅｓｅ ｔｅｘｔ ｄａｔａ ｏｆ ｍｉｅｒｏｂｌｏｇ ａｎｄ ｍｏｄｉｆｉｅｓ ｆｏｒｍｕｌａ ｏｆ ｃａｌｃｕｌａｔｉｎｇ ｓｉｍｉｌａｒｉｔｙ ｂａｓｅｄ ｏｎ ｃｌａｓｓｉｃ Ｓｉｍｈａｓｈ ａｌｇｏｒｉｔｈｍ．Ｄｕｐｌｉｃａｔｉｏｎ ｒａｔｅ ｉＳ ｃｏｎｓｉｄｅｒｅｄ ｉｎ ｔｈｅ ａｄｖａｎｃｅｄ ｆｏｒｍｕｌａ，ｂｅｓｉｄｅｓ，ｔｈｉｓ ｐａｐｅｒ ｄｒａｗｓ ｏｎ ｔｈｅ ｅｘｐｅｒｉｅｎｃｅ ｏｆ ｂｕｃｋｅｔ ｓｏ￣ｉｎｇ，ｄｉｓｔｒｉｂｕｔｅｓ ｔｈｒｅａｄｓ ｆｏｒ ｓｅｖｅｒａｌ ｔｉｍｅｓ ａｎｄ ｌｅｖｅｌｓ ｔｏ ｉｍｐｒｏｖｅ ｅｆｉｃｉｅｎｃｙ．Ｔｈｅ ｒｅｓｕｌｔｆ ｏｆ ｅｘｐｅｒｉｍｅｎｔ ｓｈｏｗｓ ｔｈａｔ ａｄｖａｎｃｅｄ ａｌｇｏｒｉｔｈｍ ｃａｎ ｒｅｄｕｃｅ ｒｕｎｎｉｎｇ ｔｉｍｅ ａｎｄ ｉｍｐｒｏｖｅ ａｃｃｕｒａｃｙ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｃｌａｓｓｉｃ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：ｍｉｃｒｏｂｌｏｇ；ｂｉｇ ｄａｔａ；ｄｅｄｕｐｌｉｃａｔｉｏｎ；Ｓｉｍｈａｓｈ；ｍｕｈｉ—ｔｈｒｅａｄ ０ 引 言 一会发生很大的变化 Ｊ，这显然并不适合比对２个文 本之问的相似程度。 Ｓｉｍｈａｓｈ算法主要分为２个步骤。 ，海量数据处理是当今网络环境下重要的课题之 而数据去重则是数据处理的第一步。网络爬虫每 天能在网络上抓取数以百万计的数据，而其中有相当 一１）Ｈａｓｈ值的计算。通过每条数据的特征值（词 组）的Ｈａｓｈ值，确定一条数据的Ｓｉｍｈａｓｈ值，最终得 到的指纹将是一个３２位的二进制串。 部分是重复的，重复的数据不仅会对数据分析处理 的速度产生影响，也会在一定程度上影响准确性，因 ２）在计算出每条的Ｓｉｍｈａｓｈ值后对Ｓｉｍｈａｓｈ值的 此进行数据去重是一个必要的工作。目前数据去重 的主要方法有Ｓｉｍｈａｓｈ、Ｍｉｎｈａｓｈ和Ｂｉｔｍａｐ等算 法¨引。本文就Ｓｉｍｈａｓｈ的去重方法进行研究，针对 原始数据的特性以及中文的特点在距离计算和检索 对比检索，通常使用海明距离 进行对比。 然而在海量数据的基础上，不可能逐个进行对 比，因此需要采用一定的方法优化。以３２位数据搜 寻海明距离３以内的为例，将原始数据复制为４份， 对于第１份数据，任意一条数据只精确匹配１～８位 相同的数据进行海明距离计算，对于第２份数据，任 意一条数据只精确匹配９～１６位相同的数据进行海 明距离计算，以此类推，以减少海明距离的计算次数 来节省时间。根据抽屉原理，所有的海明距离不大于 ３的数据都可以被找到。这种方法将３２位分为了４ 个区间，如果有必要，可以将每个区间再分为４个小 步骤上进行改进，提高算法运行的效率和准确性。 １传统的Ｓｉｍｈａｓｈ算法 Ｓｉｍｈａｓｈ算法的初衷是让相似的文本得出的 Ｈａｓｈ值也是相似的。传统的加密式Ｈａｓｈ算法比如 ＭＤ５，其设计的目的是为了让整个Ｈａｓｈ值分布尽可 能均匀，输入的内容哪怕只有轻微的变化，Ｈａｓｈ值就 收稿日期：２０１６一ｌ１—２１ 作者简介：周春晖（１９９２－），男，江苏常州人，上海交通大学软件学院硕士研究生，研究方向：分布式计算，云计算。 ２０１７年第７期 周春晖：基于Ｓｉｍｈａｓｈ的大数据去重改进算法 ３９ 区间，即复制为ｌ６份数据，第１份比对１～８位、９～ １４位都相同的，第２份比对１～８位、１６～２１位都相 同的，以此类推。 ２原始数据的特征 原始数据来自于中文的微博数据，微博的典型特 征是内容充实但是文本简短。微博的原始数据需要 经过一定的处理，比如表情、ｕｒｌ链接、＠他人的标记， 去掉这些可以使得数据更加整齐。另外还有转发的 部分也是可以删除的，比如有一条微博“今天是晴 天”和另一条被转发过的“今天是晴天．／／Ａ：ｘｘｘ／／Ｂ： ＸＸＸ”，显然这２条微博的语义和内容都是完全一样 的，去除转发的部分可以使得它们能够更容易被识 别。更多的数据特征将在后面进行说明。 中文的特点是需要进行分词，不像英文可以直接 以单词作为计算Ｈａｓｈ值的单位，中文需要将句子分 解为词组而不是单个的字，这样才有一定的语义。虽 然说两两分词也是可以的，但是准确的分词不仅可以 去除停止词，也可以提高Ｓｉｍｈａｓｈ值作为特征值的准 确性。另一方面也可以直接作为情感分析等后续操 作的材料。在实验中本文采用的是Ｌｕｃｅｎｅ下的ＩＫＡ— ｎａｌｙｚｅｒ，中文的分词器都不是特别令人满意，但是也 基本能够满足要求。中文分词通常分成２～３个字 符，在计算Ｈａｓｈ值时，生成的Ｈａｓｈ值比较短，大多数 不满３２位，如果不进行处理，第１份数据复制的处理 会精确匹配到大量的数据，造成效率上的影响。因此 本文在实验过程中将每个词组的Ｈａｓｈ值的ｌ７～３２ 位与１—１６位做或操作覆盖在１～１６位上，以使得生 成的Ｓｉｍｈａｓｈ值更加均匀。 ３改进Ｓｉｍｈａｓｈ算法 ３．１ Ｓｉｍｈａｓｈ距离优化 在传统的Ｓｉｍｈａｓｈ去重算法中，判断数据是否重 复主要通过计算海明距离，但是由于其本身的特性会 出现即使２条数据完全不相关，海明距离也会比较小 的情况。通过观察微博数据可以发现，其本身的内容 倾向于短小精悍，不经常使用修饰词，即如果２条数 据是相似的，那么其在文本内容上必然有相当程度的 重复。本文先定义２条数据的重复率： ｄｕｐ（Ａ， 等糟 器 （１） 公式（１）中，ｔｏｋ（Ａ）、ｔｏｋ（Ｂ）分别表示Ａ、Ｂ这２ 条数据在分词后的集合，重复率定义为这２个集合之 间重复的词组数和总共包括的词组数的比值。其中 一个集合自身内的词组重复不记为重复。 综合考虑海明距离和重复率，对于２条数据的相 似率做如下定义： １ Ｓｉｍ（Ａ，Ｂ） 丽 ＫＤｕｐ（Ａ，Ｂ）（２） 公式（２）中Ｋ为参数，取值一般在２～８之间。 有了相似率的定义后，还需要设定一个阈值来判 断数据是否相似，由于数据集类型的不同，应该根据 测试数据的实际效果来定义这个阈值，但是一般的建 议是不低于１＋０．２Ｋ，也就是即使海明距离为０的情 况下依然需要有２０％的重复率来确认这２段文本是 相似的，而在海明距离更大时则需要更高的重复率。 在重复率很高时即使海明距离较大也无关紧要。 ３．２ Ｓｉｍｈａｓｈ值检索优化 在改进了判断相似文本的公式后，本文最主要的 工作是改进相似文本检索的算法。对于传统的Ｓｉｍ— ｈａｓｈ值检索，每读取一条数据，需要比对所有的数据 来寻找某８，ｆ￣／１２位相同的再进行相似度的计算，在 检索大量数据时这个比对数量是很庞大的。因此本 文提出在检索之前采用类似于桶排序的方法，先将需 要确认重复的８位作为２５６个“桶”，将所有的数据 归类在２５６个组中，那么在检索时可以跳过比较是否 重复的阶段，直接进行相似度的计算，这样可以节省 大量的时间。另外在实验中发现，很少出现Ａ和Ｂ 相似、Ｂ和Ｃ相似而Ａ和Ｃ不相似的情况，因此可以 在检索时直接删除比对中重复的数据，也可以提高检 索的效率。 这种检索方法和传统的Ｓｉｍｈａｓｈ检索都面临的 一个问题是，如果Ｓｉｍｈａｓｈ值分布得不均匀，运行时 间就会很长。虽然之前处理过Ｈａｓｈ值的结果可以尽 量避免这个问题，但是总会出现这样的情况。在计算 海明距离不大于３的前提下，传统的Ｓｉｍｈａｓｈ检索的 方法是将原数据集拷贝从４份增加到１６份，比对的 值更多，那么结果就更均匀。显然本文提出的方法不 会直接复制这种操作，把组增加到８１９２个。本文对 此的解决方法是查看桶排序后各个组内的数据数量， 如果出现分布不均匀的情况，则对于数量超多的一组 或多组，再进行另一次２４位的检索操作。详细步骤 如下： １）对于任意一个数据集拷贝，检视２５６个组内的 数据数量，如果有分布不均匀，则剔除数量最多的一 个或若干个组。不均匀的判断方式有２种：①计算 ２５６个数的方差，方差大于阈值则视为不均匀，再剔 除Ｔｏｐｌ或者Ｔｏｐ２；②直接将占总数超过一定百分比 的组剔除，实际采用的是这种比较简易的方法，使用 的百分比是５０％，这就保证了一个检索线程只会产 生一个被剔除的组进行进一步的计算，可以比较好地 计算机与现代化 ２０１７年第７期 控制线程的数量。 ２）计算这个数据集拷贝在剔除一个组之后剩下 的数据的相似度比较结果，作为这份拷贝的结果。 ３）对于被剔除的组，对剩下的位数再次做４份拷 贝（因为有若干位都相同不需要参与计算），每份拷 贝再分为ｋ组： ｒ ２ Ｌ Ｊ ｉ：０，ｌ，２ ｉ ｘ３ ｉ＝３ 公式（３）中，ｎ表示总位数，ｉ表示４份拷贝的编 号。举例来说，如果要对一个ｌ８位的数据做此操作， 则第１份数据拷贝根据前４位分为１６组，第２份根 据５～８位分为ｌ６组，第３份根据９—１２位分为１６ 组，第４份根据最后６位分为６４组。然后再回到第１ 步做类似的计算。 ４）终止条件。任意一份拷贝的终止条件有３种： ①没有任意一个组的百分比超过５０％。②这份拷贝 的剩余位数小于８，且其中最大组的数据量占原始数 据量的一定百分比以下。剩余位数就是这份拷贝的 总位数减去分组的位数。设定这个终止条件的原因 Ｏ 豁 ５ × × 是一旦剩余位数小于８且需要进行下一轮操作，那么 在下一次的４份拷贝中至少会有一份只有２组，则必 然会再需要进行下一轮操作，以此类推。这样重复的 多轮操作不仅意义有限，还有可能造成线程数的迅速 膨胀，对于算法整体的效率造成影响，因此如果数据 的绝对数量可以接受，则直接进行计算而不剔除超过 ５０％的一组。③在不满足第２种的情况下，剩余位数 不大于３，这很明显只能计算一组中所有的数据之间 的海明距离。 与传统算法对比，本算法的一个优点：如果原始 数据出现大量位数相同的情况，那么在传统的Ｓｉｍ． ｈａｓｈ算法中会有若干个线程的执行时间显著地高于 其他线程，而在本算法中可以通过多次分配数据，添 加新的线程或者分配新任务到已经完成任务的线程 上，使得各线程的执行时间更加平均，各线程单次任 务的平均时间缩短使线程的分配更加灵活。 ４实验结果与分析 为了检验本算法的有效性和效率，并与传统的算 法进行比较，采用一定数量的微博数据作为输入进行 验证。由于主要目的是对比，因此采用单机进行实 验，数据量取在２０万条以内，数据平均的长度在２０ 汉字左右。 实验环境： ＣＰＵ：Ｉｎｔｅｌ＠Ｘｅｏｎ＠ＣＰＵ Ｅ３．１２３１ ｖ３＠３．４０ ＣＨ 内存：８ ＧＢ 操作系统：６４ ｂｉｔ Ｗｉｎｄｏｗｓ７ 需要说明的是，由于Ｉｎｔｅｌ现在的ＣＰＵ采用了超 线程技术，因此在本次实验中不论是传统的Ｓｉｍｈａｓｈ 算法还是改进后的算法，都不会由于线程数过多而产 生ＣＰＵ的瓶颈。 一传统Ｓｉｍｈａｓｈ 圈改进方法 一Ｌ 图 ５Ｏ０００ １Ｏ０Ｏ００ ２ＯＯ００Ｏ 图１比对次数统计 ２５０ｏ ２０００ １５００ 一传统Ｓｉｍｈａｓｈ 晕１０００ 豳改进方法 ５ｏ０ ０ 一＿嘲 霾 ５００００ ｌ０００００ ２０００Ｏ０ 图２运行时间统计 图１展示了传统方法与改进后方法的总比较次 数差异，传统的方法由于需要逐个比对，除去之前提 到的小优化，其总的比较次数是相当高的。而对比图 ２总运行时间可以明显看出，传统方法中即使是比较 一定位数的相同而不计算海明距离也是非常消耗时 间的。但是改进后方法对于时间的提升并没有比较 次数那么显著，一方面说明海明距离的计算还是占主 要的时间消耗，另一方面线程池的控制和数据分组也 会占用一部分的时间。 １Ｏ０％ ８０％ ６０％ 传统Ｓｉｍｈａｓｈ ４０％ 传统Ｓｉｍｈａｓｈ（＝０） ２０％ Ｏ％ 改进方法 ５￣）００ ｌＩ Ｈ ＨＨＩＵ ２Ｌ）【Ｊ【儿ＪＯ 图３准确率统计 图３展示了改进后的相似率计算方法在准确率 上的表现。因为无法统计原数据中重复的数据量，因 此对于每一种方法随机取出２００对重复的数据，通过 人工检查得出每一种方法的准确率。其中方法二是 传统的Ｓｉｍｈａｓｈ方法并限定在海明距离为０的情况。 通过图表可以看出，传统方法在处理中文数据时会误 判大量的数据，即使海明距离设定为０也是如此，而 改进后的方法对于准确率有很大的提高。在准确率 得到提升的同时，召回率显然会有所下降，但是改进 后方法得到的重复数据数量大约是传统方法的 ２０１７年第７期 周春晖：基于Ｓｉｍｈａｓｈ的大数据去重改进算法 ［５］ Ｎｇ Ｗ Ｋ，Ｗｅｎ Ｙｏｎｇｇａｎｇ，Ｚｈｕ Ｈｕａｆｅｉ．Ｐｒｉｖａｔｅ ｄａｔａ ｄｅｄｕ— ４０％，结合准确率来看召回率的下降应该是在可以接 受的范围内。另外，在实际的用途中，去重后的数据 将用来进行数据分析，保留少量的重复数据比删除不 重复的数据要更加合理。 ｐｌｉｃａｔｉｏｎ ｐｍｔｏｃｏｌｓ ｉｎ ｃｌｏｕｄ ｓｔｏｒａｇｅ［Ｃ ３／／ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ａｐｐｌｉｅｄ Ｃｏｍｐｕｔｉｎｇ．２０１２：４４１—４４６． ［６］ Ｉｓｓａ Ｎ Ｔ，Ｂｙｅｒｓ Ｓ Ｗ，Ｄａｋｓｈａｎａｍｕｒｔｈｙ Ｓ．Ｂｉｇ ｄａｔａ：Ｔｈｅ ｎｅｘｔ ｆｒｏｎｔｉｅｒ ｆｏｒ ｉｎｎｏｖａｔｉｏｎ ｉｎ ｔｈｅｒａｐｅｕｔｉｃｓ ａｎｄ ｈｅａｌｔｈｅａｒｅ ５ 结束语 本文基于中文微博数据对传统的Ｓｉｍｈａｓｈ去重 算法进行了改进，提出了考虑文本重复率计算文本相 似度的方法，以及利用桶排序和多次多级线程分配检 索相似Ｓｉｍｈａｓｈ值的方法。该方法比较周全地考虑了 数据的分布规律以及可能发生的较差情况。实验结果 ［Ｊ］．Ｅｘｐｅｒｔ Ｒｅｖｉｅｗ ｏｆ Ｃｌｉｎｉｃａｌ Ｐｈａｒｍａｃｏｌｏｇｙ，２０１４，７ （３）：２９３． ［７］ 周玉坤，冯丹，夏文，等．面向数据去重的基于二次哈希 的收敛加密策略［Ｊ］．计算机工程与科学，２０１６，３８ （９）：１７５５—１７６２． ［８］ 杨天明，吴海涛．一种批处理块级数据去重方法［Ｊ］．计算机应用与软件，２０１６，３３（５）：４４４６． ［９］ 罗恩韬，王国军，李超良．大数据环境中多维数据去重 表明，本文的算法明显提高了Ｓｉｍｈａｓｈ算法整体的效 率和准确率，为数据的进一步分析提供了良好的基 础。 参考文献： 的聚类算法研究［Ｊ］．小型微型计算机系统，２０１６（３）： ４３８．４４２． ［１Ｏ］ 武晓岩，李康．基因表达数据判别分析的随机森林方法 ［Ｊ］．中国卫生统计，２００６，２３（１２）：４９１． Ｙｕ Ｙｕａｎ，Ｉｓａｒｄ Ｍ，Ｆｅｔｔｅｒｌｙ Ｄ，ｅｔ １．Ｄｒａｙａｄ ＬＩＮＱ：Ａ ｓｙｓ・ ｔｅｍ ｆｏｒ ｇｅｎｅｒａｌ－－ｐｕｒｐｏｓｅ ｄｉｓｔｒｉｂｕｔｅｄ ｄａｔａ・・ｐａｒｌｌａｅｌ ｃｏｍｐｕｔｉｎｇ ［１］Ｓｔｏｒｅｒ Ｍ Ｗ，Ｇｒｅｅｎａｎ Ｋ，Ｌｏｎｇ Ｄ Ｄ Ｅ，ｅｔ ａ１．Ｓｅｃｕｒｅ ｄａｔａ ｄｅ— ｄｕｐｌｉｃａｔｉｏｎ［ｃ］／／ＡＣＭ Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｔｏｒａｇｅ Ｓｅｃｕｒｉｔｙ＆Ｓｕｒ－ ｖｉｖａｂｉｌｉｔｙ．２Ｏ０８：１—１０． ｕｓｉｎｇ ａ ｈｉｇｈ—ｌｅｖｅｌ ｌｎｇｕａａｇｅ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ８ｔｈ ＵＳＥＮＩＸ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍ Ｄｅｓｉｇｎ ａｎｄ Ｉｍ— ｐｌｅｍｅｎｔａｆｉｏｎ．２００８：１—１４． ［２］ Ｍｅｉｓｔｅｒ Ｄ，Ｂｒｉｎｋｍａｎｎ Ａ．Ｍｕｌｔｉ—ｌｅｖｅｌ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｄａｔａ ｄｅｄｕｐｌｉｃａｔｉｏｎ ｉｎ ａ ｂａｃｋｕｐ ｓｃｅｎａｌ￣ｏ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＳＹＳＴＯＲ ２００９：Ｔｈｅ Ｉｓｒａｅｌｉ Ｅｘｐｅｒｉｍｅｎｔａｌ Ｓｙｓｔｅｍｓ Ｃｏｎｆｅｒ－ ｅｎｃｅ．２００９：Ｉ一１２． Ａ，ｅｔ ａ１．Ｓｔａｔｉｓｔｉｃａｌ ｐｒｏｐ— ［１２］ Ｌｅｓｋｏｖｅｃ Ｊ，Ｌａｎｇ Ｋ Ｊ，Ｄａｓｇｕｐｔｅｒｔｉｅｓ ｏｆ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｌａｒｇｅ ｓｏｃｉｌ ａｎｄ ｉｎａｆｏｒｍａｔｉｏｎ ｎｅｔｗｏｒｋｓ［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １７ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎ— ｆｅｒｅｎｃｅ ｏｎ Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ．２００８：６９５－７０４． ［３］ Ｒａｍａｓｗａｍｙ Ｓ，Ｒａｓｔｏｇｉ Ｒ，Ｓｈｉｍ Ｋ．Ｅｆｉｆｃｉｅｎｔ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｍｉｎｉｎｇ ｏｕｔｌｉｅｒｓ ｆｒｏｍ ｌａｒｇｅ ｄａｔａ ｓｅｔｓ［Ｊ］．ＡＣＭ Ｓｉｇｍｏｄ Ｒｅ－ ｃｏｒｄ，２０００，２９（２）：４２７－４３８． ［４］ Ｃｈａｒｉｋａｒ Ｍ Ｓ．Ｓｉｍｉｌａｒｉｔｖ ｅｓｔｉｍａｔｉｏｎ ｔｅｃｈｎｉｑｕｅｓ ｆｒｏｍ ｒｏｕｎ． Ｓｅｒｇｅｙ Ｂ，Ｌａｒｒｙ Ｐ．Ｔｈｅ ａｎａｔｏｍｙ ｏｆ ａ ｌｒｇｅ—ｓｃａｌａｅ ｈｙｐｅｒｔｅｘ— ［１３］ ｔｕａｌ Ｗｅｂ ｓｅａｒｃｈ ｅｎｇｉｎｅ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋｓ ａｎｄ ＩＳＤＮ Ｓｙｓｔｅｍｓ，１９９８，３０（１７）：１０７—１１７． ｄｉｎｇ ａｌｇｏｒｉｔｈｍｓ［Ｃ］／／Ｔｈｅ ３４ｔｈ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｔｈｅｏ— ｒｙ ｏｆ Ｃｏｍｐｕｔｉｎｇ．２００２：３８０－３８８． ◆Ｉｌ◆－●１◆－…●◆－● （上接第３７页） ｌ９ ｌ Ｄｕｍｉｔｒｕ Ｃ．Ｄｅｔｅｃｔｉｎｇ ｓｏｆｔｗａｒｅ ｖｕｌｎｅｒａｂｉｌｉｔｉｅｓ ｓｔａｔｉｃ ｔａｉｎｔ ａ． ＡＣＭ，１９９０，３３（１２）：３２－４４． Ｇａｎｅｓｈ Ｖ，Ｄｉｌｌ Ｄ Ｌ．Ａ ｄｅｃｉｓｉｏｎ ｐｒｏｃｅｄｕｒｅ ｆｏｒ ｂｉｔ・ｖｅｃｔｏｒｓ ［１５］ ｎａｌｙｓｉｓ［Ｄ］．Ｂｕｃｈａｒｅｓｔ：Ｕｎｉｖｅｒｓｉｔｙ Ｐｏｌｉｔｅｈｎｉｃａ ｏｆ Ｂｕｃｈａ－ ｒｅｓｔ，２００９． ｎｄ ａａｒｒａｙｓ［ｃ］／／Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ａｉ— ｄｅｄ Ｖｅｒｉｆｉｃａｔｉｏｎ．２００７：５１９－５３１． ［１０］Ｎｅｔｈｅｒｃｏｔｅ Ｎ，Ｗａｌｓｈ Ｒ，Ｆｉｔｚｈａｒｄｉｎｇｅ Ｊ．Ｂｕｉｌｄｉｎｇ ｗｏｒｋｌｏａｄ ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ ｔｏｏｌｓ ｗｉｔｈ ｖａｌｇｒｉｎｄ『Ｃ］／／２００６ ＩＥＥＥ Ｉｎ． ｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｗｏｒｋｌｏａｄ Ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ．２００６：２． ｎｍｌｅｙ Ｄ，Ｊａｇｅｒ Ｉ，Ａｖｇｅｒｉｎｏｓ Ｔ，ｅｔ ａ１．ＢＡＰ：Ａ ｂｉｎａｒｙ ａ・ ［１６］ Ｂｒｎａｌｙｓｉｓ ｐｌａｔｆｏｒｍ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｖｅｒｉｉｆｃａｔｉｏｎ．２０１ １：４６３－４６９． ［１１］Ｋｉｎｇ Ｊ Ｃ．Ｓｙｍｂｏｌｉｃ ｅｘｅｃｕｔｉｏｎ ａｎｄ ｐｒｏｇｒａｍ ｔｅｓｔｉｎｇ［Ｊ］． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ，１９７６，１９（７）：３８５－３９４． Ｂｒｎｍｌｅｙ Ｄ，Ｊａｇｅｒ Ｉ，Ｓｃｈｗａｒｔｚ Ｅ Ｊ，ｅｔ ａ１．Ｔｈｅ ＢＡＰ Ｈａｎｄ— ［１７］ ｂｏｏｋ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｂａｐ．ｅｃｅ．ｃｍｕ．ｅｄｕ／ｄｏｅ／ｂａｐ．ｐｄｆ， ２００９－０７．１０． ｒｏｉｄ Ｐ，Ｌｅｖｉｎ Ｍ Ｙ，Ｍｏｌｎａｒ Ｄ Ａ．Ａｕｔｏｍａｔｅｄ ｗｈｉｔｅ－ ［１８］ Ｇｏｄｅｆ［１２］姚伟平，王震宇，刘建林，等．二进制代码覆盖率评估系 统的设计与实现［Ｊ］．计算机工程与设计，２０１１，３１ （２４）：５２６２－５２６４． ｂｏｘ ｆｕｚｚ ｔｅｓｔｉｎｇ［Ｃ］／／Ｎｅｔｗｏｒｋ ａｎｄ Ｄｉｓｔｉｒｂｕｔｅｄ Ｓｙｓｔｅｍ Ｓｅ— ｃｕｒｉｔｙ Ｓｙｍｐｏｓｉｕｍ．２００８：１５１－１６６． ａ１．Ｐｉｎ：Ｂｕｉｌｄｉｎｇ ｃｕｓｔｏｍ— ［１９］ Ｌｕｋ Ｃ Ｋ，Ｃｏｈｎ Ｒ，Ｍｕｔｈ Ｒ，ｅｔｉｚｅｄ ｐｒｏｇｒａｍ ａｎａｌｙｓｉｓ ｔｏｏｌｓ ｗｉｔｈ ｄｙｎａｍｉｃ ｉｎｓｔｒｕｍｅｎｔａｔｉｏｎ ［１３］Ｋｉｎｄｅｒ Ｊ，Ｖｅｉｔｈ Ｈ．Ｊａｋｓｔａｂ：Ａ ｓｔａｔｉｃ ａｎａｌｙｓｉｓ ｐｌａｔｆｏｒｍ ｆｏｒ ｂｉｎａｒｉｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ｔｈｅ ２０ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒ・ ｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｖｅｒｉｆｉｃａｔｉｏｎ．２００８：４２３－４２７． ［１４］Ｍｉｌｌｅｒ Ｂ Ｐ，Ｆｒｅｄｒｉｋｓｅｎ Ｌ，Ｓｏ Ｂ．Ａｎ ｅｍｐｉｉｒｃａｌ ｓｔｕｄｙ ｏｆｔｈｅ ｒｅｌｉａｂｉｌｉｔｙ ｏｆ ＵＮＩＸ ｕｔｉｌｉｔｉｅｓ ｆ Ｊ］．Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ［Ｃ］／／ＡＣＭ ＳＩＧＰＬＡＮ Ｎｏｔｉｃｅｓ．２００５，４０（６）：１９０－２００．