確定自動機的空間壓縮方法
2023-11-30 21:44:16
專利名稱：：確定自動機的空間壓縮方法
技術領域：
：本發明涉及網絡安全領域，特別涉及確定自動機的空間壓縮方法。
背景技術：
：正則表達式(RegularExpression)是計算機科學中用來描述或者匹配一系列符合某個句法規則的字符串的單個字符串。利用正則表達式來匹配那些符合某個模式的文本內容的方法也被稱為正則表達式匹配算法。正則表達式匹配算法一直都是計算機科學的研究焦點之一，它被廣泛應用於網絡入侵檢測、計算機病毒特徵碼匹配、網絡信息內容安全、信息檢索等多個領域中。確定自動機(DFA)是正則表達式匹配算法的基礎，DFA在計算機中以狀態轉換表的方式加以存儲。通常，用DFA進行正則表達式匹配的基本過程如下步驟a、對於給定的正則表達式，用經典的方法構建相應的DFA;步驟b、採用DFA對輸入的文本(或者網絡流)進行匹配。這一匹配過程又包括步驟b-1、當前狀態current處於DFA的初始狀態；步驟b-2、對於每一個輸入的文本字符t[i]，根據狀態轉換表的內容從自動機的當前狀態current跳轉到它的後繼狀態next;步驟b-3、如果後繼狀態next是自動機的接受狀態，那麼說明當前文本位置發生了一次匹配，輸出匹配位置；步驟b-4、繼續處理下一個字符。從上述過程可以看出，DFA是正則表達式匹配過程的核心。DFA中用於記錄當前狀態current到後繼狀態next的轉換情況的狀態轉換表的大小(也就是下文中所提到的DFA存儲空間)對實現正則表達式匹配時所佔用的計算機存儲資源的多少直接相關，而正則表達式匹配的速度也和DFA狀態轉換的速度有著密切的聯繫。近年來，隨著待處理信息量的不斷增強和實時處理的緊迫需求，對正則表達式匹配算法的性能提出了更高的要求。正則表達式匹配算法的性能包括匹配速度和所佔用計算機存儲資源兩個方面，而DFA正與這兩個方面有著密切的聯繫。因此，本領域技術人員希望通過對DFA的改變來改進現有的正則表達式匹配算法，使得改進後的正則表達式匹配算法能夠對DFA存儲空間進行壓縮以減少對計算機存儲資源的佔用，並能加快DFA狀態的轉換速度。在參考文獻1(AlgorithmtoAccelerateMultipleRegularExpressionsMatchingforDeepPacketInspectionConference:SIGCOMM'06September11-15,2006)中提出了D^A方法來壓縮DFA的存儲空間。它通過引入默認轉移(defaulttransition)來減少狀態轉移的數目，從而降低自動機的存儲空間。引入默認轉移能夠極大地減少DFA的狀態轉移，在該文中所記載的實驗表明，該方法平均能夠減少95%的狀態轉移。但是該方法的缺陷在於每處理一個字符可能需要在D2FA中進行多次狀態跳轉，導致實際的匹配性能不高。在參考文獻2(AnimprovedDFAforfastregularexpressionmatching,ACMSIGCOMMComputerCommunicationReview,Volume38,Issue5(October2008),Pages29-40)中提出了5FA方法來壓縮DFA的狀態表。該方法提取子狀態和父狀態的相同元素來消除狀態轉換表的冗餘。在狀態訪問序列中，如果當前狀態t要訪問的元素next[t，c]與其前一個狀態s的對應元素next[s，c]相同，那麼可以直接從前一個狀態中讀取相應的值。該方法能夠取得非常好的壓縮效果，但是非常費時的。綜上所述，現有技術中所公開的正則表達式匹配算法無法同時提高DFA空間的壓縮效果與DFA狀態的轉換速度，從而影響了正則表達式匹配算法的最終匹配性能。
發明內容本發明的目的是克服現有技術無法同時提高DFA空間的壓縮效果與DFA狀態的轉換速度的缺陷，從而提供一種在壓縮效果與轉換速度上達到良好平衡的方法。為了實現上述目的，本發明提供了一種確定自動機的空間壓縮方法，包括步驟1)、對確定自動機中的各個狀態做分簇操作，得到多個用於表示6步驟2)、將所述確定自動機中各個狀態的轉移邊按步驟1)所得到的簇分類，得到多個簇矩陣、與所述簇矩陣對應的位圖以及一個剩餘矩陣；其中，所述簇矩陣包括指向同一簇的轉移邊，所述位圖用於描述簇矩陣中相關元素的有效性；所述剩餘矩陣包括確定自動機中未被包含到所述簇矩陣中的剩餘轉移邊；步驟3)、為所述簇矩陣中的各行提取基值，然後將所述簇矩陣轉換成一個偏移量矩陣，再將偏移量矩陣中的各行合併，增加用於標記可合併狀態的索引數組，得到所述簇矩陣的壓縮矩陣。上述技術方案中，還包括步驟4)、壓縮所述的剩餘矩陣。上述技術方案中，所述的步驟l)包括步驟l-l)、從確定狀態機的初始狀態開始做廣度優先遍歷，得到trie樹結構；步驟l-2)、對所得到的trie樹中的各個狀態做分簇操作，得到多個用於表示狀態集合的簇；其中，在做分簇操作時，將所述確定自動機的初始狀態作為一個單獨的簇，將所述確定自動機中一個狀態的所有直接後繼狀態的集合作為一個簇。上述技術方案中，所述的步驟2)包括步驟2-1)、判斷所述確定自動機中剩餘轉移邊的數目是否小於閾值，若小於，則將剩餘的轉移邊填入所述的剩餘矩陣中，否則，執行下一步；步驟2-2)、將所述確定自動機中剩餘的所有轉移邊中指向同一簇最多的轉移邊轉移到一個簇矩陣中，並用一個對應的位圖表示該簇矩陣中元素的有效性。上述技術方案中，在所述的步驟3)中，所述的基值為基值所在行所對應簇中的最小值，所述的偏移量矩陣中的偏移量為所述簇矩陣中的轉移邊的值與所述基值間的差。上述技術方案中，在所述的步驟3)中，將偏移量矩陣中的各行合併時，滿足以下規則在矩陣T中，若且唯若對任意字符c滿足T[r][c]--l或者T[s][c]:-l或者T[s][c]二T[r][c]時，行r和行s是可合併的，其中，"-r代表對應位置的值為無效值。上述技術方案中，所述的位圖包括多個與所述簇矩陣具有一一對應關係的位圖，所述位圖用於描述與其具有對應關係的簇矩陣中元素的有效性。上述技術方案中，所述的位圖包括一個位圖，所述位圖利用位圖中元素的數值大小描述所述轉移邊在按簇分類後的位置。本發明還提供了一種由所述的確定自動機的空間壓縮方法所得到的矩陣實現正則表達式匹配的方法，包括輸入文本，用所述矩陣對所述輸入文本進行匹配。上述技術方案中，所述的用所述矩陣對所述輸入文本進行匹配包括步驟a)、在一個簇矩陣對應的位圖中查看bitmap[s][c]是否為有效狀態，若為有效狀態，則將所述簇矩陣中基值base[s]和偏移量T[equal[s]][c]之和的值作為當前狀態的直接後繼狀態，若為無效狀態，執行下一步；其中，所述的s代表當前狀態，所述的c代表輸入文本中所要匹配的字符，所述的equal代表用於標記可合併狀態的索引數組，所述的T代表簇矩陣；步驟b)、判斷是否還存在未經處理的簇矩陣，若存在，則取出未經處理的下一個蔟矩陣及其位圖後，重新執行步驟a)，否則，執行下一步；步驟c)、從所述的剩餘矩陣中取出T'[s]][c]的值，作為當前狀態的直接後繼狀態；其中，所述的T'表示剩餘矩陣。上述技術方案中，在所述的步驟b)中，按照所包含的轉移邊數量的多少依次選擇所述的簇矩陣。本發明還提供了一種確定自動機的空間壓縮裝置，包括分簇模塊、簇矩陣劃分模塊以及簇矩陣壓縮模塊；其中，所述的分簇模塊對確定自動機中的各個狀態做分簇操作，得到多個用於表示狀態集合的簇；所述的簇矩陣劃分模塊將所述確定自動機中各個狀態的轉移邊按簇分類，得到多個簇矩陣、與所述簇矩陣對應的位圖以及一個剩餘矩陣；其中，所述簇矩陣包括指向同一簇的轉移邊，所述位圖用於描述所對應簇矩陣中相關元素的有效性；所述剩餘矩陣包括確定自動機中未被包含到所述簇矩陣中的剩餘轉移邊；所述的簇矩陣壓縮模塊為所述簇矩陣中的各行提取基值，然後將所述簇矩陣轉換成一個偏移量矩陣，再將偏移量矩陣中的各行合併，增加用於標記可合併狀態的索引數組，得到所述簇矩陣的壓縮矩陣。上述技術方案中，還包括剩餘矩陣壓縮模塊，所述的剩餘矩陣壓縮模塊壓縮所述的剩餘矩陣。本發明又提供了一種正則表達式匹配裝置，包括文本輸入模塊、由所述的確定自動機的空間壓縮方法所得到的矩陣以及匹配模塊；其中，所述的文本輸入模塊輸入所要匹配的文本；所述的匹配模塊採用所述矩陣對輸入的文本進行匹配。本發明的優點在於相對於現有的DFA壓縮和匹配方法，不僅在壓縮效果上有所提高，而且在實現正則表達式匹配時在匹配速度上有很大的提高。圖1為與正則表達式".*A.{2}CD"所對應的DFA;圖2為圖1所示DFA在計算機中的存儲矩陣；圖3為圖1所示DFA經由廣度優先遍歷算法所得到的trie樹結構的示意圖4為圖2所示的存儲矩陣按簇分類後所得到的簇矩陣、位圖以及剩餘矩陣；圖5為對圖4中所得到的簇矩陣T1做壓縮操作的示意圖；圖6為本發明的確定自動機空間壓縮方法的示意圖。具體實施例方式下面結合附圖和具體實施方式對本發明進行說明。在本實施例中，以正則表達式".*A.{2}CD"為例，對壓縮該正則表達式的DFA空間的過程加以i兌明。首先由所述的正則表達式".*A.{2}CD"生成與其對應的DFA。由於由正則表達式生成DFA的過程是本領域的公知技術，因此不在此處重複說明。在圖1中給出了正則表達式".*A.{2}CD"所生成的DFA的示意圖。在該圖中，圓圈內的0、1、2、3等數字代表狀態，該DFA有0-9的10種狀態。而帶箭頭的橫線代表由一個狀態轉移到另一個狀態的條件，箭頭上的字母，如A、C、D、NotA(表示非A之外的任意字符)，代表該條件的具體內容，這些帶箭頭的橫線也被稱為狀態的轉移邊。狀態轉換條件的具體內容根據實際情況而發生變化，在文本匹配時，狀態轉換條件可以是某一具體的字符，例如，前述的狀態轉換條件A可以就是字母A本身。需要說明的是，圖1隻是DFA的一個示意圖，在計算機中對此類示意圖採用矩陣的方式加以存儲。在圖2中給出了圖1中DFA的存儲矩陣。在該矩陣中，第一列代表DFA中的所有狀態，如0、1、2……9,而第一行代表了狀態轉換的條件，如A、C、D。結合圖1可以看出，在狀態0時，當轉換條件為A時，狀態由O變為l,當轉換條件為C、D時，由於狀態沒有發生改變，因此還是0。在狀態2時，當轉換條件為A時，狀態由2變為4，當轉換條件為C、D時，由於滿足圖1中"NotA"的條件，因此狀態由2變為5。存儲矩陣中的其他狀態轉換關係與之類似。由於這一存儲矩陣中所存儲的是各個狀態間的轉換關係，因此，所述的存儲矩陣也就是
背景技術：
中所提到的狀態轉換表。在得到DFA後，需要為DFA中的各個狀態進行劃分，使得DFA的狀態集合分成若干個互不相交的子集。對DFA狀態的劃分也被稱為分簇操作，DFA狀態的子集就是由分簇操作所得到的簇。對DFA中狀態的分簇操作有多種實現方式，如將DFA中的每個狀態作為一個單獨的簇，也可按照深度優先遍歷算法或廣度優先遍歷算法由DFA得到相應樹，然後對樹進行分簇操作。在一個優選實施例中，可以從DFA的初始狀態開始做廣度優先遍歷，得到trie樹結構，然後再對所得到的trie樹中的各個狀態做分簇操作，得到與DFA所對應的簇集。在圖3中給出了圖1經由廣度優先遍歷算法所得到的trie樹結構。由於在圖上做廣度優先遍歷的實現過程為本領域技術人員所公知，因此，在此處也不再對該過程做重複說明。在為trie樹中的各個狀態做分簇操作時，應當遵循以下原則初始狀態是一個單獨的簇，將一個狀態的所有直接後繼狀態的集合作為一個簇。根據上述分簇原則，在圖3中，初始狀態"0"可以得到一個單獨的簇{0},其他的由一個狀態的所有後繼狀態的集合所得到的簇包括{1}、{2,3}、{4,5}、{6，7}、{8}、{9}。即由圖3所生成的簇集為{{0},{1}，{2,3},{4，5},{6,7}，{8},{9}}。在得到DFA的簇集後，就可以為DFA中的各個狀態的轉移邊按簇進行分類，並用不同的矩陣分別存儲分類後的結果。如果將前文中用於表示DFA的存儲矩陣稱為原始矩陣，那麼通過將DFA中各個狀態的轉移邊按簇分類，並用不同的矩陣分別存儲後，所述的原始矩陣可分為K+l個子矩陣，其中，前面的K個子矩陣被稱為簇矩陣，第i(l<=i<=K)個簇矩陣由第i大的簇構成，最後一個矩陣由存儲矩陣中剩餘的矩陣元素構成，也被稱為剩餘矩陣。對上述簇矩陣和剩餘矩陣的劃分，通常採用閾值比較的方法實現。例如，可以預先設定一個閾值delta,其值為95%，然後依次提取第一個簇矩陣，第二個簇矩陣，....，直到已提取的元素比例超過delta為止。剩下的元素填入最後的剩餘矩陣中，此時其元素佔原始矩陣的元素的比例不超過l-delta。在本發明的一個實施例中，可以將DFA中的狀態的轉移邊分為三類，並用三個矩陣存儲分類結果。具體的說，在該實施例中，指向同一簇最多的轉移邊存儲在矩陣T1中，同時用位圖bitmapl標記矩陣Tl中的有效元素；指向同一簇第二多的轉移邊存儲在矩陣T2中，同時用位圖bitmap2標記矩陣T2中的有效元素；把剩餘的轉移邊存儲在第三個矩陣T3中。其中的矩陣T1、T2就是所述的簇矩陣，而矩陣T3則是所述的剩餘矩陣。在圖4中給出了對前述圖2所示的存儲矩陣按簇分類後所得到的矩陣Tl、位圖bitmapl、矩陣T2、位圖bitmap2以及矩陣T3。從圖2的存儲矩陣可以看出，對於"狀態0"而言，其轉移後所得到的"狀態0"和"狀態1"分屬不同的簇，因此需要比較指向不同簇的轉移邊的數目。由於指向"狀態0"的轉移邊有兩條，指向"狀態1"的轉移邊只有一條，因此在矩陣T1中記錄指向{0}的轉移邊，在矩陣T2中記錄指向{1}的轉移邊，而在矩陣T3中則不記錄關於該狀態的轉移邊的任何信息。由於在矩陣T1、T2中有些位置為有效值，有些位置為無效值，且有效值與無效值的分布不具有規律性，因此分別採用了位圖bitmapl和位圖bitmap2對矩陣Tl、T2中的有效元素進行標記。如在圖4中，矩陣Tl中的"狀態0"到"狀態0"的轉移邊為有效，因此在位圖bitmapl內將相應位置標記為有效位，而將"狀態0"到"狀態1"的轉移邊在位圖bitmapl中的相應位置標記為無效位。矩陣T2的情況與之相反，因此位圖bitmap2的記錄情況也截然相反。另外，在圖2所示的存儲矩陣中還有這樣一種情況"狀態7"轉移後的狀態有三種，分別為"狀態1"、"狀態8"、"狀態0",上述三種狀態分屬於三個不同的簇，因此到其中某一簇的轉移邊的數量都為1。對於這種情況，無法區分指向哪一個簇的轉移邊的數量最多，指向哪一個簇的轉移邊的數量第二多，因此可以將指向三種簇中任意一簇的轉移邊存入矩陣Tl,將指向另一簇的轉移邊存入矩陣T2,將指向剩餘簇的轉移邊存入矩陣T3。由於本實施例中所給出的DFA示例較為筒單，因此，在本實施例中只將狀態的轉移邊分為三類，並用三個矩陣存儲對應類中的信息。但在其他實施例中，當DFA更為複雜時，可以增加狀態的轉移邊的分類數，並用更多的矩陣分別存儲不同的分類。例如，將DFA中的狀態的轉移邊分為四類，並用四個矩陣存儲分類結果；其中，指向同一簇最多的轉移邊存儲在矩陣Tl中，同時用位圖bitmapl標記矩陣Tl中的有效元素；指向同一簇第二多的轉移邊存儲在矩陣T2中，同時用位圖bitmap2標記矩陣T2中的有效元素；指向同一簇第三多的轉移邊存儲在矩陣T3中，同時用位圖bitmap3標記矩陣T3中的有效元素；把剩餘的轉移邊存儲在第四個矩陣T4中。從理論上說，根據前面的閾值比較法，DFA中狀態的轉移邊的分類數目可以繼續增加，但實驗結果證明，一般將狀態的轉移邊分為三類或四類時效果最佳。對簇矩陣中有效元素進行標記的位圖不僅可以釆用如圖4所示的表示方式，也可以採用其他的表示方式。例如，在一個實施例中，只用一個位圖表示一個存儲矩陣中所有元素在按簇分類後的位置。假設原存儲矩陣有N行，C列，且在按簇分類後得到K個簇矩陣和1個剩餘矩陣，則該位圖也有N行，C列，但該位圖中各個元素的數值不再是0或1,而是卩。仍(K+i"比特的整數，由該整數的數值大小可以知道存儲矩陣中對應元素在按簇分類會位於哪一個簇矩陣或剩餘矩陣中。採用前述圖4中位圖的表示方式，與一個存儲矩陣所對應的位圖需要KxNxC大小的存儲空間，而採用該實施例中的位圖表示方式，則只需要卩,(K+"lxNxC大小的存儲空間，顯然在存儲空間上會有進一步的減少。將DFA由圖2所示的存儲矩陣轉換為圖4所示的矩陣和位圖後，可以對所得到的矩陣做壓縮。此處所述的壓縮操作主要針對所述的簇矩陣，如前述實施例中所提到的矩陣Tl和矩陣T2。下面以前述的矩陣T1為例，對壓縮操作的具體實現過程進行說明。對於如矩陣Tl這樣的矩陣而言，矩陣中每行存儲的轉移邊都指向同一個簇，因此可以把該簇的最小值作為該行的基值(base值)，而將該行中原先存儲的轉移邊的值替換為轉移邊相對於基值的偏移量，從而將原先的矩陣Tl轉換為帶有偏移量列和base值列的偏移量矩陣。如圖5所示，對矩陣T1中的狀態O,其轉移邊指向簇{0},因此base值為0，該行的有效元素同時減去0,所得到的偏移量為"0、0"。對矩陣T1中的狀態1，其轉移邊指向簇{2,3}，因此base值為2，該行的有效元素相應地減去2，所得到的偏移量分別為"0、1、1"。對矩陣Tl、T2中的其他狀態的操作與之相似。在得到偏移量矩陣後，就可以對這一矩陣進行合併，從而實現對簇矩陣的壓縮。在合併時，應當滿足以下規則在矩陣T中，若且唯若對任意字符c滿足T[r][c]二-l或者T[s][c]"l或者T[s][c一T[r][c]時，行r和行s是可合併的，其中，"-r代表對應位置的值為無效值。圖5中示出了矩陣T1的偏移量矩陣在壓縮前後的結果。例如，"狀態1"所在行的偏移量與"狀態2"、"狀態3""狀態4"、"狀態5"、"狀態6"的偏移量滿足上述的合併條件，可與"狀態1"合併。又如，"狀態0"所在行的偏移量與"狀態7"、"狀態8"、"狀態9"的偏移量滿足上述的合併條件，因此可與"狀態0"合併。在合併後，為了表示哪些狀態之間發生了合併，在壓縮後的矩陣中增加了用於標記可合併狀態的索引數組equal。對於矩陣T2也可做類似操作。DFA的存儲矩陣除了所述的簇矩陣外，還生成了剩餘矩陣。由於剩餘矩陣中不具有簇矩陣的特點，因此無法用前述的生成偏移量矩陣並合併偏移量矩陣的方法壓縮該矩陣。剩餘矩陣所佔有的存儲空間有限，因此可以不對剩餘矩陣做壓縮操作。但在一種優選實現方式中，也可以採用目前經典的稀疏矩陣壓縮方法對剩餘矩陣進行壓縮。以上是對DFA存儲矩陣進行壓縮操作的全過程。在經過上述的壓縮操作後，圖2所示的DFA矩陣最終會轉換成多個圖5所示的壓縮矩陣。由於在實際應用中，一個DFA中的狀態數、狀態轉換條件遠遠多於實施例中所假設的情況，因此，圖5中被合併項的存儲空間遠遠大於壓縮過程中新添加的base列和equal列，因而具有良好的壓縮效果。在下面的表1中將本申請所使用的上述壓縮方法與參考文獻2所提出的5FA壓縮方法的壓縮效果進行比較。表中所提到的原始DFA是指未壓縮前的自動機，表中"本申請的壓縮方法"以及"5FA壓縮方法，，項下的數字代表壓縮率。所述的壓縮率是DFA經壓縮方法壓縮後的存儲空間與原始DFA的存儲空間的比值，因此，壓縮率越小，壓縮效果越好。在表1所示出的18組測試集中，本申請的壓縮方法在14組測試集上優於5FA方法，因而壓縮效果在總體上佔優。tableseeoriginaldocumentpage14表1在得到壓縮後的DFA以後，可以利用這一壓縮後的DFA做正則表達式匹配。在
背景技術：
中已經就正則表達式匹配的基本實現步驟做了說明，下面就如何利用壓縮後的DFA從自動機的當前狀態current跳轉到其後繼狀態next的過程進4亍i兌明。要實現狀態的跳轉首先要知道後繼狀態是哪一個，對後續狀態的查找需要藉助壓縮後的DFA。在一個實施例中要做文本匹配操作，若用s代表當前所處的DFA狀態，用輸入字符c代表狀態轉換條件。壓縮後的DFA就是前述實施例所得到的壓縮結果，那麼對狀態s的下一個狀態的查找過程如下。首先在位圖bitmapl查看位圖元素bitmapl[s][c]是否為有效狀態(通常數值1代表有效)，若為有效，則說明狀態s的後繼狀態就在矩陣Tl中，矩陣Tl的索引數組元素equall[s]指向狀態s所在行合併後的位置，因此狀態s的後繼狀態是基值basel[s]和偏移量Tl[equal1[s]][c]之和的值。若為無效狀態，那麼需要在位圖bitmap2中繼續查找。在位圖bitmap2中查看位圖元素bitmap2[s][c]是否為有效狀態，若為有效狀態，則說明狀態s的後繼狀態在矩陣T2中。矩陣T2中的索引數組元素equal2[s]指向狀態s在行合併後的位置，因此狀態s的後繼狀態是基值base2[s]和偏移量T2[equal2[s]][c]之和的值。若為無效狀態，那麼需要在矩陣T3中繼續查找。如果矩陣T3採用了壓縮算法(如前文中所提到的經典的係數矩陣壓縮方法)進行壓縮，那麼對矩陣T3解壓縮後，查看T3[s]][c]的值，所得到的結果就是狀態s的後繼狀態。如果矩陣T3沒有經過壓縮，可直接查看T3[s]][c]的值。在得到狀態s的後繼狀態後，就可以實現狀態的跳轉操作，進而由後繼狀態是否是自動機的接受狀態來判斷是否發生了匹配操作。在上述的實施例中，以矩陣T1、T2、T3為例，對後繼狀態的查找過程做了說明。在前述的說明中已經提到，在其他的實施例中，由DFA的存儲矩陣所轉換的矩陣的數目不限於三個。本領域的普通技術人員應當了解，結合上述實施例中所描述的思想，同樣可以在其他數目的矩陣中實現對後繼狀態的查找。此外，在上述狀態查找過程中，為了提高查找效率，根據矩陣中所包含的轉移邊數量的多少，按矩陣T1、矩陣T2、矩陣T3的順序依次進行查找。但本領域的技術人員應當了解，在應用中也可以不按照這一順序實現狀態的查找，但相對而言會降低狀態查找的速度。在由DFA的當前狀態跳轉到後繼狀態時，與未壓縮的DFA狀態轉換表可以直接提取相應的後繼狀態相比，經過壓縮的DFA狀態轉換表需要經過一定的計算才能得到後繼狀態，因此，DFA壓縮方法在取得壓縮效果的同時都要以損失一定的匹配速度為代價。但與現有技術中的其他DFA壓縮方法相比，本申請的壓縮方法在匹配速度的損失上較小。在表2中給出了本申請所使用的壓縮方法與參考文獻2所提出的5FA壓縮方法以及未做壓縮的原始DFA在匹配速度上的比較結果。在比較時，它們的稀疏表均採用三種經典的方法(順序存儲、三數組方法、Tetris-hashing)實現。從表中的數據可以看出，相對於原始DFA,本申請方法的匹配速度損失控制在15-20%以內，而5FA的匹配速度則慢100倍以上。因而本申請的壓縮方法的匹配速/復大大優於5FA方法。tableseeoriginaldocumentpage16表2(單位MB/s)從上述說明可以看出，本申請的方法與現有技術的其他方法相比，不僅在壓縮效果上有所提高，而且在實現正則表達式匹配時在匹配速度上有很大的提高。本發明還提供了一種確定自動機的空間壓縮裝置，包括分簇模塊、簇矩陣劃分模塊以及簇矩陣壓縮模塊；其中，所述的分簇模塊對確定自動機中的各個狀態做分簇操作，得到多個用於表示狀態集合的簇；所述的簇矩陣劃分模塊將所述確定自動機中各個狀態的轉移邊按簇分類，得到多個簇矩陣、與所述簇矩陣對應的位圖以及一個剩餘矩陣；其中，所述簇矩陣包括指向同一簇的轉移邊，所述位圖用於描述所對應簇矩陣中相關元素的有效性；所述剩餘矩陣包括確定自動機中未被包含到所述簇矩陣中的剩餘轉移邊；所述的簇矩陣壓縮模塊為所述簇矩陣中的各行提取基值，然後將所述簇矩陣轉換成一個偏移量矩陣，再將偏移量矩陣中的各行合併，增加用於標記可合併狀態的索引數組，得到所述蔟矩陣的壓縮矩陣。所述的確定自動機的空間壓縮裝置還包括剩餘矩陣壓縮模塊，所述的剩餘矩陣壓縮模塊壓縮所述的剩餘矩陣。本發明還提供了一種正則表達式匹配裝置，包括文本輸入模塊、所述的確定自動機的空間壓縮裝置以及匹配模塊；其中，所述的文本輸入模塊輸入所要匹配的文本；所述的確定自動機的空間壓縮裝置得到壓縮後的確定自動機；匹配模塊採用壓縮後的確定自動機對輸入的文本進行匹配。最後所應說明的是，以上實施例僅用以說明本發明的技術方案而非限制。儘管參照實施例對本發明進行了詳細說明，本領域的普通技術人員應當理解，對本發明的技術方案進行修改或者等同替換，都不脫離本發明技術方案的精神和範圍，其均應涵蓋在本發明的權利要求範圍當中。權利要求1、一種確定自動機的空間壓縮方法，包括步驟1)、對確定自動機中的各個狀態做分簇操作，得到多個用於表示狀態集合的簇；步驟2)、將所述確定自動機中各個狀態的轉移邊按步驟1)所得到的簇分類，得到多個簇矩陣、與所述簇矩陣對應的位圖以及一個剩餘矩陣；其中，所述簇矩陣包括指向同一簇的轉移邊，所述位圖用於描述簇矩陣中相關元素的有效性；所述剩餘矩陣包括確定自動機中未被包含到所述簇矩陣中的剩餘轉移邊；步驟3)、為所述簇矩陣中的各行提取基值，然後將所述簇矩陣轉換成一個偏移量矩陣，再將偏移量矩陣中的各行合併，增加用於標記可合併狀態的索引數組，得到所述簇矩陣的壓縮矩陣。2、根據權利要求1所述的確定自動機的空間壓縮方法，其特徵在於，還包括步驟4)、壓縮所述的剩餘矩陣。3、根據權利要求1或2所述的確定自動機的空間壓縮方法，其特徵在於，所述的步驟1)包括步驟1-1)、從確定狀態機的初始狀態開始做廣度優先遍歷，得到trie樹結構；步驟l-2)、對所得到的trie樹中的各個狀態做分簇操作，得到多個用於表示狀態集合的簇；其中，在做分簇操作時，將所述確定自動機的初始狀態作為一個單獨的簇，將所述確定自動機中一個狀態的所有直接後繼狀態的集合作為一個簇。4、根據權利要求1或2所述的確定自動機的空間壓縮方法，其特徵在於，所述的步驟2)包括步驟2-1)、判斷所述確定自動機中剩餘轉移邊的數目是否小於閾值，若小於，則將剩餘的轉移邊填入所述的剩餘矩陣中，否則，執行下一步；步驟2-2)、將所述確定自動機中剩餘的所有轉移邊中指向同一簇最多的轉移邊轉移到一個簇矩陣中，並用一個對應的位圖表示該簇矩陣中元素的有效性。5、根據權利要求1或2所述的確定自動機的空間壓縮方法，其特徵在於，在所述的步驟3)中，所述的基值為基值所在行所對應簇中的最小值，所述的偏移量矩陣中的偏移量為所述簇矩陣中的轉移邊的值與所述基值間的差。6、根據權利要求1或2所述的確定自動機的空間壓縮方法，其特徵在於，在所述的步驟3)中，將偏移量矩陣中的各行合併時，滿足以下規則在矩陣T中，若且唯若對任意字符c滿足T[r][c]--l或者T[s][c]二-l或者T[s][c]-T[r][c]時，行r和行s是可合併的，其中，代表對應位置的值為無效值。7、根據權利要求1或2所述的確定自動機的空間壓縮方法，其特徵在於，所述的位圖包括多個與所述簇矩陣具有——對應關係的位圖，所述位圖用於描述與其具有對應關係的簇矩陣中元素的有效性。8、根據權利要求1或2所述的確定自動機的空間壓縮方法，其特徵在於，所述的位圖包括一個位圖，所述位圖利用位圖中元素的數值大小描述所述轉移邊在按簇分類後的位置。9、一種由權利要求1-8之一的確定自動機的空間壓縮方法所得到的矩陣實現正則表達式匹配的方法，包括輸入文本，用所述矩陣對所述輸入文本進行匹配。10、根據權利要求9所述的正則表達式匹配方法，其特徵在於，所述的用所述矩陣對所述輸入文本進行匹配包括步驟a)、在一個簇矩陣對應的位圖中查看bitmap[s][c]是否為有效狀態，若為有效狀態，則將所述簇矩陣中基值base[s]和偏移量T[equal[s]][c]之和的值作為當前狀態的直接後繼狀態，若為無效狀態，執行下一步；其中，所述的s代表當前狀態，所述的c代表輸入文本中所要匹配的字符，所述的equal代表用於標記可合併狀態的索引數組，所述的T代表簇矩陣；步驟b)、判斷是否還存在未經處理的簇矩陣，若存在，則取出未經處理的下一個蔟矩陣及其位圖後，重新執行步驟a)，否則，執行下一步；步驟c)、從所述的剩餘矩陣中取出T'[s]][c]的值，作為當前狀態的直接後繼狀態；其中，所述的T'表示剩餘矩陣。11、根據權利要求10所述的正則表達式匹配方法，其特徵在於，在所述的步驟b)中，按照所包含的轉移邊數量的多少依次選擇所述的簇矩陣。12、一種確定自動機的空間壓縮裝置，其特徵在於，包括分簇模塊、簇矩陣劃分模塊以及簇矩陣壓縮模塊；其中，所述的分簇模塊對確定自動機中的各個狀態做分簇操作，得到多個用於表示狀態集合的簇；所述的簇矩陣劃分模塊將所述確定自動機中各個狀態的轉移邊按簇分類，得到多個簇矩陣、與所述簇矩陣對應的位圖以及一個剩餘矩陣；其中，所述簇矩陣包括指向同一簇的轉移邊，所述位圖用於描述所對應簇矩陣中相關元素的有效性；所述剩餘矩陣包括確定自動機中未被包含到所述簇矩陣中的剩餘轉移邊；所述的簇矩陣壓縮模塊為所述簇矩陣中的各行提取基值，然後將所述簇矩陣轉換成一個偏移量矩陣，再將偏移量矩陣中的各行合併，增加用於標記可合併狀態的索引數組，得到所述簇矩陣的壓縮矩陣。13、根據權利要求12所述的確定自動機的空間壓縮裝置，其特徵在於，還包括剩餘矩陣壓縮模塊，所述的剩餘矩陣壓縮模塊壓縮所述的剩餘矩陣。14、一種正則表達式匹配裝置，其特徵在於，包括文本輸入模塊、由權利要求1-8之一的確定自動機的空間壓縮方法所得到的矩陣以及匹配模塊；其中，所述的文本輸入模塊輸入所要匹配的文本；所述的匹配才莫塊採用所述矩陣對輸入的文本進行匹配。全文摘要本發明提供一種確定自動機的空間壓縮方法，包括對確定自動機中的各個狀態做分簇操作，得到多個用於表示狀態集合的簇；將確定自動機中各個狀態的轉移邊按簇分類，得到多個簇矩陣、與所述簇矩陣對應的位圖以及一個剩餘矩陣；其中，所述簇矩陣包括指向同一簇的轉移邊，所述位圖用於描述所對應簇矩陣中相關元素的有效性；所述剩餘矩陣包括確定自動機中未被包含到所述簇矩陣中的剩餘轉移邊；為所述簇矩陣中的各行提取基值，然後將所述簇矩陣轉換成一個偏移量矩陣，再將偏移量矩陣中的各行合併，增加用於標記可合併狀態的索引數組，得到所述簇矩陣的壓縮矩陣。本發明不僅在壓縮效果上有所提高，而且在實現正則表達式匹配時在匹配速度上有很大的提高。文檔編號G06F17/30GK101630323SQ20091009055公開日2010年1月20日申請日期2009年8月20日優先權日2009年8月20日發明者萍劉,劉燕兵,楊毅夫,莉郭申請人:中國科學院計算技術研究所