算法儘可能快地選擇正確的RegEx

Question

Django web框架使用正則表達式來調度傳入的請求。
假設應用程序非常龐大，並且有很多正則表達式，比如數百個。

對於任何傳入的請求，我如何確定哪些正則表達式儘快匹配？逐個遍歷列出的正則表達式是瘋狂的。

Answer 1

一個選項是構造一個可以並行匹配所有正則表達式的確定性自動機。一種方法如下：

1. 使用許多標準轉換算法之一將每個正則表達式轉換爲非確定型自動機。
2. 向這些自動機的所有開始狀態引入一個新的開始狀態，並帶有ε-轉換。這有效地創建了一個自動機，並行運行所有正則表達式自動機。確保以不同的方式在NFA中標記每個接受狀態，以便清楚地瞭解每個接受狀態對應的正則表達式。
3. 使用子集構造，將此NFA簡化爲DFA。在這個過程中，當把一個狀態標記爲接受狀態時，請記住哪個自動機認爲狀態爲接受狀態。
4. 生成DFA的表驅動實現。

現在，每當你收到新郵件時，您可以運行表驅動的這一信息，從而有效地並行運行，並返回其正則表達式，如果有的話，比賽的每一個正則表達式DFA。由於生成的DFA可能非常大，因此在內存中可能會產生大量成本，但匹配任何傳入正則表達式的時間與要匹配的字符串大小是線性關係。

Answer 2

如果您對應用程序有控制權，爲什麼不包含一些元數據來指示要使用的正則表達式的類型？您可以使用該元數據來選擇正確的RegEx。

Answer 3

將正則表達式合併爲一個，方法是將它們連接在一起|並命名組：（？< 1> regex1的）|（？< 2> regex2）|？（< 3> regex3 ...

測試輸入一次，並確定哪個正則表達式通過檢查指定的組相匹配

。