[發(fā)明專利]一種基于FPGA的并行字符串匹配算法

有效

• 申請?zhí)枺?/td>: 201810307836.4
• 申請日: 2018-04-08
• 公開（公告）號: CN108628953B
• 公開（公告）日: 2022-02-15
• 發(fā)明（設(shè)計）人: 黃以華;殷海元
• 申請（專利權(quán)）人: 中山大學(xué)
• 主分類號: G06F16/9032
• 分類號: G06F16/9032
• 代理公司: 廣州粵高專利商標(biāo)代理有限公司 44102
• 代理人: 林麗明

本發(fā)明涉及一種基于FPGA的并行字符串匹配算法，通過FPGA并行處理來實現(xiàn)在一個時鐘周期找到模式字符串前j個字符的子串，以及它的前綴和后綴的最大公共元素值，通過前綴和后綴的最大公共元素值可直接得到并輸出NEXT數(shù)組，利用NEXT數(shù)組可實現(xiàn)多個模式字符串的并行匹配。

技術(shù)領(lǐng)域

本發(fā)明涉及信息處理領(lǐng)域，更具體地，涉及一種基于FPGA的并行字符串匹配算法。

背景技術(shù)

隨著計算機(jī)硬件的不斷發(fā)展，服務(wù)器和終端中CPU加協(xié)處理器的并行處理數(shù)據(jù)已得到廣泛應(yīng)用，尤其是FPGA在計算數(shù)據(jù)密集型中的加速。FPGA具有可重構(gòu)、并行化程度高等顯著優(yōu)點，已成為當(dāng)下常用的加速設(shè)備，近年來，越來越多的基于數(shù)據(jù)中心部署FPGA并行處理架構(gòu)，利用FPGA的硬件資源將復(fù)雜算法進(jìn)行加速處理已成為一種優(yōu)化性能的新途徑。針對信息處理過程中的字符串匹配算法，目前，較為經(jīng)典的有KMP算法、BM算法以及基于BM算法改進(jìn)提出的一種QS算法。現(xiàn)在均已廣泛用于各種字符串匹配的各種場合，盡管KMP算法很早就已提出，但是其算法具有良好擴(kuò)展性和實用性，時至今日仍然是目前廣為應(yīng)用的算法。但是，隨著數(shù)據(jù)流的不斷增長和近年來硬件加速的普遍化，在硬件中實現(xiàn)KMP核心算法是非常有必要的，也是大勢所趨。

KMP是一種模式匹配算法，此算法是在BF算法的基礎(chǔ)上進(jìn)行改進(jìn)的一種高效率算法。BF算法是一種樸素的字符串匹配算法，其實現(xiàn)過程是通過遍歷字符串的每一個位置，順序匹配字符串的每一個字符。BF算法起始于文本字符串T的第一個字符和模式字符串P中的第一個字符開始比較，如果其匹配成功，然后比較后續(xù)字符，否則文本字符串的下一個字符起在重新和模式字符串的第一個字符進(jìn)行比較。算法描述如下：

文本字符串：T＝s₁s₂…s_n

模式字符串：P＝p₁p₂…p_m

以上字符串的長度一般滿足條件nm，那么樸素的BF算法完成匹配的執(zhí)行步驟為：

(1)文本字符串T與模式字符串P左端對齊，使得開始于s₁與p₁；

(2)從左到右文本字符串T與模式串P的每一個字符，直到出現(xiàn)不匹配的情況，就執(zhí)行步驟(3)，若是模式串P已經(jīng)被完全匹配，則匹配成功，結(jié)束匹配。

(3)將P向右移動一個字符的位置，再次從模式串的第一個字符開始匹配；

(4)不斷重復(fù)上述(2)的過程，直到匹配成功，結(jié)束匹配。

在模式字符串右移一位后，樸素的BF算法已將丟失了之前已經(jīng)匹配到的字符的所有信息。因此，它可能會重復(fù)比較文本字符串的字符與模式串中的字符。這導(dǎo)致其最壞的情況下的復(fù)雜度是O(mn)。KMP算法利是基于此缺點，利用了之前已經(jīng)匹配到的信息，避免了重復(fù)匹配的情況。

因此，KMP算法的在搜索階段的復(fù)雜度降到了O(n)。如圖1所示的匹配過程示例，在第三趟匹配中，當(dāng)i＝7、j＝5字符比較不等時，又從i＝4、j＝1重新開始比較，然而，在i＝4和j＝1，i＝5和j＝1以及i＝6和j＝1這三個比較都是不必進(jìn)行的。僅僅需要模式字符串向右滑動3個字符的位置繼續(xù)進(jìn)行i＝7，j＝2時的字符串比較即可。同理，在第一趟匹配過程中出現(xiàn)不等時，僅需要模式字符串向右移動兩個字符的位置繼續(xù)進(jìn)行i＝3，j＝1時的字符比較。由此，整個匹配過程中，i指針都沒有回溯。