ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

正規表現の“否定”について勘違いと、アンカー

昔、正規表現の基本を学んで、もう基礎的なことは大丈夫だろうと思っていたんですが、思いがけない重大な勘違いをしていました。

“ある文字列でない文字列”の表現の方法なんですが、正規表現ではこの表現が非常にやりづらいみたいで、私のように躓いている人もいると思うのでメモします。

どういうときにこういう正規表現を書くのかというと、私はHTMLのタグ認識をさせていました。

たとえば、以下はXMLですが、

<Root>
<Element>
なまむぎなまごめなまたまご
</Element>
</Root>


このXMLから、Elementの要素、なまむぎなまごめなまたまごを抜き出すための正規表現みたいなのを書こうとしたわけです。

まず、文字列"<Element>"の直後のアンカーを表す"(?<=<Element>)"を書きます。

アンカーも、実は今までよくわかっていなかったので、これも後でメモします。

そして、Elementの要素はなんでもいいので".*"とします。

そして、".*"だけだと"</Root>"までマッチしてしまうので、"</Element">の直前が最後なのだということを表すため、そのアンカーを表す"(?=</Element>"を書きます。

というわけでパターン文字列は"(?<=<Element>).*(?=</Element>)"となります。


ちなみに、".*"の解釈は行末で終わってしまうというのがデフォルトなので、解析対象に改行があった場合は行の概念を無視するように設定しておきます。


では、このパターンで検索してみましょう。

"なまむぎなまごめなまたまご"にマッチしました。


さて、一見これでいいように見えますが、検索対象のXMLがこんなのになったらどうなるでしょうか。

<Root>
<Element>
なまむぎなまごめなまたまご
</Element>
<Element>
あかぱじゃまあおぱじゃまきぱじゃま
</Element>
</Root>


Elementが2つに増えました。
先ほどと同じパターンで検索します。


………


なんと、

なまむぎなまごめなまたまご
</Element>
<Element>
あかぱじゃまあおぱじゃまきぱじゃま

にマッチしてしまいました!


これは、パターンの"(?<=<Element>).*(?=</Element>)"を見たときに、"<Element>"を見つけたところから".*"、つまり0文字以上の任意の文字列を探していくわけですが、

最後は"</Element>"で終わらなくてはならないわけです。

しかし、このXMLの場合、任意の文字列が続いたあとに"</Element>"で終わる場所というのが、

我々が期待していたような、"なまむぎなまごめなまたまご"の最後と、
"あかぱじゃまあおぱじゃま"の最後、2つの可能性を考えられるわけです。


このように文字列の繰り返し表現でいくつもの可能性がある場合、正規表現では一番長いものにマッチするという仕様なのです。

そのため、先ほどのXMLでは、より長い文字列となる"あかぱじゃまあおぱじゃま"のところまでマッチしてしまった、というわけです。




しかし、そんなことは私も知っていました。

なので、それを回避するためには、"<Element>"があって、「"</Element>"ではない文字列」が繰り返されて、最後に"</Element>"がくるパターンを書けばいいと思ったわけです。

このパターンでは"<Element>"と"</Element>"の間に"</Element>"があってはいけないわけですから、"あかぱじゃまあおぱじゃま"までマッチされる可能性はありません。

"なまむぎなまごめなまたまご"のところまででマッチされます。


よって、単純に".*"で文字列の繰り返しを表すのではなく、「"</Element>"ではない文字列」の繰り返しを表現するのがミソです。

つまり、否定が入ってくるわけです。


ちなみに、そんなことをしないでも、いける方法があったのを後で知りましたが、
そんなことを言ったらこの記事の意味がなくなるし、否定を使ったほうがなにかと自由度も高そうなので、なかったことにします。

一応書いとくと、文字列の繰り返し表現は一番長いものにマッチされると前述しましたが、

それが*という記号で繰り返しを表した場合です。

*?という似た記号があって、これもほぼ同じ意味なんですが、こちらはいくつかの可能性があるときに、一番短いものにマッチされます。

これを使えば、最初に"</Element>"が出てくるところの直前でマッチが終わりますから、今からやりたいことと等価になります。

つまりパターン文字列は"(?<=<Element>).*?(?=</Element>)"です。




さて、ここからが本題ですが、じゃあ「"</Element>"ではない文字列の繰り返し」ってどう書くのよって話です。

ここを私は今まで勘違いして書いてしまっていたのです。


正規表現では[]という表現があって、たとえば"[abc]"と書いたら、aまたはbまたはcである文字を表します。

なので、"[abc]+"とかは、aとbとcだけで構成される任意の文字列ですね。


また、[^]という表現もあり、たとえば"[^abc]"と書いたらaまたはbまたはcではない文字を表します。

"[^abc]+"はaとbとc以外で構成される任意の文字列となります。


つまり、この[^]こそが正規表現における否定の方法だと、私は勘違いしてしまっていたわけです。

正規表現にはグループ化といって、()で任意の文字列を一つの文字と見なす機能があるので、それを使って"(abc)"なんて書けば

"[^(abc)]+"でabcではない任意の文字列を表せるだろうと思っていたわけです。


しかし、実は[^]は、何かを否定する意味を持っているわけではなく、そこに入っている文字以外の全ての文字の集合を表しているだけだったのです。

ようするに"[^abc]"と書くのは、[]において、この中にaとbとc以外の全ての文字を書いたことと同じことなのです。


なので、"[^(abc)]"と書いたところで、文字(abc)ではない全ての文字ってなんなのでしょうか。

aとかbとかcが単体で存在するのはアリなのかナシなのか、曖昧ですが、そもそも[^]はそういうレベルのものではないわけです。

文字単体の話なので、[][^]の中に書く文字の集合は、あくまでも文字列ではなく文字の集合じゃないといけないということです。


それを裏付けるかのように、グループ化に使う()を含め、正規表現において特別な意味を持つ記号のほとんどが、実は実は[][^]の中だけは意味のないただの文字として扱われます。

そもそも()を書いても意味がなかったのです。


よって、"[^(</Element>)]+"という表現は間違いだったわけです。

この表現では、「(,<, /, E, l, e, m, n, t, >, )」以外の文字で構成される任意の文字列という意味になってしまいます。




では、どうやって正規表現で否定を表現するのか、調べました。

それには、記事冒頭にも出てきたアンカーを使います。


結論から言ってしまうと、"</Element>"ではない任意の文字列は、
"((?!</Element>).)+"で表現します。

もっとこのパターンの意味をそのままに言うと、「次から文字列"</Element>"が始まらないようなアンカーと任意の一文字、それの1回以上の繰り返し」です。

つまり、スタートはどこか知りませんが、そこから"</Element>"の直前までマッチします。


このパターンに出てくる"(?!</Element>)"とはなんでしょうか。

これは、次から文字列"</Element>"が始まらないような任意のアンカーです。


アンカーとはなにかというと、正規表現のパターンって結局、
具体的な文字を書いたり、任意の文字を表す文字を書いたり、あとはその繰り返しを表現したりと、
結局はパターン中の文字の並びは実際の解析対象の文字の並びを表しているわけです。


正規表現って言語の構文を定義する言語としての側面もあるみたいですね。

BNFとかと同じです。
正規表現にはちゃちゃっとインライン的に書けるというメリットがありますが、言語構文を定義するとなれば、しっかり領域を区別して定義していけるBNFのほうが向いていると思います。


話がそれましたが、ようするに正規表現のパターンには文字の並びを書いていくわけです。

しかし、パターンの中に実は文字だけではなく、もうひとつ書けるものがあるのです。

それが、アンカーというものです。


アンカーというのは文字列中の位置を表す概念といったところでしょうかね。

もっと簡単にいえば文字と文字の間のことですね。


"abcde"という文字列のaの前にカーソルがあったとします。
右キーを3回押したらcとdの間にカーソルが来ます。

こんなようなものがアンカーです。


"abcde"の中には本当はアンカーが隠れていたわけで、これは「a,b,c,d,e」と並んでいるだけではなくて

本当は「アンカー、a、アンカー、b、アンカー、c、アンカー、d、アンカー、e、アンカー」という並びだったわけです。
文字の間ではないですが、先頭と末尾にもあります。


正規表現において、いくつかアンカーを表現する方法があるということなのですが、簡単なのは^$です。

^は文字列の先頭にあるアンカーを表す記号で、$は文字列の一番最後にあるアンカーを表す記号です。

"^.$"というパターンを書いたら、先頭があって、任意の一文字があって、末尾がある、という意味になります。


"^$"というパターンは、先頭と末尾のアンカーの間に一つも文字がありません。

つまり、先頭と末尾は同じ場所です。
なので、このパターンでは空文字列にしかマッチしません。

空文字列にはマッチしますが、マッチするといっても、アンカーしかないので、ようするにマッチした文字列を取得しても空ですね。


ちなみに、同じ場所にあるアンカーを書いていくときに、順番はなんでもいいようで、
"$^"、つまり先に末尾を表すアンカー、続いて先頭を表すアンカーを書くというバカみたいなパターンを書いても、これは先ほどの"^$"と同じ意味です。




アンカーというものが私もよくわかりませんでした。
今回、ようやくわかってきたので記事にしました。

では、先ほど結論から書いたものを、もう一度見返してみましょう。


"</Element>"ではない任意の文字列は、"((?!</Element>).)+"と表現するということでしたね。

そして、この"(?!</Element>)"は次から文字列"</Element>"が始まらないような任意のアンカーという意味でした。

つまり、たとえば
<Root><Element></Element></Root>
という対象からそのようなアンカーを探すと、
15文字目の>と16文字目の<の間にあるアンカーを除く全てのアンカーということになります。


正規表現では、パターン中に文字を表すものを書かずに、アンカーを表すものだけを書いた場合でも、ちゃんとマッチするみたいで、

実際に上に、"(?!</Element>)"というパターンで検索をかけたら、15文字目と16文字目の間のアンカーを除いた全てのアンカーにマッチします。

アンカー(だけ)にマッチするということは、ようするにマッチ文字列にはアンカーは現れないので空文字列ですね。

大量にマッチする空文字列、これほど無駄なことはないでしょう。


さて、そして、"(?!</Element>)"のあとに、任意の一文字を表す"."を書きます。

これがないと上手いこといきません。

「"</Element>"が始まらない任意の文字の繰り返しなのだから、パターンは"(!?</Element>)+"でいいじゃないか」と思った人

それは以前の私ですが、そう思った人はアンカーについてまだなにも分かっていないので、マウスを上にグリグリして最初から読みなおしてください。


"(?!</Element)."と書いてようやく、
次から"</Element>"が始まらない任意のアンカーがあって、その次に任意の一文字がくるという並びになります。

これにマッチしない文字は、"</Element>"の先頭の<だけです。


それで、この並びに対して繰り返しを指定するわけです。

アンカーと一文字、の並びに対する繰り返しですから、「アンカー、一文字、アンカー、一文字、アンカー、一文字…」ってことです。

というわけで、この並びをグループ化して1回以上の繰り返しを表す記号を付けます。

最終的にパターンは"((?!</Element>).)+"となります。


これが、"</Element>"ではない(詳細にいうと"</Element>"を構成している一部すら入っていない)文字列を表すパターンとなります。




よって、だいぶ記事冒頭の話になりますが、書きたかったパターンは、
文字列"<Element>"の次から始まって、"</Element>"ではない文字列が続いて、"</Element>の直前で終わるというパターンなんですよね。


なので、まず先頭のアンカーが文字列"<Element>"の末尾なんだということを表すために、
記事冒頭でも言いましたがパターンの先頭に"(?<=<Element>)"と書きます。

これは解析対象において"<Element>"という文字列の直後にあるアンカーを表す表現です。

パターン中では、そのアンカーのあとに文字列を書いていくことで、文字列"<Element>"のあとの文字列なんだということを表現できます。


そしてこのアンカーを書いたあと、"</Element>"ではない任意の文字列が来るということでしたね。

さっき書いたとおり、それを表すには"((?!</Element>).)+"と書きます。

ただ、これがElementタグの内容にあたるわけですが、それは空でも仕様的にはありなので、文字の1回以上の繰り返しではなく0回以上の繰り返しにします。

なので、最後の+*にしてパターンは"((?!</Element>).)*"となります。


以上の二つを合わせて"(?<=<Element>)((?!</Element>).)*"と書けば、
文字列"<Element>"の後ろから"</Element>"の直前の文字までの文字列にマッチすることになるので、もうこれでもいいんですが、

念のためその文字列のあとに文字列"</Element>"が来ることを明示しておきます。

これを明示しない場合と明示する場合でほぼ同じですが、
前者の場合Elementタグを閉じていなくてもマッチしてしまうのに対して、

後者の場合はちゃんと最後に"</Element>"を書いていないとマッチしないので、後者のほうが意味的には正確ですね。


ある文字列のあとに"</Element>"が来るということは、文字列のあとに"</Element>"の先頭を表すアンカーが続くということですね。

文字列と、その先頭のアンカーの並びにマッチするわけです。


"</Element>"の先頭を表すには"(?=</Element>)"と表現します。

これは、解析対象において</Element>という文字列が次に続くような任意のアンカーを表しています。

(?<=)は直後を表すものだったので、直前とか直後とかわけわからなくなってきますが、
アンカーについてわかっていれば、どこのアンカーなのかという問題に過ぎないので、簡単です。


よって、このアンカーを最後に書いて、最終的にパターンは"(?<=<Element>)((?!</Element>).)*(?=</Element>)"となります。

長いですね…。
やっぱり、最初のほうで書いたとおり、この程度のものなら、
"(?<=<Element>).*?(?=</Element>)"で良かったような気がしないでもありません。


というわけで、正規表現で否定を表現するときは、アンカーに否定するためのものがあるので、それを使ってゴニョゴニョするということでした。




正規表現、基本的なところはわかってるからもういいと思っていましたが、こんな勘違いもありましたし、奥は深いようですね…。

繰り返しの回数を指定できたり、文字クラスも[]だけでなくプリセットのものがあるみたいです。


そんなのはまだいいんですが、後方参照という、マッチ文字列の一部を抜き出してパターン中の別の場所や、マッチさせたプログラムから使用できる機能があるみたいで、これを理解できたらかなり強いと思います。

ただ、これを理解するには、マッチ文字列には、キャプチャ文字列という概念や、グループという概念があるようで、それを理解していないと上手いこといかないようで、
それについて全く理解できていないので、そこからでしょうか。


前方参照というものもあるんですが、これは後方参照の別の言い方だそうです。
なんなんでしょうか。


なんにせよ、正規表現を制するものは文字列処理を制するという感じは、すごくありますよね~。

私は、もし、プログラミング初心者でプログラム組むのには慣れてきたレベルの人に、
“新しいことをひとつ覚えてみたいが何が一番よいか”、と聞かれたら正規表現と即答したいと思います。


習得するとしないとでは、便利さが段違いですね。
覚えたことによる利益を、覚えるための労力で割った値が、一番大きいと思います。


というわけで、私自身まだまだ分かっていないところがあるので、これからも機会があれば勉強していきたいです。

tag: 正規表現 パターンマッチ 文字列処理 XML HTML アンカー

コメント

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/425-f3dc1f04
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。