10

正規表現間のある種の距離を計算できますか？

アイデアは、2つの正規表現がどのように類似しているかを測定することです。

4

6 に答える 6

6

両方の正規表現に対して決定論的有限状態マシンを構築し、遷移を比較できます。両方の遷移の差を使用して、これらの正規表現の距離を測定できます。

于 2010-01-25T09:29:27.323 に答える
5

使用できるメトリックがいくつかあります。

  1. 有効な一致の長さ。一部の正規表現には固定サイズ、一部には上限、一部には下限があります。それらの長さまたは可能な長さがどれほど類似しているかを比較します。

  2. 一致する文字。すべての正規表現には、一致に含めることができる文字のセット（おそらくすべての文字）が含まれます。含まれている文字のセットを比較します。

  3. 大きなドキュメントを使用して、各正規表現が一致する数と、それらが同一である数を確認します。

厳密な同等性をお探しですか？

于 2010-01-25T09:25:11.503 に答える
2

SOに関する以前の質問に隠された答えがあります：正規表現からの文字列の生成。1つの正規表現を使用して文字列を生成し、そのうちのいくつが他の正規表現と一致するかを確認することで、（非対称）距離測度を計算できます。

これは、共有プレフィックス/サフィックスを取り除くことで最適化できます。たとえば、プレフィックスa[0-9]*をa[0-7]*共有して、とaの間の距離を計算できるようにします。[0-9]*[0-7]*

于 2010-01-25T12:07:51.083 に答える
2

実際の正規表現ストリング間のレーベンシュタイン距離を計算できると思います。これは確かに、2 つの異なる正規表現文字列間の「距離」を測定する 1 つの方法です。

もちろん、ここでは正規表現がまったく必要ない可能性があると思います。正規表現が適用される実際の「値」文字列のレーベンシュタイン距離を計算すると、より良い結果が得られる可能性があります。

于 2010-01-25T09:35:50.850 に答える
2

2 つの正規表現があり、一連の入力例がある場合は、すべての入力を各正規表現と照合してみることができます。入力ごとに:

  • 両方が一致するか、両方が一致しない場合、スコアは 0 です。
  • 一方が一致し、他方が一致しない場合、スコアは 1 です。

このスコアをすべての入力で合計すると、正規表現間の「距離」が得られます。これにより、典型的な入力に対して 2 つの正規表現がどのくらいの頻度で異なるかがわかります。サンプル入力セットが大きい場合、計算が非常に遅くなります。両方の正規表現がほぼすべてのランダム文字列に一致せず、予想される入力が完全にランダムである場合、まったく機能しません。たとえば、正規表現「sgjlkwren」と正規表現「ueuenwbkaalf」は、ランダムな入力でテストされた場合、おそらくどちらも一致しないため、このメトリックはそれらの間の距離がゼロであることを示します。それはあなたが望むものかもしれませんし、そうでないかもしれません (おそらくそうではありません)。

正規表現の構造を分析し、偏ったランダム サンプリングを使用して、完全にランダムな入力よりも頻繁に一致する文字列を意図的にヒットできる場合があります。たとえば、両方の正規表現で文字列が「foo」で始まる必要がある場合は、テスト入力も常に foo で始まるようにして、両方で失敗することがわかっている文字列をテストする時間を無駄にしないようにすることができます。

結論として、入力セットが制限されているか、正規表現言語が制限されている非常に特殊な状況でない限り、それは不可能だと思います。入力と正規表現に制限がある場合は、可能かもしれません。これらの制限が何であるかを指定してください。おそらく、より良いものを思いつくことができます.

于 2010-01-25T09:31:03.610 に答える
1

まず、2つの表現の「違い」がどのように見えるかを自分で理解する必要があると思います。基本的に、距離メトリックを定義します。

一般的に、作成するのはかなり異なります。何をする必要があるかによって、大きな違いとして、ある場所で1つの異なるキャラクターを許可することがわかる場合があります。他の場合では、結果として生じるが同じ文字をいくつでも許可しても、大きな違いは生じない可能性があります。

また、通常、距離関数について話すとき、それらを適用することも強調したいと思います...まあ、それらをトークンと呼びましょう。私たちの場合、文字シーケンス。あなたが喜んですることは、これらのトークンではなく、ルールにこのメソッドを適用することです。多数のトークンが一致します。それが理にかなっているのかよくわかりません。

それでも、私たちは何かを考えることができると信じていますが、一般的ではありませんが、1つの特定の非常に制限されたケースについてです。私たちに示すためのある種の例がありますか？

于 2010-01-25T09:25:12.667 に答える