我的任務是確定一個字符串是否應該導致在我的C＃命令處理器中引發一個命令，這可以在運行時配置。確定正則表達式是否相互抵消
我有兩個正則表達式集合。對於第一個集合「EnabledPatterns」，如果任何一個模式匹配命令字符串，則啓用該命令。對於第二個'DisabledPatterns'，如果任何模式匹配命令字符串，則該命令被禁用。可能存在重疊，EnabledPattern中的模式與DisabledPattern中的模式匹配相同的字符串。例如：。
EnablePatterns包含^ ABC $ DisabledPatterns包含^ A * $
鑑於上面的例子中我想除去EnabledPatterns條目，從而diabling命令處理用於匹配 'EnabledPatterns' 命令。正則表達式。
有沒有辦法做到這一點作爲一個預處理，每次收集的任何改變，以便我可以建立一個活動，啓用模式的列表，而無需交出命令字符串。我基本上想要確定當重疊部分被移除時是否有可能的匹配。
爲什麼你需要白名單和黑名單？我認爲你在這裏遇到了一個合乎邏輯的問題，把它寫出來，並對你的意圖有一個思考。
因爲用戶可能想要在例如夜班期間禁用啓用的命令的子集。 – 2009-11-25 23:39:29
你正在過度。運行啓用的命令。獲得結果。針對第一個結果運行禁用的命令。記住這個可憐的混蛋，他必須在將來保持你的解決方案！ – Gregory 2009-11-26 03:09:33
我會說你最好的選擇是先檢查被禁用的模式，然後只檢查啓用模式，如果禁用的模式都返回false。
編輯：
好吧...我只是通過這個曾與一些人在辦公室......
原來有A N^4的算法，您可以用做這個。
基本上，你需要：
要比較DFA，您需要先對起始節點處的兩個圖進行並行深度優先搜索，然後再搜索輸入。每次在每個圖形中跟隨輸入時，都會創建一個複合節點（n1，n2），其中n1是第一個圖形中的節點，n2是第二個圖形中的節點。 （n1 *，n2）（n1，n2 *），（n1 *，n2 *）或者（n1，n2），如果其中一個節點爲接受狀態， 。
一旦你完成了，看看n1是接受狀態（n1 *，x）的所有邊緣。如果X也是接受狀態，則regex1是regex2的子集。
該算法應該在最壞情況下爲O（n^4）。這可能會更好，但不會比這更糟糕。
我會看到關於發佈一些代碼。
但是，顯然，如果改變的正則表達式的體積顯着低於正在檢查的傳入內容的體積，那麼您只會這樣做。否則，取消正則表達式的費用將抵消任何正則表達式的性能優勢。
編輯2：
我的O分析（N^4）運行時間是基於狀態的在較大的DFA的數量。然而，這忽略了這樣一個事實，即在NFA轉換之後，DFA中的狀態數可能最終爲2^M，其中M是NFA中的狀態數。
這意味着實際的複雜性最終被類似：
O（2^4）
這是非多項式（這是壞的）。
大多數情況下，NFA國家的數量不會接近那麼高，所以在實踐中不應該太慢。
但是，我會高度建議運行這樣的任何類似的離線過程，而不是一個在線的。
編輯3：
是可能的正則表達式直接轉換爲DFA。但是，我找不到在線算法的描述，每一個都只是指向龍書中的實現。不幸的是，我現在沒有它的副本（這是可恥的，我知道）。所以現在我只是繼續使用regex => nfa => dfa方法。在找到一個庫之後，拿到這本書，並從中獲取算法，我會研究修改代碼以使用直接方法。
我試圖在處理任何命令之前減少列表 - 到達命令的速度可能很大，如果我可以快速返回，因爲我已經預先計算出沒有啓用任何命令。 – 2009-11-25 23:41:06
我可以看到。我剛剛發佈了一些可能有用的更新。如果我有一些時間，我會發布一些代碼。 – 2009-11-26 02:11:04
Scott， 讚賞 - 我需要閱讀關於NFA/DFA的信息以瞭解您的帖子。 – 2009-11-26 21:23:03
你想做的事情歸結爲兩個正則表達式的AND是否爲空（即不匹配任何內容）。理論上講，這是可以計算的。兩種常規語言的AND也是常規的。而普通語言是否爲空的問題是可以確定的。
但是，這可能對您沒有多大幫助，因爲您可能不希望在程序中模擬有限自動機。
你的傳入命令流的本質是什麼，我猜想這是你可能的優化的來源。 – Don 2009-11-26 00:29:03
這些命令是結構中的字符串。 for Finance.Transactions.Backup。*例如。我可能想在一天中'啓用'Finance.Transactions.Post。*，但在晚上禁用'Finance'。然而，任務是在沒有命令存在的情況下消除模式 - 無論何時重新更換過濾器，我都需要將它們（用於處理速度）降低到可能的最低數量的模式。在前面的例子中，有效的已啓用模式列表將是空的。 – 2009-11-27 20:15:50