ヘビのマッチ

情報工学ってなんだろう...正規表現とは何かとんだ恥かき村の恥じかき爺さんですよッなどに書かれていますが、問題としては面白いので awk でやってみましょう。

awk でこの正規表現を全て表記することはできません。 木村さんがとんだ恥かき村の恥じかき爺さんですよッに書いていますが、「gensub の置換文字列の中だけ」しか後方参照は使えませんので、ひとつの正規表現で記述しきることはできません。

そこで、最初に記述してみたものは以下のようなものでした。

#! /usr/bin/gawk -f
# hebi.awk

{
    # 通常の awk の場合
    if ($0 ~ /^>'/ && $0 ~ /=~$/) {
        tmp = $0;
        printf("%s : ", $0);
        sub(/^>'/, "", $0);
        sub(/~$/, "", $0);
        for (i = 1; i < length($0); i++) {
            eq_front += sub(/^=/, "", $0);
        }
        for (i = length($0); i > 0; i--) {
            eq_back += sub(/=$/, "", $0);
        }
        if (eq_front == eq_back && $0 == "#") {
            hit = 1;
        }
    }
    if (hit == 1) {
        print "match";
    } else {
        print "not match";
    }
    eq_front = 0;
    eq_back = 0;
    hit = 0;

    # gawk の後方参照を使用した場合
    if (gensub(/^>'(=+)#=+~$/, ">'\\1#\\1~", 1, tmp) == tmp) {
        print tmp " : match";
    } else {
        print tmp " : not match";
    }
}

最初の部分は、頭と尻尾を切って、真ん中で分けて・・・までは良いのですが、その後が非常に面倒なことをやってしまいました。 後方参照を用いたものは、後方参照で "#" よりも前の部分を取得して、それを前後につなげたものと同じかどうかの判定を行っています。

$ gawk -f hebi.awk hebi.txt
>'===#===~ : match
>'===#===~ : match
>'===#==~ : not match
>'===#==~ : not match
>'==#==~ : match
>'==#==~ : match
>'==#===~ : not match
>'==#===~ : not match

しかし、この方法だと非常に頭に入りづらく何をやっているかが直感的に分からないでしょう。 以前、タモリの番組できゅうりを刻む時間を競っていたものがありましたが、ある人が頭としっぽを切って半分にして切りはじめ、時間を一気に短縮させたということがありました。 同じことをやればいいのです。

#! /usr/bin/gawk -f
# hebi2.awk

{
    printf("%s : ", $0);
    sub(/^>'/, "", $0);        # 頭を切って
    sub(/~$/, "", $0);         # しっぽを切って
    mid = index($0, "#");      # 真ん中を調べて
    # 切って比較する
    if (substr($0, 1, mid - 1) == substr($0, mid + 1) && $0 ~ /=+#=+/) {
        print "match";
    } else {
        print "not match";
    }
}

このヘビをレゴブロックのようなもので作っていると思ってください。 頭としっぽを切って真ん中で分割したものが同じであれば良いという非常に単純なものです。 オートマトンとか正規表現とかではないですが、幼稚園でも教えられるようなアルゴリズムにすることができます。

$ gawk -f hebi2.awk hebi.txt
>'===#===~ : match
>'===#==~ : not match
>'==#==~ : match
>'==#===~ : not match

ひとつの正規表現で記述ができると格好良く見えるかもしれませんが、何をやっているかが分かって、他の言語でも使えるようなアルゴリズムが好まれる場合もあります。 特に awk の場合には、命令や関数が限られていますから、その傾向は強いかもしれません。

tag_gawk.pngtag_gawk.png