基于Wu—Manber算法的大规模URL模式串匹配算法

贾博威+吴志刚+张树壮

摘要：大规模高速URL匹配是许多网络安全系统中的关键技术，经典串匹配算法在大规模URL情况下有许多限制。针对URL数据的特点在经典多模式串匹配算法Wu-Manber基础上提出XWM-Tree算法和XWM-Hash算法。算法应用了模式串窗口选择，两阶段哈希和关联容器组织冲突链表等多种优化手段，大幅度提高了算法的匹配性能。在大规模真实数据集上的测试结果表明本文提出的算法匹配速度可以提高一倍以上，尤其是当最短模式串较长的时候更有优势。

关键词： 多模式串匹配； URL匹配； Wu-Manber算法

中图分类号：TP391

文献标志码：A

文章编号：2095-2163（2017）05-0004-06

JIA Bowei， WU Zhigang， ZHANG Shuzhuang

Institute of Network Technology， Beijing University of Posts and Telecommunications， Beijing 100876， China）

Abstract：

Largescale highspeed URL matching is a key technology in many network security systems The classical pattern string matching algorithm has many limitations in largescale URLs In this paper， based on the WuManber algorithm， the XWMTree and XWMHash are proposed for URL matching The algorithm proposed in this paper applies a variety of optimization methods to speed up matching performance， such as optimal window selection， twophase hash and associative data structure The test on the real data set shows that the algorithms proposed in this paper has better matching performance than other algorithms， especially when the shortest pattern string is longer and the matching speed is about twice than other algorithms

Keywords：multistring matching； URL matching； WuManber algorithm

基金項目： 国家重点研发计划资助项目（2016YFB0801200）。

收稿日期： 2017-08-28

0引言

多模式串匹配是计算机科学领域的一个经典问题，所谓多模式串匹配就是在给定一个模式串集合P={p1，p2，…，pr}的情况下，（其中pi=pi1pi2…pim）对于一个任意给定的字符串T=t1t2…tn，找出P中的字符串在T中所有的出现位置。这里称P为模式串集合，pi为模式串，T为文本串，并且P和T都是定义在字母表Σ上的字符串。

多模式串匹配在网络信息安全领域有着十分广泛的应用，包括网络入侵检测/防御系统（IDS/IPS）、防火墙系统、垃圾邮件检测系统和反病毒系统等[1]。除此之外，串匹配技术在其它领域也有十分广泛的应用，如拼写检查、语言翻译、数据压缩、搜索引擎等[2]。目前，超文本传输协议（Hypertext Transfer Protocol， HTTP）是互联网领域应用最广泛的协议之一，除了传统的桌面端应用之外，很多移动端应用也使用HTTP协议作为承载协议。URL在HTTP协议中是最重要的一个域，标识着被请求的资源的位置[3]。对有害的URL进行过滤可以有效地对访问非法、有害等不良信息内容进行控制与管理。在海量的URL数据中检测有害信息需要消耗大量的计算资源和存储资源，在这种情况下如何保证串匹配算法正确高效地运行，是当前网络信息安全领域面临的一个重大难题。目前，在大规模URL匹配方面已有学者进行研究[4-6]，但是还未达到实际系统中的应用需求，亟待进一步的探讨研究。

本文在经典多模式串匹配算法Wu-Manber[7]的基础上结合URL数据的特点提出改进措施，大幅度提高了算法的匹配性能，尤其在最短模式串长度较长的时候则更具优势。本文第二节论述了大规模URL模式串匹配的相关工作；第三节详细介绍了本文提出的改进措施和算法；第四节将本文的改进算法和其它串匹配算法进行实验评估；第五节是本文的结论。

1相关工作

URL匹配是模式串匹配的一种特殊应用，目前主要有2种解决方法：一种是直接使用经典的模式串匹配方法，另一种是在经典模式串的基础上结合URL的特点进行改进。

经典模式串应用于大规模URL匹配方面大致可以分为3类：基于自动机的多模式串匹配算法、基于哈希表的多模式串匹配算法和基于位并行的多模式串匹配算法。在此，可做基础阐释如下。

1）基于自动机的匹配算法的典型代表是AC算法[8]和SBOM算法[9]，该类算法匹配性能稳定，不受模式串长度和统计特征的影响，算法时间复杂度正比于待匹配文本串的长度。应用于大规模URL串匹配时，该类算法的主要问题是存储自动机需要消耗巨大的内存。针对以上问题，文献[10]在AC算法基础上运用统计策略提出基于数据访问特征的混合自动机构建算法，在真实的数据上测试表明这种改进能够压缩掉5%的内存。endprint

2）基于哈希的多模式串匹配算法是以哈希表作为基本数据结构并使用字符块技术来增大文本串和模式串不匹配的可能性，从而提高跳跃的机会。该类算法的典型代表是Wu-Manber算法[7]，该算法在十万规模的随机字符串上能够取得较好的匹配效果。但是由于URL数据是一种带有语义特征的数据，其字符的分布并不具有随机性，因此在大规模URL匹配中Wu-Manber算法由于严重的哈希冲突导致性能十分低劣。文献[11]提出HashTrie算法，该算法利用递归散列技术将模式串集合信息存储在位向量中，并用rank操作进行快速校验，该算法比AC算法能够节约高达996%的内存开销，但是实际匹配性能却只有AC算法的一半左右，并不适合高速匹配的应用环境。

3）基于位并行的算法是用位向量来模拟自动机的匹配过程，将自动机的状态跳转表示为位向量的运算，利用机器字来并行执行。这类算法的代表是shift-and和shift-or算法[5]，但是该类算法受限于机器字长只在小规模模式串的时候取得较好的匹配效果，不适用于大规模URL模式串匹配。文献[12]利用q-gram技术对shift-or和BNDM算法[13]进行拓展，基本思想是：将多个模式串利用q-gram技术规约成一个简单的模式串，然后使用快速的单模式串匹配技术快速过滤掉不可能匹配的文本，但是这种技术只能在1～10万规模的模式串上取得较好的效果，不适合大规模模式串匹配。

目前，在大规模URL匹配方面已有学者展开广泛研究。文献[4]提出一种基于过滤的SOGOPT算法，该算法基于经典的SOG算法结合模式串窗口选择和分组规约两种优化技术，大幅度提高了算法的匹配性能。但是该算法受限于系统的机器字长和最短模式串的长度，当机器字长较短或者模式集的最短模式串长度较长时，能够同时并行搜索的模式串个数减少，导致算法的匹配性能降低。文献[6]结合哈希技术和双数组Trie数据结构提出TFD算法，该算法是在哈希表中冲突的节点上建立双数组Trie树结构来加快精确校验的过程。但是，由于算法中使用了Trie数据结构，因此该算法的内存消耗和双数组AC自动机具有相当的量级，限制了该算法的应用。文献[5]以“/”和“”将URL分块，在此基础上设计基于URL过滤的算法能够取得较高的匹配性能，但是这种方法只支持分块URL前缀匹配，并不支持子串匹配，限制了其应用范围。

综上所述，目前针对多模串匹配研究主要围绕通用串匹配方面，针对大规模URL匹配方面近年来已有学者开始关注，但还少见推出有效的算法。本文在Wu-Manber算法的基础上，针对URL的特点，从降低哈希冲突和减少精确比对次数的角度出发，采用窗口选择、两阶段哈希和关联容器组织冲突链表等多种优化技术，提高了算法的匹配性能。

[BT4]2本文算法设计研究

本节提出一种面向大规模URL模式串匹配的串匹配算法，该算法在经典的串匹配算法Wu-Manber的基础上，针对URL数据的特点进行优化，以适应大规模URL模式串匹配的需求。本文主要通过以下3种优化方法提高匹配性能：

1）将文献[4]中的模式串窗口选择技术应用在算法中。模式串窗口选择技术能够为每个模式串选择出一个独特且具有代表性的窗口来唯一代表每个模式串，因此在用哈希函數进行哈希的时候能够显著降低各个模式串被放入同一个桶中的概率。

2）采用两阶段哈希。算法中使用了2个压缩的哈希表来存储匹配过程中的跳转值。使用2个压缩的哈希表能够在保证哈希均匀的情况下大幅度降低内存的使用。

3）使用关联容器组织冲突模式串，并取消Wu-Manber算法中的prefix表。关联容器具有根据键值快速查找的能力，能够显著减少校验时的比对次数。

本文在21节中分析了Wu-Manber算法在大规模URL匹配中的缺点和不足。针对Wu-Manber算法的缺点，在22～24节分别介绍了本文使用的3种优化技术。在25节给出了本文提出的算法的预处理和匹配过程。

21Wu-Manber算法分析

Wu-Manber算法是Sun Wu[7]在1994年提出的经典多模式串匹配算法，该算法利用“坏字符”跳转的思想。在预处理阶段建立3张哈希表，分别为shift表、hash表和prefix表。在扫描文本串的时候，shift表根据读入字符串决定向后跳转的字符数。hash表用来存储尾块字符散列值相同的模式串。prefix表用于存储尾块字符散列值相同的模式串的首块字符散列值。在匹配的过程中，如果当前文本串的shift值为0，则说明可能产生了匹配，需要进一步验证；此时需要在prefix表中验证尾块相同模式串的前缀是否也相同，如果相同则在尾块相同的hash表中逐一验证来查找是否有匹配发生。

当将Wu-Manber算法直接应用于大规模URL匹配的时候，匹配性能低下，主要有2方面的原因，具体表述如下：

1）哈希冲突严重。一方面，Wu-Manber算法采用2～3个字节作为哈希时的字符块，这在中小规模模式串匹配中没有问题，当模式串规模增大时哈希冲突将会非常严重；另一方面，URL数据本身是一类带有语义的数据，因为大量的URL都具有相同的前缀和/或后缀[5]， Wu-Manber算法直接使用模式串最左边m个字符串作为匹配窗口，这将导致很多模式串都具有相同的匹配窗口，因此哈希冲突将非常严重。

2）精确校验耗时严重。Wu-Manber算法在匹配的过程，当shift值为0的时候，就要进入精确校验阶段。由于冲突的模式串在hash表中是以单链表的形式存储的，在校验的时候就要遍历单链表来逐一检查是否有匹配发生。而URL数据经常具有相同的前缀，导致具有相同前缀的冲突链表很长，所以当遍历冲突链表查找精确匹配的模式串的时候将消耗大量的CPU时间。

[BT5]22模式串窗口选择

模式串窗口选择技术是刘燕兵[4]等人在优化SOG算法的时候提出的，这种优化技术不仅能够用在SOG算法的优化中，同样也能用在Wu-Manber算法中。在原始的Wu-Manber算法中，会选取最短模式串的长度m做为匹配窗口值，然后截取所有模式串的最左边m个字符作为每个模式串的窗口。但是由于URL数据是一类字符分布极不均匀的数据，URL数据中存在大量的相同的前缀或相同的后缀[5]，导致大量的模式串具有相同的匹配窗口。模式串窗口选择技术能够为每个模式串选择出一个独特且具有代表性的窗口来唯一代表每个模式串，从而减少哈希冲突。本文提出的模式串匹配算法是在此基础上设计得到的。endprint

例如，对于模式串集合P={googlecom， googlecomhk， googlecomtw， googlecomjp， googlecomtr}，如果用最左边10个字符作为所有模式串的窗口，则所有的模式串集合都将具有相同的匹配窗口googlecom，因此在哈希的时候模式串集合中的5个模式串都将会哈希到同一个桶中，而且这种冲突不是使用更好的哈希函数就能解决的。使用窗口选择技术处理模式串集合之后，每个模式串的匹配窗口如表1所示，可以看出每个模式串都具有不同的匹配窗口，因此这将降低不同模式串哈希到同一个桶中的概率。

为了解决内存占用的问题，本文使用2个压缩的哈希表来提高算法的匹配性能，同时使算法的内存消耗维持在一个较低水平。这里同样称这2个哈希表为shift表和hash表，并设置shift表和hash表分别具有2m和2n个条目，同时使用哈希函数h1和h2进行映射，其中h1將长度为B的字符块映射成长度为m个二进制位的值，h2将长度为B的字符块映射成长度为n个二进制位的值。这里，shift表用于在扫描文本串的时候，根据读入字符串决定可以跳过的字符数；hash表中每个条目用来组织存储尾块字符散列值相同的模式串。事实上，如果当前验证的字符块在其它模式串中从未出现或不在其它模式串匹配窗口的右端出现时，当前匹配的滑动窗口可以向后移动更大的距离，为此本文提出的算法在hash表中添加一个skip值，用于精确验证后向后跳转。在匹配的过程中对当前匹配窗口中后B个字符串先用h1进行计算，如果shift表项不为0，则向后跳转；如果shift表项为0，则表示可能有匹配；这时用h2对当前匹配窗口中的后B个字符块计算哈希值并查看hash表中相应的表项，如果有冲突的模式串，则进行精确验证，并在验证之后使用skip值让当前文本的匹配窗口向后跳转，否则，根据hash表项中的skip值让当前匹配窗口向后跳转。

24使用关联容器组织冲突节点

在Wu-Manber算法中，验证prefix表之后，每当有可能产生匹配都要在hash表相应的冲突链表中逐个验证是否有完全一致的模式串。逐一验证过程是一个非常耗时的操作，为了减少验证的次数并充分利用在22节中选择出的窗口，本文提出的算法在hash表中为冲突的节点使用关联容器来组织冲突链表，并取消了Wu-Manber算法中的prefix表。

关联容器是一类可以通过键值高效地存储和读取元素的数据结构，其底层实现通常是某种形式的平衡二叉树或者哈希表，本文分别使用这2种数据结构实现了XWM-Tree算法和XWM-Hash算法（eXtend Wu-Manber algorithm），算法性能对比在第3部分。使用关联容器的关键是如何为给定的模式串构造出键值。Wu-Manber算法中prefix表是用于存储尾块字符散列值相同的模式串的首块字符散列值，这里为取代prefix表的功能，本文使用每个模式串匹配窗口的长度为l=m-B的前缀哈希值作为每个模式串的键值。因此这种冲突模式串的组织形式完全可以替代prefix表的功能，而又不会影响算法的正确性。由于这里只需要验证具有相同键值的模式串，而键值的查找可以通过关联容器的特性快速查找，因此在进行校验的时候可以大幅减少校验次数。25算法描述

本文提出的算法分为预处理和扫描两个阶段。预处理主要包括使用窗口选择技术为每个模式串选择出具有代表性匹配窗口，然后根据每个模式串匹配窗口的后缀字符块生成shift表和hash表，并根据匹配窗口的前缀字符串计算出键值，将每个模式串插入到hash表中相应的关联容器中。图1是预处理的示意图，其中灰色部分表示利用模式串窗口选择技术为每个模式串选出的匹配窗口，浅灰色部分为用于计算shift表和hash表的模式串窗口的尾块字符，深灰色部分是用于计算键值的模式串窗口的前缀串，hash表中的map字段存放指向关联容器的指针，通过该指针和计算出的键值可以将模式串分别插入到hash表中相应的条目中。

当预处理结束后就可以进入扫描匹配阶段，算法1是扫描匹配的伪代码描述。匹配的过程中需要维持一个大小为m的匹配窗口，其中3～12行是用当前文本匹配窗口的后缀字符串计算shift值，如果shift值不为0则让当前文本向后跳转；13～18行是处理shift值为0的情况，这时用当前文本的匹配窗口的后缀字符串计算哈希值来索引hash表中相应表项，如果关联容器不为空则计算匹配窗口的前缀哈希值作为键值，通过该键值在关联容器中查找并进行比对。第19行是在进行精确校验之后向后跳转的过程。

3实验评估

本文从匹配速度和内存消耗两个方面分别将使用平衡二叉树和哈希表组织冲突的XWM-Tree和XWM-Hash算法与SOGOPT算法（使用64位机器字长）、TFD算法、双数组AC算法（da_ac）进行比较。此外，本文还讨论了最短模式串长度对算法的影响。在XWM-Tree和XWM-Hash算法中，α=075， m=28，n=24。

31实验数据和实验环境

本文使用的数据是从骨干路由器上采集去重后的8 000万条URL数据（约15 GB），并从这些URL数据中提取出1 000多万条模式串，最短模式串长度为8，最长模式串长度为128。

实验的软硬件环境如下：CPU为Intel Xeon E5-2650 v3 @23 GHz；内存为32 GB；操作系统为Red Hat Enterprise Linux Server release 70 （Maipo），内核版本为3100-123el7x86_64。所有代码均使用C++语言编写，使用g++ 482编译，在编译的过程中开启-O3优化。所有的程序都采用单线程运行。

32实验结果及分析

从图2～图5可以看出无论是使用平衡二叉树组织冲突模式串的XWM-Tree算法，还是使用哈希表组织冲突的XWM-Hash算法都比其它算法具有较高的匹配性能。当最短模式串长度为8时，XWM-Tree算法、XWM-Hash算法和SOGOPT算法在1 000万模式串的情况下具有相当的匹配速度，且都比双数组AC算法和TFD算法具有更高的匹配速度。当最短模式串的长度较长时本文提出的算法的优势逐渐显现出来，无论是XWM-Tree算法，还是XWM-Hash算法在最短模式串长度较长的时候，匹配速度都是其它算法的2倍左右；而SOGOPT算法随着最短模式串长度的逐渐增长，分组规约的组数逐渐减少，校验时的比较次数增加，因此算法性能逐渐下降。双数组AC算法和TFD算法由于采用双数组Trie数据结构，受最短模式串长度和模式串数量的影响较小，匹配性能比较稳定。使用哈希表组织冲突的XWM-Hash算法比使用平衡二叉树组织冲突的XWM-Tree算法匹配速度略低。endprint

从图6～9中可以看出，在内存消耗方面，XWM-Tee算法和XWM-Hash算法由于采用的是2个压缩的哈希表，因此能够维持内存消耗在一个较低的水平。当模式串数量在100～700万的时候，本文提出的算法内存消耗要比SOGOPT算法略高，但当模式串数量达到1 000万时，XWM算法和SOGOPT算法具有相当的内存消耗，且都明显低于TFD算法和双数组AC算法。而XWM-Hash算法由于是采用哈希表组织的冲突模式串，内存消耗要比XWM-Tree算法严重，即便如此当达到1 000万模式串的时候XWM-Hash算法消耗也还不到2 GB内存，这大大低于双数组AC算法和TFD算法近8 GB的内存消耗。[JP]

4结束语

在网络日益发展的今天，大规模URL匹配过滤是目前网络安全系统中亟待解决的問题，本文在经典的多模式串匹配算法Wu-Manber的基础上，针对URL数据的特点，从降低哈希冲突和减少精确比对次数的角度出发，利用多种优化技术提高了匹配性能，并且使得算法的内存消耗维持在较低的水平，真实数据上的测试表明，本文提出的算法与其它算法相比在大规模URL匹配方面能够提高一倍以上的性能，适用于运营商级别的应用环境中。

参考文献：

张树壮， 罗浩， 方滨兴 大规模复杂规则匹配技术研究[J] 高技术通讯， 2010，20（12）： 1217-1223

[2] 郭莉， 谭建龙，刘萍，等 面向信息内容安全的串匹配技术[C]// 2008年互联网新媒体新技术研讨会论文集 深圳： 国务院新闻办公室网络局，2008： 30-60

[3] 赵思远 HTTP 协议头及错误码详解[J] 计算机与网络， 2016， 42（11）： 40-43

[4] 刘燕兵， 邵妍， 王勇， 等 一种面向大规模URL过滤的多模式串匹配算法[J] 计算机学报， 2014，37（5）：1159-1169

[5] 徐东亮 高性能在线模式匹配算法研究[D] 哈尔滨：哈尔滨工业大学， 2015

[6] YUAN Zhenlong， YANG Baohua， REN Xiaoqi， et al TFD： A multipattern matching algorithm for largescale URL filtering[C]//Computing， Networking and Communications （ICNC）， 2013 International Conference onBeijing，China： IEEE， 2013： 359-363

[7] [JP4]Wu S， Manber U A fast algorithm for multipattern searching[R]Tucson， AZ： Department of Computer Science， University of Arizona， 1994 [JP]

[8] [JP4]AHO A V， CORASICK M J Efficient string matching： An aid to bibliographic search[J] Communications of the ACM， 1975， 18（6）： 333-340[JP]

[9] ALLAUZEN C， CROCHEMORE M， RAFFINOT M Factor oracle： A new structure for pattern matching[C]//International Conference on Current Trends in Theory and Practice of Computer Science Springer Berlin Heidelberg， 1999： 295-310

[10]熊刚， 何慧敏， 于静， 等 HybridFA： 一种基于统计的 AC 自动机空间优化技术[J] 通信学报， 2015， 36（7）： 31-39

[11]张萍， 刘燕兵， 于静， 等 HashTrie： 一种空间高效的多模式串匹配算法[J] 通信学报， 2015， 36（10）： 172-180

[12]SALMELA L， TARHIO J， KYTJOKI J Multipattern string matching with qgrams[J] Journal of Experimental Algorithmics （JEA）， 2006， 11（11）：1-19

[13]NAVARRO G， RAFFINOT M A bitparallel approach to suffix automata： Fast extended string matching[C]//Combinatorial Pattern Matching Berlin/Heidelberg：Springer ， 1998： 14-33

3结束语

本文首次将广义拓扑熵应用于人类参考基因组片段复制的研究中。实验结果表明，片段复制区域序列的广义拓扑熵低于参考基因组中随机选取区域的广义拓扑熵，这说明广义拓扑熵可以有效地将片段复制区域与其他DNA序列区域区分开来。广义拓扑熵可为参考基因组的片段复制区域识别及个人基因组拷贝数复制的精准识别奠定基础并提供新的解决思路。

广义拓扑熵有2个显著的优势：

1）理论上，可以证明广义拓扑熵是拓扑熵的推广，是拓扑熵的完整表达形式。广义拓扑熵可以全面继承拓扑熵在DNA序列分析上的各项优势。

2）广义拓扑熵充分考虑了子串本身的序列复杂度，可以更加全面地分析DNA序列的复杂性。通过广义拓扑熵在人类参考基因组片段复制区域及随机选取区域上的序列对照研究，实验结果表明：广义拓扑熵可以将片段复制区域与随机选取区域进行较好的区分，取得了显著的实验效果。endprint

理論上，基因组拼接方法可以实现个人基因组变异的精准识别。然而，拼接方法目前在拷贝数复制区域尚未取得突破性的进展。虽然广义拓扑熵在参考基因组片段复制的分类方面取得理想效果，但仍然期待更为成熟的测序技术以及更为先进的基因组拼接算法来实现个人基因组在拷贝数复制区域的成功拼接[16-17]。届时，随着高通量测序技术的逐渐成熟以及拼接算法的不断完善，利用广义拓扑熵对个人基因组拷贝数复制进行精准识别和预测将具有广阔的应用前景。

参考文献：

A， EICHLER E E Primate segmental duplications： Crucibles of evolution， diversity and disease[J] Nature reviews Genetics， 2006， 7（7）： 552-564

[2] GIRIRAJAN S， CAMPBELL C D， EICHLER E E Human copy number variation and complex genetic disease[J] Annu Rev Genet， 2011， 45：203-226

[3] LORENTZ G G Metric entropy and approximation[J] Bulletin of the American Mathematical Society，1966，72： 903-937

[4] ADLER R L， KONHEIM A G， MCANDREW M H Topological Entropy[J] Transactions of the American Mathematical Society， 1965， 114（2）： 309-319

[5] YAKOV S Kolmogorov-Sinai entropy[J] Scholarpedia， 2009，4（3）：2034

[6] RENYI A On measures of entropy and information[C]// Procfourth Berkeley Sympon Mathstatist & Probunivof Calif Berkeley， Calif： California Press， 1961： 547-561

[7] [JP3]VINGA S， ALMEIDA J S R[KG-8]e[DD（-1]′[DD）]nyi continuous entropy of DNA sequences[J] Journal of theoretical biology， 2004， 231（3）： 377-388[JP]

[8] KIRILLOVA O V Entropy concepts and DNA investigations[J] Physics Letters A， 2000， 274（5/6）： 247-253

[9] FARACH M， NOORDEWIER M， SAVARI S， et al On the entropy of DNA： Algorithms and measurements based on memory and rapid convergence[J] Proceedings of the Sixth Annual Acm-Siam Symposium on Discrete AlgorithmsSan Francisco， California， USA：ACM， 1995： 48-57

[10]COLOSIMO A， DE LUCA A Special factors in biological strings[J] Journal of theoretical biology， 2000， 204（1）： 29-46

[11]TROYANSKAYA O G， ARBELL O， KOREN Y， et al Sequence complexity profiles of prokaryotic genomic sequences： A fast algorithm for calculating linguistic complexity[J] Bioinformatics， 2002， 18（5）： 679-688

[12]GABRIELIAN A， BOLSHOY A Sequence complexity and DNA curvature[J] Computers & chemistry， 1999， 23（3/4）： 263-274

[13]KOSLICKI D Topological entropy of DNA sequences[J] Bioinformatics， 2011， 27（8）： 1061-1067

[14]JIN S， TAN R， JIANG Q， et al A generalized topological entropy for analyzing the complexity of DNA sequences[J] PloS One， 2014， 9（2）： e88519

[15]JIN Shuilin， WANG Zhou， LIN Junyu， et al The complexity of promoter regions based on a vector topological entropy[J] Current Bioinformatics， 2016， 11：1-4

[16]MAGI A， TATTINI L， PIPPUCCI T， et al Read count approach for DNA copy number variants detection[J] Bioinformatics， 2012， 28（4）： 470-478

[17]ALKAN C， COE B P， EICHLER E E Genome structural variation discovery and genotyping[J] Nature reviews Genetics， 2011， 12（5）： 363-376endprint