Zenn
📌

正規表現の必須要素を抽出する

2021/03/23に公開
Go
正規表現
tech

はじめに

この記事は5年ほど前にアドベントカレンダーで書いた記事の焼き直しです。正規表現パズルを解こうと思って、昔作ったプログラムを引っ張り出してみたんですが、go.mod にも対応してなかったのでリファクタリングしてまとめ直してみました。

( '-`).oO( なかなかこざかしいコードが書いてあって、こざかしい、こざかしいと思いながら書き直していたんですが、結局は5年前のコードがよく練られていて、ぐぬぬ、ぐぬぬといいながら愚直に書き直していきました・・・。

それ、正規表現である必要ありますか？

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

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

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

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

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

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

アルゴリズムは、非常にシンプルです。下のアルゴリズムは、みんな大好きNavarro の黄色い本こと Flexible Pattern Matching in Strings から引用させていただきました。

なんとなしの解説

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

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

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

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

文字リテラル

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

選択

x|y と選択があったとき、正規表現 x と y について、それぞれ 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 のいずれか<u>良さそうなもの</u>を使う
  • Suffix は、Y.Suffix か、X.Suffix・Y.All のいずれか<u>良さそうなもの</u>を使う
  • Fact は、X.Fact もしくは、Y.Fact、X.Suffix・Y.Prefix のいずれかから<u>良さそうなもの</u>を選んで使う

と計算されます。ここで、集合の連結 ・ は、それぞれの集合の要素を掛け合わせるような演算になります。
たとえば、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 が求まっても候補が多すぎて結局使えないということもあります。あんまり数が多くなってきたらθと置き換えてしまうとか、その辺どうするか、とか考えどころです。

Go で実装する

前々から、このアルゴリズムで遊んでみたいとは思ってました。仕組みも単純だし、すぐ実装できそうです。アルゴリズムは単純なのですが、正規表現の構文木を作るのはやはりめんどくさいです。なので、なかなか手が出なかったのですが、Go には 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()メソッドの本体があるので、ここを読むのがわかりやすいです。

regexp/syntax.Regexp から作られる regexp.Regexp には prefix というフィールドがあって、まさに前方一致での必須要素が計算されるようになっています。前方一致があるときはあらかじめ文字列マッチでチェックして計算のコストを削減するようになっています。

// Regexp is the representation of a compiled regular expression.
// A Regexp is safe for concurrent use by multiple goroutines,
// except for configuration methods, such as Longest.
type Regexp struct {
	expr           string       // as passed to Compile
	prog           *syntax.Prog // compiled program
	onepass        *onePassProg // onepass program or nil
	numSubexp      int
	maxBitStateLen int
	subexpNames    []string
	prefix         string         // required prefix in unanchored matches
	prefixBytes    []byte         // prefix, as a []byte
	prefixRune     rune           // first rune in prefix
	prefixEnd      uint32         // pc for last rune in prefix
	mpool          int            // pool for machines
	matchcap       int            // size of recorded match lengths
	prefixComplete bool           // prefix is the entire regexp
	cond           syntax.EmptyOp // empty-width conditions required at start of match
	minInputLen    int            // minimum length of the input in bytes

	// This field can be modified by the Longest method,
	// but it is otherwise read-only.
	longest bool // whether regexp prefers leftmost-longest match
}

必須要素を計算するコマンド

https://github.com/ikawaha/factors

コマンドラインで試す

$ factors '((GA|AAA)*)(TA|AG)'
Exact: θ
Prefix: θ
Suffix: {AG, TA}
Fragment: {AG, TA}

解析木を表示して試す

注：解析木の表示には Graphviz が必要です。

さいごに

Gnu grep でも正規表現の必須要素を計算してマッチングの高速化をおこなっています。Exact, Prefix, Suffix にあたる部分は集合でなく、必須の文字列として計算し、Fragment は複数要素を保持しますが、共通要素を抽出し、より grep で利用しやすいようになっているようです。このように正規表現の必須要素を抽出するアルゴリズムはヒューリスティックに工夫しがいのあるものです。ぜひ自分専用のアルゴリズムを作ってみて下さい。

あと、今回は Go 1.16 で go:embed を 利用してみた んですが、これは便利ですね。HTML ファイルの内容を string にバインドして利用してみました。まえは、Go のファイルにべた書きにしてたんですけど、別ファイルにできるので見通しがよくなりますね╭( ･ㅂ･)و ̑̑。

Happy hacking!

Discussion