読者です 読者をやめる 読者になる 読者になる

golang で正規表現の必須要素を抽出してみる

はじめに

この記事は Go Advent Calendar 2015 14日の記事です.

正規表現の必須要素の抽出についてお話ししたいと思います.古典的な話題ですし,鋭い方は golang と別に関係ないんじゃないの?と思われるかもしれませんが,最後に Russ Cox 氏の素晴らしい記事,

にもふれたいと思いますので,最後までおつきあいください.これは,Google Code Search で使われた正規表現のマッチングに関する記事になってます.

この記事が,Russ Cox 氏の記事へのイントロになれば幸いです.

それ,正規表現である必要ありますか?

正規表現は文字列マッチに比べるとどうしても遅いです.しかし,正規表現によっては文字列マッチに落とし込んでから検索できる場合もあります. 極端な例で言えば,apple という文字列も正規表現ですが,これは文字列と等しいので,文字列マッチしたほうがよさそうです.では,apple|orange というのはどうでしょう.これは,appleorange にしかマッチしないので,文字列マッチですみそうな感じがします.

ばっちりマッチする文字列がないときもある

では,(AG|GA)ATA(TT)* というのはどうでしょうか?(TT)* という正規表現は,空文字列にも,TTにも,TTTTにも,TTTTTT・・・にもマッチして,候補は無限に存在します.apple|orange のようにばっちりマッチする文字列を得ることは難しそうです.しかし,よく見るとこの正規表現にマッチする文字列が AGATAGAATA なる文字列から始まることは確実なので,テキストの中から,AGATAGAATA を探し出してから,該当する部分にだけ正規表現のマッチングをかけるようにして,効率化を図ることが出来そうです.

このように,正規表現の中から,マッチングに必須の要素を抜き出すという試みは Gnu Grep でも利用されている古典的な方法です.

ヒューリスティックスなので,実装などはいろいろ工夫のしがいもある面白いアルゴリズムなのですが,ここではなるべく簡単に説明できたらと思います.

正規表現の必須要素を抽出するアルゴリズム

アルゴリズムは,非常にシンプルです.下のアルゴリズムは,みんな大好き Navarro の黄色い本から引用させていただきました.

Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences

Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences

f:id:ikawaha:20151211165743p:plain

なんとなしの解説

詳しいことは Navarro の本を読んでいただければと思いますが,ざっくり説明してみたいと思います.

  • ばっちりマッチする文字列の集合 : All
  • 前部分語であることが分かっている文字列の集合:Prefix
  • 後部分語であることが分かっている文字列の集合:Suffix
  • 正規表現にマッチする文字列には必ず現れる部分文字列の集合:Fact

という4つの集合の組を再帰的に構築していきます.基本的には,All が求まるなら,Prefix と Suffix,Fact は All と同じです(ばっちりマッチするのがあれば,その文字列は,前部分語だし,後部分語だし,部分語でもある).この4つ組を Factor と呼ぶことにします.

Factor は再帰的に定義されます.方針としては,* が使われてるところは,候補が絞れないので,あきらめる.そうでなければ頑張ってみるという感じです.

文字リテラル

文字リテラル a があったとき,Factor は ({a}, {a}, {a}, {a}) です.空文字列の場合も同様です.

選択

x|y と選択があったとき正規表現 xy について,それぞれ Factor X と Factor Y が(再帰的に)計算できるので,x|y の Factor は,それぞれの要素の和を取ったものになります.

つまり,(X.All∪Y.All, X.Prefix∪Y.Prefix, X.Suffix∪Y.Suffix, X.Fact∪Y.Fact)と計算できます.

たとえば,a|b なら,({a},{a},{a},{a})({b},{b},{b},{b}) をあわせて,({a,b},{a,b},{a,b),{a,b}) となります.単純にそれぞれの和を取るだけなので簡単です.

連結

xy と連結されているとき,Factor X と Factor Y が計算できて,xy は,

  • All は,X.All・Y.All
  • Prefix は,X.Prefix を使うか,X.All・Y.Prefix のいずれか良さそうなものを使う
  • Suffix は,Y.Suffix か,X.Suffix・Y.All のいずれか良さそうなものを使う
  • Fact は,X.Fact もしくは,Y.Fact,X.Suffix・Y.Prefix のいずれかから良さそうなものを選んで使う

と計算されます.ここで,集合の連結 は,それぞれの集合の要素を掛け合わせるような演算になります. たとえば,X = {a, b, c}, Y = {x, y, z} なら,X・Y = {ax, ay, az, bx, by, bz, cx, cy, cz} となります.

閉包

x* のとき候補は無数にあって定まりません.このとき特別 Factor を (θ, θ, θ, θ) とします.θ は文字列全体からなる集合と同じような意味で使われていて,候補が定まらないことを意味しています.なので,θにどんな集合を演算しても,θになります.すなわち,θ・A = A・θ = θ∪A = A∪θ = θということです.

わかったような?

アルゴリズムは単純なので,方針は概ね分かると思うのですが,細かいところが実装に任せられています. たとえば,連結の時の「良さそうなのを選んで使う」というやつです.これは,選択肢のどれを使ってもいいんですが,

  • 少なくとも θであるものは使わない方がよさそうです
  • また,集合の要素は少ない方がいいでしょうし(連結でかけ算で増えてくし,最終的なチェックも少なくて済みそう)
  • 集合の要素の一番短い文字列長が大きい方が有利そうです(1文字の要素しか入ってないと,テキスト検索するとき1文字の候補がいっぱいあって結局意味ない可能性もあるので長い文字列が分かった方がよさそう).

用途によっていろいろと工夫しがいがありそうです.

ここでは省略されてますが,文字クラス([a-z]とか)はどのように扱うかとか,+ はどうするかとか,?はどうするかとかもあります. 文字クラスは選択で繋がれた形に展開すれば良さそうですが,あまり数が多いときはθと置き換えてしまってもいいでしょう. + は,かならず1回は要素が現れるので,xx* のように置き換えられます. ? はなくてもいいのでうまく要素が定まりません.θとしてしまっていいでしょう.

細かいところは実装しだいです.

また,連結するときに集合の要素がかけ算で増えてしまうので,Factor が求まっても候補が多すぎて結局使えないということもあります.あんまり数が多くなってきたらθと置き換えてしまうとか,その辺どうするか,とか考えどころです.

なぜ golang か?

前々から,このアルゴリズムで遊んでみたいとは思ってました.仕組みも単純だし,すぐ実装できそうです.アルゴリズムは単純なのですが,正規表現構文木を作るのはとーってもめんどくさい (個人差があります) ので,なかなか手が出なかったです.ところが,golang には regexp/syntax というパッケージがあって,正規表現構文木を直接扱うことが言語的にもサポートされています.なんて素敵!

type Regexp struct {
        Op       Op // operator
        Flags    Flags
        Sub      []*Regexp  // subexpressions, if any
        Sub0     [1]*Regexp // storage for short Sub
        Rune     []rune     // matched runes, for OpLiteral, OpCharClass
        Rune0    [2]rune    // storage for short Rune
        Min, Max int        // min, max for OpRepeat
        Cap      int        // capturing index, for OpCapture
        Name     string     // capturing name, for OpCapture
}

こんな構造体で構成されてます.選択も連結も2項演算ではなくて,a|b|c みたいなときは,Sub に a, b, c が入ってます.細かいところは,writeRegexp(...) というString()メソッドの本体があるので,ここを読むのがわかりやすいです.

遊べるものを用意しました

なかなかうまく説明も出来ないので,簡単なプログラムを作りました.go get して手元で動かして遊んでみてください. サーバとして動かせば,ブラウザ上でアルゴリズムが組み立てる解析木を確認することが出来ます.

github.com

f:id:ikawaha:20151211184301p:plain

Google Code Search での正規表現マッチ

さて,

Regular Expression Matching with a Trigram Index

という Russ Cox 氏の素晴らしい記事についても紹介したいと思います.この記事は,Google Code Search のような沢山のコードの中から正規表現で高速にマッチングを行うにはどうしたらいいか,その手法がまとめてあります.詳しくは記事を読んでいただきたいんですが,おおざっぱに3行で(ひどい)まとめると,

  • 対象ドキュメントは転置インデックスを用いてインデキシングしておく.3-gram を用いる
  • 正規表現の必須要素を計算する.ただし,3-gram の形で抽出する
  • 正規表現の必須要素からクエリを作って,インデックスを検索する

ということです.高速に検索するには,いかに必要ないドキュメントを見ないで済むかということでもあり,対象となるドキュメントを見つけてから実際に正規表現マッチするので高速化できます.そして,このコードは, github.com ここにそろってますので,是非中も見てみてください.

おわりに

今年を振り返ってみると,2月に golang が書きたくて(?)転職して, ikawaha.hateblo.jp

夏には GoCon で発表もさせていただきました. ikawaha.hateblo.jp

ジャストシステムkuromoji.jsid:takuya-a さん,janome@moco_beta さんと一緒に形態素解析の実装についてパネルさせてもらったりしていい経験になりました.

転職してからは golang しか書いてないといえるくらい,golang で楽しく開発させてもらって幸せでした.

来年はなにか新しいネタ考えて遊べるといいなー.

それでは よい(クリスマス|お年)を! ← ここまで読んでいただければFactor が何になるかおわかりですよね :p

追記

こちらにはその昔,UNIX MAGAZINEgrepソースコードを解説した記事がまとまってます.その中に,Factor の抽出方法についての解説もありますのでご参考にどうぞ.