[發(fā)明專利]確定自動機(jī)的空間壓縮方法

有效

• 申請?zhí)枺?/td>: 200910090556.3
• 申請日: 2009-08-20
• 公開（公告）號: CN101630323A
• 公開（公告）日: 2010-01-20
• 發(fā)明（設(shè)計）人: 楊毅夫;劉燕兵;劉萍;郭莉
• 申請（專利權(quán)）人: 中國科學(xué)院計算技術(shù)研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京泛華偉業(yè)知識產(chǎn)權(quán)代理有限公司
• 代理人: 王 勇

1.一種確定自動機(jī)的空間壓縮方法，包括：

步驟1)、對確定自動機(jī)中的各個狀態(tài)做分簇操作，得到多個用于表示 狀態(tài)集合的簇；

步驟2)、將所述確定自動機(jī)中各個狀態(tài)的轉(zhuǎn)移邊按步驟1)所得到的 簇分類，得到多個簇矩陣、與所述簇矩陣對應(yīng)的位圖以及一個剩余矩陣； 其中，所述簇矩陣包括指向同一簇的轉(zhuǎn)移邊，所述位圖用于描述簇矩陣中 相關(guān)元素的有效性；所述剩余矩陣包括確定自動機(jī)中未被包含到所述簇矩 陣中的剩余轉(zhuǎn)移邊；

步驟3)、為所述簇矩陣中的各行提取基值，然后將所述簇矩陣轉(zhuǎn)換成 一個偏移量矩陣，再將偏移量矩陣中的各行合并，增加用于標(biāo)記可合并狀 態(tài)的索引數(shù)組，得到所述簇矩陣的壓縮矩陣；其中，

所述的基值為基值所在行所對應(yīng)簇中的最小值，所述的偏移量矩陣中 的偏移量為所述簇矩陣中的轉(zhuǎn)移邊的值與所述基值間的差；

所述的將偏移量矩陣中的各行合并時，滿足以下規(guī)則：在矩陣T中， 當(dāng)且僅當(dāng)對任意字符c滿足T[r][c]＝-1或者T[s][c]＝-1或者T[s][c]＝ T[r][c]時，行r和行s是可合并的，其中，“-1”代表對應(yīng)位置的值為無效 值。

2.根據(jù)權(quán)利要求1所述的確定自動機(jī)的空間壓縮方法，其特征在于， 還包括：

步驟4)、壓縮所述的剩余矩陣。

3.根據(jù)權(quán)利要求1或2所述的確定自動機(jī)的空間壓縮方法，其特征 在于，所述的步驟1)包括：

步驟1-1)、從確定狀態(tài)機(jī)的初始狀態(tài)開始做廣度優(yōu)先遍歷，得到trie 樹結(jié)構(gòu)；

步驟1-2)、對所得到的trie樹中的各個狀態(tài)做分簇操作，得到多個用 于表示狀態(tài)集合的簇；其中，在做分簇操作時，將所述確定自動機(jī)的初始 狀態(tài)作為一個單獨的簇，將所述確定自動機(jī)中一個狀態(tài)的所有直接后繼狀 態(tài)的集合作為一個簇。

4.根據(jù)權(quán)利要求1或2所述的確定自動機(jī)的空間壓縮方法，其特征 在于，所述的步驟2)包括：

步驟2-1)、判斷所述確定自動機(jī)中剩余轉(zhuǎn)移邊的數(shù)目是否小于閾值， 若小于，則將剩余的轉(zhuǎn)移邊填入所述的剩余矩陣中，否則，執(zhí)行下一步；

步驟2-2)、將所述確定自動機(jī)中剩余的所有轉(zhuǎn)移邊中指向同一簇最多 的轉(zhuǎn)移邊轉(zhuǎn)移到一個簇矩陣中，并用一個對應(yīng)的位圖表示該簇矩陣中元素 的有效性。

5.根據(jù)權(quán)利要求1或2所述的確定自動機(jī)的空間壓縮方法，其特征 在于，所述的位圖包括多個與所述簇矩陣具有一一對應(yīng)關(guān)系的位圖，所述 位圖用于描述與其具有對應(yīng)關(guān)系的簇矩陣中元素的有效性。

6.根據(jù)權(quán)利要求1或2所述的確定自動機(jī)的空間壓縮方法，其特征 在于，所述的位圖包括一個位圖，所述位圖利用位圖中元素的數(shù)值大小描 述所述轉(zhuǎn)移邊在按簇分類后的位置。

7.一種由權(quán)利要求1-6之一的確定自動機(jī)的空間壓縮方法所得到的矩 陣實現(xiàn)正則表達(dá)式匹配的方法，包括：

輸入文本，用所述矩陣對所述輸入文本進(jìn)行匹配；所述的用所述矩陣 對所述輸入文本進(jìn)行匹配包括：

步驟a)、在一個簇矩陣對應(yīng)的位圖中查看位圖元素bitmap[s][c]是否 為有效狀態(tài)，若為有效狀態(tài)，則將所述簇矩陣中基值base[s]和偏移量 T[equal[s]][c]之和的值作為當(dāng)前狀態(tài)的直接后繼狀態(tài)，若為無效狀態(tài)，執(zhí) 行下一步；

其中，所述的s代表當(dāng)前狀態(tài)，所述的c代表輸入文本中所要匹配的 字符，所述的equal代表用于標(biāo)記可合并狀態(tài)的索引數(shù)組，所述的T代表 簇矩陣；

步驟b)、判斷是否還存在未經(jīng)處理的簇矩陣，若存在，則取出未經(jīng)處 理的下一個簇矩陣及其位圖后，重新執(zhí)行步驟a)，否則，執(zhí)行下一步；

步驟c)、從所述的剩余矩陣中取出T′[s]][c]的值，作為當(dāng)前狀態(tài)的直 接后繼狀態(tài)；其中，所述的T′表示剩余矩陣。

8.根據(jù)權(quán)利要求7所述的正則表達(dá)式匹配方法，其特征在于，在所 述的步驟b)中，按照所包含的轉(zhuǎn)移邊數(shù)量的多少依次選擇所述的簇矩陣。