[發(fā)明專利]可變步長流分割和多模式匹配

在審

• 申請?zhí)枺?/td>: 201080016841.1
• 申請日: 2010-04-13
• 公開（公告）號: CN102395985A
• 公開（公告）日: 2012-03-28
• 發(fā)明（設(shè)計）人: N·華;T·V·拉克斯曼;H·宋
• 申請（專利權(quán)）人: 阿爾卡特朗訊公司
• 主分類號: G06K9/62
• 分類號: G06K9/62;H04L29/06
• 代理公司: 北京市中咨律師事務(wù)所 11247
• 代理人: 楊曉光;于靜

1.一種用于將輸入符號流與符號模式進行匹配的機器執(zhí)行的方法，該方法包括：

(a)將輸入符號流分割成為符號的可變大小塊以產(chǎn)生至少兩個不同長度的輸入流片段；以及

(b)將至少兩個輸入流片段中的每一個與符號模式的模式片段進行比較，其中模式片段相比于符號模式具有較少的符號。

2.根據(jù)權(quán)利要求1所述的方法，其中步驟(a)包括：

(a1)在輸入符號流中符號的k-gram上執(zhí)行單向函數(shù)以生成與k-gram相關(guān)聯(lián)的值，其中(k＞0)；

(a2)對值進行過濾以識別與至少一個k-gram相關(guān)聯(lián)的至少一個特定值；以及

(a3)根據(jù)與至少一個特定值相關(guān)聯(lián)的至少一個k-gram在輸入符號流中的位置將輸入符號流劃分為至少兩個片段。

3.根據(jù)權(quán)利要求2所述的方法，其中：

單向函數(shù)是哈希函數(shù)；

值是哈希值；

至少一個特定值是與至少一個k-gram相關(guān)聯(lián)的至少一個特定哈希值；

步驟(a1)包括產(chǎn)生與大小為w的窗內(nèi)的多個k-gram相對應(yīng)的多個哈希值，其中(k＜w)；以及

步驟(a2)包括選擇與至少一個k-gram相關(guān)聯(lián)的至少一個特定哈希值作為窗內(nèi)最小的哈希值。

4.根據(jù)權(quán)利要求1所述的方法，其中步驟(a)進一步包括將所述符號模式分割成至少頭塊、核心塊、和尾塊，其中所述模式片段對應(yīng)于頭塊、核心塊、和尾塊中的一個。

5.根據(jù)權(quán)利要求1所述的方法，其中使用單個的可變步長離散有限自動機(VS-DFA)執(zhí)行步驟(b)。

6.根據(jù)權(quán)利要求5所述的方法，其中使用包括至少兩個核心塊的字母表構(gòu)建VS-DFA。

7.根據(jù)權(quán)利要求5所述的方法，其中VS-DFA包括對應(yīng)于至少兩個不同的可能模式匹配中一個的準(zhǔn)狀態(tài)，其中在至少兩個不同的可能模式匹配中確定模式匹配是頭塊和尾塊的函數(shù)。

8.根據(jù)權(quán)利要求5所述的方法，其中：

所述符號模式對應(yīng)于第一符號序列；以及

使用至少包括模式片段和對應(yīng)于第二符號序列的第二符號模式的片段的字母表來構(gòu)建VS-DFA，第二符號序列與第一符號序列不同。

9.根據(jù)權(quán)利要求1所述的方法，進一步包括：

(c)將至少一個由p個連續(xù)的單符號輸入流片段組成的序列合并到單個p符號輸入流片段，其中(p＞1)。

10.一種用于將輸入符號流與符號模式進行匹配的設(shè)備，該設(shè)備包括：

(a)將輸入符號流分割成為符號的可變大小塊以產(chǎn)生至少兩個不同長度的輸入流片段的裝置；以及

(b)將至少兩個輸入流片段中的每一個與符號模式的模式片段進行比較的裝置，其中模式片段相比于符號模式具有較少的符號。