技術領域

本發明涉及信息識別技術領域，更為具體地，涉及一種海量特征串集合的匹配方法及系統。?

背景技術

模式匹配是信息識別中的重要核心技術之一，用于從目標串中發現特征串。隨著信息技術的高速發展，模式匹配被越來越廣泛地應用于網絡信息搜索、數據流挖掘、網絡入侵檢測以及計算生物學等領域。?

模式匹配是指在文本T=t₁t₂...t_n中找出某個給定的特征串集合P={p₁，p₂，...，p_r}的所有出現位置，其中T和p_i(1≤i≤r)是在有限字符表∑上的字符序列。隨著網絡和生物學的發展，在匹配更多的特征串條目的同時，需要保持有較高的處理速度，這就對多模式匹配的處理能力提出了更高的要求。然而在很多現有的多模式匹配算法中，當特征串規模超過1萬時，由于其處理能力的下降，已經無法滿足需求，因而基于位并行與q-gram技術的多模式匹配方法應運而生。此種方法在數量10萬以下規模的特征串匹配過程中能夠取得較好的效果。?

基于位并行技術的多模式匹配算法，例如Shift-And/Or算法、BNDM算法，其基本思想是：將特征串集合與文本串的匹配狀態用位向量存儲，匹配過程就是用位操作更新位向量的過程。由于Shift-And和Shift-Or算法的原理基本相同，以下著重介紹Shift-And算法和BNDM算法的原理。?

（1）Shift-And算法維護一個字符串的集合，集合中的每個字符串既是特征串p的前綴，同時也是已讀入文本的后綴。每讀入一個新的文本字符，該算法采用位并行的方法更新該集合。該集合用一個位掩碼D=d_m...d₁來表示。D的第j位被置為1，當且僅當p₁...p_j是t₁...t_i的后綴。?

Shift-And算法首先構造一個表B，記錄字母表中每個字符的位掩碼b_m...b₁。如果p_j=c，掩碼B[c]的第j位被置為1，否則為0。首先置D=0^m，對?于每個新讀入的文本字符t_i+1，用如下公式對D進行更新：?

D_i+1←((D_i<<1)|0^m+11)&B[t_i+1]?

上面0^m表示有連續m個0，例如，用0³1來表示0001。在匹配時，逐個掃描文本字符并更新向量D，測試是否匹配成功的掩碼為10^m-1。即當D_i&10^m-1≠0^m時，在文本位置i處匹配成功。?

（2）BNDM（Backward?Nondeterministic?Dawg?Matching，向后非確定性匹配）算法的搜索與BDM算法相同，但它使用位并行來識別特征串。在當前搜索窗口內，設已讀入的字符串為u，BNDM算法維護一個集合，記錄u在p中所有出現位置。同Shift-And算法一樣，該集合可以用一個位向量D來表示。如果特征串p₁...p_j+|u|-1等于u，那么D的第m-j+1位是1，表示p的位置j是一個活動狀態。?

同Shift-And算法一樣，BNDM算法預先計算一張表B，表B用一個位掩碼記錄了該字符在p中出現的位置。對于每個新讀入的文本字符t_i，利用如下公式，可以從D更新到D'，其中，D'←(D<<1)&B[t_i]，初始化D=1^m，且需要用額外變量last保存特征串前綴的最左位置。?