自動正規表現ビルダ

私はN個の文字列を持っています。また、私に知られていないK個の正規表現があります。各文字列は、正規表現のいずれかと一致するか、またはガベージです。セットにはL個のガベージ文字列があります。 KとLの両方は不明です。自動正規表現ビルダ

正規表現を推論したいと思います。明らかに、この問題には無限の数の解があります。私は正規表現の "詳細" を最大化）L

3を最小限に抑える）K

2を最小限に抑える）が

1、 "合理的に良い解決策" を見つける必要があります。私はこの品質にとって正しい言葉が何であるか分かりません。たとえば、文字列 "ab123"は/ ab \ d + /または/\ w+.+/と記述できますが、最初の正規表現はより特定的です。

すべての3つの要件は、特定の合理的な重みを付けて、1つの複合基準として扱う必要があります。

L = 0、K = 1の場合（正規表現は1つで、ごみはありません）、文字列に対してLCS（最長共通部分シーケンス）を見つけ、対応する正規表現そこから。しかし、 "ノイズ"（L> 0）がある場合、この方法は機能しません。

すべてのアイデア（または既存の作品へのポインタ）を高く評価します。

出典

2009-05-21 Igor Krivokon

情報は何を与えていますか？ちょうどN弦ですか？正規表現はすでに決定されていますが、あなたから隠されていますか？あなたは簡単に "|"でそれらを結合することによって、文字列の特定のセットに一致する正規表現を生成することができます。 –

:)これは不正行為になります。私はこの種の解決策を防ぐために別の基準が必要だと思う...正規表現のlenthを制限する、そうだ。 –

あなたの条件＃3は、指定されたN個の文字列のセットにない一致する文字列の数を最小限に抑えるものとして記述することができます。最小化する3つのことがあるとすれば（L = 0が必要な場合もありますが）、より重要な要素を重み付けする必要があります。 – user57368

ここで賢明なことはありませんが、おそらく私はこの問題を完全に理解していませんか？

なぜLを0に減らすだけではないのですか？正規表現ごとに各文字列をチェックします。文字列が正規表現のいずれとも一致しない場合、それはガベージです。一致した場合、一致した正規表現/文字列を覚えておき、それぞれの正規表現の定義を推測するためにL = 0、K = 1でLCSを実行します。

出典

2009-05-21 22:46:11 benson

私は最初に正規表現を持っていません。それらを推論する問題。 –

学問のキーワードは「文法的推論」です。残念ながら、あなたが提案していることを行うための効率的で一般的なアルゴリズムはありません。あなたの本当の問題は何ですか？

編集：データ記述言語に興味があるようです。 PADS（http://www.padsproj.org/）は典型的な例です。何をしようとする

出典

2009-05-21 22:55:20 Dave

>本当の問題は何ですか？私は趣味のプロジェクトとして、ビッグファイル用の「マジックエディタ」を実装しています。大部分はデータ（時折のコメントや「不規則性」を加えたもの）です。頻繁に書式を変更したり、値の列などを削除したりする必要があります。通常、私はこの種のものをすばやくperl one-linerでやっています。しかし、私はregexesに精通していない人々のためのより "視覚的"なソリューションを作りたかったのです。彼らはただ1つの行を編集し、ファイル内の他の（類似の）行は自動的に変更されます。 –

PADSをチェックします、ありがとう！ –

は、ひねりを加えた語学学習または言語推論です：代わりにを与えられた例（そしておそらく反例）のセットの上にを一般化、あなたが持つ言語を推測したいです小さくても特定文法。

私はどれだけの研究が行われているのか分かりません。ただし、n文字列をすべて受け入れる最小（=一般的）正規表現を検索する場合は、MDL（最小記述長）とFSMs（有限状態機械）の論文を検索してください。 Google Scholarで

つ興味深いのクエリ：

出典

2009-05-21 22:56:09 Stephan202

ありがとう！ MDLに関する論文をチェックします。 –

答えて

関連する問題