匹配從噸模式的字符串

Question

我想製作一個URL匹配系統。它將以這種方式工作：

數據庫將包含許多模式。像這樣的模式的一些元數據：

pattern1, keyword 
pattern2, keyword 
... 
... 

我有一個輸入URL。如htttp：//example.com/blabla/111/2222/detail.htm

系統將獲取輸入和輸出輸入URL的最匹配模式的關鍵字。每秒會有超過20,000個請求。

我們需要設計的是模式和數據庫模型。我已經花了2周時間在這個系統中。

我在考慮匹配樹中的URL。

樹中的所有節點都能夠做2種輸出：哪個節點應該繼續匹配URL，或節點知道哪個關鍵字應該應用到URL。

每個節點都將連接一個回調（存儲在db中的腳本）。所以不同的節點會有不同的行爲。

但我們擁有的東西是噸模式。我想我需要有一個工具來將模式轉換爲「節點」。或者至少可以使用數據庫中的模式構建具有現有節點的樹。

我還在想樹生成。但應該有更好的方法。

任何想法都會非常有幫助。謝謝！！！

Answer 1

你需要一個工業強度的字符串匹配算法：http://en.wikipedia.org/wiki/String_searching_algorithm。我認爲數據庫支持的方法不會奏效，因爲它聽起來像需要模式匹配，而不是精確的前綴匹配。

但是，如果您使用的是前綴匹配（從頭開始的最長匹配），那麼您可以使用前綴trie，即trie。如果我是你，我會使用數據庫作爲持久存儲，但保留我的匹配內存中的匹配trie。

Answer 2

首先，請閱讀本文：

Regular Expression Matching Can Be Simple And Fast

在正則表達式的符號，你所擁有的是一個簡單的 「交替」：

pattern1|pattern2|pattern3|... 

...有你想要的附加約束要知道哪個模式匹配。我相信增加「湯普森NFA」來提供這些細節將是直截了當的。 （想法：在內部，在每個模式的末尾放置一個獨特的魔法標記以唯一標識模式，魔術標記將匹配空字符串...因此，當您的匹配引擎命中一個時，它立即知道哪個模式匹配。）

這會給你引擎的正則表達式的全部力量。即使你不想從那篇論文中調整NFA實現，在正則表達式中也有大量的理論和實踐工作。所以我肯定會從大的交替正則表達式開始，並從那裏開始工作。

爲了獲得更好的速度，你可以嘗試使用正則表達式優化器（類似於Perl的Regexp::Optimizer），然後再將大的交替regexp轉換爲NFA。

或者你可能想從一個通用的正則表達式引擎（如PCRE）開始，看看它是否足夠快。