Migemo Groupingの連続表現 - Giraffe+の開発についてのブログ

連続した文字列をMigemo Grouping(MigemoとAND, OR, NOTの組み合わせ)で表現する件の解説です。

例

hatenadaiari-

"はてなだいありー"や"ハテナダイアリー"にはマッチするが、"はてなダイアリー"にはマッチしない。

hatena(daiari-)

"はてなダイアリー"にもマッチする。

hatena(daiari-|bookmark)

"はてなブックマーク"にもマッチする。

以下仕様。簡潔にするため、出力例はmigemoを適用してません。実際には区切られた文字列ひとつずつがmigemoの対象になります。

基本

文字列とグループ(括弧でくくったもの)の間に空白を入れずに続けて書くと、文字列の連続性を意識した正規表現を生成します。

a(b)c -> (?=.*abc)

は、aで始まる単語とbで始まる単語とcで始まる単語が、その順番で連続してる文字列にマッチします。

AND

グループがANDである場合、文字列を消費せず、前部と連続しない正規表現になります。グループに続く文字列は、その場も含め、その後にあればいいという意味になり、.*?がANDと次の正規表現との間に挿入されます。

a(b c)d -> (?=.*a(?=.*b)(?=.*c).*?d)

は、aで始まる単語の後にbで始まる単語とcで始まる単語とdで始まる単語がある文字列にマッチします。
ANDが最後の配置されてもいいように、挿入されるのは.+?ではなく、.*?になっています。aとdが連続するものもマッチします。
bとcの位置はaの後であればよく、dの後にあるもの、例えばadcb等にもマッチします。
ANDは前部との連続性を維持すると無意味になる性質上、奇妙な仕様になっています。

OR

グループがORである場合、そのまま消費的な正規表現を返します。

a(b|c)d -> (?=.*a(b|c)d)

は、aで始まる単語の後にbで始まる単語かcで始まる単語があって、そのすぐ後にdで始まる単語がある文字列にマッチします。

NOT

グループがNOTである場合、文字列を消費しませんが、前部と連続してることは表現します。グループに続く文字列は、その場も含め、その後にあればいいという意味になり、.*?がNOTと次の正規表現との間に挿入されます。

a(-b)c -> (?=.*a(?!b).*?c)

は、aで始まる単語とbで始まる単語が連続せず、aで始まる単語の後にcで始まる単語がある文字列にマッチします。

組み合わせ

ORとNOTは内部も連続した場合と同じものを生成しますが、ANDは連続してない場合と同じになります。

a(-b|-c)d -> (?=.*a((?!b).*?|(?!c).*?)d)
a(-(b|c))d -> (?=.*a(?!(b|c)).*?d)
a(-b -c)d -> (?=.*a(?!(?=.*b))(?!(?=.*c)).*?d)
a(-(b c))d -> (?=.*a(?!(?=.*b)(?=.*c).*?).*?d)

ANDとORが対になってないので、NOT(A OR B)と(NOT(A) AND NOT(B))が違う結果になります。

補足

連続時の演算子には2つの属性があります。前方と後方の連続性です。ORは両方、NOTは前部のみ、ANDは無しで、見事に三つとも別物になってしまっています。

ANDの仕様がなぜこんななのかをもう少し説明すると、ANDが前方との連続を維持する場合、ANDが保持する2つの要素は両方ともNOTのみになるためです。そして、(-a -b)が前方と連続する場合、(-(a|b))と同じ意味になります。
表現手段が他にあり、かつそれしか出来ないなら、そんなものは捨てて、全くの別物として表現力を広げたほうがいいと判断しました。

実際にどういう出力になっているかは、Giraffe+で下記のスクリプトを実行(エディットに入力してF1)すると解かります。

Migemo.query_grouping("文字列" 0).flush

第一引数が対象文字列、第二引数が最大リテラル文字数です。例えば第二引数が2なら、2文字以下の文字列はMigemoの対象になりません。

Boost.Spiritを使ったグルーピングのソースがand_or_grouping.hppで、それを利用したMigemo Groupingのソースはmigemo_grouping.hppです。それぞれ同名のcppがBoost.Testを使ったテストです。

ちょっと使ってみると括弧を閉じるのが面倒なことに気付きました。次VER(Giraffe+ 0.5.58)では省略可能にします。