優化一個巨大的「OR」模式

我有一個「或」如以下示例的模式： （X Y Z）| （X Y A B）| （X A K）| （M A J K）| （M A B）| （M Z）。 我的問題是，我真正的問題OR'ed操作數是巨大的，並導致大內存消耗問題。然而，形成圖案本身的條目很少（X，Y，Z，A，B，K，M和J）。因此，將該模式轉換（優化）爲如下模式： （X（（Y（Z |（A B）））|（A K）））| （M（（A（（J K）| B））| Z）） ，很可能會解決我的記憶問題。優化一個巨大的「OR」模式

我需要一種算法來採取輸入模式（如串也許）和產生優化的一個（如串也可能）。

來源

2013-05-01 Hesham Eraqi

對不起，我們在這裏沒有幫助，你可以自己寫，如果你遇到問題並且有疑問就回來， – kapa 2013-05-01 14:36:29

甚至用什麼語言？因爲這很容易，如果我知道我在回答什麼，只需要我一兩分鐘就可以到 – AngryDuck 2013-05-01 14:43:36

我試過解決這個問題，但失敗了。也許它需要額外的努力。 @AngryDuck我需要的算法不是代碼。這可能看起來微不足道，但我沒有實現它。 – 2013-05-01 14:46:06

請注意，(XA)|(XB) = X(A|B)。在此基礎上的財產，我可以建議如下貪婪的解決方案：

讓P是表達，X在P最常見的條目：P = (XR1)|(XR2)|...|(XRn)|Q。然後，以X了括號，P可以表示爲P = XR | Q，其中R = (R1|R2|...|Rn)。完成後，遞歸解決問題R和Q。

來源

2013-05-01 14:47:07

這聽起來是合乎邏輯的答案。謝謝:) – 2013-05-01 15:50:04

如果這些是序列，那麼'（AX）|（BX）=（A | B）X'也是正確的，但是你的方法不會簡化這些。（如果他們是布爾值也是如此，但更容易處理：在開始之前將所有元素放在一致的順序中） – rici 2013-05-01 17:57:35

通常，布爾表達式的簡化是NP-hard的（參見，例如，Is minimization of boolean expressions NP-Complete?）。

如果你有最多8文字或非否定變量，最多有256種可能min-terms，這是不是一個巨大的數字，所以我想你有很多更多的變數比8.考慮使用Quine-McCluskey Method簡化您的表達而不是一些特別的方法。或者，如果變量的數量很大但不是很大（例如，小於64的小數倍），則將每個最小項表示爲一個位掩碼，並且在讀取它們時一起表示OR項，而不是象徵性地進行評估。

來源

2013-05-01 15:04:08

從使用的regex標籤的，我推斷這是要優化的表達式是正則表達式，而不是一個布爾表達式。

正則表達式可以很容易地簡化爲DFA（狀態機），儘管狀態數量可能是指數正則表達式的大小。獲得DFA後，您可以使用其中一種衆所周知的算法minimizing DFAs;在O(n log n)中執行此操作並不困難，其中n是州的數量。

一個好的正則表達式庫應該能夠爲你做所有這些，但許多不這樣做。你可能想看看Ragel。

如果DFA的正則表達式實際上比正則表達式，這是罕見的，但不是完全未知的要大很多，你可能會發現，上述過程不會炸燬內存。由於這個原因，許多正則表達式庫不執行完整的DFA減少;相反，他們只是減少到一個NFA，然後懶洋洋地執行電力公司的建設，緩存結果。這應該以增加掃描時間爲代價來避免內存問題。

一個正則表達式的一個例子，其示出了指數吹脹：

A(A|B)(A|B)(A|B)(A|B)(A|B)(A|B)

相應的DFA必須至少有32種狀態（即，2 其中5是(A|B)重複數

來源

2013-05-01 15:40:57 rici

謝謝。我會看看Ragel，並會回覆你:) – 2013-05-01 16:31:34

優化一個巨大的 「OR」 模式

回答

相關問題

優化一個巨大的「OR」模式