2

わかりました...だから、これはストレッチかもしれません。TextStrings のリストを関数にフィードすると、正規表現の構文が返されます。追跡するアイテムのタグまたはタグのパターンを使用しています。存在する可能性のあるすべてのパターンを検出できるようにしたいと考えています。それをまとめられる正規表現がいいなと思いました。

これは以前に行われたことがありますか。

私は VB.NET で作業しています C# の提案は問題ありません。

多分これは貧弱なプログラミング設計です。しかし、ほとんどの場合、どこから検索を開始する必要がありますか? Googleで何を検索しますか？

または、このような機能を設計する方法を教えてもらえますか?

4

3 に答える 3

1

非常に興味深い質問です。良い答えがあるかどうかはわかりませんが、これが最初に頭に浮かんだことでした：

Loop through each target string
    Loop through each character in each target string
       Categorize that character as precisely as possible.  7 = \d, f=[a-z] etc
       Create a list of the categories for each character in order.
       Add that list of categories to a list of lists
    End character loop
End target string loop

カテゴリ リストのリストを使用して、すべてのターゲット文字列に一致する正規表現を決定してみてください。たとえば、カテゴリ リストのリストが次のようになっているとします。

\d,\d,\d,[a-z],[a-z]
\d,\d,\d,[a-z],[a-z]
\d,\d,[a-z],[a-z]

2 ～ 3 桁の数字の後に 2 つの小文字が続く正規表現のニーズを判断できる場合があります。始めることはあまりありませんが、おそらく開始する場所はありますか? あなたが実用的な解決策を思い付くかどうか見てみたいと思います...

于 2012-08-24T22:52:33.673 に答える
0

この問題についての私の考え：

問題文

有限文字列S1..Snの有限集合Sが与えられた場合、自明な解^ S1 | S2 | S3 | .. | Sn $を避けて、これらの文字列全体に一致し、他の文字列には一致しない正規表現を見つけます。

観察

'。'を持つことはできません。文字クラスまたは'+'、'*'または'{x、}'数量詞。これらは、入力セット外の文字列の照合を可能にするためです。

アルゴリズム

# strings and collections indexed from 1

regex := "^" + make_regex(S) + "$"

function make_regex(Ss)

    # string -> length
    Ls := { length Ss[i] | 1 <= i <= n } 

    # set of starting characters
    Cs := unique { Ss[i][1] | i in 1..n L[i] >= 1 } 
    cl := last in Cs

    ret := "("
    For c in Cs

        # substrings of all non-empty strings that start with c
        Scs := { S[i][2..] | i in 1..n, L[i] >= 1, S[i][j] = c }
        ret := ret + c + make_regex(Scs) 

        If c != cl
            ret := ret + "|"
        End

    End

    If Ss contains ""
        ret := ret + "|()"

    End
    ret := ret + ")"
    return ret
End

入力

abc
abcd
cde
cef

結果

^(a(b(c(d|())))|c(d(e)|e(f)))$

一意の文字列の正規表現を見つけることはその長さに対して線形であるため、これはO（n * Lmax）であると思います。ただし、入力セット内の一般的なプレフィックスが多いほど、O（Lmax）に近くなるため、結果と一致します。^ S1 | S2 | .. | Sn $、つまりO（n*）よりもはるかに高速です。 Lmax）。

于 2012-08-26T18:16:15.480 に答える
0

これ.*は面白いコメントですが、すべてのデータを受け入れ、他のデータを受け入れない最小限の正規表現 (オペレーターごとのコスト メトリックの場合) であるという制約を追加すると、質問はより興味深いものになります。

これは次の問題につながります。データはおそらくすべての例を反映していないため、実際に探しているのはデータをクラス (文字、数値、記号) で分割することです。しかし、それも難しいでしょう: あるインスタンスでは文字の大文字小文字を本当に気にかけているが、別のインスタンスでは気にしていない場合はどうなるでしょうか。一部の記号が区切り記号であり、他の記号が区切り記号であり、さらに他の記号がデータの一部である場合はどうでしょう。

言い換えれば、十分な制限があれば、(制限された文法で) 可能な正規表現を幅優先検索し、機能するものを見つけたら停止することができます。特定のユースケースでそれが現実的である場合、それらの制限に大きく依存します...一般的な正規表現の制限のないケースでは現実的ではありません。

于 2012-08-24T23:32:34.713 に答える