一種字符串的搜索系統及方法與流程

2023-04-28 11:30:24 3

本發明涉及數據搜索技術領域，尤其涉及一種字符串的搜索系統及方法。

背景技術：

在企業大數據中，85％的數據是非結構化的文本日誌數據。在這類數據中快速查找、搜索信息對企業決策至關重要，例如在社交網上分析消費者的走向和趨勢可直接指導如何發放產品廣告，金融分析可能會在茫茫的大數據中尋找「我買了房子」，公安部門在反恐過程中可能會尋找並分析有關穆斯林極端分子的某些術語等等。在沒有預先設計好的以關鍵字為索引的結構數據的情況下，隨機字符串的搜索還是以掃描整個文件的方式來找，主要的掃描搜索工具有grep和awk，但這些軟體工具的數度很慢，用最快的伺服器運行，最快也只能達到100－300mbps，遠遠落後於如今最基本的網絡數度和存儲數度。最近，密齒根大學的科研人員提出了附在cpu旁的硬體加速器來完成在文件裡的字符搜索，大大地提高了掃描的數度。

但是，如果利用目前的掃描工具查找字符串，則需要把數據一一從存儲系統調到內存，然後伺服器的cpu用類似grep的軟體工具掃描、查找，要花幾個小時的時間，並且佔用了大量的伺服器資源；而硬體加速器雖然提高了純軟體的掃描數度，但是還是要首先將大量的數據從存儲系統讀進內存然後進行掃描搜索，其存儲瓶頸以及存儲與cpu的瓶頸問題依然沒有解決。

因此，需要一種速度快、能夠避免存儲瓶頸的字符串的搜索系統。

技術實現要素：

本發明所要解決的技術問題在於提供了一種字符串的搜索系統及方法，該搜索系統大大地減輕了伺服器cpu的負載、提高了搜索查詢速度。

為解決上述技術問題，本發明採用以下技術方案：

一方面，提供了一種字符串的搜索系統，該搜索系統包括：re搜尋引擎，及位於固態硬碟上的cpu核、flash控制器和flash陣列；所述re搜尋引擎包括re編譯器和re處理器，所述re處理器設於固態硬碟上；

所述re編譯器用於獲取用戶輸入的正則表達式和待匹配文件信息，將所述正則表達式編譯成指令序列，把所述指令序列發送給re處理器，把所述待匹配文件信息發送給cpu核；

所述re處理器用於接收所述指令序列，及接收flash控制器發送的根據cpu核的數據獲取請求從flash陣列中獲取的待匹配數據，從所述待匹配數據中搜索符合所述指令序列的數據，並將搜索結果返回給re編譯器；所述數據獲取請求由cpu核根據所述待匹配文件信息向flash控制器發送。

其中，所述re編譯器包括編譯預處理模塊、詞法分析模塊、語法分析模塊和隨機數產生模塊，編譯預處理模塊用於對用戶輸入的正則表達式進行輸入合法性檢查和優化處理；詞法分析模塊和語法分析模塊用於將經過優化的正則表達式翻譯成指令序列；re編譯器還包括隨機數產生模塊，用於產生在預置數值範圍的預置個數的隨機數，作為re處理器中的初始隨機種子。

其中，所述re處理器包括數據過濾模塊、多路調度模塊、運算模塊和多級歸併排序模塊：

所述數據過濾模塊用於根據所述指令序列中的前綴匹配規則，結合正則表達式的字邊界規則或一位負向零寬斷言對所述待匹配數據進行過濾；

所述多路調度模塊用於利用所述初始隨機種子採用偽隨機洗牌算法得到運算模塊中的運算單元的調度結果；

所述運算模塊包括若干個的運算單元，用於根據調度結果按照指令序列中的指令編碼和操作數完成過濾後的待匹配數據的搜索運算；

所述多級歸併排序模塊對搜索運算產生的結果按照偏移地址從小到大的順序排列得到搜索結果，並把所述搜索結果返回給re編譯器。

其中，所述re編譯器位於主機上或所述固態硬碟的cpu核上，主機與固態硬碟通過pcie接口進行數據傳輸。

其中，所述re編譯器在主機上由c語言實現。

其中，所述re處理器基於fpga由硬體描述語言verilog或vhdl實現。

其中，所述運算模塊包括16個運算單元。

其中，所述多級歸併排序模塊由級聯的多路歸併排序算法實現。

其中，所述編譯與處理模塊還用於將正則表達式中的重複操作進行展開，語法錯誤檢查，對於純字符的匹配快速生成指令序列。

另一方面，提供了一種字符串的搜索方法，該搜索方法包括：

re編譯器獲取用戶輸入的正則表達式和待匹配文件信息，將用戶輸入的正則表達式編譯成指令序列，把所述指令序列發送給re處理器，把所述待匹配文件信息發送給cpu核；

cpu核根據所述待匹配文件信息向flash控制器發送數據獲取請求；

flash控制器根據所述數據獲取請求從flash陣列中獲取待匹配數據，把所述待匹配數據發送給re處理器；

re處理器接收所述指令序列和所述待匹配數據，從所述待匹配數據中搜索符合所述指令序列的數據，並將搜索結果返回給re編譯器。

與現有技術相比，本發明的有益效果為：本發明搜索和查詢是在離數據最近的存儲設備或存儲系統進行，無需將大量的數據調到伺服器cpu內存，大大地減輕了伺服器cpu的負載、提高了搜索查詢速度，接近總線傳輸速度，與現有技術相比，查找速度可提高數十倍、甚至上百倍，從根本上解決了在大數據查找分析的存儲瓶頸和存儲系統與cpu接口的瓶頸問題。

附圖說明

為了更清楚地說明本發明實施例中的技術方案，下面將對本發明實施例描述中所需要使用的附圖作簡單的介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據本發明實施例的內容和這些附圖獲得其他的附圖。

圖1是本發明具體實施方式中提供的一種字符串的搜索系統的實施例的結構框圖。

圖2是本發明具體實施方式中提供的re編譯器的實施例的結構框圖。

圖3是本發明具體實施方式中提供的re處理器的實施例的結構框圖。

圖4是本發明具體實施方式中提供的一種字符串的搜索方法的實施例的方法流程圖。

具體實施方式

為使本發明解決的技術問題、採用的技術方案和達到的技術效果更加清楚，下面將結合附圖對本發明實施例的技術方案作進一步的詳細描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域技術人員在沒有作出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。

下面結合附圖1～3對本發明實施例作進一步的詳細描述。請參考圖1，其是本發明具體實施方式中提供的一種字符串的搜索系統的實施例的方法流程圖，如圖1所示，在一些實施例中，該搜索系統包括：re(regularexpression，正則表達式)搜尋引擎，及位於固態硬碟2上的cpu核21、flash控制器23和flash陣列24；re搜尋引擎包括re編譯器11和re處理器22，所述re處理器22設於固態硬碟2上；re編譯器11用於用於獲取用戶輸入的正則表達式和待匹配文件信息，將所述正則表達式編譯成指令序列，把所述指令序列發送給re處理器22，把所述待匹配文件信息發送給cpu核21；re處理器22用於接收所述指令序列，及接收flash控制器23發送的根據cpu核21的數據獲取請求從flash陣列24中獲取的待匹配數據，從所述待匹配數據中搜索符合所述指令序列的數據，並將搜索結果返回給re編譯器11；所述數據獲取請求由cpu核21根據所述待匹配文件信息向flash控制器23發送。用戶通過主機輸入正則表達式和待匹配文件信息，re編譯器11獲取用戶輸入的正則表達式和待匹配文件信息，re處理器22完成搜索之後將搜索結果返回給re編譯器11，re編譯器11對搜索結果進行處理，並通過主機呈現給用戶，用戶便可操作主機從re編譯器中獲取搜索結果對應的數據。

本發明實施例提供的搜索系統搜索和查詢由設於離數據最近的固態硬碟的re處理器進行，flash控制器將待匹配數據發送給re處理器，re處理器從待匹配數據中搜索符合所述指令序列的數據，在離數據最近的存儲設備或存儲系統進行搜索和查詢，無需將大量的數據調到伺服器cpu內存，大大地減輕了伺服器cpu的負載、提高了搜索查詢速度，接近總線傳輸速度，與現有技術相比，查找速度可提高數十倍、甚至上百倍，從根本上解決了在大數據查找分析的存儲瓶頸和存儲系統與cpu接口的瓶頸問題。

圖2是本發明具體實施方式中提供的re編譯器的實施例的結構框圖，如圖2所示，在一些實施例中，re編譯器11包括編譯預處理模塊112、詞法分析模塊113、語法分析模塊114和隨機數產生模塊111，編譯預處理模塊112用於對用戶輸入的正則表達式進行輸入合法性檢查和優化處理；詞法分析模塊113和語法分析模塊114用於將經過優化的正則表達式翻譯成指令序列；隨機數產生模塊111用於產生在預置數值範圍的預置個數的隨機數，作為re處理器中的初始隨機種子。

在一些優選的實施例中，所述編譯與處理模塊還用於將正則表達式中的重複操作進行展開，語法錯誤檢查，對於純字符的匹配快速生成指令序列。

圖3是本發明具體實施方式中提供的re處理器的實施例的結構框圖，如圖3所示，在一些優選的實施例中，re處理器22包括數據過濾模塊221、多路調度模塊222、運算模塊223和多級歸併排序模塊224：數據過濾模塊221用於根據所述指令序列中的前綴匹配規則，結合正則表達式的字邊界規則或一位負向零寬斷言對所述待匹配數據進行過濾；多路調度模塊222用於利用所述初始隨機種子採用偽隨機洗牌算法得到運算模塊223中的運算單元的調度結果；運算模塊223包括若干個的運算單元2231～223n，用於根據調度結果按照指令序列中的指令編碼和操作數完成過濾後的待匹配數據的搜索運算；多級歸併排序模塊224對搜索運算產生的結果按照偏移地址從小到大的順序排列得到搜索結果，並把所述搜索結果返回給re編譯器11。

數據過濾模塊221根據所述指令序列中的前綴匹配規則，結合正則表達式的字邊界規則或一位負向零寬斷言對待匹配數據進行過濾，使得搜索系統可根據用戶的需求查找100％的匹配、部分匹配、帶有通配符的字符串、變長的字符串、帶有特殊字符的字符串等等，數據過濾221加載字符串的同時對待匹配數據進行過濾，將前綴匹配的字符地址傳給re處理器22，不保存前綴不匹配的字符的地址，支持向前一位的零寬斷言過濾，用戶可配置，這一步驟大大減輕re處理器22的壓力。

多路調度模塊222採用偽隨機洗牌算法得到運算單元2231～223n的調度結果，使運算單元2231～223n根據調度結果按照指令序列中的指令編碼和操作數完成過濾後的待匹配數據的搜索運算，採用偽隨機洗牌算法可以避免由於待匹配數據固定格式造成單路繁忙問題，每個地址按調度結果傳給n個運算單元，n為2的n次方，n為正整數。作為一個優選的實施例，運算模塊包括16個運算單元，16個運算單元並行處理，各個運算單元相互獨立地執行指令系列，大大提高了搜索查詢速度。n取16，與選擇的總線寬度匹配，有利於提高搜索查詢速度。作為一個優選的實施例，n也可為其他2的n次方，如32、64等。

其中，採用偽隨機洗牌算法每一時刻都隨機產生一個0～15的排列，例如某一時刻產生的隨機排列為(14，8，9，2，10，5，13，0，4，15，7，1，6，11，12)，每個數出現且僅出現一次，即實現0～15的隨機洗牌算法，實現對16個運算單元的調度。作為一個優選的實施例，re編譯器內部的隨機數產生模塊產生32個互不相同的1～255的隨機數，其中4個隨機數為1組，用來計算一個0～23的隨機數。計算方法如下：每個隨機數在fpga中作為lfsr(線性反饋移位寄存器)的初始狀態，在每個時鐘到來的時候會產生1個0～31的隨機數。每個lfsr模塊產生的隨機數在0～23的概率為0.875，在24～31之間的概率為0.125。因此4個lfsr中產生的4個隨機數中至少有一個隨機數在0～23範圍內的概率為0.996。當隨機數都不在0～23之間時，默認數值為0。這樣8個0～23的隨機數用來產生0～15的排列。如果是0～32的隨機序列則需要32+16個隨機數，這和具體算法有關，但整體框架不變，都是由re編譯器產生初始隨機種子，再由fpga上的re運算器產生隨機數。

在一些優選的實施例中，re編譯器11設置於主機1上，如圖1所示。作為另一個優選的實施例re編譯器11也可設置於固態硬碟2的cpu核21上。在一些優選的實施例中，主機1與固態硬碟2通過pcie接口3進行數據傳輸，通過axi(advancedextensibleinterface)總線傳輸數據。在一些優選的實施例中，re編譯器11在主機1上由c語言實現，re處理器22在固態硬碟2上基於fpga(field－programmablegatearray，現場可編程門陣列)由硬體描述語言verilog或vhdl(very-high-speedintegratedcircuithardwaredescriptionlanguage，超高速集成電路硬體描述語言)等實現。

在一些優選的實施例中，所述多級歸併排序模塊224由級聯的多路歸併排序算法實現，將搜索結果按照在文本中的偏移地址從小到大的順序進行排列，並將最後結果返回給re編譯器11，返回結果的格式為：{行號+偏移地址+長度}。re編譯器對返回的結果進行處理，並通過主機呈現給用戶。

本發明實施提供的搜索系統搜索和查詢由設於離數據最近的固態硬碟的re處理器進行，flash控制器將待匹配數據發送給re處理器，re處理器從待匹配數據中搜索符合所述指令序列的數據，在離數據最近的存儲設備或存儲系統進行搜索和查詢，無需將大量的數據調到伺服器cpu內存，大大地減輕了伺服器cpu的負載、提高了搜索查詢速度，接近總線傳輸速度，與現有技術相比，查找速度可提高數十倍、甚至上百倍，從根本上解決了在大數據查找分析的存儲瓶頸和存儲系統與cpu接口的瓶頸問題，而且可根據用戶的需求查找100％的匹配、部分匹配、帶有通配符的字符串、變長的字符串、帶有特殊字符的字符串等等，該搜索系統具有並行和流水線的特殊設計，有效提高了搜索查詢速度，具有反向查找功能，根據字母出現的頻率，在所查找的字符串內任意一點開始搜索，能快速在非結構化的數據裡查找隨機任意字符串。

以下是本發明具體實施方式中提供的一種字符串的搜索方法的實施例，系統的實施例基於上述的一種字符串的搜索系統的實施例實現，在搜索方法中未盡的描述，請參考前述搜素系統的實施例。

請參考圖4，其是本發明具體實施方式中提供的一種字符串的搜索方法的實施例的方法流程圖，如圖4所示，在一些優選的實施例中，該搜索方法包括：

步驟s101：re編譯器獲取用戶輸入的正則表達式和待匹配文件信息，將所述正則表達式編譯成指令序列，把所述指令序列發送給re處理器，把所述待匹配文件信息發送給cpu核。

步驟s102：cpu核根據所述待匹配文件信息向flash控制器發送數據獲取請求。

步驟s103：flash控制器根據所述數據獲取請求從flash陣列中獲取待匹配數據，把所述待匹配數據發送給re處理器。

步驟s104：re處理器接收和所述待匹配數據，從所述待匹配數據中搜索符合所述指令序列的數據，並將搜索結果返回給re編譯器。

用戶可操作主機從re編譯器中獲取搜索結果對應的數據，以搜索美國電話號碼為例，對搜索系統的搜索流程做進一步說明。如美國電話號碼的正則表達式如下：(？<＝\s)\d{3}[-.]？\d{3}[-.]？\d{4}，其中「(？<＝\s)」表示匹配串的前面必須是空格字符，但是該空格字符不計入匹配串的長度；「\d」表示0-9的數字，後面的{3}表示前面的元素重複3次；「[-.]」表示「-」或「.」，後面的「？」表示前面的元素，即「[-.]」出現0次或1次。以此類推，該正表達式匹配的內容如下加黑部分所示：

p:444-555-1234f:246.555.8888m:1235554567

具體處理流程如下：

(1)re編譯器將用戶輸入的正則表達式編譯成指令序列，將指令序列發送給re處理器，並將用戶輸入的待匹配文件信息發送給cpu核。示例的正則表達式產生的指令序列如表1所示：

表1指令序列

其中「lsplit」表示循環開始，後面參數依次為循環次數上限、下限和循環結束的下一條指令地址；「prange48，57」表示匹配ascii碼介於48到57之間的字符；「ljmp」表示循環結束，後面的參數依次為循環次數上限、下限和循環起始指令地址；「ppair45，46」表示匹配ascii碼為54或46的字符；「match」表示匹配結束。

(2)cpu核根據待匹配文件信息向flash控制器發送數據獲取請求。

(3)flash控制器根據數據獲取請求從flash陣列中獲取待匹配數據，將待匹配數據發送給re運算器。

(4)re處理器接收所述指令序列、及所述待匹配數據，根據所述指令序列從所述待匹配數據中搜索符合指令序列的數據，並將搜索結果返回給re編譯器。若運算器包括16個運算單元，具體過程如下：

a)前綴檢查：每16b數據為一組，因此輸入數據分為三組「p:_444-555-1234」、「f:_246.555.8888」和「m:_1235554567」。過濾器按照「\d」規則對前綴進行匹配，只有偏移為3的「4」、偏移為19的「2」和偏移為35的「1」符合要求(見下劃線處)。

b)多路調度器產生為三組數據分別產生三組16個偽隨機洗牌的結果，因此偏移3、19、35分別進入不同的運算單元。否則，由於3、19、35除以16的餘數均為3，則都會被發送給運算單元3，造成運算單元3繁忙，其他運算器空閒的狀態。

b)以偏移為3為例，運算單元n根據指令序列依次對後續「246.555.8888」進行匹配，結果為匹配成功。

c)多級歸併排序模塊採用歸併排序算法對16個運算單元的搜索結果進行排序。歸併排序分為二級，{0，1，2，3}分為一組進行歸併排序，以此類推，16個運算單元會得到4個結果，再將這個結果進行歸併排序，系統最終輸出的搜索結果({行號，偏移地址，長度})為：{0，3，12}，{0，19，12}，{0，35，10}。

d)re處理器把搜索結果返回給re編譯器。re編譯器對搜索結果進行處理，並通過主機呈現給用戶。

本發明實施搜索和查詢是在離數據最近的存儲設備或存儲系統進行，無需將大量的數據調到伺服器cpu內存，大大地減輕了伺服器cpu的負載、提高了搜索查詢速度，接近總線傳輸速度，與現有技術相比，查找速度可提高數十倍、甚至上百倍，從根本上解決了在大數據查找分析的存儲瓶頸和存儲系統與cpu接口的瓶頸問題，而且可根據用戶的需求查找100％的匹配、部分匹配、帶有通配符的字符串、變長的字符串、帶有特殊字符的字符串等等，該搜索系統具有並行和流水線的特殊設計，有效提高了搜索查詢速度，具有反向查找功能，根據字母出現的頻率，在所查找的字符串內任意一點開始搜索，能快速在非結構化的數據裡查找隨機任意字符串。

以上結合具體實施例描述了本發明的技術原理。這些描述只是為了解釋本發明的原理，而不能以任何方式解釋為對本發明保護範圍的限制。基於此處的解釋，本領域的技術人員不需要付出創造性的勞動即可聯想到本發明的其它具體實施方式，這些方式都將落入本發明的保護範圍之內。