5

So this is a bit unusual use of RegEx; I want to calculate number (or indicate infinite if suitable) of distinct strings that would be matched by a specific pattern.

For example let's consider [a-zA-Z] which would yield 52, [a-zA-Z]{1,2} which would yield 2652 (52+52×52−52×2; subtracting 52×2 for strings like aa,MM which are not distinct) or [a-zA-Z]+ which would be ∞.

Of course I'd like this mechanism to be able to deal with more complex regular expressions than that. I'm particularly interested in solutions for PHP and Ruby. Is this even possible?

4

2 に答える 2

3

正規表現は、指定されたパターンと比較することにより、指定された文字列を照合するために使用されます。任意の正規表現は多数の文字列と一致する可能性があり、正規表現が長いほど、一致できる文字列が多くなります。

私の意見では、あなたが求めていることは正規表現ではできません。正規表現を分解し、一致する文字列の量を推測しようとするプログラムを作成できます。そうは言っても、そのようなプログラムの構築はおそらく簡単ではありません。

たとえば、あなたの場合、 [a-zA-Z] は完全に一致aするだけでなくz（大文字のバリアントでも同じです）、それらの文字を含む任意の文字列とも一致します。これは基本的に、これまでにない任意の文字列ですこれらの文字の少なくとも 1 つが含まれていると想像してください。

と のアンカーを追加する^と$、ヒットの数が減る可能性がありますが、それでも 48 を超える数が残ることになり{EmptyString}a{EmptyString}ます^a$。

于 2012-09-14T14:18:24.563 に答える
2

このタスクを達成するには、正規表現エンジン自体よりも複雑なソリューションが必要になると思います。正規表現エンジンは単に「テスト」(および「キャプチャ」しますが、その複雑さは些細なことです) にすぎませんが、タスクでは、潜在的な入力の言説全体をテストするか (もちろん、完全に非現実的です)、またはその数を推測する必要があります。数学的に潜在的な入力。しかし、潜在的な入力の数を推測するために、「このアトムの潜在的な入力は?」と尋ねる各ステップを除いて、正規表現エンジンが行うのとほぼ同じステップを踏まなければならないことは避けられないことに注意してください。

このようなカウンターをどのような目的で使用するかはわかりませんが、2 つの正規表現の潜在的な入力の大きさを比較することだけを目的としている場合は、サンプリング方法を使用することをお勧めします。つまり、大きなセットを生成することです。ランダムな文字列の数、およびこれらのうちのいくつが各正規表現に一致するかを数えます。(そして、これは行き過ぎであり、非常に推測的ですが、純粋なランダム文字列は自然言語のようなグループ化のパターンを示す可能性は低いため、フラクタル手法 (ラマンデルブロー) を使用してサンプルを生成する必要がある場合があります。 )

とにかく演繹的な数え方をしたい場合は、問題を単純化するのに役立つ 2 つのアイデアを次に示します。

  1. *or (エスケープされておらず、文字クラス内にない)が見つかった場合+、答えは無限大であることがわかります。についても同様です{M,}。編集:まあ、量指定子が正規表現の「不可能な」部分にない限り、たとえば(.*(?=a)(?=b))、次の文字は「a」と「b」の両方でなければならないと主張されている場合を除きます!

  2. 多くの式を交互ステートメントに拡張できるため、最終的な解決策が何であれ、文字クラスと量指定子を完全に無視し、交互グループごとのアトムの数 (互いに掛け合わせることができます) のみに焦点を当てることができます。

    1. のような文字クラス[0-9a-f]は に展開でき0123456789abcdef、さらに は に展開できます(?:0|1|2|...|d|e|f)。

    2. x?(別名 x{0,1})、x{M,N}、 などの有限量指定子は、 、 などx{,N}に拡張できます。(?:|x)(?:x|xx|xxx|...)

頑張ってください！

于 2012-09-14T15:04:17.207 に答える