將字符串與多個模式相匹配的最快方法

我有一個字符串列表，它們是帶有AND和OR運算符和通配符的模式。現在給出一個輸入字符串，如果匹配任何模式則返回true，否則返回false。將字符串與多個模式相匹配的最快方法

說，我有'n'模式和長度'm'的查詢現在，顯而易見的方法是運行一個循環和grep爲字符串中的每個模式。這需要O（nm）時間。

現在，我的問題是，是否有可能做得更好？我在想某種表達式評估有限狀態機可能？有沒有這樣的名稱/參考實現？

感謝

2016-11-15 Saksham Manchanda

請注意，現代CPU在線性數據結構上快速循環（特別是當循環適合片內存儲器並且可以預測分支時），並且在指針之後和片外訪問內存時要慢得多。無論你嘗試什麼，你都應該將它與一個愚蠢的蠻力算法進行比較。 –

您當然可以創建一個有限狀態機來處理來自所有模式的合併搜索。有關將RegEx轉換爲FSM的討論，請參閱http://stackoverflow.com/questions/525004/short-example-of-regular-expression-converted-to-a-state-machine。 –

您正在尋找Boyer–Moore string search algorithm。

如果您首先解析模式並將其構建爲Abstract Syntax Tree，然後將查詢字符串解析爲另一個抽象語法樹，然後使用節點搜索（對於根），您也可以獲得好結果，樹比較算法（而不是微不足道的）來查看在查詢字符串中是否找到任何模式字符串。理論上，查詢字符串的解析可以在O（n）中完成，但實際上我懷疑它會導致更好的性能。儘管這可能是一個有趣的練習。

來源

2016-11-15 22:52:31

我想你已經誤解了OP（或者我有）;我認爲OP *是*使用「模式」來指代正在搜索的內容。我認爲有很多字符串搜索，並且只有一個字符串搜索。（此外，「模式」似乎比簡單的子串複雜得多。） – ruakh

@ruakh你說得對。我將重新回答我的答案。 –

將字符串與多個模式相匹配的最快方法

回答

相關問題