102

コンピュータがユーザー提供の例によって正規表現を「学習」することは可能ですか?

明確にするために：

  • 正規表現を学びたくない。
  • テキストから部分を選択するか、開始または終了マーカーを選択することによって、ユーザーが対話的に提供する例から正規表現を「学習」するプログラムを作成したいと考えています。

出来ますか？Google で検索できるアルゴリズムやキーワードなどはありますか?

編集：回答ありがとうございますが、この機能を提供するツールには興味がありません。論文、チュートリアル、ソース コード、アルゴリズムの名前などの理論的な情報を探しているので、自分で何かを作成できます。

4

10 に答える 10

36

有効な一致のリストのみに基づいて意味のある正規表現を生成できるコンピューター プログラムはありません。その理由をお見せしましょう。

例として 111111 と 999999 を指定すると、コンピューターは次のように生成します。

  1. これら 2 つの例に正確に一致する正規表現:(111111|999999)
  2. 6 つの同一の数字に一致する正規表現(\d)\1{5}
  3. 6 つの 1 と 9 に一致する正規表現[19]{6}
  4. 任意の 6 桁に一致する正規表現\d{6}
  5. 上記の 3 つのいずれかで、単語の境界がある場合。\b\d{6}\b
  6. 最初の 3 つのいずれかで、前後に数字がないもの。例: (?<!\d)\d{6}(?!\d)

ご覧のとおり、例を正規表現に一般化する方法はたくさんあります。コンピュータが予測可能な正規表現を構築する唯一の方法は、考えられるすべての一致を一覧表示することです。次に、それらの一致に正確に一致する検索パターンを生成できます。

考えられるすべての一致をリストしたくない場合は、上位レベルの説明が必要です。それこそが、正規表現が提供するように設計されているものです。6 桁の数字の長いリストを提供する代わりに、「任意の 6 桁」に一致するようにプログラムに指示するだけです。正規表現構文では、これは \d{6} になります。

正規表現と同じくらい柔軟な高レベルの記述を提供する方法は、正規表現と同じくらい複雑でもあります。RegexBuddyのようなツールができることはすべて、高レベルの記述の作成とテストを容易にすることです。簡潔な正規表現構文を直接使用する代わりに、RegexBuddy を使用すると、平易な英語のビルディング ブロックを使用できます。ただし、例を一般化する必要がある場合とそうでない場合を魔法のように知ることができないため、高レベルの説明を作成することはできません。

ユーザーが提供するガイドラインに従ってサンプル テキストを使用して正規表現を生成するツールを作成することは確かに可能です。このようなツールを設計する際の難しい部分は、正規表現自体よりもツールの習得を難しくせず、ツールを一般的な正規表現ジョブまたは単純な正規表現に制限することなく、必要なガイド情報をユーザーにどのように求めるかです。

于 2009-03-07T01:42:42.713 に答える
8

はい、確かに「可能」です。擬似コードは次のとおりです。

string MakeRegexFromExamples(<listOfPosExamples>, <listOfNegExamples>)
{
   if HasIntersection(<listOfPosExamples>, <listOfNegExamples>)
     return <IntersectionError>

   string regex = "";
   foreach(string example in <listOfPosExamples>)
   {
      if(regex != "")
      {
         regex += "|";
      }
      regex += DoRegexEscaping(example);
   }
   regex = "^(" + regex + ")$";

   // Ignore <listOfNegExamples>; they're excluded by definition

   return regex;
}

問題は、例のリストに一致する正規表現が無数にあることです。このコードは、セット内で最も単純で最も愚かな正規表現を提供し、基本的に正の例のリスト内のすべてに一致します (負の例を含め、それ以外には何も一致しません)。

本当の課題は、すべての例に一致する最短の正規表現を見つけることだと思いますが、それでも、結果の式が「正しいもの」であることを確認するために、ユーザーは非常に適切な入力を提供する必要があります。

于 2009-03-05T19:46:51.500 に答える
7

「誘導」という言葉だと思います。あなたは規則正しい文法を身に付けたいと思っています。

有限の例（正または負）では不可能だと思います。しかし、私の記憶が正しければ、相談できるオラクルがあれば可能です。(基本的には、プログラムが内容になるまで、ユーザーに yes/no の質問をさせなければなりません。)

于 2009-03-05T19:40:42.967 に答える
5

このサイトで少し遊んでみたいと思うかもしれません。これは非常にクールで、あなたが話していることと似たようなことをしているように聞こえます: http://txt2re.com

于 2009-03-05T19:36:41.930 に答える
4

プロローグに基づいて、このような問題専用の言語があります。プロゴルといいます。

他の人が述べたように、基本的な考え方は帰納的学習であり、AI サークルでは ILP (帰納的論理プログラミング) と呼ばれることがよくあります。

2 番目のリンクは、ILP に関する wiki 記事です。これには、このトピックについて詳しく知りたい場合に役立つソース資料が多数含まれています。

于 2009-03-07T01:53:24.433 に答える
3

@ユヴァルは正しいです。あなたが見ているのは計算学習理論、つまり「帰納的推論」です。

「学ぶ」の定義は自明ではないため、質問はあなたが思っているよりも複雑です。一般的な定義の 1 つは、学習者はいつでも答えを吐き出すことができますが、最終的には答えを吐き出すのをやめるか、常に同じ答えを吐き出さなければならないというものです。これは入力の数が無限であることを前提としており、プログラムがいつ決定に到達するかについての保証はまったくありません。また、後で別のものを出力する可能性があるため、いつ決定に達したかはわかりません。

この定義により、通常の言語は学習可能であると確信しています。他の定義では、それほどではありません...

于 2009-03-06T21:19:04.220 に答える
0

人が正規表現を学ぶことができれば、プログラムも基本的に可能です。ただし、学習できるようにするには、そのプログラムを正しくプログラムする必要があります。幸いなことに、これはかなり有限の論理空間であるため、プログラムにオブジェクトなどを見ることができるように教えるほど複雑ではありません。

于 2009-03-05T19:43:59.103 に答える