基于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