[發明專利]海量特征串集合的匹配方法及系統有效
| 申請號: | 201310363274.2 | 申請日: | 2013-08-16 |
| 公開(公告)號: | CN103544208A | 公開(公告)日: | 2014-01-29 |
| 發明(設計)人: | 侯智瀚;尹延偉 | 申請(專利權)人: | 東軟集團股份有限公司 |
| 主分類號: | G06F17/30 | 分類號: | G06F17/30 |
| 代理公司: | 北京鴻元知識產權代理有限公司 11327 | 代理人: | 陳英俊 |
| 地址: | 110179 遼*** | 國省代碼: | 遼寧;21 |
| 權利要求書: | 查看更多 | 說明書: | 查看更多 |
| 摘要: | |||
| 搜索關鍵詞: | 海量 特征 集合 匹配 方法 系統 | ||
1.一種海量特征串集合的匹配方法,包括預處理階段和特征串匹配階段,其中,所述預處理階段包括:
確定位向量掩碼表的空間容量;
根據對輸入的特征串集合所包含的算法字符個數及特征串的數量的統計,對所述特征串進行分組,建立分組位向量掩碼表;
根據所述算法字符的位長確定散列函數;
所述特征串匹配階段包括:
根據輸入的特征串所包含的算法字符的個數確定普通匹配窗口長度和長匹配窗口長度,并為當前待匹配數據設置一個偏移值作為起始偏移值,其中,通過機器字符與所述散列函數的轉換獲得所述算法字符;
根據所述起始偏移值為起點對當前待匹配數據進行偏移并定位,獲取當前普通匹配窗口的數據;
從所述當前普通匹配窗口的末端獲取一個算法字符,用直接尋址的方式從所述位向量掩碼表中獲取位向量;其中,
如果所述位向量中的所有有效位不全為0,則以所述位向量為初始向量,以當前讀入的算法字符作為新的長匹配窗口的起點,在所述新的長匹配窗口的長度范圍內,采用位并行方式對所述位向量進行即時更新,并對即時更新的位向量進行非零判斷;其中,在所述位向量進行更新的過程中,
如果所述位向量的有效位全為0,將當前讀入的算法字符的位置作為新的起始偏移值,并結束更新;
如果所述位向量的有效位不全為0且所述位向量的某一個分組的最高位為1,則匹配當前分組特征串的后綴,保留初始向量中相應的有效位;其中,
在所述特征串的分組為不等長分組時,如果已經匹配后綴的特征串所屬分組的長度小于等于后綴命中時在長匹配窗口中讀入的算法字符的個數,則直接記錄一次命中的可能,可能會發生命中的特征串的末尾即是當前讀入的算法字符;
當所述位向量的更新過程結束時,如果所述特征串發生過后綴匹配,則僅保留初始向量中所有發生過后綴命中的活動位,其余全部清0,作為所述特征串前綴匹配的初始向量,在當前的起始偏移值所指向的普通匹配窗口中進行所述特征串匹配命中的確認;
如果在匹配所述特征串的后綴過程中,所述偏移值沒有改變,則對所述偏移值進行重新定位,獲取新的起始偏移值,并在所述偏移值重新定位的過程中,以位并行的方式同步進行特征串匹配。
2.如權利要求1所述的海量特征串集合的匹配方法,其中,在對所述特征串進行分組的過程中,
根據所述特征串的分組數、每組位長、每組所容納的特征串的數量以及所述位向量掩碼表的參數,獲取每組的過濾通過率;
通過每組的過濾通過率獲得每組分組方式的過濾通過率,將所有分組方式中過濾通過率最低的分組方式作為最終的分組方式對所述特征串進行分組。
3.如權利要求2所述的海量特征串集合的匹配方法,其中,通過下述等式獲取每組分組方式的過濾通過率:
其中,g表示分組數,Ri表示每一組內的過濾通過率,Si是前i組的過濾通過率,當i=g時,Sg表示每組分組方式的過濾通過率。
4.如權利要求1所述的海量特征串集合的匹配方法,其中,在當前的起始偏移值所指向的普通匹配窗口中進行匹配命中的確認的過程中,
依次從所述普通匹配窗口末端反向逐個獲取算法字符,更新所述位向量;
如果更新后的所述位向量的某一個分組的最低位是1,則記錄一次特征串匹配命中的可能,其中,可能會發生命中的特征串的起點即是當前讀入的算法字符。
5.一種海量特征串集合的匹配系統,包括特征串分組單元和特征串匹配單元:
其中,所述特征串分組單元包括:
空間容量確定單元,用于確定位向量掩碼表的空間容量;
位向量掩碼表建立單元,用于根據對輸入的特征串集合所包含的算法字符個數及特征串的數量的統計,對所述特征串進行分組,建立分組位向量掩碼表;
散列函數確定單元,用于根據所述算法字符的位長確定散列函數;
所述特征串匹配單元包括:
初始單元,用于根據輸入的特征串所包含的算法字符的個數確定普通匹配窗口長度和長匹配窗口長度,并為當前待匹配數據設置一個偏移值作為起始偏移值,其中,通過機器字符與所述散列函數的轉換獲得所述算法字符;
數據獲取單元,用于根據所述起始偏移值為起點對當前待匹配數據進行偏移并定位,獲取當前普通匹配窗口的數據;
位向量獲取單元,用于從所述當前普通匹配窗口的末端獲取一個算法字符,用直接尋址的方式從所述掩碼表中獲取位向量;
匹配單元,用于當所述位向量中的所有有效位不全為0時,以所述位向量為初始向量,以當前讀入的算法字符作為新的長匹配窗口的起點,在所述新的長匹配窗口的長度范圍內,采用位并行方式對所述位向量進行即時更新,并對即時更新的位向量進行非零判斷;其中,在所述位向量進行更新的過程中,
如果所述位向量的有效位全為0,將當前讀入的算法字符的位置作為新的起始偏移值,并結束更新;
如果所述位向量的有效位不全為0且位向量的某一個分組的最高位為1,則已經匹配了當前分組特征串的后綴,保留初始向量中相應的有效位;其中,
在所述特征串的分組為不等長分組時,如果已經匹配后綴的特征串所屬分組的長度小于等于后綴命中時在長匹配窗口中讀入的算法字符的個數,則直接記錄一次命中的可能,可能會發生命中的特征串的末尾即是當前讀入的算法字符;
當所述位向量的更新過程結束時,如果所述特征串發生過后綴匹配,則僅保留初始向量中所有發生過后綴命中的活動位,其余全部清0,作為所述特征串前綴匹配的初始向量;
匹配命中單元,用于在匹配單元發生過后綴命中時,在當前的起始偏移值所指向的普通匹配窗口中進行所述特征串命中的確認;
偏移值獲取單元,用于在匹配所述特征串的后綴過程中,當所述偏移值沒有改變時,對所述偏移值進行重新定位,獲取新的起始偏移值,并在偏移值重新定位的過程中,以位并行的方式同步進行特征串匹配。
該專利技術資料僅供研究查看技術是否侵權等信息,商用須獲得專利權人授權。該專利全部權利屬于東軟集團股份有限公司,未經東軟集團股份有限公司許可,擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作,請聯系【客服】
本文鏈接:http://www.17sss.com.cn/pat/books/201310363274.2/1.html,轉載請聲明來源鉆瓜專利網。





