のような一連のシンボルを生成できる Java プログラムを作成しました"abcdbcdefbcdbcdefg"。私が必要としているのは正規表現オプティマイザ"a((bcd){2}ef){2}g"です。
入力には のような Unicode が含まれている可能性があるため"a\u0063\u0063\bbd"、私は Java バージョンを好みます。
「より短い」式を取得したい理由は、スペース/メモリを節約するためです。ここでのシンボルのシーケンスは非常に長くなる可能性があります。
一般に、「最短」の最適化された正規表現を見つけるのは困難です。したがって、ここでは、「最短」の基準を保証するものは必要ありません。
与えられた入力文字列または文字列のセットに一致する最短の正規表現を作成する問題は、計算上「困難」になるだろうという厄介な感じがあります。（コルモゴロフの複雑さを計算する問題との類似点があります...）
abcdbcdefbcdbcdefgマッチング速度の点での最適な正規表現はabcdbcdefbcdbcdefg. 繰り返しグループを追加すると、正規表現文字列が短くなる場合がありますが、正規表現は速くなりません。実際、正規表現エンジンが繰り返しグループをアンロールしない限り、遅くなる可能性があります。
これが必要な理由は、スペース/メモリの制限によるものです。
これを行う必要があるという明確な証拠はありますか?
入力文字列が本当に長い場合を除き、これを行っても十分な量のスペースを節約できないと思います。(そして、それらが長い場合は、通常のテキスト圧縮アルゴリズムを使用して文字列を圧縮すると、より良い結果が得られます。)
正規表現は圧縮の代わりにはなりません
文字列定数を表すために正規表現を使用しないでください。正規表現は、多くの文字列の 1 つに一致するように設計されています。それはあなたがしていることではありません。
入力文字列の有限セットをエンコードするための小さな正規表現を見つけようとしていると思います。もしそうなら、可能な限り最良の件名を選択していません。
既存のプログラムを提供することはできませんが、プログラムを作成する方法については説明できます。
標準的な最小正規表現形式はなく、真の最小サイズの正規表現を決定するのは NP ハードです。確かにあなたのセットは有限なので、これはより単純な問題かもしれません. 私はそれについて考えなければならないでしょう。
しかし、優れたヒューリスティック アルゴリズムは次のようになります。
ステップ 3 では、一意の最小 DFAが得られることに注意してください。これはおそらく、文字列セットをエンコードする最良の方法です。