PerlにはRegexp::Assembleという便利なライブラリがあります。
複数の正規表現を受け取り、それらのいずれかにマッチする正規表現を構築するためのライブラリです。
my $ra = Regexp::Assemble->new;
$ra->add( 'ab+c' );
$ra->add( 'ab+\\d*\\s+c' );
$ra->add( 'a\\w+\\d+' );
$ra->add( 'a\\d+' );
print $ra->re;
このライブラリのGo実装を金曜日の夜から書き始めて、ようやく形になってきたので公開しました。
package main
import (
"fmt"
"log"
"github.com/itchyny/rassemble-go"
)
func main() {
xs, err := rassemble.Join([]string{"abc", "ab", "acbd", "abe"})
if err != nil {
log.Fatal(err)
}
fmt.Println(xs)
xs, err = rassemble.Join([]string{
"北海道", "青森県", "岩手県", "宮城県", "秋田県", "山形県", "福島県", "茨城県",
"栃木県", "群馬県", "埼玉県", "千葉県", "東京都", "神奈川県", "新潟県", "富山県",
"石川県", "福井県", "山梨県", "長野県", "岐阜県", "静岡県", "愛知県", "三重県",
"滋賀県", "京都府", "大阪府", "兵庫県", "奈良県", "和歌山県", "鳥取県", "島根県",
"岡山県", "広島県", "山口県", "徳島県", "香川県", "愛媛県", "高知県", "福岡県",
"佐賀県", "長崎県", "熊本県", "大分県", "宮崎県", "鹿児島県", "沖縄県",
})
if err != nil {
log.Fatal(err)
}
fmt.Println(xs)
}
ライブラリ用途を意図していますが、動作確認 (とこのブログでの説明) のためにcliツールとしても使えるようにしています。
% go get github.com/itchyny/rassemble-go/cmd/rassemble
% rassemble abcd abd acd ad
ab?c?d
% rassemble $(head -n30 /usr/share/dict/words)
a(?:a(?:l(?:ii)?|m|rd(?:vark|wolf))?|ba(?:c(?:a(?:te|y)?|i(?:nat(?:e|ion)|s(?:cus|t))|k|tinal(?:ly)?)?)?)?|A(?:a(?:ni|r(?:on(?:i(?:c(?:al)?|t(?:e|ic)))?|u))|b(?:ab(?:deh|ua))?)?
作ったきっかけは、以下のブログを見たことでした。
本当はこのツールのアイデアが思いついたときには、GoのRegexp::Assemble実装も作ってやろうと思っていたのですが、難しくて断念しました…。このツールのアイデア自体は数年前にあったのですが、Regexp::Assembleがネックになって作れておらず、結局その実装を諦めた結果このツールを世に送り出すことができました。
Regexp::AssembleのGo移植は誰かやってほしい…!
GoのテストをCIで簡単に並列実行する | おそらくはそれさえも平凡な日々
確かに本家の実装を覗いてみるとそこそこ行数があり、複雑なコードで頭がクラクラします。
しかし、Regexp::Assembleは正規表現のパースのコードも含んでおり、そこがかなりの行数を占めています。
Goで実装する場合は、パースは標準ライブラリにまかせてしまえば良いので、正規表現のマージ処理に専念することができます。
また、本家を一行ずつ変換する必要はなく、テストケースを眺めながら処理を想像しつつ書いていけば、移植はそんなに難しくありません (実は私も本家のソースコードはほとんど読んでいません)。
基本的には前方がまとまっている方が正規表現は速いはずですから、トライ木の正規表現版を作れば良いわけです。
例えば
abcde
abcfg
afcfg
この3つの単語からトライ木を作ると
a -> b -> c -> d -> e
\ \-> f -> g
\-> f -> c -> f -> g
のようになりますから
a(?bc(?:de|fg)|fcfg)
となりますし、これが正規表現だとしても同じ話です。
a\w\d*(?:abc)? は a, \w, \d* (?:abc)? がそれぞれ一つの塊と考えて、これが一致するだけ貪欲に前方をまとめるだけです。
面白いのは後方をまとめる処理です。
Regexp::Assembleの例には次のような例が載っています。
my $ra = Regexp::Assemble->new;
$ra->add( 'ab+c' );
$ra->add( 'ab+\\d*\\s+c' );
$ra->add( 'a\\w+\\d+' );
$ra->add( 'a\\d+' );
print $ra->re;
後方をまとめないと (?:a(?:b+c|b\d*\s+?c|\w+\d+|\d+)) のようになってしまいます。
実はこれも難しい処理ではありません。
| で結合された、前方がばらばらの複数の正規表現を、二重ループで後ろが一致するものを束ねればよいのです。
もしかしたら、うまく実装したらオーダーが下がるかもしれませんが、最初は素朴に実装するのがよいでしょう。
最初に前方をまとめてしまい、その後に後方をまとめる処理を行えばよいはずです。
文字列として最短の正規表現を生成することはゴールではありません。
前方一致を優先させた正規表現を作ればよいはずです。
例えば、最初に例としてあげた a(?bc(?:de|fg)|fcfg) は、 a(?:bcde|[bf]cfg) と書くほうが文字数は少なくなります。
これは後方一致を優先させた結果ですが、 a を見た後に複数の分岐があり、それらがいずれも b を確認する必要があります。
もう少しわかりやすい例をあげると、
a00
a01
a10
a11
a22
b00
b01
b10
b11
これを前方一致でまとめると (rassemble-goの出力結果は)
a(?:[01][01]|22)|b[01][01]
となりますが、
[ab][01][01]|a22
のほうが短いですよね。
しかし、こちらの「短い」正規表現は、先頭の文字が a かどうかを複数の分岐で行っています。
解きたいのは、短い正規表現を吐くことではなく、前方一致を優先させてまとめ、程々に後方もまとめた正規表現を生成することなのです。
ですから、前方一致を貪欲にまとめていけば良いのです。
本家のソースコードをしっかりと確認したわけではありませんが、この実装で概ね本家と同じ正規表現を生成できています。
% rassemble 'ab*c*d?' 'abcc*d?' 'ad?'
a(?:(?:b*|bc)c*)?d?
% rassemble abacination abaction abalienation abarticulation abbreviation abdication abduction aberration
ab(?:a(?:c(?:ina)?|(?:lien|rticul)a)|(?:brevi|err)a|d(?:ica|uc))tion
もしかしたら後方はまとめなくてもいいんじゃないかと思われるかもしれません。
しかし、実際に後方をうまくまとめないと、冗長な正規表現になってしまうパターンは存在します。
abcde
acde
abde
abce
abe
ace
ade
ae
これを後方をまとめる処理を行わないと、
a(?:b(?:c(?:de|e)|de|e)|c(?:de|e)|de|e)
となりますが、後方をまとめることで
% rassemble abcde acde abde abce abe ace ade ae
ab?c?d?e
とすることができます。
かなり簡潔になりました。
これがうまく動いたときは感動しました。
かなり恣意的な例ですが、後方をまとめないと指数関数的に長くなってしまう (圧倒的にまとめられる) 正規表現はあるのです。
実際にはここまで極端な例はあまりないと思いますが、都道府県を結合するときもなんとなく「県」はまとまってほしいわけです。
上記にrassemble-goを使ったときの出力を書いておきましたが、実際に多くの県がまとまっていますね。
前方一致を優先させることから、「大分県」が他の県と結合せずに「大阪府」とまとまっています。
前方一致としては 山[口形梨]| や 福[井岡島]、後方一致としては (?:富|和歌|岡)山 や (?:神奈|石|香)川、(?:[広徳]|鹿児)島 のようにまとまっています。
地名が山や川や島でまとまるのは納得感があります。
福島が島じゃなく福でまとまっているのは前方一致優先ですね。
ところで、上記の例 (a(?:[01][01]|22)|b[01][01]) をRegexp::Assembleにわたすと次のような形になります。
a(?:0[01]|1[01]|22)|b(?:0[01]|1[01])
のようになり、 [01] の部分が冗長になっています。
このように、rassemble-goはいくつかのケースでRegexp::Assembleと動作が異なることが分かっています。
% rassemble ab?c ac
ab?c
% rassemble ab+c ac
ab*c
% rassemble abcde abc bbcde bbc cbcde cbc
[a-c]bc(?:de)?
冗長な ? の除去や、後方一致の深い判定はやってないようですね。
でも最後の例なんかは、rassemble-goのようにまとめたほうがよい気がします。
Go言語で実装した時に一番悩んだのは、実は文字列の扱いです。
まず、正規表現を自前でパースするのは骨の折れる事ですから、regexp/syntaxパッケージを使うことは最初から決めていました。
このパッケージでパースすると以下のような構造体が返ってきます。
type Regexp struct {
Op Op
Flags Flags
Sub []*Regexp
Sub0 [1]*Regexp
Rune []rune
Rune0 [2]rune
Min, Max int
Cap int
Name string
}
例えば abcde という連続する文字列は、
&syntax.Regexp{ Op: syntax.OpLiteral, Rune: []rune("abcde") }
のような形になっています。
これは一文字ずつの木を作りたい時には若干不便です。
例えば、abcd*e?という正規表現は abc, d*, e? という3つの *syntax.Regexp になります。
これと abef*g* を結合すると、 ab(?:cd*e?|ef*g*) のようになります。
これは、abc と abe を比較して、2文字目まで一致するのでそこまでを切り出して、残りの文字列からまた新しい *syntax.Regexp を作る必要があります。
一文字ずつの構造体になっていれば、このような複雑さはないはずです。
この構造体から自前の構造体に変換しようか結構悩みましたが、今はまだ *syntax.Regexp のまま計算しています。
そして、上でトライ木と述べましたが、実は *syntax.Regexp のまま構文木を操作しています。
一文字ずつに分割したほうが正規表現を表す構造としてきれいですし、一致判定のコードは統一的に書けるでしょう。
しかし *syntax.Regexp 相当の構造体を自前で実装するのは大変です。
構造体に埋め込んで一文字だけを特別扱いするとか、一文字ずつの *syntax.Regexp に分割するとか色々考えましたが、結局それを分割するのにもオーバーヘッドがありますし、コードのきれいさがそこまで見合わないだろうと判断しています。
また、多くの (少なくとも入力の文字列長以上の) 構造体を確保してしまうという、パフォーマンスの懸念もあります。
なので、今の実装の文字列の一致判定は []rune 同士をたどっています。
正規表現をまとめるからには、まとめた正規表現のパフォーマンスが気になるところです。
実際に /usr/share/dict/words の先頭100件、500件、そして1000件をrassemble-goで結合した正規表現と、 | で結合した正規表現を使って、/.../words の先頭2000件の単語をマッチ (MatchString) させたときのパフォーマンスを比較してみました。
BenchmarkRassembleJoin100-16 7065 164284 ns/op
BenchmarkSimpleJoin100-16 1237 1051659 ns/op
BenchmarkRassembleJoin500-16 1634 651378 ns/op
BenchmarkSimpleJoin500-16 224 5405078 ns/op
BenchmarkRassembleJoin1000-16 1112 1038448 ns/op
BenchmarkSimpleJoin1000-16 98 10608690 ns/op
やはりGoの正規表現でも、きちんと先頭をまとめた正規表現を使ったほうが速いことが分かりますね。
苦労して実装したものが実は全く意味なかったとしたらがっくりだったのですが、意味がありそうでよかったですね。
ただし、上記のベンチマークではrassemble-goで正規表現を結合するコストを無視しています。
特に後方一致の計算には時間がかかります (時間がかかると言っても /usr/share/dict/words の全件 (235886単語、2493109バイト) を結合するのに0.6秒くらいです、10000単語なら0.05秒以下で終わります)。
前処理とかプログラムで一回だけ走る箇所に使うのは大丈夫ですが、高いパフォーマンスが求められる箇所でのご利用はお控えください。
そもそも、そういう場面でGoの正規表現を使うのは間違っているのですが…
Regexp::AssembleのGo実装 rassemble-go を作りました。
この休日にがっつり集中して書いたのですが、実装していてめちゃくちゃ楽しかったです。
休日は溶けました。
今はかなり愚直な実装になっているので、もう少しパフォーマンス改善できないか考えているところです。
バグがあったら報告してください。
