有沒有用Java編寫的Regex優化器？

Question

我寫了一個Java程序，可以生成一系列符號，如"abcdbcdefbcdbcdefg"。我需要的是Regex優化器，它可能導致"a((bcd){2}ef){2}g"。

由於輸入可能包含unicodes，如"a\u0063\u0063\bbd"，我更喜歡Java版本。

我想得到一個「短」表達式的原因是爲了節省空間/內存。這裏的符號序列可能會很長。

一般來說，要找到「最短」的優化正則表達式很難。所以，在這裏，我不需要那些保證「最短」標準的人。

Answer 1

我有一個討厭的感覺，創建匹配給定輸入字符串或字符串集合的最短正則表達式的問題將在計算上是「困難的」。 （與計算Kolmogorov複雜性的問題相似...）

值得注意的是，在匹配速度方面abcdbcdefbcdbcdefg的最佳正則表達式很可能是abcdbcdefbcdbcdefg。添加重複組可能會使正則表達式字符串更短，但不會使正則表達式更快。事實上，除非正則表達式引擎展開重複組，否則它可能會變慢。

我需要這個的原因是由於空間/內存的限制。

您是否有明確的證據證明您需要來做到這一點？

我懷疑你不會通過這樣做來節省一些有價值的空間......除非輸入的字符串真的很長。 （如果他們是長的，那麼你將使用普通的文本壓縮算法壓縮字符串得到更好的結果。）

Answer 2

正則表達式是不是壓縮

不要使用普通的替代品表達式來表示一個字符串常量。正則表達式旨在用於匹配多個字符串之一。這不是你在做什麼。

Answer 3

我假設你正在試圖找到一個小的正則表達式來編碼一個有限的輸入字符串集合。如果是這樣，你還沒有選擇最好的主題行。

我不能給你一個現有的程序，但我可以告訴你如何寫一個方法。

沒有規範的最小正則表達式和determining the true minimum size regex is NP hard。當然你的集合是有限的，所以這可能是一個更簡單的問題。我得考慮一下。

但是一個良好的啓發式算法是：

1. 構建一個微不足道的非確定性有限自動機（NFA）接受所有的字符串。
2. 使用子集構造將NFA轉換爲確定性有限自動機（DFA）。
3. 使用標準算法最小化DFA。
4. 使用construction from the proof of Kleene's theorem得到一個正則表達式。

請注意，步驟3 確實爲提供了唯一的最小DFA。這可能是編碼字符串集合的最佳方式。