少し目先を変えて他のことを

調べてみた｡*1
資料が致命的に少ないFTS3にCustom tokenizerを外部拡張として喰わせる方法とかをぼちぼち｡

まずは最初に､

言葉の定義を｡｡｡

FTS3: SQLiteに実装されている全文検索モジュール｡現在ドラフト｡
Tokenizer: 全文検索のIndexingを行う際､どのような規則でIndexを作成するかが詰まってるモジュール*2
Source: Tokenizerに渡ってきたそのものの文字列｡これをTokenizerでTokenに分解する｡
Token: Sourceに渡ってきた文字列を分解した要素*3

何もしないで出来ること｡

はじぇんじぇんなかったりする*4 コンパイル段階で､FTS3が有効になってないと､そもそもからして使えない｡*5

じゃあ､どのように使うのか

というと､以下の通り､基本的に仮想テーブルとして作成する｡*6

CREATE VIRTUAL TABLE <TableName> USING FTS3(<FieldName>,TOKENIZE <TokenizerName>,<ModuleArgument>*);

FTSに関係するような部分だけかいつまむと､TokenizerNameでトークンナイザを指定して､ModuleArgumentで､Tokenizerに引数を渡すことが可能｡引数を取らない､Moduleなら省略可能だし､デフォルトが決してる場合も同様｡
ちなみにTokenizerは組み込みで､"simple"と"porter"が選択可能｡それぞれのトークンナイザの特徴は以下

simple: 文字通りシンプルにスペース区切りを一つのトークンとして扱う(ex;"Hello world!"なら､HelloとWorldにわ分割されて､!は無視される｡)
porter: 主に英単語とかで､複数形､過去形などで語尾の変化が起きると言う揺らぎを､一定の経験則からなるアルゴリズムでその揺らぎを除去した上で除去後の単語を一つのトークンとするトークンナイザ(ex:"Three pieces punpkine pies."は"three" "piece" "punbkine" "pie"になるかんじ)

ええ､どれも日本語相手には使えない　orz

基本的に､extensionのloadベースでdllを喰わせるので､sqlite3_loadextension_init関数を利用する｡C#というか､オブジェクト指向しかほぼやってなかった身からすると､結構トリッキーなことしてるなぁとおもった*7
で､喰わせた後に実操作になるわけですが､かなり間違った言い方をすると､sqlite3_tokenizerとsqlite3_tokenizer_cursorを継承する形でカスタムトークンナイザとそれに対応するカーソルを作成して､元々用意されてるsqlite3_tokenizer_moduleにカスタムロジックを書いた関数を詰め込んでそいつらを呼び出して貰う感じ*8｡

と言うわけで､日本語相手にする場合はどーしなきゃならないかというと､自分でTokenizerを作る必要がある｡

ちょっと補足

日本語を相手にする場合､このあたりがぢつはかなりしんどいことになる｡なぜなら､句読点区切りじゃトークンとして大きすぎるし､さりとて1文字単位なら細かすぎて何から何まで条件に合致してしまう｡理想としては文節単位あたりが粒度的にも最適なんだろうけど､なにせ表音文字しかない言語じゃないから単語単位でスペースが入るなんてことはくなり､文字通り､機械的にシンプルな方法でトークンを生成するのが非常に困難になる｡さらに言うなら､漢字と仮名なんていう全く文字の意味として異なってる文字連中が混在してやってくるわけだし｡｡｡
で､こいつをどのようにトークンナイズするかというと､､､

形態素解析による分かち書き
1. 実際の処理方法
  1. MeCubやChaSenと言った形態素解析機に通して､文節単位でトークンナイズする｡
2. 利点
  1. 最適なトークンサイズになりやすい
  2. 検索時のノイズが乗りにくい｡
3. 欠点
  1. 完全なトークンナイズは不可能｡
  2. 処理に時間がかかる
  3. ノイズが乗りにくい代わりに､トークンナイズが失敗すると検索結果のすり抜けが発生する｡
n-gram
1. 実際の処理方法
  1. 機械的にn文字切り抜いてそれをトークンとする｡その際オーバーラップさせる*9
2. 利点
  1. 言語*10に依存しないトークンナイズが可能
  2. 処理は比較的速め
  3. 機械的な処理になるので､コーディングも上に比べれば楽｡
  4. 検索のすり抜けがユニコード正規化の話を無しにすれば起こらない
3. 欠点
  1. nを適当な数にしないと､検索時に総当たりになる*11
  2. インデックスサイズの肥大化*12
  3. 検索時にノイズが乗りやすい*13

という感じになる｡

ということで､､､

どのようにして､FTS3にCustomTokenizerをloadさせるかというところあたりをざくりと｡全体的な流れは以下の通り｡

fts3_tokenizer.hにdefineされてる構造体を使ってカスタムロジックをSQLiteが喰えるようにする｡
それを､SQLiteの外部モジュールとしてロードできるようにAPIを作成｡
で､そいつを呼び出して完了｡

と言う流れになるかと｡

カスタムトークンナイザの作り方

は､以下の通り｡(ソースはfts3_tokenizer.hより抜粋)

使用する構造体は以下の通り(とりあえず､今はプロトタイプ宣言のみ)

//ロジックを呼び出すコールバック関数へのポインタが詰まってる構造体｡
typedef struct sqlite3_tokenizer_module sqlite3_tokenizer_module;

//トークンナイザそのものの構造体｡
typedef struct sqlite3_tokenizer sqlite3_tokenizer;

//xNextで使うカーソル(後述)
typedef struct sqlite3_tokenizer_cursor sqlite3_tokenizer_cursor;

sqlite_tokenizer_moduleの詳細｡

コイツは以下のように定義されてる｡でかいので元コメントは一部､削除してます｡

struct sqlite3_tokenizer_module {

//元コメント通り､常に0になってないとまずい｡
  int iVersion;

//テーブルが作成された､Tokenizerが適用されたTableを利用するなどのときに､呼ばれるコールバック｡
  int (*xCreate)(
//いくつ引数を伴ってたかを
    int argc,                           /* Size of argv array */
//実際の引数文字への二次元配列
    const char *const*argv,             /* Tokenizer argument strings */
//作られたトークンナイザを返す｡
    sqlite3_tokenizer **ppTokenizer     /* OUT: Created tokenizer */
  );

//コネクションが切れたときなどに呼ばれるコールバック｡Createと対になる｡
  int (*xDestroy)(sqlite3_tokenizer *pTokenizer);

//トークンナイザに文字列が渡ってきたときに呼ばれるコールバック｡
//ありように言ってしまえば､Select InsertなどFieldに値を入れる/検索するSQLが発行された時一番最初に呼ばれる｡
  int (*xOpen)(
// xCreateで作られたTokenizerへのポインタ
    sqlite3_tokenizer *pTokenizer,       /* Tokenizer object */
//pInput:インプットバッファへのポインタ
//nBytes:バッファサイズ
    const char *pInput, int nBytes,      /* Input buffer */
//後で使う､カーソルへのポインタ(戻し)
    sqlite3_tokenizer_cursor **ppCursor  /* OUT: Created tokenizer cursor */
  );

//処理完了後にカーソルをCleanするために呼ばれるコールバック｡
  int (*xClose)(sqlite3_tokenizer_cursor *pCursor);

//コイツが実処理のロジック部分｡
//トークンを一個ずつ作ってはreturnするので､何回も呼ばれる(イテレーションみたいなもんです)
//戻りのintで終了か､途中かをコールバック元に通知する｡ちなみに戻りはsqlite3.hのSQLITE_OKが途中､SQLITE_DONEで終了
//で､ここでStateHolderとして､Cursorを利用する｡ちなみに､モジュールそのものが状態をもつことは絶対禁止｡
  int (*xNext)(

//カーソルへのポインタ
    sqlite3_tokenizer_cursor *pCursor,   /* Tokenizer cursor */
//ppToken:作成したトークンを詰める
//pnBytes:トークンのサイズを詰める
    const char **ppToken, int *pnBytes,  /* OUT: Normalized text for token */
//もと文字列の何バイト目から始まってるかを詰める｡
    int *piStartOffset,  /* OUT: Byte offset of token in input buffer */
//何バイト目までなのかを詰める｡
    int *piEndOffset,    /* OUT: Byte offset of end of token in input buffer */
//何個目のトークンなのかを詰める｡
    int *piPosition      /* OUT: Number of tokens returned before this one */
  );
};

sqlite_tokenizerの詳細

定義は以下｡

struct sqlite3_tokenizer {
  const sqlite3_tokenizer_module *pModule;  /* The module for this tokenizer */
  /* Tokenizer implementations will typically add additional fields */
};

モジュール比すればどえらくシンプル｡
オブジェクト指向的にいうと､これをベースとして､継承してカスタムトークンナイザを作る感じなんだけど､そこはいかんせんCなので､ちょっとトリッキーになる｡どー言うことかというと､以下みたいに書く｡

typedef struct MyTokenizer
{
	sqlite_tokenizer base;
	MyCustomstructure *Data;
} MyTokenizer;

このように書く｡で､モジュール中のxCreateの引数に､ベースへのポインタを渡してやると､後々そいつをキャストして自分のトークンナイザを呼べる｡何で呼べるかを書いてしまうと､メモリレイアウトの話からはじめにゃならんので割愛｡

sqlite_tokenizer_cursorの詳細

コイツもえらくシンプルな定義｡

struct sqlite3_tokenizer_cursor {
  sqlite3_tokenizer *pTokenizer;       /* Tokenizer for this cursor. */
  /* Tokenizer implementations will typically add additional fields */
};

で､sqlite3_tokenizerと同じような方法でカスタムカーソルを作成することが出来る｡

ということで､きょうのまとめ

最後に今日のまとめと落ち穂拾いを｡｡｡
雑感から言うと､元々がC#なひとなので､カーソルやトークンナイザのカスタム版作成どう作成するかで､えらくけつまずいた｡OO的には継承してごにょるわけなので｡
ちなみに､なんでモジュール自体が状態を持ってはいけないかというと､マルチスレッドで上位層が走ってると､Openが二回連続で呼ばれてしまうことがあるからだとおもう｡*14

ということで､次回はどのようにしてsqliteにロードさせるのか当たりを｡｡｡

ちなみに､あたしが後で思い出せればいいやて感じで書いてますので､もし何かあればお気軽にコメントを｡｡｡自分が理解出来てる範囲なら出来る限りお答えする所存｡

*1:現実逃避とも言う orz

*2:Tokenを作るからTokenizerてわけかな?

*3:これがIndexされる

*4:非常に狭義な意味で｡

*5:Windows版のShellプログラムは対応している

*6:あくまでこれは一例｡詳細はここらへんを見て下さい｡

*7:SQLITE_EXTENSION_INIT1とSQLITE_EXTENSION_INIT2のあたり

*8:データとロジックが別々の構造体で管理されてるイメージ｡先の継承とは､元の構造体を最上位にメンバとして持つ構造体を作って実現してる

*9:出現位置との兼ね合いでオーバーラップさせなくても良い方法もあるけど

*10:処理言語じゃなくて自然言語ね

*11:例えばn=3にして､二文字しか検索対象としない場合､データがないので総当たりになる

*12:オーバーラップさせる必要があるため

*13:n=2として､例えば東京都と入れてあった場合､京都でヒットしてしまう

*14:状態を持ってはいけないからこそ､Cursorという概念があるのはりかいできてるけど､これは完全な推測