WindVoiceの日記： 【夏休みの妄想】正規表現を考えてくれるプログラム

プログラムで、正規表現を生成してくれるようなものはできないだろうか。

入力文字列をいくつか与えて、それのどこにマッチして欲しいのかを指定する。
入力を充分にすれば、必要十分な正規表現を教えてくれるようなものだ。
例えば、以下のような動作をする。

my $teacher = Tell::Me::Regex->new();

@message = {
    "Aug 10 00:01:02 hostname ftp: connect from 10.20.30.40",
    "Aug 10 00:03:04 hostname ftp: connect from 10.21.40.71",
    "Aug 10 00:05:06 hostname ftp: connect from 10.22.50.72",
    "Aug 10 00:07:08 hostname ftp: connect from 10.23.60.73"
}

$teacher->IWantToGet($message[0], "10.20.30.40");
$teacher->IWantToGet($message[1], "10.21.40.71");
$teacher->IWantToGet($message[2], "10.22.50.72");
$teacher->IWantToGet($message[3], "10.23.60.73");

my $regex1 = $teacher->TellMeRegex(); # ex. $regex1 = "\d{2}\.\d{2}\.\d{2}\.\d{2}"

もちろん、無茶な依頼はエラーになって当然だろう。

$teacher->reset();
$teacher->IWantToGet($message[0], "host1.example.com");
$teacher->IWantToGet($message[1], "client.hoge.co.jp");
$teacher->IWantToGet($message[2], "some.where.com");
$teacher->IWantToGet($message[3], "my.home.server.com");

my $regex2 = $teacher->TellMeRegex(); # ex. $regex2 = "Error: Think Yourself."

こういうのがあれば、プログラマーではない人がユーティリティを自分で作ったりなど、使い道があるだろうと思う。

もちろん、正規表現は同じ結果を得るにもいろいろな書き方があるし、looseな回答をする$teacherで良い時もあれば、strictな回答をする$teacherが欲しい場合などもあるから、相当ハードルが高い。だから夏休みの妄想なわけだけど、さて、どんなところから手をつけたらいいのだろう。

コーパス

[M-FalconSky (8868)]

対象が文章的であるような場合
コーパスとって、類語解析して、類語データベースの正規化データで埋めるとこまでは行けそう

# poem_teacherとか?

変数的部分はコンパイラみたいなこと+過剰マッチ検出(ここは人力で作りこみ?) 抑制かなぁ?

あとは遺伝的アルゴリズムによるマッチャー生成エンジンとか?

# GA_teacher、『GA 芸術科アートデザインクラス』の先生ではないぞよ。

--
M-FalconSky (暑いか寒い)

Re:コーパス

[WindVoice (14680)]

確かにどこまで押し進めるかというのは難しいところで、（壮大に妄想するなら）例えば、$teacherが質問を返せばいいと思うんですよ。数字は何でもいいの？数字は何桁でもいいの？ピリオドはもっとたくさん出てくる場合もあるの？ずばりこれってIPアドレス？など。的確な質問と的確な答えが揃えば、欲しいものが得られるでしょうが……

進めていくと正規表現というよりは連想する人工知能のようなものの開発の話になっちゃいますね。もし出来ちゃったら、正規表現というよりは検索エンジンで便利につかえそうだなぁ。

--
人生は七転び八起き、一日は早寝早起き

Re:コーパス

[shibuya (17159)]

ワトソンのライバルを国産化する大規模部プロジェクトになるのでしょうか? クイズ番組荒らし、サポセンのセンター長、その他生身の人には望めないどんなとっぴな問いでもきちんと対応できるお仕事をする偉大な兄弟を創造する夢を幻視しました。

Re:コーパス

[WindVoice (14680)]

ちょっとネットで検索するだけで、製品化して売っている人 [regexmagic.com]がいるのを見つけてしまいました。人工知能じゃないし、私のコードサンプルのような簡単な仕組みではないけれど、デモムービーを見る限りはある程度のことがこなせそうです。でも、推論は組み込まれていない様子（そりゃそうか）。デモムービーは数値関係にマッチするものだけなのがちょっと残念ですが……

--
人生は七転び八起き、一日は早寝早起き

Re:コーパス

[WindVoice (14680)]

ある程度シンプルながら実現している例 [txt2re.com]も見つけたのでメモしておこう。ちょっとした用途ならこれで間に合うかもしれない。

--
人生は七転び八起き、一日は早寝早起き

生徒の出来が悪いと教師は苦労する

[Anonymous Coward]

その例だと
"10\.2\d\.\d0\.\d{2}"
とか
"10\.2[0-3]\.[3-6]0\.[47][0-3]"
みたいなものを返されても文句は言えないわけだが。
そもそも要件が「任意のIPv4アドレス」ではなく「特定のサブネットに含まれる任意のIPアドレス」だったらそっちのほうが正解に近い可能性すらある。

Re:生徒の出来が悪いと教師は苦労する

[WindVoice (14680)]

もちろん文句は言えない。大体、IWantToGet()で示された例「だけ」にヒットする自明な正規表現({入力１}|{入力２}|...|{入力N})のような回答を返すダメteacherだって用件は満たすし、稀にはそれこそが欲しい回答の場合だってあるわけだから。どっちかというとパターン認識の問題というより生徒の気持ちを汲み取る機能が重要になる。

--
人生は七転び八起き、一日は早寝早起き

Re:

[Anonymous Coward]

ていうか「任意のIPv4アドレス」がほしかったとしても
"\d{2}\.\d{2}\.\d{2}\.\d{2}"
数字が3桁になるようなIPv4アドレスを全部見逃してくれるような正規表現を返してくれるんじゃガラクタだな(もっとも例の入力からそこを推測しろというほうが親コメに書いた通り無理ゲーなわけだが)。

Re:

[Anonymous Coward]

十分な入力を考えて与えられるのに自分で正規表現が書けないという状況がそもそも想像しづらい。
十分な入力を考えることができなかったら、いつかコーナーケースで爆発炎上する正規表現を与えられかねないわけで(具体例は親コメントにある通り)、ちょっと「なつやすみのじゆうけんきゅう」以上のもので使う気になれない。
古典的な自動プログラミングのパラドックスそのものだな。要件を必要十分に記述できればというが、要件を必要十分に記述していったらそれはもはやプログラミングと変わらない。