保存字符串匹配規則及利用保存規則進行字串匹配的方法
2023-08-01 08:53:16 2
專利名稱：保存字符串匹配規則及利用保存規則進行字串匹配的方法
技術領域：
本發明涉及網絡管理領域，尤其涉及網絡中的字符串匹配問題。
背景技術：
隨著網絡的發展和技術的進步，人們開始站在「內容」的角度，也就是從「應用層」的角度去看待網絡，去管理和經營網絡。「內容」網絡的一個需要解決的重要問題就是對內容的識別。很多情況下，這一工作表現為對網絡上傳輸的數據中的一些重要的字符串進行最長前綴匹配，並根據其所匹配的內容規則執行相應的動作。因此，字符串匹配作為計算機科學的基礎問題，在網絡不斷發展的情況下，受到了日益廣泛的關注，這方面的算法被層出不窮的提出，尤其是最長前綴匹配，由於其在路由查找等方面的重要作用，已經在業界獲得了廣泛的應用。
字符串匹配是將組成兩個字符串的字符進行比較，判斷兩個字符串之間關係的操作，其中判別兩字符串是否完全相等的操作被稱為字符串的精確匹配。在字符串的精確匹配中，如果兩字符串的長度相等，而且它們對應位置上的每一個字符都相同，就認為這兩個字符串精確匹配成功，否則就認為精確匹配不成功。字符串精確匹配的操作通常用於在存有許多記錄的信息庫中查找某條特定信息。信息庫中的每條記錄通常有一個能唯一區分出各條記錄的項稱為關鍵字，記錄中其它的信息稱為記錄的用戶數據。查找的過程就是用某個要查找相關信息的字串S到信息庫中與每條記錄的關鍵字串進行精確匹配，從而找到關於串S的信息。在本發明中稱關鍵字Key和此關鍵字對應的用戶數據User_Data所組成的一個二元組為規則，記作R＝(Key，User_Data)。通過如下實例，對字符串的最長前綴匹配加以說明，設有如表1所示的規則集合
表1其中，表1中的編號不是規則中的內容，只是為便於以下敘述而引入的。
假設有字符串S＝aabegft，在這五條規則的五個關鍵字中，與S為最長前綴匹配關係的那個關鍵字K要滿足下面的兩個條件1、K是S的前綴，如本例中規則1、2、4的關鍵字。
2、在滿足條件1的那些關鍵字中，K的長度是最長的；在本例中，規則4的關鍵字是S的最長前綴匹配，而不是1或2，雖然1和2也都是S的前綴，但是由於它們的長度沒有4長，因此，與S不構成最長前綴匹配。
現結合兩個具體實例，對現有技術中實現最長前綴匹配的方法加以描述現有技術一由於路由器在查找路由表時常需要用到最長前綴匹配，因此，最長前綴匹配在網際網路中的用處很大。為了提高其速度，許多硬體廠商推出了能實現最長前綴匹配的網絡處理晶片，這些網絡處理器晶片都有各自的協處理器來實現字符或數字串的最長前綴匹配，其典型實現字符串前綴匹配的方法為1)匹配規則的組織先在內存中將規則構造成一種特殊的數據結構，這種結構是線性表+Patricia樹+葉子的形式，此種形式被稱為複合樹，如圖1所示。圖中11為一個線性表，12、13和14為Patricia樹，以該Patricia樹作為中間節點，10、15、16、17、18和19為葉子節點，葉子節點中存有規則的關鍵字和規則的內容。在此樹中保存匹配規則的過程為首先創建一棵空複合樹，即在內存中為此結構的線性表、中間節點、葉子節點申請內存空間；然後將規則一條條地插入到這棵空樹中，便形成了這種數據結構；然後，在這棵空樹中插入規則，其插入規則的過程為將規則的關鍵字看成比特序列，取出其中的幾個比特，如圖1取的是前3比特，以其形成的值為索引，將關鍵字所在葉子的地址記在線性表中；在有多個關鍵字的這幾個比特位都是相同從而導致衝突時，通過Patricia樹來解決這一衝突；圖中中間節點12、13、14形成了Patricia樹，該節點12內的數字(4)、(6)指出此節點處的分支是因為關鍵字後續的哪一位不同而引起的，這樣，衝突的關鍵字會因為後續比特位的不同而由Patricia樹的不同分支區分開來，從而解決了衝突問題。
2)規則的匹配匹配時，待匹配字串S也被看成比特序列，先將其中的與前述關鍵字相應的幾個比特取出，以這幾位形成的數值作為索引到線性表中找到相應表項；再沿此表項引出的Patricia樹搜索，便可以找到待匹配字串S的最長前綴匹配串。在樹中尋找待匹配的串的最長前綴匹配串的過程，也可稱為樹的查找，或樹的搜索。
在上述的現有技術一中，插入規則的過程由網絡處理器提供的微碼程序實現，而2)中所描述的匹配和搜索過程通過硬體實現，以此種方式，能夠提高最長前綴匹配的速度；然而，現有技術一也具有相當的局限性，表現在由於網絡處理器本身設計工藝及成本等方面的考慮，其對關鍵字的長度是有限制的，如4GS3的關鍵字最長是192比特，C-5的是112比特，這對於關鍵字較短的路由查找、較簡單的流分類等應用場合已經足夠，但對於內容網絡設備所需要的幾百字節(上千比特位)的內容規則的匹配則顯得太短，很不夠用。另外對於軟體實現的方案，由於內存資源的限制，設計數據結構時，也需要對樹的關鍵字長度有一定的限制。
現有技術二為了突破硬體本身的制約，實現對關鍵字長度超過限制的規則的匹配，一種較為直接的實現方式是將多棵複合樹級聯起來，構造成如圖2所示的級聯樹，為了敘述方便，後文中將上述的複合樹簡稱為樹。
圖2中20、21、22、23所表示的都是現有技術一中所述的樹結構，不過其中某一級子樹的葉子，如圖2中的30、37等，指向下一級的子樹，將它們連在一起形成了級聯樹。圖2中假設每個樹允許的關鍵字長度最大為L比特，Sa、Sb、Sw、Sp代表長度為L比特的字符或數字串，Se、Sf、Sr、St代表長度小於等於L比特的串。SaSb表示將Sa和Sb兩個串連接起來所形成的關鍵字串，例如若Sa為0010，Sb為0101，則SaSb就表示00100101。以長度超過L比特的關鍵字串SaSbSe為例，現有技術二中，利用這種級聯樹保存字符串匹配規則的方法是1、將關鍵字按順序分成多段子關鍵字，除最後一段子關鍵字外，各子關鍵字的長度為L，最後一段子關鍵字的長度等於或小於L，此例中將關鍵字串SaSbSe分成為Sa、Sb、Se三段；2、用現有技術一中的方法創建一棵空樹20，作為第一級樹；然後取出關鍵字第一段Sa，以Sa為關鍵字，將其用現有技術一中的插入方法插入到樹20中，將其對應的葉子Sa30的用戶數據中的級聯標記31記為01，以表示級聯，其它不級聯的葉子相應位置處記為00，以表示不級聯；3、創建一棵與現有技術一所描述的數據結構相同的空樹21，同時從串SaSbSe中取出後續的L比特位Sb，以Sb為關鍵字，將其插入到第二級的樹21中，生成葉子37，並在20中的葉子30中設置一個表示級聯狀態的指針32指向此樹21；再取Se插入第三級複合樹22的葉子33中，如此遞推下去，直到關鍵字的所有比特都被取到，便構造好了最後一級複合樹，如圖2中的22，圖中用一個″-″表示此樹的葉子的級聯狀態指針為空，表示其不再有下一級子樹。
現有技術二中，利用所構建的樹進行匹配的方法為對於待匹配的串S，也依次取其0到L-1比特作為子關鍵字在第一級子樹中匹配，找到葉子後，再沿葉子的級聯指針到第二級子樹中匹配下一段子關鍵字，如此遞推直到掃描完整個S或在某棵子樹中出現局部匹配失敗。
由於是最長前綴匹配，在某棵子樹中出現局部匹配失敗時並不能認為整個的最長前綴匹配失敗了，此時需要在以前所經過的子樹的葉子中尋找可能的最長前綴匹配，這個過程稱為回溯，回溯後才能知道是否真的失敗了。為了便於實現回溯，在插入新的子關鍵字Knew時，若發現樹中已有某子關鍵字Kold是Knew的最長前綴匹配，則在Knew的葉子中還要設置一個回溯指針指向Kold，這樣在查找時，若匹配Knew成功而進行Knew下級任意一個子樹匹配時失敗，那麼Kold就應該是最長前綴匹配的結果，於是用Knew的這個指針便能找到Kold，並以Kold作為最長前綴匹配的結果。若回溯前面所經過的葉子節點都不能找到最長前綴匹配，則表明對S的最長前綴匹配確實失敗了。現有技術二中的級聯結構的葉子節點的結構參見圖3。
現有技術二利用現有技術一中的複合樹作為結構單元，將超長的關鍵字分成多段分別插入到多棵複合樹中，並將這些樹級聯起來形成級聯樹，便可在這種級聯樹的結構上完成對超長的字符串的規則匹配。但是，現有技術二需要用多棵樹來實現級聯樹的構造，而且所需的樹的數目由於依賴於處理的規則，因而是不確定的。對於網絡處理器來說，其樹的管理要佔用一定的硬體資源，因此用戶可用的樹的數目是很有限的，如4GS3是128。這樣現有技術二的處理能力就會很有限。
發明內容
有鑑於此，本發明的主要目的在於提供一種用於保存字符串匹配規則的方法，採用該方法能夠將長字符串匹配規則或者超長字符串的匹配規則保存在規則樹中，並且，採用該方法能夠實現利用數目較少的規則樹保存字符串匹配規則，以減少規則樹所佔據的硬體資源。
為實現上述目的，本發明所述的一種保存字符串匹配規則的方法，包括以下步驟步驟A以L-M為單位將當前待保存在規則樹中的規則的關鍵字分為S段子關鍵字，其中，在所分得的S段子關鍵字中，除第S段子關鍵字之外的各段子關鍵字的長度均等於L-M，第S段子關鍵字的長度小於或等於L-M，L為規則樹所保存規則中關鍵字的最長長度，M為葉子編號的長度，所分得的段數S為自然數；步驟B自第1段子關鍵字開始，到第S-1段子關鍵字為止，順序執行步驟B1和步驟B2，其中，第1段子關鍵字的上一級葉子編號為0；步驟B1當前子關鍵字前串聯上一級葉子的葉子編號，形成新的字串，判斷規則樹中是否已有以該新字串為關鍵字的葉子，如果沒有，則在規則樹中生成一個以該新字串為關鍵字的葉子，並為該新生成的葉子分配唯一的葉子編號，將該新生成葉子的級聯標誌置為級聯，然後將該新生成葉子置為當前葉子；如果有，且該找到的葉子的級聯標誌為級聯，則將該找到的葉子置為當前葉子；步驟B2將步驟B1中所處理的子關鍵字的下一段子關鍵字作為當前子關鍵字，將步驟B1中所處理的子關鍵字的葉子編號作為當前的上一級葉子編號，返回執行步驟B1；步驟C第S段子關鍵字前串聯上一級葉子的葉子編號，形成新的字串，判斷規則樹中是否已有以該新字串為關鍵字的葉子，如果沒有，則在規則樹中生成一個以該新字串為關鍵字的葉子，然後將待保存規則中的數據內容寫入該葉子，如果有，直接將待保存規則中的數據內容寫入該葉子。
其中，步驟B1中所述判斷規則樹中是否已經有以所述字串為關鍵字的葉子包括以下步驟
步驟B11判斷在規則樹中是否有以所述字串的最長前綴匹配為關鍵字的葉子，如果沒有，則判斷得到規則樹中沒有以所述字串為關鍵字的葉子，如果有，則執行步驟B12；步驟B12判斷步驟B11中找到的最長前綴匹配關鍵字是否與所述字串相同，如果不是，則判斷得到規則樹中沒有以所述字串為關鍵字的葉子，如果是，則判斷得到規則樹中有以所述字串為關鍵字的葉子。
其中，步驟B12中，如果最長前綴匹配關鍵字與所述字串不同，該方法進一步包括將所述新生成的葉子的回溯指針指向該最長前綴匹配關鍵字所對應的葉子。
其中，步驟B1中，如果在規則樹中找到的以所述字串為關鍵字的葉子不級聯，所述將找到的葉子置為當前葉子進一步包括為所述找到的葉子分配唯一的葉子編號，將該找到的葉子置為級聯，和將該找到的葉子的回溯指針指向其自身。
其中，步驟C中所述判斷規則樹中是否已經有以該字串為關鍵字的葉子包括以下步驟步驟C1判斷在規則樹中是否有以所述字串的最長前綴匹配為關鍵字的葉子，如果沒有，則判斷得到規則樹中沒有以該字串為關鍵字的葉子，如果有，則執行步驟C2；步驟C2判斷步驟C1中找到的最長前綴匹配關鍵字是否與所述字串相同，如果不是，則判斷得到規則樹中沒有以該字串為關鍵字的葉子，如果是，則判斷得到規則樹中有以該字串為關鍵字的葉子。
其中，步驟C中所述將規則的數據寫入葉子為將規則中的數據寫入葉子的「其它」域中。
其中，在步驟B1中和步驟C中，所述在規則樹中新構建一個以所述字串為關鍵字的葉子進一步包括將該新構建葉子的上一級葉子中的「下級計數」域中的值加1。
其中，刪除規則樹中的一個規則時，該方法進一步包括步驟D1以L-M為單位將待刪除的規則中的關鍵字分為T段子關鍵字；其中，在所分得的T段子關鍵字中，除第T段子關鍵字之外的各段子關鍵字的長度均等於L-M，第T段子關鍵字的長度小於或等於L-M，所分得的段數T為自然數；步驟D2自步驟D1的第1段子關鍵字開始，到第T-1段子關鍵字為止，順序執行以下步驟D21～步驟D22，其中，第1段子關鍵字的上一級葉子編號為0步驟D21在當前子關鍵字前串聯上一級葉子的葉子編號，形成新的字串，判斷在規則樹中能否找到以該字串為關鍵字的葉子，如果是，則執行步驟D22，否則，刪除過程失敗；步驟D22將在步驟D21中所找到的葉子節點記錄在預先定義的數組中，以該葉子的葉子編號作為上一級葉子編號，以當前子關鍵字的下一級子關鍵字作為當前子關鍵字，返回步驟D21；步驟D3第T段子關鍵字前串聯上一級葉子編號，形成新的字串，判斷在規則樹中能否找到其關鍵字與該新的字串完全相同的葉子，如果是，則將該葉子節點記錄在步驟D22所述的數組中，然後執行步驟D4，否則，刪除過程失敗；步驟D4根據步驟D22中數組的記錄，自該數組中所記錄的待刪除規則的最後一個葉子節點開始，到該待刪除規則的第一個葉子節點為止，依次執行以下步驟判斷當前處理的葉子的「下級計數」域是否為0，如果是，則刪除該當前處理的葉子，並將該當前處理的葉子的上一級葉子的「下級計數」域的值減1，然後，將該上一級葉子置為當前處理的葉子，返回執行本步驟；否則，結束刪除過程。
其中，如果當前處理的葉子為所述最後一個葉子節點，且該葉子的「下級計數」域不為0，該方法進一步包括刪除該葉子節點中指向其自身的回溯指針。
本發明還提供了一種利用上述的字符串匹配規則樹進行字符串匹配的方法，該方法將待匹配的字符串分為若干段子關鍵字，每段子關鍵字分別串聯上一級葉子編號形成字串，在上述所構建的字符串匹配規則樹中依次查找這些字串，從而實現字符串的匹配。
本發明的一種利用字符串匹配規則樹進行字符串匹配的方法包括以下步驟步驟E以L-M為單位將待匹配的字符串分為P段子關鍵字，其中，在所分得的P段子關鍵字中，除第P段子關鍵字之外的各段子關鍵字的長度均等於L-M，第P段子關鍵字的長度小於或等於L-M，所分得的段數P為自然數；步驟F自第1段子關鍵字開始，到第P段子關鍵字為止，順序執行以下步驟F1～步驟F2，其中，第1段子關鍵字的上一級葉子編號為0步驟F1當前子關鍵字前串聯上一級葉子的葉子編號，形成新的字串，判斷規則樹中是否有以該字串為關鍵字的葉子，如果有，則執行步驟F2，否則，匹配失敗；步驟F2判斷在步驟F1所找到的葉子是否級聯，如果是，則將該葉子的葉子編號作為上一級葉子編號，將當前子關鍵字的下一級子關鍵字作為當前子關鍵字，然後返回步驟F1，直至找到的葉子不級聯；否則，該葉子為匹配結果的最後一級葉子，從該葉子中取出規則的數據，匹配結束。
其中，步驟F1中，如果規則樹中有以該字串為關鍵字的葉子，該方法進一步包括將該葉子按照順序記錄在預先定義的數組中。
其中，步驟F1中，如果規則樹中沒有以該字串為關鍵字的葉子，該方法進一步包括
自所述數組記錄的最後一個葉子節點開始，按順序判斷該數組所記錄的葉子的回溯指針是否為空，如果是，則返回本步驟，直至判斷得到所記錄的所有葉子的回溯指針均為空，則匹配失敗，否則，回溯指針所指向的葉子為匹配結果的最後一級葉子，從該葉子中取出規則的數據，匹配結束。
可見，本發明採用一棵規則樹保存字符串匹配規則，將待保存的規則中的關鍵字分為若干段子關鍵字，這些子關鍵字與相應的葉子編號串聯形成字串，在規則樹中，以這些字串作為葉子的關鍵字，從而將待保存的規則分段插入到規則樹中。在利用該規則樹進行字符串匹配時，將待匹配的字符串分為若干段子關鍵字，每段子關鍵字分別串聯上一級葉子編號形成字串，在上述的規則樹中依次查找這些字串，從而實現字符串的匹配。
由於本發明中將待保存規則的關鍵字分為若干段插入規則樹，因此，可以實現保存長字符串匹配規則或超長字符串匹配規則，進而可以利用該規則樹實現長字符串或超長字符串匹配；由於在本發明中，採用一棵規則樹保存字符串匹配規則，因此，減少了保存字符串匹配規則時的樹的數量，從而節省了規則樹所佔用的硬體空間，使得該方法的處理能力得以提高，並拓寬了該方法的應用範圍。
圖1為現有技術中用於構建規則的複合樹的結構示意圖。
圖2為現有技術中用於構建規則的級聯樹的結構示意圖。
圖3為現有技術中級聯樹的葉子結構示意圖。
圖4為本發明中的葉子結構的示意圖。
圖5為本發明中用於保存字符串匹配規則的樹的結構示意圖。
圖6為本發明中將規則插入規則樹的流程圖。
圖7為本發明中將規則從規則樹中刪除的流程圖。
圖8為本發明中利用規則樹進行字符串匹配搜索的流程圖。
具體實施例方式
本發明為一種保存字符串匹配規則的方法以及利用保存匹配規則的規則樹進行字符串匹配的方法，在保存字符串匹配規則方面，該方法可以看作是對上述現有技術二的改進，為每級樹要引出的新的子樹的葉子賦予一個葉子編號N，該編號佔M比特，在取當前處理的子關鍵字的後續L-M比特子關鍵字構造下一級子樹時，物理上並不創建一棵新的子樹，而是以N串聯上該後續的L-M比特子關鍵字，形成新的字串，為該新的字串構造葉子，將該葉子插入規則樹中，重複上述步驟，直至將規則中關鍵字的各段子關鍵字以及規則的內容均插入規則樹中。採用此種方式在規則樹中保存匹配規則，可以只構建一棵規則樹，而無需構建其它的子樹，從而達到邏輯上精簡的效果；在為新的葉子分配葉子編號N時，該編號N為針對不同葉子的一個唯一編號，以此方式，即使在現有技術二中不同子樹的葉子中的關鍵字可能相同，由於引出它們的葉子編號N不同，兩者級聯後所得到的新的關鍵字就不會相同，由此仍可以根據該關鍵字唯一標識出這一級的子關鍵字，同時，以N在前L-M比特子關鍵字在後的形式實現串聯，還可以保證最長前綴匹配的結果的正確性。
下面結合附圖對本發明保存字符串匹配規則的方法進行詳細描述。
本發明採用如圖4所示的葉子結構保存字符串匹配規則，在該葉子結構中，葉子的關鍵字是由兩部分串聯在一起形成的串，如圖4中所示用+表示兩部分之間的連接，前一部分是上一級葉子的葉子編號，後一部分是當前葉子所對應的子關鍵字，兩者合在一起的長度不超過L比特；預先設定葉子編號佔M(M＜＜L) 比特，對關鍵字進行分段時，以L-M比特為單位進行分段，以保證子關鍵字與葉子編號串聯在一起的長度不超過L比特。在該葉子結構中，葉子的「級聯標誌」、「回溯指針」、「其它」這三個欄位的含意同現有技術二所述的內容相同，不同的是去掉了現有技術二中的「下一級子樹」域，增加了「葉子編號」和「下級計數」兩個域，其中，「葉子編號」域所記錄的內容為該葉子的唯一葉子編號，「下級計數」記錄此葉子邏輯上所引出的下級葉子的數目，設置此域是為了刪除規則時判斷是否要刪除該葉子節點。
在本發明保存字符串匹配規則的方法中，字符串匹配規則的保存是通過將規則一條條地插入樹中進行的，下面結合一個具體實例，對本發明中的保存字符串匹配規則的方法加以詳細描述。
在該實施例中，有規則(Key1，D1)、(Key2，D2)、(Key3，D3)需要保存，其中關鍵字Key1以L-M比特為單位分為三段子關鍵字S1、S2、S3；關鍵字Key2以L-M比特為單位分為兩段子關鍵字S1、S4；關鍵字Key3以L-M比特為單位分為兩段子關鍵字S2、S4；上述S1和S2的長度為L-M比特，S3和S4的長度小於L-M比特；將上述規則採用圖4所示的葉子結構插入保存匹配規則的空樹中，圖5為插入這些規則後的樹的結構，在圖5中僅詳細畫出葉子部分，由於線性表與中間節點與本方案關係不大，只簡單畫出；將上述三個規則插入樹的步驟包括步驟A首先插入規則(Key1，D1)，具體包括步驟A1取出Key1的第一段子關鍵字S1；步驟A2以00串聯上S1構成新的字串00+S1，在樹中探索是否已經有以00+S1為關鍵字的葉子，由於在本發明實施例中，保存規則的樹最初為空樹，因此，本步驟中在樹中必定找不到以00+S1為關鍵字的葉子，直接執行步驟A3；其中，在向樹中每插入一個新的規則時，該規則的第一段子關鍵字的上一級葉子都被設置為空，並且將上一級葉子編號設置為00，因此在本步驟中，以00串聯S1構成新的字串00+S1；步驟A3將00+S1插入樹中，產生葉子521，葉子521中的用戶數據部分中的各個值被初始化為0；其中，所述葉子的用戶數據部分參見圖4所示，後續步驟中新產生葉子時，均是首先將葉子的用戶數據部分的各個值初始化為0；步驟A4由於Key1還有下一段子關鍵字S2，因此，葉子521的級聯標誌被標記為1，以表示葉子521還將與其它下級葉子級聯，同時，為葉子521分配一個唯一的葉子編號01；步驟A5取出Key1的下一段子關鍵字S2，此時，上一級葉子為521，上一級葉子編號為01；步驟A6上一級葉子編號01串聯子關鍵字S2構成新的字串01+S2，在樹中搜索是否已經有以01+S2為關鍵字的葉子，由於本實施例中，樹中此時還沒有以01+S2為關鍵字的葉子，因此，直接執行步驟A7；步驟A7將01+S2插入樹中，產生葉子522，將葉子522的用戶數據部分的各個值初始化為0，將上一級葉子521中的「下級計數」域中的值加1，本實施例中，521的「下級計數」域中的值經過本步驟後由0變為1；步驟A8由於Key1還有下一段子關鍵字K3，因此，葉子522的級聯標誌被置為1，並為葉子522分配一個唯一的葉子編號02，以供後續步驟使用；步驟A9取出Key1的下一段子關鍵字S3，此時，上一級葉子為522，上一級葉子編號為02；步驟A10上一級葉子編號02串聯上子關鍵字S3構成新的字串02+S3，在樹中探索是否已經有以02+S3為關鍵字的葉子，由於本實施例中，樹中此時還沒有02+S3為關鍵字的葉子，因此，直接執行步驟A11；步驟A11將02+S3插入樹中，產生葉子523，將葉子523的用戶數據部分的各個值初始化為0，將上一級葉子522中的「下級計數」域中的值加1，本發明實施例中，522的「下級計數」域中的值經過本步驟後由0變為1；步驟A12由於此時Key1的各段子關鍵字已經取完，因此，不必再為葉子523分配葉子編號，只需將規則(Key1，D1)中的數據D1寫入到葉子523的「其它」域中，以保存該規則中的數據內容，至此，規則(Key1，D1)插入完畢；步驟B插入規則(Key2，D2)，具體包括步驟B1取出Key2的第一段子關鍵字S1，此時上一級葉子被設置為空，上一級葉子編號被設置為「00」；步驟B2上一級葉子編號00串聯上第一段子關鍵字S1構成新的字串00+S1，在樹中探索是否已經有以00+S1為關鍵字的葉子，由於本實施例中，步驟A已經在樹中構造了以00+S1為關鍵字的葉子，因此，無需再次構造以00+S1為關鍵字的葉子，直接執行步驟B3；步驟B3取出Key2的第二段子關鍵字S4，此時，上一級葉子為00+S1所對應的葉子521，上一級葉子編號為葉子521的編號01；步驟B4上一級葉子編號01串聯上當前子關鍵字S4構成新的字串01+S4，在樹中探索是否已經有以01+S4為關鍵字的葉子，由於在本實施例中，此時還沒有以01+S4為關鍵字的葉子，因此，執行步驟B5；步驟B5將01+S4插入樹中，產生葉子524，將當前的上一級葉子521的「下級計數域」的值加1，經過本步驟後，葉子521的「下級計數域」的值由1變為2；步驟B6由於此時Key2的各段子關鍵字已經取完，因此，不必為葉子524再分配編號，只需將規則(Key2，D2)中的數據D2寫入葉子524中的「其它」域中，以保存該規則中的內容，至此，規則(Key，D2)插入完畢；步驟C插入規則(Key3，D3)，具體包括步驟C1取出Key3的第一段子關鍵字S2，此時上一級葉子被設置為空，上一級葉子編號被設置為「00」；步驟C2上一級葉子編號00串聯當前子關鍵字S2構成新的字串00+S2，在樹中探索是否已經有以00+S2為關鍵字的葉子，由於本實施例中，此時在樹中還沒有構造以00+S2為關鍵字的葉子，因此，執行步驟C3；
步驟C3將00+S2插入樹中，產生葉子525；步驟C4由於Key3還有下一段子關鍵字S4，因此，葉子525的級聯標誌被標記為1以表示葉子525還將與其它下級葉子級聯，同時，為葉子525分配一個唯一的葉子編號03；步驟C5取出Key3的下一段子關鍵字S4，此時，上一級葉子為525，上一級葉子編號為03；步驟C6上一級葉子編號03串聯當前子關鍵字S4構成新的字串03+S4，在樹中探索是否已經有以03+S4為關鍵字的葉子，由於在本實施例中，樹中此時還沒有以03+S4為關鍵字的葉子，因此，執行步驟C7；步驟C7將03+S4插入樹中，產生葉子526，將葉子526的用戶數據部分的各個值初始化為0，將上一級葉子525中的「下級計數」域中的值加1，本發明實施例中，525的「下級計數」域中的值經過本步驟後由0變為1；步驟C8由於此時Key3的各段子關鍵字已經取完，因此，不必再為葉子526分配編號，只需將規則(Key3，D3)中的數據D3寫入到葉子526的「其它」 域中，以保存該規則中的內容，至此，規則(Key3，D3)插入完畢。
以上所述為規則(Key1，D1)、規則(Key2，D2)以及規則(Key3，D3)的保存過程，考慮到字符串匹配過程中可能出現的例如回溯等的問題，下面利用另一實施例，說明在考慮到例如回溯等各個方面問題的情況下，實現保存字符串匹配規則的過程。
假設採用規則樹T保存字符串匹配規則，該規則樹T的初始狀態可以為空，也可以已經保存有一些其它的字符串匹配規則，在本實施例中，有規則(Key，Data)要通過插入到規則樹T中來保存，關鍵字Key的長度為B比特，以L-M比特為單位將關鍵字Key分為多段子關鍵字，其中，L比特為圖4所示的葉子結構中的「上一級葉子編號+本級子關鍵字」的最大長度，M為圖4所示的葉子結構中的「葉子編號」所佔長度，以L-M比特為單位對關鍵字進行分段的目的在於使得該關鍵字的各段子關鍵字與葉子編號連接在一起所構成的字串的長度不超過圖4葉子結構中所規定的長度L；進行上述分段後，除最後一段子關鍵字外，Key的各段子關鍵字的長度都為L-M，最後一段的長度小於或等於L-M比特；以S表示分段數，如果B能夠被(L-M)整除，則S＝B/(L-M)，如果B不能夠被(L-M)整除，則S＝[B/(L-M)+1]，這裡[]表示對其內部的數值取整數部分；根據上面所述的分段過程，將所得到的Key的S段子關鍵字分別記作K1，K2……KS-1，KS；參見圖6，通過將字符串匹配規則插入規則樹以保存字符串匹配規則的過程具體包括以下步驟步驟600設置循環變量i，初始化循環變量i＝1，用該循環變量i表示關鍵字Key所分得的各個子關鍵字的序號；步驟601將所插入規則的第一段子關鍵字的上一級葉子的葉子編號置為0，並且，將所插入規則的第一段子關鍵字的上一級葉子置為空；本步驟的目的在於在向規則樹T中每插入一個新的規則時，保證該規則的第一段子關鍵字的上一級葉子都被設置為空，並且上一級葉子編號為0；步驟602將上一級葉子標號連接上子關鍵字Ki，形成新的字串Nki；最初執行該步驟602時，Ki為K1，上一級葉子編號為0；在執行後續步驟的循環流程返回步驟602時，該上一級葉子編號和Ki發生相應變化；步驟603在已經構造的T樹中查找Nki的最長前綴匹配，如果找到，則執行步驟611及後續步驟，否則，執行步驟604及後續步驟；步驟604～步驟607由於在T樹中沒有找到Nki，因此，將Nki插入T樹中，得到葉子Nfi，為該葉子分配唯一的葉子編號NLi，並且將葉子Nfi標記為級聯，然後，將上一級葉子的「下級計數」域中的值加1，該加1的步驟只在上一級葉子不為空時執行，在上一級葉子為空的情況下不執行；步驟608將NLi作為當前的上一級葉子編號，將Nfi作為當前的上一級葉子；
步驟609～步驟610將循環變量i加1，然後，判斷循環變量i的當前值是否等於Key關鍵字的分段數目s，如果不是，說明對於Key關鍵字中各個子關鍵字的處理還沒有完成，返回步驟602，繼續處理Key關鍵字中的剩餘子關鍵字；否則，表明當前處理的子關鍵字是Ks-1，只剩下最後一個子關鍵字Ks待處理，執行步驟621及後續步驟；步驟611由於在步驟603中，在T樹中找到了Nki的最長前綴匹配，在本步驟中，將該找到的最長前綴匹配所對應的葉子設置為葉子OFi；步驟612判斷葉子OFi的關鍵字是否與Nki相同，如果是，表明當前子關鍵字Ki在樹T中所需構造的葉子已經在樹T中構造了，該已經構造的葉子就是葉子OFi，則執行步驟618及後續步驟；如果不是，表明當前子關鍵字Ki在樹T中所需構造的葉子在樹T中還沒有構造，則執行步驟613及後續步驟；步驟613～步驟615將Nki插入到樹T中，得到以Nki為關鍵字的葉子Nfi，為該葉子分配唯一的葉子編號NLi，並且置葉子Nfi為「級聯」；步驟616將葉子Nfi的回溯指針指向葉子OFi；本步驟中進行該設置的目的是為了便於回溯找到可能的最長前綴匹配，進行此種回溯指針設置的原因在於由於葉子Nfi中的關鍵字Nki與葉子OFi中的關鍵字不同，並且葉子OFi的關鍵字為Nki的最長前綴匹配，因此，OFi中關鍵字的長度肯定小於Nki中的關鍵字長度，也就是說，OFi的關鍵字的長度肯定小於L，由OFi的關鍵字長度小於L可以進而得到OFi的下一級肯定不再級聯其它葉子，OFi必定是某個規則的最後一級葉子；根據葉子OFi的上述性質以及OFi中的關鍵字是Nki的最長前綴匹配這一特點，可以利用在步驟616中所設定的回溯指針查找得到可能的最長前綴匹配，具體為一旦葉子Nfi的下一級或下幾級的葉子無法與待匹配的字符串匹配，則進行回溯查找，當回溯到葉子Nfi時，利用葉子Nfi上的回溯指針找到葉子OFi，由於葉子OFi中的關鍵字為葉子Nfi中關鍵字的最長前綴匹配且小於葉子Nfi中的關鍵字，並且由於OFi肯定為某一規則的最後一級葉子，因此，該OFi為最長前綴匹配結果；舉例來說，下述情況下，需要利用回溯指針實現最長前綴匹配存在如下3個規則規則1A，B1；規則2A，B1B2，C，D；規則3A，B1B2，C，E，F；其中B1和B2的長度加起來等於L；在將規則2和規則3插入規則樹的過程中，將會分別查找到字串01+B1B2的最長前綴匹配的葉子，該最長前綴匹配葉子為規則1中子關鍵字B1的所對應的葉子，按照上述步驟，規則2和規則3中對應B1B2的兩個葉子的回溯指針分別指向規則1中子關鍵字B1所對應的葉子；假設待匹配的關鍵字為A，B1B2，C，E，K，那麼其匹配過程會經過A、B1B2、C、E四段，最後到K時，在規則樹中不能找到與K相匹配的葉子，於是判斷子關鍵字E的葉子的回溯指針是否為空，判斷得到該回溯指針是空的，則再判斷上一級葉子的回溯指針是否為空，判斷得到該子關鍵字C所對應的葉子的回溯指針也是空的，則再向前判斷子關鍵字B1B2所對應的葉子的回溯指針是否為空，判斷得到該葉子的回溯指針為指向子關鍵字B1所對應的葉子，因此，找到該待匹配字符串A，B1B2，C，E，K的最長前綴匹配結果是A，B1；對於利用回溯指針實現最長前綴匹配的具體實施例，還會在後續利用所構造的匹配規則樹進行字符串最長前綴匹配的具體實施例中加以介紹；步驟617將上一級葉子的「下級計數」域中的值加1，然後執行步驟608，繼續處理關鍵字Key的其它子關鍵字；步驟618～步驟619根據葉子OFi中的級聯標誌判斷葉子OFi是否是級聯的，如果是，表明葉子OFi作為規則的一部分已經被插入到樹中，相應的，葉子OFi肯定已經被分配了唯一的葉子編號，因此，直接執行步驟620；如果不是，表明葉子OFi為某一規則的最後一級葉子，該葉子當前並沒有同其它的下級葉子級聯，相應的，該葉子沒有被分配唯一的葉子編號，則為葉子OFi分配唯一的葉子編號OLi，將葉子OFi置為級聯，並將葉子OFi的回溯指針指向自身，然後，執行步驟620；其中，本步驟中，將葉子OFi的回溯指針指向自身的原因是由於葉子OFi為某一規則的最後一級葉子，因此將該葉子的回溯指針指向自身，以使得在進行字符串匹配時能夠利用回溯指針找到該最後一級葉子；步驟620將葉子OFi作為上一級葉子，將OFi的葉子編號作為上一級葉子編號，然後，執行步驟609，對關鍵字Key的其它子關鍵字進行處理；步驟621由於在步驟610中判斷得到當前i的值為關鍵字Key的分段數s，因此，本步驟處理關鍵字Key的最後一個子關鍵字Ks將當前的上一級葉子標號連接上Ks，形成新的關鍵字Ke；步驟622判斷在樹T中是否能夠找到其關鍵字是Ke的最長前綴匹配的葉子，如果是，執行步驟626及後續步驟，否則，執行步驟623及後續步驟；步驟623由於在樹T中沒有找到關鍵字是Ke的最長前綴匹配的葉子，因此，將Ke插入到樹T中，得到以Ke為關鍵字的葉子Fke；步驟624～步驟625將當前的上一級葉子的下級計數加1，並將規則的數據部分Data寫入葉子Fke的「其它」域中，以保存規則的具體內容，然後，結束該規則(Key，Data)的插入過程；步驟626由於在步驟622中，在樹T中找到了Ke的最長前綴匹配，因此，本步驟中將該找到的最長前綴匹配所對應的葉子設置為葉子Nke；步驟627～步驟628判斷葉子Nke的關鍵字是否是步驟621中所形成的子關鍵字Ke，如果是，表明在樹T中已經構造了子關鍵字Ke的葉子Nke，將規則數據部分Data寫入葉子Nke的「其它」域中，以保存規則的具體內容，然後，結束該規則(Key，Data)的插入過程；如果不是，表明在樹T中還沒有構造子關鍵字Ke的葉子，因此，執行步驟623～步驟625，直至結束規則(Key，Data)的插入過程。
對於規則集中的各個規則，採用上述實施例所述的方法分別插入樹中即可，最終可以得到一棵可以對長度超過L的字符串進行最長前綴匹配的樹。
在本發明實施例中，在插入規則(Key，Data)時，採用循環變量i作為插入該規則時的標號，在有多條規則需要插入規則樹時，可採用如下方法實現標號的唯一性將編號與一系列的比特位一一映射，通過該映射關係可以得到哪些編號用了，哪些編號還未曾使用，從而可以實現分配和回收這些編號，對於最多有Rm條規則且每條規則中的關鍵字Key的最長為Lm的情況，最多只需要Rm*Lm/L個編號即可。
由於匹配規則可能發生變化，需要根據該變化對已經構建的規則樹中的規則進行刪除，因此，本發明提供了規則刪除的方法，該方法利用精確匹配，在規則樹中查找要被刪除的規則，然後刪除，參見圖7所示，其具體實現步驟包括步驟701將需要被刪除的規則的關鍵字以L-M為單位分為多段子關鍵字，其分段方法與上述通過規則樹保存字符串匹配規則時的分段方法相同；步驟702將第一段子關鍵字的上一級葉子置為空，將該上一級葉子的葉子編號置為0；步驟703自步驟701所分得的第一段子關鍵字開始，至倒數第二段子關鍵字為止，在規則樹中查找各段子關鍵字所對應的葉子，並將找到的葉子節點記錄在預先定義的數組中，具體依次執行以下步驟7031～步驟7032步驟7031當前的上一級葉子編號串聯上當前的子關鍵字，構成新的字串，在規則樹中查找關鍵字為該字串的最長前綴匹配的葉子，如果找到，則執行步驟7032；否則，刪除規則失敗，結束刪除過程；步驟7032將在步驟7031中所找到的葉子記錄在預先定義的數組B中，該數組B用於保存所經過的葉子節點，將該葉子的葉子編號作為上一級葉子編號，將當前處理的子關鍵字的下一級子關鍵字作為當前子關鍵字，返回步驟7031，直至處理完所述的倒數第二段子關鍵字；步驟704在規則樹中查找到最後一段子關鍵字所對應的葉子，將找到的葉子節點記錄在數組B中，具體為最後一段子關鍵字前串聯上一級葉子編號，形成新的字串，在規則樹中查找關鍵字與新的字串完全相同的葉子，如果找到，則將該葉子節點記錄在步驟7032所述的數組B中，否則，刪除過程失敗；步驟705找到數組B中所記錄的最後一個葉子節點，判斷該節點的「下級計數」域是否為0，如果是，表明該節點的下一級不再有其它的葉子與之相連，執行步驟706；否則，表明該節點的下一級還有其它規則的葉子與之相連，執行步驟708；步驟706刪除當前所處理的葉子節點，然後根據數組B中的記錄，找到該葉子節點的上一級葉子節點，以該上一級葉子節點作為當前處理的葉子節點，將該當前處理的葉子節點的「下級計數」域的值減1，然後執行步驟707；步驟707判斷當前處理的葉子節點的「下級計數」域的值是否為0，如果是，則返回步驟706，直至當前處理的葉子節點的「下級計數」的值不為0；否則，結束刪除規則的過程；步驟708隻刪除該葉子「其它」域中所保存的數據，並且刪除該葉子中指向其自身的回溯指針，保留該葉子節點，然後，結束刪除規則的過程。
本發明還提供了一種利用上述的字符串匹配規則樹進行字符串最長前綴匹配的方法，該方法將待匹配的字符串分為若干段子關鍵字，各段子關鍵字前分別串聯相應的葉子編號，構成新的字串，利用該新的字串在規則樹中進行匹配查找。
下面結合附圖，對本發明中利用規則樹進行字符串最長前綴匹配的方法進行詳細描述。
參見圖8，本發明實現利用規則樹進行字符串最長前綴匹配需要以下步驟步驟801將待匹配的字符串以L-M為單位分為多段子關鍵字，其分段方法與上述保存字符串匹配規則時的分段方法相同；步驟802將第一段子關鍵字的上一級葉子置為空，將該上一級葉子的葉子編號置為0；步驟803～步驟804將當前的上一級葉子編號串聯上當前的子關鍵字，構成新的字串，判斷在規則樹中是否能夠查找關鍵字為該字串的最長前綴匹配的葉子，如果找到，則執行步驟805，直至處理完步驟801分段所得到的所有子關鍵字；否則，執行步驟808；步驟805～步驟807判斷在步驟804中所找到的葉子是否級聯，如果是，表明該葉子並不是匹配規則的最後一個葉子節點，則將該葉子節點記錄在預先定義的數組A中，該數組用以保存匹配過程中所經過的葉子節點，然後，以該找到的葉子的編號作為當前的上一級葉子編號，以當前的子關鍵字的下一級子關鍵字作為當前關鍵字，返回步驟803；否則，表明該找到的葉子為滿足最長前綴匹配要求的字符串匹配規則的最後一級葉子，從該葉子的「其它」域中取出該規則的數據，結束匹配過程；步驟808～步驟810根據搜索過程中在數組A中所保存的已經經過的葉子節點，找到當前葉子節點的上一級葉子節點，判斷該葉子節點中的「回溯指針」域是否為空，如果為空，則返回步驟808，直至當前葉子的上一級葉子節點中的「回溯指針」域不為空，如果不為空，則根據上述已經介紹的回溯指針所指向的葉子的性質，當前葉子的上一級葉子節點中的「回溯指針」域所指向的葉子就是待匹配字符串的最長前綴匹配，從該葉子的「其它」域中取出規則的數據，然後，結束搜索過程；其中，如果在已經經過的所有葉子節點中都不能找到「回溯指針」域不為空的葉子，則表明在規則樹中無法找到待匹配的字符串的最長前綴匹配規則，最長前綴匹配失敗，結束搜索過程。
以上所述僅為本發明的較佳實施例而已，並不用以限制本發明，凡在本發明的精神和原則之內，所作的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。
權利要求
1.一種保存字符串匹配規則的方法，其特徵在於，該方法包括以下步驟步驟A以L-M為單位將當前待保存在規則樹中的規則的關鍵字分為S段子關鍵字，其中，在所分得的S段子關鍵字中，除第S段子關鍵字之外的各段子關鍵字的長度均等於L-M，第S段子關鍵字的長度小於或等於L-M，L為規則樹所保存規則中關鍵字的最長長度，M為葉子編號的長度，所分得的段數S為自然數；步驟B自第1段子關鍵字開始，到第S-1段子關鍵字為止，順序執行步驟B1和步驟B2，其中，第1段子關鍵字的上一級葉子編號為0；步驟B1當前子關鍵字前串聯上一級葉子的葉子編號，形成新的字串，判斷規則樹中是否已有以該新字串為關鍵字的葉子，如果沒有，則在規則樹中生成一個以該新字串為關鍵字的葉子，並為該新生成的葉子分配唯一的葉子編號，將該新生成葉子的級聯標誌置為級聯，然後將該新生成葉子置為當前葉子；如果有，且該找到的葉子的級聯標誌為級聯，則將該找到的葉子置為當前葉子；步驟B2將步驟B1中所處理的子關鍵字的下一段子關鍵字作為當前子關鍵字，將步驟B1中所處理的子關鍵字的葉子編號作為當前的上一級葉子編號，返回執行步驟B1；步驟C第S段子關鍵字前串聯上一級葉子的葉子編號，形成新的字串，判斷規則樹中是否已有以該新字串為關鍵字的葉子，如果沒有，則在規則樹中生成一個以該新字串為關鍵字的葉子，然後將待保存規則中的數據內容寫入該葉子，如果有，直接將待保存規則中的數據內容寫入該葉子。
2.根據權利要求1所述的方法，其特徵在於，步驟B1中所述判斷規則樹中是否已經有以所述字串為關鍵字的葉子包括以下步驟步驟B11判斷在規則樹中是否有以所述字串的最長前綴匹配為關鍵字的葉子，如果沒有，則判斷得到規則樹中沒有以所述字串為關鍵字的葉子，如果有，則執行步驟B12；步驟B12判斷步驟B11中找到的最長前綴匹配關鍵字是否與所述字串相同，如果不是，則判斷得到規則樹中沒有以所述字串為關鍵字的葉子，如果是，則判斷得到規則樹中有以所述字串為關鍵字的葉子。
3.根據權利要求2所述的方法，其特徵在於，步驟B12中，如果最長前綴匹配關鍵字與所述字串不同，該方法進一步包括將所述新生成的葉子的回溯指針指向該最長前綴匹配關鍵字所對應的葉子。
4.根據權利要求1所述的方法，其特徵在於，步驟B1中，如果在規則樹中找到的以所述字串為關鍵字的葉子不級聯，所述將找到的葉子置為當前葉子進一步包括為所述找到的葉子分配唯一的葉子編號，將該找到的葉子置為級聯，和將該找到的葉子的回溯指針指向其自身。
5.根據權利要求1所述的方法，其特徵在於，步驟C中所述判斷規則樹中是否已經有以該字串為關鍵字的葉子包括以下步驟步驟C1判斷在規則樹中是否有以所述字串的最長前綴匹配為關鍵字的葉子，如果沒有，則判斷得到規則樹中沒有以該字串為關鍵字的葉子，如果有，則執行步驟C2；步驟C2判斷步驟C1中找到的最長前綴匹配關鍵字是否與所述字串相同，如果不是，則判斷得到規則樹中沒有以該字串為關鍵字的葉子，如果是，則判斷得到規則樹中有以該字串為關鍵字的葉子。
6.根據權利要求1所述的方法，其特徵在於，步驟C中所述將規則的數據寫入葉子為將規則中的數據寫入葉子的「其它」域中。
7.根據權利要求1所述的方法，其特徵在於，在步驟B1中和步驟C中，所述在規則樹中新構建一個以所述字串為關鍵字的葉子進一步包括將該新構建葉子的上一級葉子中的「下級計數」域中的值加1。
8.根據權利要求7所述的方法，其特徵在於，刪除規則樹中的一個規則時，該方法進一步包括步驟D1以L-M為單位將待刪除的規則中的關鍵字分為T段子關鍵字；其中，在所分得的T段子關鍵字中，除第T段子關鍵字之外的各段子關鍵字的長度均等於L-M，第T段子關鍵字的長度小於或等於L-M，所分得的段數T為自然數；步驟D2自步驟D1的第1段子關鍵字開始，到第T-1段子關鍵字為止，順序執行以下步驟D21～步驟D22，其中，第1段子關鍵字的上一級葉子編號為0步驟D21在當前子關鍵字前串聯上一級葉子的葉子編號，形成新的字串，判斷在規則樹中能否找到以該字串為關鍵字的葉子，如果是，則執行步驟D22，否則，刪除過程失敗；步驟D22將在步驟D21中所找到的葉子節點記錄在預先定義的數組中，以該葉子的葉子編號作為上一級葉子編號，以當前子關鍵字的下一級子關鍵字作為當前子關鍵字，返回步驟D21；步驟D3第T段子關鍵字前串聯上一級葉子編號，形成新的字串，判斷在規則樹中能否找到其關鍵字與該新的字串完全相同的葉子，如果是，則將該葉子節點記錄在步驟D22所述的數組中，然後執行步驟D4，否則，刪除過程失敗；步驟D4根據步驟D22中數組的記錄，自該數組中所記錄的待刪除規則的最後一個葉子節點開始，到該待刪除規則的第一個葉子節點為止，依次執行以下步驟判斷當前處理的葉子的「下級計數」域是否為0，如果是，則刪除該當前處理的葉子，並將該當前處理的葉子的上一級葉子的「下級計數」域的值減1，然後，將該上一級葉子置為當前處理的葉子，返回執行本步驟；否則，結束刪除過程。
9.根據權利要求8所述的方法，其特徵在於，如果當前處理的葉子為所述最後一個葉子節點，且該葉子的「下級計數」域不為0，該方法進一步包括刪除該葉子節點中指向其自身的回溯指針。
10.一種利用字符串匹配規則樹進行字符串匹配的方法，其特徵在於，該方法包括以下步驟步驟E以L-M為單位將待匹配的字符串分為P段子關鍵字，其中，在所分得的P段子關鍵字中，除第P段子關鍵字之外的各段子關鍵字的長度均等於L-M，第P段子關鍵字的長度小於或等於L-M，所分得的段數P為自然數；步驟F自第1段子關鍵字開始，到第P段子關鍵字為止，順序執行以下步驟F1～步驟F2，其中，第1段子關鍵字的上一級葉子編號為0步驟F1當前子關鍵字前串聯上一級葉子的葉子編號，形成新的字串，判斷規則樹中是否有以該字串為關鍵字的葉子，如果有，則執行步驟F2，否則，匹配失敗；步驟F2判斷在步驟F1所找到的葉子是否級聯，如果是，則將該葉子的葉子編號作為上一級葉子編號，將當前子關鍵字的下一級子關鍵字作為當前子關鍵字，然後返回步驟F1，直至找到的葉子不級聯；否則，該葉子為匹配結果的最後一級葉子，從該葉子中取出規則的數據，匹配結束。
11.根據權利要求10所述的方法，其特徵在於，步驟F1中，如果規則樹中有以該字串為關鍵字的葉子，該方法進一步包括將該葉子按照順序記錄在數組中。
12.根據權利要求11所述的方法，其特徵在於，步驟F1中，如果規則樹中沒有以該字串為關鍵字的葉子，該方法進一步包括自所述數組記錄的最後一個葉子節點開始，按順序判斷該數組所記錄的葉子的回溯指針是否為空，如果是，則返回本步驟，直至判斷得到所記錄的所有葉子的回溯指針均為空，則匹配失敗，否則，回溯指針所指向的葉子為匹配結果的最後一級葉子，從該葉子中取出規則的數據，匹配結束。
全文摘要
本發明公開了一種保存字符串匹配規則的方法，該方法將待保存的規則的關鍵字分為若干段子關鍵字，各段子關鍵字分別與相應的葉子編號串聯形成字串，然後，以該字串為關鍵字在規則樹中構建葉子，從而將規則的關鍵字以及規則的數據部分插入規則樹中保存；本發明還公開了一種利用規則樹進行字符串匹配的方法，該方法將待匹配的字符串分為若干段子關鍵字，各段子關鍵字與相應的葉子編號串聯形成字串，在上述的規則樹中查找這些字串的最長前綴匹配，從而實現字符串的匹配過程。該方法能夠實現保存長字符串匹配規則，並且由於在利用規則樹保存規則時不需要子樹，因此可以減少硬體資源的佔用，提高處理能力。
文檔編號H04L29/00GK1652534SQ200410001099
公開日2005年8月10日 申請日期2004年2月3日 優先權日2004年2月3日
發明者肖斌 申請人:華為技術有限公司