5

ネストされた正規表現の繰り返しが還元可能かどうかを確認できるアルゴリズムを探しています。正規表現の解析は既に行われていると仮定します。

例：

(1{1,2}){1,2} === 1{1,4}
    It matches 1, 11, 111, 1111 which can be rewritten as a single repeat

(1{2,2}){1,2} can not be reduced
    It matches 11 and 1111 which can not be rewritten as a single repeat.

(1{10,11}){1,2} can not be reduced

(1{10,19}){1,2} === 1{10,38}

(1{1,2}){10,11} === 1{10,22}

(1{10,11})* can not be reduced

(1*){10,11} === 1*

私はこのタイプの操作のパターンを見つけようとしてきましたが、考えられるすべての解決策に一致する必要がなく、縮小を妨げる穴を探す必要はありませんでした。f( A, B, C, D ) -> ( E, F )次のような任意の入力を解決できる単純な関数 ( ) が必要です。

(1{A,B}){C,D} -> 1{E,F}
4

2 に答える 2

3 
// (x{A,B}){C,D} -> x{E,F}
bool SimplifyNestedRepetition(int A, int B,
                              int C, int D,
                              out int E, out int F)
{
    if (B == -1 || C == D || A*(C+1) <= B*C + 1)
    {
        E = A*C;

        if (B == -1 || D == -1) F = -1;
        else F = B*D;

        return true;
    }
    return false;
}
  • 無制限の場合x{A,B}、何度でも繰り返すことができます。
  • (x{A,B}){C}常に還元可能です。
  • の場合、最長の繰り返しシーケンスと最短の繰り返しA*(C+1) <= B*C + 1シーケンスの間にギャップがないため、それを減らすことができます。CC+1

B = -1orは、またはD == -1のように無制限を意味します。x*x{5,}

テストケース:

Input           Reducible?
(x{0,0}){0,0}   Yes - x{0,0}
(x{0,1}){0,0}   Yes - x{0,0}
(x{0,2}){0,0}   Yes - x{0,0}
(x{1,1}){0,0}   Yes - x{0,0}
(x{1,2}){0,0}   Yes - x{0,0}
(x{1,3}){0,0}   Yes - x{0,0}
(x{2,2}){0,0}   Yes - x{0,0}
(x{2,3}){0,0}   Yes - x{0,0}
(x{2,4}){0,0}   Yes - x{0,0}
(x{0,0}){0,1}   Yes - x{0,0}
(x{0,1}){0,1}   Yes - x{0,1}
(x{0,2}){0,1}   Yes - x{0,2}
(x{1,1}){0,1}   Yes - x{0,1}
(x{1,2}){0,1}   Yes - x{0,2}
(x{1,3}){0,1}   Yes - x{0,3}
(x{2,2}){0,1}   No 
(x{2,3}){0,1}   No 
(x{2,4}){0,1}   No 
(x{0,0}){0,2}   Yes - x{0,0}
(x{0,1}){0,2}   Yes - x{0,2}
(x{0,2}){0,2}   Yes - x{0,4}
(x{1,1}){0,2}   Yes - x{0,2}
(x{1,2}){0,2}   Yes - x{0,4}
(x{1,3}){0,2}   Yes - x{0,6}
(x{2,2}){0,2}   No 
(x{2,3}){0,2}   No 
(x{2,4}){0,2}   No 
(x{0,0}){1,1}   Yes - x{0,0}
(x{0,1}){1,1}   Yes - x{0,1}
(x{0,2}){1,1}   Yes - x{0,2}
(x{1,1}){1,1}   Yes - x{1,1}
(x{1,2}){1,1}   Yes - x{1,2}
(x{1,3}){1,1}   Yes - x{1,3}
(x{2,2}){1,1}   Yes - x{2,2}
(x{2,3}){1,1}   Yes - x{2,3}
(x{2,4}){1,1}   Yes - x{2,4}
(x{0,0}){1,2}   Yes - x{0,0}
(x{0,1}){1,2}   Yes - x{0,2}
(x{0,2}){1,2}   Yes - x{0,4}
(x{1,1}){1,2}   Yes - x{1,2}
(x{1,2}){1,2}   Yes - x{1,4}
(x{1,3}){1,2}   Yes - x{1,6}
(x{2,2}){1,2}   No 
(x{2,3}){1,2}   Yes - x{2,6}
(x{2,4}){1,2}   Yes - x{2,8}
(x{0,0}){1,3}   Yes - x{0,0}
(x{0,1}){1,3}   Yes - x{0,3}
(x{0,2}){1,3}   Yes - x{0,6}
(x{1,1}){1,3}   Yes - x{1,3}
(x{1,2}){1,3}   Yes - x{1,6}
(x{1,3}){1,3}   Yes - x{1,9}
(x{2,2}){1,3}   No 
(x{2,3}){1,3}   Yes - x{2,9}
(x{2,4}){1,3}   Yes - x{2,12}
(x{0,0}){2,2}   Yes - x{0,0}
(x{0,1}){2,2}   Yes - x{0,2}
(x{0,2}){2,2}   Yes - x{0,4}
(x{1,1}){2,2}   Yes - x{2,2}
(x{1,2}){2,2}   Yes - x{2,4}
(x{1,3}){2,2}   Yes - x{2,6}
(x{2,2}){2,2}   Yes - x{4,4}
(x{2,3}){2,2}   Yes - x{4,6}
(x{2,4}){2,2}   Yes - x{4,8}
(x{0,0}){2,3}   Yes - x{0,0}
(x{0,1}){2,3}   Yes - x{0,3}
(x{0,2}){2,3}   Yes - x{0,6}
(x{1,1}){2,3}   Yes - x{2,3}
(x{1,2}){2,3}   Yes - x{2,6}
(x{1,3}){2,3}   Yes - x{2,9}
(x{2,2}){2,3}   No 
(x{2,3}){2,3}   Yes - x{4,9}
(x{2,4}){2,3}   Yes - x{4,12}
(x{0,0}){2,4}   Yes - x{0,0}
(x{0,1}){2,4}   Yes - x{0,4}
(x{0,2}){2,4}   Yes - x{0,8}
(x{1,1}){2,4}   Yes - x{2,4}
(x{1,2}){2,4}   Yes - x{2,8}
(x{1,3}){2,4}   Yes - x{2,12}
(x{2,2}){2,4}   No 
(x{2,3}){2,4}   Yes - x{4,12}
(x{2,4}){2,4}   Yes - x{4,16}
于 2012-06-25T05:50:15.697 に答える
2

バックリンクのような「高度な」正規表現機能を使用していない場合、正規表現は状態マシンの単純なバージョンである有限状態オートマトンにすぎません。それらには、すべての FSA に対して、 1 つの一意の最小 FSAが存在するという非常に優れた特性があり、それを見つけるのは非常に簡単です:ウィキペディア

あなたの問題はより具体的に見えますが、その中で説明されている最小化アルゴリズムのいくつかを見ると役立つと確信しています。

于 2012-06-25T08:00:14.340 に答える