Sunday柔軟なインデックス構造を目指して進化するLucene先日、ドキュメントをセグメントファイルに書き出すクラスであるDocumentsWriterのリファクタリングをしよう、というチケットがコミットされた。インデックスへの書き込みのプロセスをよりモジュール化して、将来の新しいインデクシング関連の機能追加はプラグインの追加で対応できるようにしよう、というのが狙いである:https://issues.apache.org/jira/browse/LUCENE-1301これはまた、フレキシブルインデクシングと呼ばれる新機能に対応するための第一歩でもある。現在、Luceneのインデックスファイルの構造は公開されているとおり、固定的なものである(それでもTermVectorやPayloadのオプションがON/OFFできたり、Field値の文字列の登録をON/OFFできたり、圧縮する/しないを選択することができたり、FieldのlengthNormをON/OFFできたりと、他の多くのOSS検索エンジンよりも相当に柔軟ではある)。これを将来はpositionやfrequencyを省略したり、逆にpositionに対して付加情報を追加できるようにしたり、圧縮アルゴリズムを自由に選択できるようにしたり・・・という具合にインデックスへの登録内容の自由度をさらに高められるようにする。アプリケーションの要件によって、インデックスに文書の関連情報を登録するのにも使えるほか、余分な情報を登録しないことでインデクシングや検索の性能向上にも貢献すると考えられる。frequency情報を省略できるようにする、というパッチが提案されている:https://issues.apache.org/jira/browse/LUCENE-1340frequencyを省略すればスコアにも影響が出るだろうが、スコアによる順位よりもフィールド値によるソートを多用するアプリケーションであれば気にならない。フィールド単位でfrequency情報を省略するかどうか選べるので、frequencyがそもそも不要なフィルタ系のフィールド(県名や性別、ユーザ権限など)であればこれを導入するメリットは大きい。そのようなフィールドでfrequency情報の登録を行わないようにすれば、インデクシング時間を短くしたり、ディスクI/Oが減ることで検索性能を向上させたり、メモリ消費量を少なくしたり、ディスク消費量を減らせたり・・・と、少し考えただけでも相当な効果が望めるものである。TuesdayIndexDeletionPolicyとSnapshotDeletionPolicyLuceneのインデックスファイルはマージのタイミングで新しいセグメントファイルが作成されていく。ファイル名はxxx.cfsやsegments_yyyとなりxxxやyyyの部分はインクリメントされていくのでインデックスへの文書の登録中や最適化中であっても以前の(オープン時の)インデックスの内容で検索が可能となっている。古いインデックスのセグメントファイルはいつかのタイミングで消さなければならない。2.2からこのタイミングをコントロールできるようにIndexDeletionPolicyというインタフェースが導入された。}}消されないまま残っているセグメントはコミットのListとして渡されるので、最新を残してdelete()しているのがわかる。このクラスはインデックスのスナップショットを取得するsnapshot()メソッドと、取得したスナップショットを開放するrelease()メソッドを持つクラスである。snapshot()とrelease()呼び出しの間で取得したスナップショットのバックアップを取るような応用が考えられる。}}「ここでバックアップを作成」の部分にバックアップのコードを挿入すれば、インデックスの更新を止めることなく検索で使用している最新のインデックスのバックアップを取ることができるようになる。vectorによりアクセスしやすくなった。:}上記のように、単語と出現回数はString[]、int[]という具合に配列で戻ってくる。よって出現回数の多いもの順に並べるというようなことをしたいときは、Comparatorを別途用意し、Collections.sort()などを使ってソートする必要があり面倒である。Lucene本でもそのようにしている(P282-283)。:}このTermVectorMapperの実装クラスを用意して次のようにIndexReaderに渡すと、適宜上記のメソッドが呼び出される。2.3にはSortedTermVectorMapper、FieldSortedTermVectorMapperおよびPositionBasedTermVectorMapperの3つのTermVectorMapperがすでに用意されている。getTermVectorEntrySet();以下ではこのSortedTermVectorMapperを使ったプログラムを紹介する。world!」という文字列を表示したりするのがプログラマの間では常識のようになっている。programhttp://en.wikipedia.org/wiki/Hello_worldとりあえずこのような文字列が決まっているとサンプルを提示するほうとしてはいろいろ悩まなくていいので簡単だ。world!」はあまり使わない。いうか、これまで使ったことがない。2語しかないのでつまらないからだ。「サザエさん」のデータは転置索引の説明に使ったり、次のようにLucene入門用プログラムのデータに使ったりしている:はじめてのLucene全文検索プログラムhttp://lucene.jugem.jp/?eid=67形態素解析やN-gramのAnalyzerの出力には「メガネは顔の一部です」をという文字列を使っている。TermFreqVectorのサンプルで使用することが多い。頻出語トップ10に現れて面白かった。安倍首相のときは、(TermFreqVectorではなくPayloadであったが)「美しい国」を連呼していることが見て取れることがわかった:記事から名詞だけを取り出すhttp://lucene.jugem.jp/?eid=133そこで今回のTermVectorMapperは福田首相の所信表明演説をデータとして使用することにする。);}reader.close();}}TermFreqVectorを使って同様のことを行うLucene本のプログラムと比べると、だいぶシンプルなプログラムになっている。結果を比較してみたところ、次のようになった。133人の演説で共通に現れる単語には薄く色付けしてある。これを見ると、小泉首相はトップに「改革」がきており、同じ改革路線を継承した形の安倍首相も「改革」がトップに来ているのがわかる。3人とも「国民」が2番目にきている。「向ける」となっている。この中で「皆様」に興味が引かれた私は、どのような使われ方をしているのかを調べた。すると、「国民の皆様」「野党の皆様」「被災者の皆様」「地方の皆様」という使われ方をしているのがわかり、いまさらながら若い首相の苦労が偲ばれたのだった。プログラムの実行にあたっては、StopFilterやPOSFilterに「ストップワード」や「ストップ品詞」を適切に設定する必要がある。RC1が公開中である。2.2からあっという間だった。2.2のリリース時は2.2の新機能を紹介しようと思い、サンプルプログラムを書きながら紹介記事を書いたりしたものだが、全部紹介しきらないうちにやがて新機能は「新」機能ではなくなり、そして今回の2.3のリリースを迎えることとなってしまった。コミッターたちは自分たちの仕事をいつやっているのだろう。2.3で新しく追加されたSinkTokenizerとTeeTokenFilterを使って実装する方法を紹介しよう。(自動)抽出することをいう。情報検索では抽出された「エンティティ」で絞り込み検索用のリンクを自動的に生成するなどの応用が可能となる。先ほどマイクロソフトによる買収の発表があった検索エンジン大手のFAST社の製品はエンティティ抽出の機能を持つらしい。知られるベイシス・テクノロジはエンティティ抽出のための製品も持っている:Rosette固有表現抽出システムhttp://www.basistech.co.jp/entity-extraction/SinkTokenizerとTeeTokenFilter今回紹介するエンティティ抽出のサンプルは、上記製品のように本格的なものではなく、形態素解析器(SenTokenizer)が出力するトークンのタイプを単純に判断して行うものとする。2.3になる前からSenTokenizerはトークンのタイプで「人名」や「地名」などとして品詞情報を出力できたので、やろうと思えば今までもエンティティ抽出は可能だった。2.3で追加されたSinkTokenizerとTeeTokenFilterでエンティティ抽出のようなプログラムを書くのが楽になった、ということがあげられる。SinkTokenizerとTeeTokenFilterは必ず組み合わせて使うことが前提である。SinkTokenizerはトークンを保持するバッファを内蔵する。そのトークンはTeeTokenFilterを通じて受信(sink)する。TeeTokenFilterは他の一般のTokenFilterと同様、上流のTokenizerからTokenizeされたトークンを受け取り、あたかもLinuxのteeコマンドのようにトークンをコピーして一方をSinkTokenizerに渡す。トークンは下流のTokenFilterに渡す。しておいて、SinkTokenizerに滞留したトークンを別のTokenFilterで処理してエンティティ抽出を行うのだ。大阪府知事選10日告示http://www.tokyo-np.co.jp/s/article/2008010801000867.html「橋下」が認識されていないこと、「熊谷貞俊」が「熊谷」「貞」と抽出されている以外は、きれいにエンティティが抽出できているのがわかるだろう(辞書をメンテナンスすればこれらも拾うことができる)。この出力結果を漫然と見ているだけでは形態素解析器が出力している品詞情報との違いがわかりにくく、ありがたみが感じられないだろう。このプログラムで重要なのは、抽出されたエンティティがオリジナルの文書と関連付けられて索引付けされているところだ。WednesdayLuceneでベイズ分類(experimental)Luceneのインデックスをベイズ分類に応用しようという実験的なパッチが提案されている:LUCENE-1039こちらの理論には素人なのでアルゴリズムは軽くスルーして、プログラムと実行結果を示す。これを使えば、文章を学習させたLuceneインデックスを使って、別の新しい文章の分類ができる。完璧では当然ないので、次のように間違うこともある(2番目は「政治」ではなく「芸能」と分類して欲しい):*****女優の広末涼子がイメージキャラクターを務める日本コカ・コーラ「からだ巡茶」の新CM「さよならハロー・フープ」編の撮影が行われた。芸能*****榊原といえば先日車上荒らしの被害にあったばかり。政治*****会談で大連立が話題になったかどうかについて「いろんな話をしたが、そこまで至らなかった」と否定した。首相官邸で記者団の質問に答えた。政治*****(与野党)共通の認識を持った政治運営がなされる可能性が出てきた。政治ただ、学習の量が足りないだけなのかもしれない。)[0].getClassification());}}なかなか楽しいプログラムなので、試したい人がいるかもしれない。そこで、LUCENE-1039のパッチの当て方とビルドの方法を簡単に説明しよう。http://svn.apache.org/repos/asf/lucene/java/trunkこれ以降、上記のオペレーションでできたtrunkディレクトリを$LUCENE_HOMEとする。contribのclassifierをビルドする。ant以上のビルドで$LUCENE_HOME/build/以下にできた3つのJARファイルを使って前述のプログラムをコンパイル、実行できる。FridayRailsアプリからSolrを使う全文検索のデモRailsアプリケーションからSolrを使う全文検索のデモを作成したので公開する。http://www.rondhuit-demo.com/yademo/デモシステムの全体構成は、次のようになっている。デモシステムは、「フロントアプリサーバ」と「検索エンジンサーバ」の2つのサーバプロセスからなる。「検索エンジンサーバ」はTomcatの上にSolrをデプロイして構成している。「フロントアプリサーバ」にはRailsで作られたアプリケーションが載っており、これがバックエンドの「検索エンジンサーバ」に検索のリクエストを送っている。Solrから返ってきた検索結果をHTMLにしてブラウザに戻している。上図の「フロントアプリサーバ」にはRailsという記述がないが、Flareと書いてあるのがRailsで構築されたSolrクライアントアプリケーションだ。このFlareがsolr-rubyを使ってSolrとの検索リクエスト/レスポンスの処理を行っている。デモデータには「Yahoo!オークション」の商品データ約201万件を使用している。このデモデータはYahoo!のWebサービスAPIを使用して2007年7月から9月頃にかけてクロールして収集したものである。検索の結果表示される商品説明はクロールしたHTMLをそのまま表示しているため、検索結果画面が多少乱れたり、画像抜けが起こったりする部分がある。本デモにはYahoo!オークションとしての機能は一切なく、単なる全文検索システムのデモであることをあらかじめお断りしておく。このデモの使い方や特徴を以下で簡単に述べる。検索キーワードサジェスチョンFlareのセールスポイントの一つが「検索キーワードのサジェスチョン」機能である。Suggestなどでおなじみのものだ。「検索キーワードのサジェスチョン」は検索キーワードの最初の数文字を入力すると、ユーザが検索ボタンをクリックする前にシステムがバックグラウンドで検索を行い、検索ヒット数と共に検索キーワードの候補をユーザに提示してくれるものだ。ユーザにとって「タイプ量が節約できる」「他人の検索キーワードからヒントが得られる」「検索ボタンをクリックする前にどのくらい絞り込めるのかがわかる」など、多くのメリットがあるのがこの機能の特徴である。Flareはこれを最初から提供している。Railsプログラマの期待を裏切ることなく、簡単な「規約」にしたがうだけでこの強力な機能がUIについてくるので製作側にとってもメリットが大きい。Flareのサジェスチョン機能はGoogleと異なり、あくまでもLuceneのインデックスを使ってサジェスチョンしているので、サジェスチョンの単位が「語」にとどまっている。その仕組み上から背後では膨大な計算が行われており、ドキュメント数やユーザ数が多い場合に応答速度の点で若干難がある。上図のようにカタカナ1文字で「ソ」と入力する場面は(ローマ字変換入力の場合)日本語ではあまりないと考えられるので、日本語での利用を考えたときには別の仕組みが必要である。したがって、Flareの「検索キーワードのサジェスチョン」は使えるアプリケーションかどうかをよく考えて導入するのがよいだろう。これらの問題点を解消した「検索キーワードのサジェスチョン」を弊社で開発中である。絞り込み検索FlareのデフォルトのUIでは、画面右側に自動的に絞り込み検索用のリンクが作成・表示される。Yahoo!オークションの商品データを使用したこのデモでは、Yahoo!オークションのカテゴリ(category)と出品者(seller_id)の上位20位までが表示されている。絞り込み検索では、リンクをクリックするだけで簡単に検索結果を絞り込むことができるようになっているため、ユーザからの人気が高い機能の一つである。この機能もFlareの簡単な「規約」にしたがうだけで使うことができる。検索条件の保存Flareでは検索窓に入力した検索キーワードと、絞り込み検索でクリックしたリンクを「検索条件」としてCookieに保存している。その内容は画面左上のFlareのロゴ(このロゴ画像はいくつかあるベータ版のうちのひとつであり、将来変わる可能性がある)の下に表示されている。constraints]のリンクをクリックしてそれまでの検索条件を消去する。各検索条件の右隣にある小さな[x]のアイコンをクリックして当該検索条件だけを削除することもできる。検索条件をクリックすると、検索条件をその場で変更して再検索もできる。このUIはRailsプログラマにはおなじみのものだろう。Mondayクチコミの評判の悪い店のランキングを下げる私はLuceneおよびSolr(最近はこちらの方がLuceneよりも多い)のコンサルティングやサポートを顧客に提供することを生業としている。いろいろな顧客の話を聞いていると、ランキング(検索結果のドキュメントの表示順のこと)を意図的に操作して出力したい、という要望が予想以上に多いのに驚く。)」で書いたようなある場所(現在地や最寄り駅)から近い順にお店情報を表示する、などである。「FunctionQueryの実用的なサンプル」で紹介したように、検索語の出現位置でランキングを操作する、という要求もあった。この他にもサイト運営者への「掲載料」の支払い額で企業がランクわけがされていて、掲載料をたくさん支払っている優良顧客の情報をtf*idfとは関係なく上位に持ってきてほしい、という要望も意外に多い。このような、ランキングへの顧客の多様な要求に柔軟に対応できるのもLuceneの隠れた大きな特徴のひとつである。今回はBoostingQueryを使って「クチコミの評判の悪い店」のランキングを意図的に下げる、ということを実装してみる。BoostingQueryとはBoostingQueryは、オリジナルのQueryインスタンスorigQueryに、マイナス評価を与えるnegativeQueryを組み合わせ、さらにマイナス評価に該当したときに指定した降格係数(まったくの私の造語だが、1未満のboost値のこと)を掛けて最終的なスコアとするQueryである。);あとは普通にqueryをIndexSearcherのsearch()に渡せばよい。BoostingQueryのnegativeQueryは、仕様をちょっと聞くとBooleanQueryのMUST_NOTとなんか似ている。両者はまったく異なるものである。BooleanQueryのMUST_NOTは、指定したQueryにヒットするドキュメントは検索結果には含まれない、まったくの「否定」となる。BoostingQueryのnegativeQueryはMUST_NOTのように「否定」ではないので、negativeQueryにヒットしたドキュメントが検索結果からはじかれる、ということはない。negativeQueryにヒットしたドキュメントのスコアはdemoteBoostの値が掛けられるのである。それにより、origQueryにヒットしたドキュメントのうち、さらにnegativeQueryに該当するドキュメントのスコアを下げることができる(あるいは、demoteBoostを1より大きくとることで、negativeQuery(この場合はpositiveQueryと呼ぶべきであろう)に該当するドキュメントのスコアを上げることができる)。coreではなくcontrib/queriesにあるので、contrib/queriesよりlucene-queries-x.x.jarを持ってきてクラスパス上に配置する必要がある。店名/メニュー/評判はプログラム試験用の創作であり、実在のお店やデータとは一切関係ありません。ジオ・ジアンテのサーモンのクリームパスタはまずい。","リストランテ・ピノリットのサーモンのクリームパスタはおいしい。","リストランテ・ピノリットのイベリコ生ハムのサラダはおいしくない。ジオ・ジアンテのイベリコ生ハムのサラダはお奨めです。店名/メニュー/評判はプログラム試験用の創作であり、実在のお店やデータとは一切関係ありません。ジオ・ジアンテのサーモンのクリームパスタはまずい。リストランテ・ピノリットのサーモンのクリームパスタはおいしい。リストランテ・ピノリットのイベリコ生ハムのサラダはおいしくない。ジオ・ジアンテのイベリコ生ハムのサラダはお奨めです。スコア(検索結果の前に表示されている実数)はどちらの検索文字列でも1.0と等しくなるので、この場合のランキングはドキュメントの登録順に表示されている。「まずい」や「おいしくない」というマイナス評価のドキュメントを先に登録しているので、「おいしい」や「お奨めです」より前に表示されてしまっている。店名/メニュー/評判はプログラム試験用の創作であり、実在のお店やデータとは一切関係ありません。リストランテ・ピノリットのサーモンのクリームパスタはおいしい。ジオ・ジアンテのサーモンのクリームパスタはまずい。ジオ・ジアンテのイベリコ生ハムのサラダはお奨めです。リストランテ・ピノリットのイベリコ生ハムのサラダはおいしくない。店名/メニュー/評判はプログラム試験用の創作であり、実在のお店やデータとは一切関係ありません。ジオ・ジアンテのサーモンのクリームパスタはまずい。","リストランテ・ピノリットのサーモンのクリームパスタはおいしい。","リストランテ・ピノリットのイベリコ生ハムのサラダはおいしくない。ジオ・ジアンテのイベリコ生ハムのサラダはお奨めです。店名/メニュー/評判はプログラム試験用の創作であり、実在のお店やデータとは一切関係ありません。);}}NEGATIVE_EVALSという文字列配列に「まずい」や「おいしくない」などのマイナス評価を示す文言を登録してあり、それをもとにnegativeQueryのインスタンスを作成している。当然のことながら、これらに合致しない文言は評判が悪いとは認識されない。SaturdayWildcardTermEnumを使うLuceneのインデックスにはフィールドごとに整理された単語帳がある。単語帳の単語はソートされた状態で格納されており、TermEnumを使ってその中の単語を列挙することができる。);terms.close();}TermEnumはTerm(=フィールド名+フィールド値)を列挙するものであるから、ループをまわしていくとTermがいつの間にか目的外のフィールドを指していることがありえるので、赤字の判定行が必要となる。[速達]......上記のように「通」から始まり、単語帳の指定フィールドの単語が尽きるまでTermが列挙されるのがわかる。ここでTermEnumの代わりにWildcardTermEnumを使うと「通」で開始する単語だけを列挙することが可能となる。2.2のcontribにN-gramで単語を切り出すNGramTokenizerとEdgeNGramTokenFilterが追加された(同時にEdgeNGramTokenizerとNGramTokenFilterも追加されたが、これらはあまり使われない気がする)。Analyzerといえば、CJKAnalyzerであった。これはCJK文字のときにだけ2文字単位で切り出すもので、bi-gramとも呼ばれるものである。"メガネは顔の一部です。);}}このプログラムを実行すると、次のようになる:メガネは顔の一部です。[です]CJKAnalyzerは上記のように日本語の文字を2文字単位に切り出す。このとき、となりどうしのトークンの文字が互いに重なるように切り出すのがN-gramの特徴である。「メガネ」は「メガ」と「ガネ」に分割される。することで後に「メガネ」で検索するときにも「(メガ)(ガネ)」という成句で検索されるために文章中の「メガネ」がうまい具合に検索できるのだ。CJKAnalyzerを使う動機としては、(形態素解析の)JapaneseAnalyzerと比較して辞書のメンテナンスが不要で流行語に強い、などが理由にあげられる。CJKAnalyzerを敬遠する理由としては、(Lucene本にも書いた例だが)「京都」で引いたときに「東京都」が引っかかってしまうとか(これはGoogleでもみられる現象だ)、1文字の単語が検索できない、などがあげられる。「京都」で「東京都」が検索できてしまうのは目をつぶれるとしても、後者は特に困った問題である。先のサンプルの例文はCJKAnalyzerを使っているときは、「顔」という検索語では検索できない。NGramTokenizerNGramTokenizerはコンストラクタで指定した大きさのトークンを文章から切り出すTokenizerである。);これをCJKAnalyzerの代わりに使用すれば、先ほどの「顔」で検索できない、という問題も解消できる。具体的なプログラムを示すと、まずNGramTokenizerはAnalyzerではないので、使用するにはAnalyzerを作成する必要がある。);}}上記のMyAnalyzerを最初のプログラム例のCJKAnalyzerと入れ替えて使用する。実行すると、次のようになる:メガネは顔の一部です。