だからタスク...
アルゴリズムの入力には、一連の行S1..SNがあります。 これらの行では、R（Si）= true、i [1、N]（数千のオーダーのN）になるような最小の正規表現Rを作成する必要があります。
最小性の要件は厳密ではなく、構築された正規表現の最小性を証明する必要はありません。 文字列S1..SNに類似の構造がある場合、regexpはこの構造を明らかにする必要があります。 プログラマーの標準タスクは適度に具体化されていますが、ある程度の行動の自由もあります。
ソリューションアルゴリズム...
- 文字列S1およびS2の最小の正規表現を見つけます。
- 各行に行の先頭と末尾の文字を追加すると、S1 = ^ S1 $になります
- S1とS2の最大共通部分文字列を探しています。 このUをS1、S2の最大共通部分文字列とします。 （ 最大共通部分文字列を見つけるためのいくつかの有名なアルゴリズムがあり、手段があれば、IBMからTeiresiasアルゴリズムを購入できます）
- T.O. 部分文字列Uは、行S1とS2をそれぞれ2つの部分（左と右）に分割することがわかります。
S1: S1L || U || S1R
S2: S2L || U || S2R
ここで、SiLとSiRは、文字列S1とS2の左右の部分文字列です。
- どうやら二分木による再帰が頼みます。 文字列Uをツリーのルートに配置します。 S1LとS2Lの両方の行が空でない場合、左の子を作成し、それらの比較を開始します。 同様に、右側の部分文字列について。
U
/ \
UL UR
- ある段階で共通の部分文字列が見つからない場合（または短い1〜2文字）、「。*」を現在のノードに配置し、最後の再帰呼び出しを終了します。 これは非常に失礼な表現ですが、私のタスクに適しています。 このステップでは、アルゴリズムをニーズに合わせて最適化する余地がたくさんあります。
- ツリーが構築された後、その対称走査により、S1およびS2に必要な正規表現SXを取得します（場合によっては「。*」になるため、式の開始文字と終了文字を再度追加する必要があります）
- 同じアルゴリズムを使用して、結果の文字列SXとS3を比較すると、SXが得られます。これは、最初の3行の正規表現です。
- すべての行にわたる帰納法により、目的の正規表現であるR = SXを取得します。
UPDの 例...
例として、Habrの記事へのリンクを見てみましょう。
S1=http://habrahabr.ru/blogs/edu_2_0/40236/ true
S2=http://habrahabr.ru/blogs/microsites/40089/ true
S3=http://habrahabr.ru/blogs/google_chrome/38748/ true
S4=http://habrahabr.ru/blogs/show/37839/ true
S5=http://nikolaikopernik.habrahabr.ru/blog/54889/ true
S6=http://habrahabr.ru/blogs/telecom/39902/ true
-----------------
REGEXP = ^http://.*habrahabr.ru/blog.*/$
SIZE : 6
TIME : 0.0070 s
この例はJavaで実行されます。 6000行でテスト-2秒で正規表現を作成しました。
UPD アルゴリズムが実装され、機能します。 適切な量の適切な量のデータに対して、かなり簡潔な正規表現を作成します。 批判して使用します。
UPD これが信頼できる理由と、単純な結合^（S1 | .. | SN）$がロールしない理由を説明します。 システムが行F1、F2、F3、...のストリームで動作することを想像してください。同様の構造のすべての行（URLを例に挙げます）。 いくつかの行は「良い」、他の行は「良くない」です:)そして、「良い」をチェックすることは非常に高価な操作です。 したがって、文字列の一般的なストリームから、長いチェックの後、文字列S1..SNは「良い」文字列であることがわかりました。 ストリングFiがストリングS1..SNと同様の構造を持っている場合、高い確率で「良好」になるという仮定はシステムで当てはまります。 それが正規表現がN行に基づいて構築されている理由です-そのため、行のタイプによってのみその「良さ」を判断します:)私は説明があまり賢くないことを願っています:)