ククログ

groongaにデータを登録してからインデックスが更新されるまでの流れ

全文検索エンジンgroongaを囲む昼下がり@札幌はたっぷり3時間もあるので、「groongaがどのように動いているか」、「より効率的に検索するためにはどうしたらよいか」などといった話ができるはずです。

この文書は、札幌でのgroonga勉強会で使うための「groongaがどのように動いているか」を説明に使うための文書です。後でgroongaのドキュメントにマージする予定です。

それでは、groongaがどのように全文検索用のインデックスを作成しているかを説明します。まず、全文検索機能で重要なオブジェクトを説明して、その後にそれらを使ってどのようにインデックスを作成しているかを説明します。

主要オブジェクト

groongaの全文検索機能で大事なオブジェクトは以下の3つです。

1. テーブル
2. カラム
3. トークナイザー

それぞれ順に説明します。

テーブル

groongaでは、ひとまとまりのデータを「レコード」と呼びます。これはRDBと同じです。RDBでも行ごとにまとまったデータをレコードと呼んでいます。

groongaのテーブルは「レコードID」を管理するオブジェクトです。「レコードID」とはレコードを一意に識別する数値です。

なお、1つのテーブルで管理できるレコード数（レコードID）の理論的な上限値は約2億6千万レコードです。

テーブルには以下の3つの種類があります。

1. 配列
2. ハッシュテーブル
3. パトリシアトライ

配列はID列を持ったテーブルです。レコードを追加すると新しいレコードIDを払い出します。基本的にレコードIDは1, 2, 3, ...というように順に払い出されます。

ハッシュテーブルはID列とIDと1対1に対応するキーを持ったテーブルです。レコードを追加するときは必ずキーも一緒に指定します。レコードが追加されるとキーに対応したレコードIDを払い出します。ハッシュテーブルが払い出すレコードIDも1, 2, 3, ...というように順に払い出されます。もし、レコードを追加するときに指定したキーが既存のレコードと同じキーだった場合は新しくレコードIDを払い出さず、既存のレコードと同じIDを返します。

パトリシアトライもハッシュテーブルと同様にID列とIDと1対1に対応するキーを持ったテーブルです。レコードの追加も同じように動きます。

配列ではレコードIDでのみレコードを特定できますが、ハッシュテーブルとパトリシアトライはレコードIDだけではなくキーでもレコードを特定できます。

パトリシアトライとハッシュテーブルとの違いはキーの検索方法です。

ハッシュテーブルではキーの検索方法は完全一致検索のみです。つまり、キーからレコードIDを求めるには、求めたいレコードのキーと同一のキーを指定するしかないということです。一方、パトリシアトライでは、完全一致検索だけではなく前方一致検索もできます。

例えば、ククログのデータがgroongaのデータベースに入っているとします。1エントリが1レコードに対応し、エントリが書かれた日付をキーにしているとします。すると、ここ2ヶ月では以下のようなキーになります。

• "2011-8-11"
• "2011-8-24"
• "2011-9-5"
• "2011-9-13"
• "2011-9-29"

この中から2011/9に書かれたエントリのみを表示したいとします。すると、2011/9に書かれたエントリのレコードIDの一覧を取得しなければいけません。この場合、パトリシアトライを使っていると"2011-9-"でキーを前方一致検索することで実現できます。しかし、ハッシュテーブルではこのようなことはできません。

また、パトリシアトライを使うとキーワードリンクなどといったこともできるようになります。

なお、レコードの参照速度の速い順にテーブルの種類を並べると以下のようになります。

1. 配列
2. ハッシュテーブル
3. パトリシアトライ

配列と他の2つのテーブルの使い分けは、ID以外にレコードを特定するキーが欲しいかどうかで考えます。ハッシュテーブルとパトリシアトライの使い分けは、キーを完全一致検索だけで使うかどうかで考えます。

カラム

テーブルはレコードIDを管理するだけで、レコードが持つ値はカラムに保存します。1つのレコードに対して複数のカラムをひもづけることができるため、レコードは複数の値を持つことができます。

カラムには以下の3つの種類があります。

1. スカラーカラム
2. ベクターカラム
3. インデックスカラム

スカラーカラムは1つの値だけを保存できるカラムです。数値を保存するカラムなら「29」や「2929」などを保存できます。文字列を保存するカラムなら「"groonga"」や「"札幌"」などを保存できます。

ベクターカラムは複数の値を保存できるカラムです。同じ種類の値だけを保存できる配列と考えるのがよいでしょう。数値を保存するカラムなら「[2, 29, 292]」などを保存できます。文字列を保存するカラムなら「["groonga", "札幌"]」などを保存できます。

インデックスカラムは転置インデックスを保存するカラムです。転置インデックスは単語IDとその単語IDが含まれている文書IDをひもづけたデータ構造です。

groongaのインデックスカラムでは、単語IDはインデックスカラムのあるテーブルのレコードIDに対応します。文書IDは検索対象のテーブルのレコードIDに対応します。なお、インデックスカラムがあるテーブルのことを「語彙表（lexicon）」と呼びます。

スカラーカラムとベクターカラムはどのテーブルでも一緒に使えますが、インデックスカラムは配列と一緒に使うことはできません。ハッシュテーブルかパトリシアトライと一緒に使う必要があります。これは、groongaでは単語をキーとしたレコードを作成することによりレコードID（= 単語ID）を作成しているためです。

トークナイザー

トークナイザーとは文書から単語を切り出すオブジェクトのことです。例えば、"I am a boy"という文書から「I」、「am」、「a」、「boy」という4つの単語を切り出したりします。この切りだすことを「トークナイズ」と呼びます*1。転置インデックスを作成するときは、単語IDと文書IDをひもづけるために文書内の単語を抽出する必要があります。それを行うのがトークナイザーです。

groongaでは、語彙表用のテーブル毎にトークナイザーを指定します*2。

転置インデックスの更新は元の文書を登録・更新・削除したときにgroongaが自動的に行います。そのため、ユーザが明示的にトークナイザーを使うことはありません。単に指定するだけです。

groongaで利用できるトークナイザーの一部は以下の通りです。

• TokenBigram: バイグラムでトークナイズする。
• TokenMecab: MeCabを使ってトークナイズする。
• TokenDelimit: 空白区切りでトークナイズする。

データ更新時の動作

データを更新するとgroonga内部で自動的に転置インデックスが更新されます。そのときの動作を説明します。

まず、最初は、検索対象のテーブル（= 文書を保存するテーブル）にも語彙表のテーブルにもなにもレコードがありません。

それでは、検索対象のテーブルにデータを保存しましょう。

"Yes good"という文書を保存しました。最初の文書なのでレコードID（= 文書ID）は1になっています。データが保存されるとgroongaが内部で自動的に転置インデックスを更新します。

"Yes good"は「Yes」と「good」という2つの単語にトークナイズされます。まずは、「Yes」が語彙表に登録されます。これは最初の単語なのでレコードID（= 単語ID）は1になっています。続いて、単語IDが1に対応するインデックスカラムには保存された文書の文書IDとして1を登録します。

次に2つ目の単語である「good」を処理します。

「good」も「Yes」と同様に処理します。まずは、「good」が語彙表に登録されます。「good」の単語IDは2になります。続いて、単語IDが2に対応するインデックスカラムに保存された文書の文書IDである1を登録します。

もうひとつ文書を保存します。

2番目の文書なので文書IDは2になりました。データが保存されるとgroongaが内部で自動的に転置インデックスを更新します。

"Hey good"は「Hey」と「good」という2つの単語にトークナイズされます。まずは、「Hey」が語彙表に登録され、単語IDが3になります。続いて、単語IDが3に対応するインデックスカラムには保存された文書の文書IDとして2を登録します。

次に2つ目の単語である「good」を処理します。

「good」はすでに登録されている単語なので、新しく追加せずに既存の「good」と同じ単語IDを使います。「good」の単語IDは2なので、対応するインデックスカラムに文書IDとして2を登録します。このとき、すでに文書ID 1も登録されているので文書ID 2は追加します。

このようにして転置インデックスが作成されます。

まとめ

groonga内部でどのように転置インデックスを更新しているかを説明しました。この動作がわかっていると検索が期待通りに動かないときにどこが問題かを見つけやすくなります。例えば、語彙表のキーに期待通りの単語が入っていなかったら、間違ったトークナイザーを指定しているかもしれません。もし、そもそも語彙表に単語が入っていなかったら、転置インデックスの自動更新が動いていないのでしょう。異なるカラム用にインデックスカラムを作成していないかを確認する必要があります。

それでは、全文検索エンジンgroongaを囲む昼下がり@札幌で会いましょう。

ツイートする

フォローする

Debian GNU/LinuxでWindows用バイナリをビルドする方法

2011/10/13時点でのDebian GNU/Linux sidでの話です。

Debian GNU/Linux上では、KVMやXenなどの仮想マシンを使わなくてもDeiban GNU/LinuxやUbuntu用のパッケージのビルドをできますし、CentOSやFedora用のパッケージのビルドもできます。Windows用のバイナリもDebian GNU/Linux上でビルドできると1台のマシンですべてのパッケージをビルドできるのでgroongaのようにたくさんの環境向けのパッケージを用意する場合に便利です。

以前、Rubyではrake-compilerを使ってWindows用のバイナリ入りgemをビルドできることを紹介しましたが、ここで紹介するのはrake-compilerが中で何をしているかについてです。rake-compilerがやっていることがわかると、rake-compilerなしでも同じことができるため、Rubyの拡張ライブラリ以外でもDebian GNU/Linux上でWindows用バイナリをビルドできるようになります。

用意するもの

Debian GNU/Linux上でWindows用バイナリをビルドするためにはクロスコンパイルする必要があります。そのために、x86（32bit版Windows）にもx64（64bit版Windows）にも対応したMinGW-w64を使います。MinGW-w64はGCCでWindows用バイナリをビルドするために必要なヘッダーファイルやライブラリなど一式を提供します。

mingw-w64パッケージをインストールしてMinGW-w64環境を作ります。

% sudo aptitude -V -D -y install mingw-w64

準備はこれで完了です。

クロスコンパイルしやすいソフトウェア

./configure; make; make installでビルドするGNUビルドシステムを使っているソフトウェアはクロスコンパイルしやすいです。これは、configure内にクロスコンパイル用の処理が含まれているからです。

ここでは、GNUビルドシステムを使っているgroongaを使って、どのようにビルドするかを紹介します。ソースコードをダウンロードして展開しておきましょう。

% wget http://packages.groonga.org/source/groonga/groonga-1.2.6.tar.gz
% tar xvzf groonga-1.2.6.tar.gz
% cd groonga-1.2.6

ビルド

クロスコンパイルするときに一番大事なのがconfigureのところです。むしろ、configureをうまくやれたら後はmake; make installするだけなので違いはconfigureだけになるべきです。

configureを実行するときのポイントは--hostオプションです。ここにビルド対象のプラットフォームを指定します。x64用にビルドするときは以下のように--host=x86_64-w64-mingw32を指定します。

% ./configure --host=x86_64-w64-mingw32

もし、システムにlibmecab-devパッケージがあるとLinux用のMeCabが使われてしまいます。libglib2.0-devパッケージも同様です。そのような場合は、以下のようにconfigureで自動検出している部分を無効にしてください。

% ./configure --host=x86_64-w64-mingw32 --without-mecab --disable-benchmark

configureが成功したらいつも通りmakeします。

% make

パッケージを作るときはmake installにDESTDIR変数を指定して一時的な場所にインストールしてからアーカイブするとよいでしょう。

% make install DESTDIR=/tmp/groonga
% cd /tmp/groonga/
% mv usr/local groonga-1.2.6
% zip -r groonga-1.2.6.zip groonga-1.2.6

簡単ですね。

なお、x86用にビルドする場合は--host=i686-w64-mingw32を指定してください。

システムにインストールされているMinGWを確認する（つまり、--hostに指定できる値を調べる）には以下のようにします。

% (cd /usr; echo *mingw*)
i686-w64-mingw32/ x86_64-w64-mingw32/

この場合は--host=i686-w64-mingw32または--host=x86_64-w64-mingw32を指定できます。

まとめ

groongaを例にしてDebian GNU/Linux上でWindows用のバイナリをビルドする方法を紹介しました。これで、Debian GNU/Linux上でDebianパッケージもRPMもWindows用バイナリもビルドできてリリース作業が楽になりますね。

ツイートする

フォローする

groongaの全文検索処理の流れ

groongaにデータを登録して、インデックスを更新すると全文検索をすることができます。ここでは、groongaが内部でどのような処理をして全文検索をしているかを説明します。

前提

まず、以下のように「Yes good」と「Hey good」という文書が登録されているとします。

このとき、「Yes good」で検索したらどうなるかを説明します。

トークナイズ

まず、入力の「Yes good」をトークナイズします。このとき使用するトークナイザーは使用する転置インデックスと同じものです。転置インデックスが使用するトークナイザーは語彙表（lexcion）を見ればわかります。今回はTokenDelimitトークナイザーですね。

TokenDlimitは空白区切りでトークナイズするトークナイザーなので「Yes good」は「Yes」と「good」にトークナイズされます。

転置インデックスの参照

トークナイズしたら、それぞれの単語について転置インデックスを参照します。転置インデックスの参照は2段階あります。

まず、単語をキーとしてlexiconを検索し、単語ID（= lexiconのレコードID）を取得します。「Yes」の場合は単語IDは「1」です。

次に、単語IDを使って単語に対応する転置インデックスの値を取得します。単語ID「1」に対応する転置インデックスの値は文書ID「1」です。つまり、「Yes」という単語を含む文書は文書IDが「1」の文書だということです。

続いて、単語「good」の転置インデックスを参照します。「Yes」のときと同様にまずはlexiconを検索します。「good」の単語IDは「2」です。

「Yes」の時と同様に、単語IDを使って単語に対応する転置インデックスの値を取得します。単語ID「2」に対応する転置インデックスの値は文書ID「1」と「2」です。つまり、「good」という単語を含む文書は文書IDが「1」の文書と「2」の文書だということです。

元の入力は「Yes good」だったので、「Yes」の転置インデックスにも「good」の転置インデックスにも両方含まれている文書ID「1」だけがヒットした文書になります*1。文書ID「2」は「good」の転置インデックスに含まれていますが、「Yes」の転置インデックスには文書ID「2」が含まれていないので「Yes good」ではヒットしません。

部分文字列での全文検索

このケースでは「ood」など部分文字列ではヒットしません。どうしてヒットしないかを説明します。

まず、「ood」をトークナイズすると空白がないので「ood」という1単語にトークナイズされます。次に、「ood」という単語でlexiconを検索するとそのような単語は登録されていないので、単語IDを取得できません。そのため、この時点でヒットする文書がないと判断し、転置インデックスは参照しません。

それでは、部分文字列でも検索できるようにするにはどうすればよいかというと、トークナイザーを変更します。どうしてトークナイザーがでてくるかというのは、先に説明した転置インデックスを参照する処理の流れを考えるとわかります。

転置インデックスを参照する処理は以下の2つの処理にわけられます。

1. lexiconから単語IDを取得する。
2. 単語IDを使って転置インデックスの値を取得する。

「ood」で検索する例で確認した通り、「lexiconから単語IDを取得する」ことができないために部分文字列で検索できていません。よって、部分文字列でも「lexiconから単語IDを取得する」ことができるようにすれば、部分文字列でも検索できるようになります。

ここでトークナイザーの出番です。lexiconに登録される単語は文書をトークナイズして得られた単語です。そのため、トークナイズするときに部分文字列も単語としてトークナイズすればlexiconに単語の部分文字列も登録されます。すると、検索時に部分文字列でlexiconを参照しても単語IDを取得することができます。

groongaにはいくつか組み込みのトークナイザーがあります*2。部分文字列でも検索できるようにするには空白区切りで単語にトークナイズするTokenDelimitではなく、2文字単位で単語にトークナイズするTokenBigramを使います*3。

トークナイザーとしてTokenBigramを使うと「Yes good」は「Ye」・「es」・「s 」・「 g」・「go」・「oo」・「od」・「d」にトークナイズされます。

このとき、「ood」で検索したらどうなるかを説明します。

まず、転置インデックスが使っているのと同じトークナイザーTokenBigramでトークナイズします。「ood」は「oo」・「od」にトークナイズされます。lexiconを検索すると「oo」の単語IDは6で「od」の単語IDは7です。どちらも登録されている単語なのでヒットする文書がありそうです。

次に、単語ID「6」と単語ID「7」の転置インデックスを参照します。「oo」も「od」もどちらも文書ID「1」に含まれていることがわかります。よって、文書ID「1」の文書は「ood」という文字列を含んでいることがわかります*4。

検索時はこのように動作するため、トークナイザーによって検索結果が異なります。

トークナイザーの使い分け

では、トークナイザーはどのような基準で選ぶとよいのでしょうか。一見すると、部分文字列でも検索できるトークナイザーの方がよさそうに見えます。しかし、必ずしもそうとは限りません。部分文字列でもヒットするということは、望んでいない文書もヒットする可能性が増えるということです。

例えば、「cat」で「category」もヒットするようになります。「cat」で検索しているときに「category」に関する文書もヒットすると、それはノイズとなります。ノイズが多いと目的の文書を見つけづらくなってしまうため、使い勝手が悪くなります*5。よって、部分検索もできるようにしたほうがよいかどうかはアプリケーションに依る、ということになります。

なお、groongaは1つの全文検索で複数の転置インデックスを使うことにより、「完全一致した文書はスコアを高めにつけて、部分一致した文書はスコアを低めにつける」ということもできます。これは、転置インデックス毎*6に異なるトークナイザーを利用できるためです。

タグ検索

転置インデックスを用いると全文検索と同じ方法でタグ検索も実現できます。

実は、上記のTokenDelimitを使った全文検索の説明はタグ検索の動作そのものになっています。「Yes」や「good」をタグだと考えてもう一度読みなおしてみてください。

まとめ

groongaでの（簡略化した）全文検索処理の流れを説明しました。思ったように検索ができない場合は、全文検索の処理の流れを考えながら挙動を確認していくと、どこが問題かをみつけやすくなるはずです。

ツイートする

フォローする

どうして開発者がドキュメントを書くべきか

オフィス文書形式が要求されるようなドキュメントではなくて、自分が開発したライブラリのドキュメント（リファレンスマニュアルやチュートリアルなどライブラリのユーザーが読むためのドキュメント）の話です。以下の「ドキュメント」もそのような意味で使っています。

使いやすいライブラリを開発したかったらプログラムだけではなくドキュメントも書くべきです。

なぜドキュメントを書くか

ドキュメントを書く習慣があるかどうかは開発者によってあったりなかったりです。使っているプログラミング言語に相関がある気もしますし、リリースするかどうかに相関がある気もします。理由はいろいろあるでしょうが、ドキュメントを書く習慣のない開発者の方が多いでしょう。

書かない理由はこんな感じでしょうか。

• 面倒。
• 自分しか使わないからいらない。
• どのように書けばよいかわからない。（どのツールを使えばよいかわからない。）

一方、書く理由はこんな感じでしょう。

• 他の人が使えるようにしたい。
• 何度も同じ事を質問されて、個別に説明することの方がドキュメントを用意することより面倒になった。

だいたいあっていますか？しかし、使いやすいライブラリを開発したい場合は「ユーザーの視点でAPIを見直すため」にドキュメントを書くという視点を忘れてはいけません。

ユーザーの視点でAPIを見直す

ドキュメントはライブラリのユーザーが読むものです。そのため、たとえ開発者がドキュメントを書くとしても、開発者の立場ではなく、ユーザーの立場になってドキュメントを書く必要があります。そうしないと「ユーザーが読んでもわからない」・「誰の役にたつのかわからない」ドキュメントになってしまいます。

ドキュメントを書くときはなるべく簡潔な記述になるように意識します。これは「なるべく情報を落とせ」ということではありません。「複雑な説明や長い説明がなくても使えるようにしろ」ということです。

例えば、WebページをPDFで保存するライブラリを作ったとします。もし、以下のようなドキュメントになっていたら要注意です。

まず、WebPrinterオブジェクトを作ります。

  web_printer = WebPrinter.new

次にPDFで保存したいURLを設定してWebページをダウンロードします。

  web_printer.url = "http://www.clear-code.com/"
  web_printer.download

最後に出力PDFファイル名を指定してPDFを出力します。

  web_printer.print("clear-code.pdf")

ドキュメントを書いていて「手順が多いな」・「たくさん書いているな」と気付けることが重要です。それに気付いたら「もっと簡潔にドキュメントを書けるようにするにはどんなAPIになっていればよいだろう」と考えてください。これをやるかどうかでライブラリの使い勝手はかなり変わります。

例えば、上述のWebPrinterは以下のように使えるようにすることもできます。

WebPrinter.printにPDFで保存したWebページのURLと出力PDFを指定します。

  WebPrinter.print("http://www.clear-code.com/", "clear-code.pdf")

このようなAPIを提供するには以下のような便利メソッドを定義するだけですね。

class WebPrinter
  class << self
    def print(url, pdf_path)
      printer = new
      printer.url = url
      printer.download
      printer.print(pdf_path)
    end
  end
end

このように、ユーザーの立場で考えて、ユーザが使いやすいものになっているかという視点を意識しながらドキュメントを書くことであなたのライブラリはもっと使いやすいものになります。

まとめ

ドキュメントを書くことがキライな開発者は「ドキュメントを書くよりもコードを書くことに時間を使った方がずっとよいソフトウェアになる」と思っているかもしれません。形だけのドキュメントを書くならたぶんそうなんでしょう。しかし、「ユーザが使いやすいソフトウェアか」という視点でドキュメントを書けば、それはよいソフトウェアの開発につながります。

なお、このような視点でドキュメントを書くとプログラムの改善作業が発生します。そのため、リリース前に慌ててドキュメントを書くとドキュメントもAPIも中途半端な状態のままリリース、あるいは、リリース日の延期になったりします。あらかじめ、ドキュメントを書く時間だけではなく、プログラムを改善する時間も見込んでおきましょう。

参考: Gaucheの開発者のshiroさんも別の視点で見るためにドキュメントを書くというようなことに言及しています。（ただし、「ユーザー視点」というわけではなさそうです。）

• Island Life - Gaucheにdocstringが無い理由
• Island Life - コードと別にドキュメントを書く意味

ツイートする

フォローする