一種基於硬體查找表的模式字符的查找方法與流程
2024-03-09 17:35:15 1
本發明涉及存儲器技術領域，尤其涉及一種基於硬體查找表的模式字符的查找方法。
背景技術：
字符串匹配即對一段數據進行指定字符串的查找匹配，可用於對帶有指定特徵字符串的一段數據進行篩選、過濾等應用。
現有字符串匹配方法多採用高級程式語言(如C語言,Java等)編程的軟體方式實現匹配算法，例如：哈希、KMP算法等，通過不同的查找順序減少得到匹配結果的時間。
但是，用高級程式語言編程運行於CPU(Central Processing Unit，中央處理器)，以軟體的形式實現字符串匹配的方法並行處理能力相對較差，速度相對較慢，需考慮運行軟體算法的CPU調度問題，不適合用於對實時高速數據流進行字符串匹配。
技術實現要素：
針對上述問題，本發明提出了一種基於硬體查找表的查找模式字符串的方法，所述硬體查找表包括至少一個存儲區；
所述存儲區包括多個存儲單元，所述存儲單元於所述存儲區內的訪問地址的編址方式對應一預定編碼字符集，還提供一模式字符串，所述存儲單元的位寬等於所述模式字符串的字符長度，所述存儲單元的每一位分別順序對應所述模式字符串中的每個字符；
還包括以下步驟：
步驟S1，將所述存儲區中，對應所述模式字符串中每個字符的所述存儲單元的對應位，置邏輯值1；
步驟S2，獲取一目標字符串；
步驟S3，讀取所述目標字符串的第一位；
步驟S4，定義讀取到的所述字符為當前字符；
步驟S5，以所述預定編碼字符集對所述當前字符進行解碼，以獲取所述當前字符對應的編碼；
步驟S6，根據所述編碼於所述存儲區查找對應的所述存儲單元；
步驟S7，於所述步驟S6查找到的所述存儲單元中獲取第一位；
步驟S8，判斷所述步驟S7中獲取的所述第一位的值是否為1，如果是則提供一數字值N，定義N＝1，並執行所述步驟S9，如果否執行所述步驟S17；
步驟S9，判斷所述模式字符串的字符長度是否等於1，如果是執行步驟S16；
步驟S10，判斷所述目標字符串剩餘的字符長度是否小於所述模式字符串的長度-N，如果是執行步驟S18；
步驟S11，讀取所述目標字符串的下一位，定義讀取到的字符為第二當前字符；
步驟S12，以所述預定編碼字符集對所述第二當前字符進行解碼，以獲取所述第二當前字符對應的編碼；
步驟S13，根據所述編碼於所述存儲區查找對應的所述存儲單元；
步驟S14，令N＝N+1，於所述步驟S13查找到的所述存儲單元中獲取第N位；
步驟S15，判斷所述步驟S14中獲取的所述第N位的值是否為1，如果是返回執行所述步驟S11，如果否執行所述步驟S17；
步驟S16，模式字符串查找成功，退出；
步驟S17，判斷所述當前字符是否為所述目標字符串的最後一位，如果是執行步驟S18，如果否讀取所述目標字符串的下一位，並定義讀取到的字符為當前字符，返回所述步驟S5。
步驟S18，模式字符串查找失敗。
上述的方法，其中，所述步驟S1包括以下步驟：
步驟S1A，讀取所述模式字符串的第一位字符；
步驟S1B，定義讀取到的所述字符為當前字符；
步驟S1C，以所述預定編碼字符集對所述當前字符進行解碼，以獲取所述當前字符對應的編碼；
步驟S1D，根據所述編碼於所述存儲區查找對應的所述存儲單元；
步驟S1E，根據所述當前字符於所述模式字符串中的位置於所述步驟S1D查找到的所述存儲單元中獲取對應的位；
步驟S1F，將所述步驟S1E中獲取的所述位置邏輯值1；
步驟S1G，判斷所述當前字符是否為所述模式字符串的最後一位，如果是執行步驟S2，如果否讀取所述模式字符串的下一位，並定義讀取到的字符為當前字符，返回所述步驟S1C。
上述的方法，其中，所述預定編碼字符集為ASCII編碼字符集。
上述的方法，其中，所述存儲單元的數量為128個。
上述的方法，其中，所述模式字符串的最大字符長度為8。
上述的方法，其中，所述步驟S16與所述步驟S17之間，還包括判斷所述目標字符串剩餘字符長度是否大於等於所述模式字符串的字符長度，若否則執行所述步驟S18。
一種基於硬體查找表的查找模式字符串的方法，所述硬體查找表包括多個如上任一所述的存儲區，每個所述存儲區中的存儲單元的位寬不同。
上述的方法，其中，所述硬體查找表為靜態隨機存取存儲器。
上述的方法，其中，所述存儲區設置有8個。
上述的方法，其中，8個所述存儲區按照所述存儲單元位寬大小依次拼合排列，使不同的所述存儲區中對應相同字符的所述存儲單元以相同的訪問地址進行訪問。
上述的方法，其中，8個所述存儲區按照所述存儲單元位寬依次為8位，7位，6位，5位，4位，3位，2位，1位。
有益效果：本發明提出的一種基於硬體查找表的模式字符的查找方法，採用硬體實現方式的查找匹配過程，不佔用CPU資源，提高系統並行處理能力，利用硬體運行速度快的特點，在若干個硬體時鐘周期內即可得到匹配結果，能對實時輸入的高速待匹配數據流進行實時的查找匹配結果輸出。
附圖說明
圖1為本發明一實施例中基於硬體查找表的模式字符的查找方法的流程示意圖；
圖2為本發明一實施例中存儲器的結構示意圖；
圖3為本發明一實施例中存儲區的排列結構示意圖；
圖4為本發明一實施例中對一個字符長度的模式字符進行查找的示意圖；
圖5為本發明一實施例中對兩個字符長度的模式字符進行查找的示意圖。
具體實施方式
下面結合附圖和實施例對本發明進行進一步說明。
在一個較佳的實施例中，如圖1所示，提出了一種基於硬體查找表的查找模式字符串的方法，如圖2所示，硬體查找表可以包括至少一個存儲區10；
如圖3所示，存儲區10可以包括多個存儲單元20，存儲單元20於存儲區10內的訪問地址的編址方式對應一預定編碼字符集，還提供一模式字符串，存儲單元20的位寬等於模式字符串的字符長度，存儲單元20的每一位分別順序對應模式字符串中的每個字符；
還包括以下步驟：
步驟S1，將存儲區10中，對應模式字符串中每個字符的存儲單元20的對應位，置邏輯值1；
步驟S2，獲取一目標字符串；
步驟S3，讀取目標字符串的第一位；
步驟S4，定義讀取到的字符為當前字符；
步驟S5，以預定編碼字符集對當前字符進行解碼，以獲取當前字符對應的編碼；
步驟S6，根據編碼於存儲區10查找對應的存儲單元20；
步驟S7，於步驟S6查找到的存儲單元20中獲取第一位；
步驟S8，判斷步驟S7中獲取的第一位的值是否為1，如果是則提供一數字值N，定義N＝1，並執行步驟S9，如果否執行步驟S17；
步驟S9，判斷模式字符串的字符長度是否等於1，如果是執行步驟S16；
步驟S10，判斷目標字符串剩餘的字符長度是否小於模式字符串的長度-N，如果是執行步驟S18；
步驟S11，讀取目標字符串的下一位，定義讀取到的字符為第二當前字符；
步驟S12，以預定編碼字符集對第二當前字符進行解碼，以獲取第二當前字符對應的編碼；
步驟S13，根據編碼於存儲區10查找對應的存儲單元20；
步驟S14，令N＝N+1，於步驟S13查找到的存儲單元20中獲取第N位；
步驟S15，判斷步驟S14中獲取的第N位的值是否為1，如果是返回執行步驟S11，如果否執行步驟S17；
步驟S16，模式字符串查找成功，退出；
步驟S17，判斷當前字符是否為目標字符串的最後一位，如果是執行步驟S18，如果否讀取目標字符串的下一位，並定義讀取到的字符為當前字符，返回步驟S5。
步驟S18，模式字符串查找失敗。
在一個較佳的實施例中，步驟S1包括以下步驟：
步驟S1A，讀取模式字符串的第一位字符；
步驟S1B，定義讀取到的字符為當前字符；
步驟S1C，以預定編碼字符集對當前字符進行解碼，以獲取當前字符對應的編碼；
步驟S1D，根據編碼於存儲區查10找對應的存儲單元20；
步驟S1E，根據當前字符於模式字符串中的位置於步驟S1D查找到的存儲單元20中獲取對應的位；
步驟S1F，將步驟S1E中獲取的位置邏輯值1；
步驟S1G，判斷當前字符是否為模式字符串的最後一位，如果是執行步驟S2，如果否讀取模式字符串的下一位，並定義讀取到的字符為當前字符，返回步驟S1C。
在一個較佳的實施例中，預定編碼字符集可以為ASCII編碼字符集，也可以是其他種類的編碼字符集，此處的ASCII編碼字符集只是其中一種情況，不應視為是對本發明的限制。
上述實施例中，優選地，存儲單元20的數量為128個。
上述實施例中，優選地，模式字符串的最大字符長度為8。
在一個較佳的實施例中，步驟S16與步驟S17之間，還包括判斷目標字符串剩餘字符長度是否大於等於模式字符串的字符長度，若否則執行步驟S18。
在一個較佳的實施例中，還提供了一種基於硬體查找表的查找模式字符串的方法，硬體查找表包括多個如上任一的存儲區10，每個存儲區中的存儲單元20的位寬不同。
在一個較佳的實施例中，硬體查找表為靜態隨機存取存儲器。
在一個較佳的實施例中，存儲區10設置有8個。
在一個較佳的實施例中，8個存儲區10按照存儲單元20位寬大小依次拼合排列，使不同的存儲區10中對應相同字符的存儲單元20以相同的訪問地址進行訪問。
在一個較佳的實施例中，如圖3所示，8個存儲區10按照存儲單元20位寬依次為8位，7位，6位，5位，4位，3位，2位，1位。
具體地，圖3中存儲區10中的存儲單元從右往左存儲空間依次增加，最大存儲空間為8位；圖4中是對一個字符長度的模式字符進行查找的示意圖；圖5中是對兩個字符長度的模式字符進行查找的示意圖，在這種存儲單元20從右往左存儲空間依次增加的先定下，存儲單元20的最大存儲空間為8位，即能查找的模式串的最大字符長度為8個字符長度。
綜上所述，本發明提出的一種基於硬體查找表的模式字符的查找方法，採用硬體實現方式的查找匹配過程，不佔用CPU資源，提高系統並行處理能力，利用硬體運行速度快的特點，在若干個硬體時鐘周期內即可得到匹配結果，能對實時輸入的高速待匹配數據流進行實時的查找匹配結果輸出。
通過說明和附圖，給出了具體實施方式的特定結構的典型實施例，基於本發明精神，還可作其他的轉換。儘管上述發明提出了現有的較佳實施例，然而，這些內容並不作為局限。
對於本領域的技術人員而言，閱讀上述說明後，各種變化和修正無疑將顯而易見。因此，所附的權利要求書應看作是涵蓋本發明的真實意圖和範圍的全部變化和修正。在權利要求書範圍內任何和所有等價的範圍與內容，都應認為仍屬本發明的意圖和範圍內。