関口宏司のLuceneブログ

OSS検索ライブラリのLuceneおよびそのサブプロジェクト(Solr/Tika/Mahoutなど)について
<< 書籍に関する問い合わせフォームの設置 | main | 独自QueryParserの作成(5) >>
独自QueryParserの作成(4)
検索式演算子の優先度

AND/OR/NOTの演算子を含む検索式を正しくBooleanQueryに展開するために、演算子の「結合規則」や「優先順位」を決める必要がある。MyQueryParserではこれを次の表のように定めることとする:

演算子結合規則優先度
AND=>
OR=>
NOT(二項)=>
(省略)=>


「結合規則」はすべて=>となっており、これは「左結合」を意味する。また演算子NOTは二項演算子なので「A NOT B」のように使用する場面に適用されるものであり、「NOT A」のようなNOTについてはのちほど考えることにする。また演算子を省略した場合は初回に決めたMyQueryParserの仕様どおりANDと解釈する。

生成規則を作成する

左結合の二項演算子の式を表現する生成規則は次のとおりである(前回紹介した「JavaCC - コンパイラ・コンパイラ for Java」などを参照):



leftExpr() ::= higherExpr() ( <OP> higherExpr() )*



また、被演算子の式を表現する生成規則は次のとおりである:



prim() ::= <WORD> | <LP> expr() <RP>



これらの生成規則を前出の表の優先順位に沿って組み合わせていく。

最初は被演算子の式を表現する生成規則を使ってphraseExpr()を作成する。これは次のようである:



phraseExpr() ::= <WORD> | <LP> defaultExpr() <RP>



次に、表の中でもっとも優先度の高いAND演算子の生成規則を作成する。これは左結合なのでleftExpr()を用いて次のようになる:



andExpr() ::= phraseExpr() ( <OP_AND> phraseExpr() )*



ここで、leftExpr()の右辺のhigherExpr()は優先順位が上位のphraseExpr()に置き換えられている。

次に、表の中で次に優先度の高いOR演算子の生成規則を作成すると、次のようになる:



orExpr() ::= andExpr() ( <OP_OR> andExpr() )*



以下同様にNOTと省略時の演算子の生成規則を作成する:



notExpr() ::= orExpr() ( <OP_NOT> orExpr() )*

defaultExpr() ::= notExpr() ( notExpr() )*



以上をまとめると、検索式の生成規則は全体で次のようになる:



phraseExpr() ::= <WORD> | <LP> defaultExpr() <RP>
andExpr() ::= phraseExpr() ( <OP_AND> phraseExpr() )*
orExpr() ::= andExpr() ( <OP_OR> andExpr() )*
notExpr() ::= orExpr() ( <OP_NOT> orExpr() )*
defaultExpr() ::= notExpr() ( notExpr() )*



""を認識する

次に「"(ダブルクオーテーション)」でくくられた検索質問語を認識するように修正を加える。""でくくられるものは、ひとつ以上の単語でフレーズとなることから、前出のphraseExpr()に追加して、次のようになる:



phraseExpr() ::= <WORD> | <QUOTE> (<WORD>)+ <QUOTE> | <LP> defaultExpr() <RP>



ここで、「"」は<QUOTE>という表現に置き換えている。

「NOT 検索質問語」をサポートする

次に「NOT A」というフォーマットの検索式をサポートするように修正を加える。

ここで使われるNOTは前出の二項演算子のNOTとは異なり単項演算子である。しかも、(数式の単項演算子"-"(マイナス)とは異なり)検索式の途中には出現せず、常に先頭にのみ使われる。ということは、検索式は「defaultExpr()」かあるいは「NOT defaultExpr()」であると考えてよい。結局、検索式queryExpr()の生成規則は、全体として次のようになる:



phraseExpr() ::= <WORD> | <QUOTE> (<WORD>)+ <QUOTE> | <LP> defaultExpr() <RP>
andExpr() ::= phraseExpr() ( <OP_AND> phraseExpr() )*
orExpr() ::= andExpr() ( <OP_OR> andExpr() )*
notExpr() ::= orExpr() ( <OP_NOT> orExpr() )*
defaultExpr() ::= notExpr() ( notExpr() )*
queryExpr() ::= defaultExpr() | <OP_NOT> defaultExpr()



生成規則のコード化

生成規則を(読みやすさを考えて)順序を逆転し、JavaCCのコードに置き換えると次のようになる:



Query queryExpr() :
{
}
{
defaultExpr() | <OP_NOT> defaultExpr()
}

Query defaultExpr() :
{
}
{
notExpr() ( notExpr() )*
}

Query notExpr() :
{
}
{
orExpr() ( <OP_NOT> orExpr() )*
}

Query orExpr() :
{
}
{
andExpr() ( <OP_OR> andExpr() )*
}

Query andExpr() :
{
}
{
phraseExpr() ( <OP_AND> phraseExpr() )*
}

Query phraseExpr() :
{
}
{
<WORD> | <QUOTE> (<WORD>)+ <QUOTE> | <LP> defaultExpr() <RP>
}



次回は上記JavaCCのコードにアクションを記述する。また、検索禁止語への対応は(JavaCCではなく)Javaのプログラムでおこなうため、アクションを記述したあとに考える。
| 関口宏司 | Lucene自由自在 | 07:23 | comments(4) | trackbacks(1) |
いつも拝読させていただいております。
こちらのエントリ、tableタグの至る所に改行タグが挿入されていて、Safari や Firefox で見ると異様に大量の空白行が表示されるようです。
FYI
| インギ | 2006/11/13 5:43 PM |
インギさん、こんにちは。
そうなんです。なんでそうなってしまうのか、よくわからないのですが。。。
| 関口 | 2006/11/13 7:37 PM |
blogサーバ側で自動的に改行が入るようになっているのではないでしょうか?
table,tr,tdまで改行せず続けて書けば良いかもしれません?
| インギ | 2006/11/13 11:10 PM |
> table,tr,tdまで改行せず続けて書けば良いかもしれません

ビンゴでした!
| 関口 | 2006/11/13 11:16 PM |









http://lucene.jugem.jp/trackback/101
JavaCC―コンパイラ・コンパイラfor Java
JavaCC―コンパイラ・コンパイラfor Java よい本です.そもそもJavaCCの情報はWebにもあまりなく,詳しい解説をしている本が他にありま...
| もぼなもな書房 | 2009/05/22 4:50 PM |
+ Solrによるブログ内検索
+ PROFILE
     12
3456789
10111213141516
17181920212223
24252627282930
31      
<< December 2017 >>
+ LINKS
検索エンジン製品 - 比較のポイント
商用検索エンジンを購入した企業担当者は読まないでください。ショックを受けますから・・・
>>製品比較 10のポイント
+ Lucene&Solrデモ
+ ThinkIT記事
+ RECOMMEND
Apache Solr入門 ―オープンソース全文検索エンジン
Apache Solr入門 ―オープンソース全文検索エンジン (JUGEMレビュー »)
関口 宏司,三部 靖夫,武田 光平,中野 猛,大谷 純
+ RECOMMEND
Lucene in Action
Lucene in Action (JUGEMレビュー »)
Erik Hatcher,Otis Gospodnetic,Mike McCandless
FastVectorHighlighterについて解説記事を寄稿しました。
+ RECOMMEND
+ SELECTED ENTRIES
+ RECENT COMMENTS
+ RECENT TRACKBACK
+ CATEGORIES
+ ARCHIVES
+ MOBILE
qrcode
+ SPONSORED LINKS