Text
Page: 1
Groonga
改良型Ngram
トークナイザー
Naoya (@naoa̲y)
全⽂検索エンジンGroongaを囲む⼣べ5
2014/11/29
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 2
自⼰紹介
✓ Naoya (@naoa̲y)
✓ 数年ほど特許事務所勤務
✓ 前は数年ほどユーザSIでインフラSE
✓ Groongaでプログラミングを学ぶ
✓ GroongaのCプラグインなら書ける
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 3
制作物
✓ 特許の全⽂検索サービス
を個⼈で制作 (中)
✓ 専門家以外でも有用な知財情報へ迅
速にアクセスできるように
✓ 権利の死活情報でも絞込みができ
侵害調査やフリーな技術調査が可能
✓ 知財流通促進・フリーな技術流用に
よる産業の発達促進
✓ 今回紹介する改良もフリーな技術情
報をヒントに発想を取り⼊れたもの
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 4
制作物
✓ ⼀番大きな⽇本語のデータベー
スで数百GiB超(カラム非圧縮)
✓ 数百GiB規模のDBを⼩規模で
できるだけ実用的な速度で検索
したい
✓ Ngramトークナイザーを⾼速
化、効率化したプラグイン作成
(したけど時間が⾜りなくてまだ反映できてない)
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 5
改良型Ngramトークナイザ
ー
✓ YaNgram - Yet another
Ngram tokenizer plugin
https://github.com/naoa/groonga-tokenizer-
yangram
✓ 検索時のオーバラップスキップ
✓ 静的な頻度情報に応じた可変
Ngram(Vgram)
✓ 既知フレーズのグループ化
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 6
Groongaの全⽂検索の流れ
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 7
Groongaのトークナイザー
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 8
Ngramトークナイザー
✓ 所定の⻑さのユニットサイズで
1⽂字ずつずらす
1:Unigram 2:Bigram
3:Trigram
✓ 例：「今⽇は⾬だ」⇒
「今⽇/⽇は/は⾬/⾬だ/だ」
✓ Groongaは1⽂字でも検索でき
るように末尾1⽂字も含まれる
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 9
Ngramトークナイザー
✓ デフォルトではアルファベッ
ト、記号、数字はグループ化
✓ 検索ノイズ低減、検索速度向上のた
め
✓ アルファベット、記号、数字も
Ngramにしたいのであれば、
TokenBigramSplit〜系を使う
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 10
Ngramトークナイザーのメ
リット
✓ 漏れのない検索が可能
✓ 新語、造語に対応
特許⽂献の場合、権利解釈の範囲を狭めないように固有
名詞があまり使われず商標も使えないので造語だらけ
✓ メンテナンスコスト不要
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 11
Ngramトークナイザーのデ
メリット
✓ 1⽂字ずつずらすためトークン
の総数が多くなり転置索引のサ
イズが大きくなる
転置索引のサイズはほぼトークンの総数によって決まる
✓ 検索ノイズが含まれることがあ
る 例：東京都に対して京都でヒットする
✓ ⽇本語の場合、あまり大きな影
響ではない 要件による
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 12
形態素解析トークナイザー
✓ 形態素解析器を使って⽂脈に応
じて単語単位に分かち書き
TokenMecab
✓ 分割ルールは学習モデルと辞書
による Unidicであれば短く分かち書き
✓ 例：「今⽇は⾬だ」⇒
「今⽇/は/⾬/だ」
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 13
形態素解析トークナイザーの
メリット
✓ 検索ノイズの低減
例：東京都に対して京都がヒットしない
✓ 単語ごとにずらせるため転置索
引のサイズがコンパクト
形態素解析の場合「転置索引」⇒「転置索引」1つ
Bigramの場合「転置索引」⇒「転置/置索/索引/引」4つ
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 14
形態素解析トークナイザーの
デメリット
✓ 検索漏れ有
✓ 辞書の追加やモデルの再学習な
どメンテナンスコスト大
✓ 検索クエリと⽂章中では⽂脈が
異なり分割ルールが異なること
がまれによくある チューニングが大変
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 15
キー探索
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 16
キー探索
✓ ハッシュ表やパトリシアトライ
などを使って語彙表のキーとし
て登録されたトークンを探す
✓ いわゆる辞書引き・KVS
✓ Groongaではインデックス≠キ
ー
✓ キー探索は非常に速くμsecオ
ーダー KVSが速いのは知っているはず
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 17
キーの種類数が増える要因
✓ ⽂字の種類数が多いこと
組み合わせが増えるためキーの種類数は多くなる
✓ ⽇本語の⽂字の種類は多い
ひらがなカタカナ50種 漢字いっぱい
✓ 英語の⽂字の種類は非常に少な
い
アルファベット26種
✓ ⽇本語はキーの種類が多い
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 18
キーの種類数が増える要因
✓ ⽂字数が多いこと
組み合わせが増えるためキーの種類数は多くなる
✓ NgramのNが大きいほどキー
の種類数が多い
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 19
キーの種類数増によるキー探
索速度への影響
パトリシアトライ(ADD後⇒GET)
キー種類数
キー1件取得秒数
1万
21 μsec
1千万
37 μsec
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 20
キーの種類数増によるキー探
索速度への影響
✓ キー探索はキーの種類が増えて
も線形的に時間が増えない
例：ハッシュ表O(1)、パトリシアトライO(k)
✓ キー種類増の検索速度への影響
は非常に軽微
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 21
ポスティング探索
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 22
ポスティング探索
✓ キー探索によって取得したポス
ティングリスト中のトークンの
出現位置と検索クエリのトーク
ンの出現位置の相対的な並びが
⼀致するかどうかを⽐較
✓ トークンの出現頻度が増えると
ポスティングリストが⻑くなる
✓ ⼀番時間がかかるところ
シーケンシャルサーチを除く
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 23
トークンの出現頻度が増える
要因
✓ ⽂字の種類数が少ないほどキー
の種類数は少ない
⇒ トークン1個あたりの出現頻
度は大きい
✓ ⽇本語はキーの種類が多い
⇒トークンの出現頻度が少ない
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 24
トークンの出現頻度が増える
要因
✓ ⽂字数が少ないほどキーの種類
数は少ない
⇒ トークン1個あたりの出現頻
度は大きい
✓ NgramのNが大きいとキーの
種類数が多い
⇒ トークンの出現頻度が少な
い
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 25
Bigramトークナイザーの出
現頻度と検索速度例
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 26
トークンの出現頻度増による
ポスティング探索速度への影
響
✓ ⽂書数/サイズが多くなるとト
ークンの出現頻度が増えポステ
ィングリストが非常に⻑くなる
✓ トークンの出現頻度に応じてほ
ぼ線形的に検索時間が伸びる
✓ 大抵の場合、ポスティングリストの
探索でCPUがボトルネック
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 27
検索速度を⾼速に保つために
重要なこと
✓ キーの種類数よりもポスティン
グリストが⻑くなりすぎないよ
うにする
✓ CPUクロック数を上げる
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 28
形態素解析トークナイザーの
出現頻度例
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 29
形態素解析トークナイザーの
⾼速化
✓ 助詞などの頻出語をストップワ
ードにする
✓ 頻出語を含む複合語を辞書登録
✓ ⾒出しタグ等⽂書に必ず含まれ
るフレーズを除去もしくは辞書
登録
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 30
Ngramトークナイザーの⾼
速化
✓ Nのサイズを大きくする
Bigram ⇒ Trigram
✓ トークンの種類が増えて１つご
とのポスティングリストは短く
なる
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 31
Trigramトークナイザーの
出現頻度と検索速度例
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 32
Bigramトークナイザーの出
現頻度と検索速度例(再褐)
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 33
Ngramトークナイザーの⾼
速化
✓ Trigramにすれば基本的に3⽂
字以上の検索速度が速くなる
✓ ⽇本語は⽂字種も多いため
Trigramであればかなり速い
✓ が、まだ速くする⽅法がある
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 34
Ngramトークナイザーをさ
らに⾼速化するために
✓ Ngramの⽂書追加時は1⽂字ず
らしでキーを登録する必要あ
✓ ⽇本語は⽂章中の単語境界が判断で
きないため
✓ 「今⽇は⾬だ」⇒
「今⽇/⽇は/は⾬/⾬だ/だ」
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 35
Ngramトークナイザーをさ
らに⾼速化するために
✓ 検索時は開始位置が決まってい
るので1⽂字ずらしする必要は
ない
⇒オーバラップ部分をスキップ
✓ 「今⽇は⾬」⇒「今⽇/⽇は/は⾬」
×
✓ 「今⽇は⾬」⇒「今⽇/
○
Groonga改良型Ngramトークナイザー
/は⾬」
Powered by Rabbit 2.1.2
Page: 36
Ngramトークナイザーをさ
らに⾼速化するために
✓ 末尾で短くなるところは短い奴
を採用するのではなく1つ⼿前
の⻑い⽅を採用する
短いやつはポスティングリストが⻑く検索が遅い
✓ 「今⽇は⾬だ」
⇒「今⽇/
/は⾬/ /だ」×
⇒「今⽇/
/は⾬/⾬だ」○
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 37
Ngramトークナイザーをさ
らに⾼速化するために
✓ これを追加実装したのが以下の
トークナイザー
TokenYaBigram
TokenYaTrigram
~SplitSymbolAlphaもあり
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 38
TokenBigram/
TokenYaBigramの速度
Wikipedia(ja)で1000回検索
トークナイザー 検索秒数平均
TokenBigram
0.0508sec
TokenYaBigra
0.0325sec
m
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 39
TokenTrigram/
TokenYaTrigramの速度
Wikipedia(ja)で1000回検索
トークナイザー 検索秒数平均
TokenTrigram
0.0146sec
TokenYaTrigr
0.0063sec
am
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 40
TokenYaBigram/
TokenYaTrigramの速度
✓ YaBigramはBigramに⽐べ1.5
倍ほど速い
✓ YaTrigramはTrigramに対し
て2倍ほど速い
✓ NgramのNのサイズが大きい
ほどオーバーラップを⾶ばす量
が大きくなるためより速くなる
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 41
TokenBigram/
TokenTrigramのキー
Wikipedia(ja)
トークナイ キーの数 キーサイズ
ザー
TokenBi
576747 136.047
gram
4
MiB
TokenTri
286918 684.047
gram
83
MiB
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 42
TokenTrigramのデメリッ
ト
✓ TokenTrigramは
TokenBigramに⽐べキー数と
キーサイズが増大
✓ メモリ使用量が増大
✓ キーサイズは⼩さいほうが望ましい
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 43
Bigramトークナイザーの出
現頻度と検索速度例(再褐)
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 44
Ngramトークナイザーを効
率化するために
✓ トークンの出現頻度は大きく偏
っている
✓ 大半のトークンは出現頻度が⾼
くなく⼗分な検索速度が得られ
ている
✓ Bigramの出現頻度が⾼い部分
さえTrigramにできれば良い
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 45
Ngramトークナイザーを効
率化するために
✓ これを追加実装したのが以下の
トークナイザー
✓ TokenYaVgram
TokenYaVgramBoth
~SplitSymbolAlphaもあり
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 46
TokenYaVgram
✓ 管理テーブルのキーと⼀致する
Bigramトークンのみを後ろに
伸ばしてTrigramにする
✓ 管理テーブルにあらかじめ出現
頻度に応じたBigramトークン
を登録しておく
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 47
TokenYaVgram
✓ 「画像処理装置」で「処理」を
管理テーブルに登録
✓ 「画像/増処/処理装/理装/装
置/置」
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 48
TokenYaVgram
✓ 検索クエリの末尾では、
Trigram対象のBigramトーク
ンであっても後ろに伸ばせない
✓ この場合は強制的に前⽅⼀致検
索させる
✓ 「画像処理」で「処理」を登録
⇒「画像/
/処理*」
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 49
TokenYaVgram/
TokenBigramの速度
Wikipedia(ja)で1000回検索
トークナイザー 検索秒数平均
TokenBigram
0.0444 sec
TokenYaVgra
0.0166 sec
m
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 50
TokenYaVgram/
TokenBigramのキー
Wikipedia(ja)
トークナイ キーの数 キーサイズ
ザー
TokenBi
576747 136.047
gram
4
MiB
TokenYa
742519 172.047
Vgram
8
MiB
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 51
TokenYaVgramの効果
✓ キーサイズの増大を抑えつつ、
検索速度の⾼速化を実現
✓ しかし、検索クエリ末尾のもの
は後ろに伸ばすことができない
✓ 「画像処理装置」で「装置」を
登録
⇒「画像/増処/処理/理装/装
置/置」
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 52
TokenYaVgramBoth
✓ 管理テーブルのキーと⼀致する
Bigramトークンのみを後ろに
伸ばしてTrigramにする
✓ 1つ後ろのBigramトークンが
管理テーブルのキーと⼀致する
トークンも後ろに伸ばして
Trigramにする
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 53
TokenYaVgramBoth
✓ 管理テーブルにはあらかじめ出
現頻度に応じたBigramトーク
ンを登録
✓ 「画像処理装置」で「処理」を
登録
⇒「画像/増処理/処理装/理装/
装置/置」
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 54
TokenYaVgramBoth
✓ この場合、検索クエリでは伸ば
せないケースが非常に多く発⽣
する
✓ 全ての場合で強制的に前⽅⼀致
検索させる を得ない
✓ 「画像処」で「処理」を登録
⇒「画像/増処*」
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 55
TokenYaVgramBoth/
TokenBigramの速度
Wikipedia(ja)で1000回検索
トークナイザー 検索秒数平均
TokenBigram
0.0444 sec
TokenYaVgra
0.0065 sec
mBoth
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 56
TokenYaVgramBoth/
TokenBigramのキー
Wikipedia(ja)
トークナイ キーの数 キーサイズ
ザー
TokenBi
576747 136.047
gram
4
MiB
TokenYa
856077 200.047
VgramB
9
MiB
oth
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 57
TokenYaVgramBothの効
果
✓ 出現頻度が⾼いもののみ
Trigramにすることでキーサイ
ズの増大を抑えつつ、検索速度
の⾼速化を実現
✓ TokenYaTrigram並の検索速
度ながらもキーサイズを
TokenTrigramの1/3以下に抑
えられた
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 58
既知フレーズのグループ化
✓ あらかじめ既知のフレーズを管
理テーブルに登録
✓ そのフレーズのみグループ化し
てトークナイズ
✓ パトリシアトライのLCPサーチを利
用して⾼速にフレーズ抽出
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 59
既知フレーズのグループ化
✓ 「１２⽉は寒い」で「１２⽉」
を登録
⇒「１２⽉／は寒／寒い」
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 60
既知フレーズのグループ化の
効果
✓ 検索ノイズの低減
✓ ⾒出しタグや頻出語を含む複合
語などを登録することにより頻
出トークン数を低減
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 61
まとめ
✓ 検索速度を⾼速に保つのために
はポスティングリストが⻑くな
りすぎないようにする
✓ Ngramの検索時はオーバラッ
プさせなくても良い
✓ トークンの出現頻度は偏る
✓ これらの特性から検索を⾼速
化、効率化するためにNgram
トークナイザーを改良
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 62
おまけ その他のプラグイン
✓ groonga-token-filter-yatof
https://github.com/naoa/groonga-token-filter-yatof
✓ 適当なトークンフィルター集
✓ LengthとかSymbolとかSynonym
とか
✓ 使おうとしている
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 63
おまけ その他のプラグイン
✓ groonga-command-token-
count
https://github.com/naoa/groonga-command-token-
count
✓ ポスティングリストをたどってトー
クン数を数える
✓ 別にコマンドプラグインである必要
はなかった
✓ 使っている
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 64
おまけ その他のプラグイン
✓ groonga-function-
snippet̲tritonn
https://github.com/naoa/groonga-function-
snippet̲tritonn
✓ フルスペックスニペット関数
Mroonga(Tritonn) Like
✓ 地獄のシンタックス
✓ 使っている
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 65
おまけ その他のプラグイン
✓ groonga-tokenizer-
tinysegmenter
https://github.com/naoa/groonga-tokenizer-
tinysegmenter
✓ TinySegmenterを使った形態素解
析トークナイザー 態素解析用の辞
書を持たないのでコンパクト
✓ 学習ツール公開している⼈がいるの
でそれ使えば簡単に学習できる
✓ 使っていない
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 66
おまけ その他のプラグイン
✓ groonga-tokenizer-yadelimit
https://github.com/naoa/groonga-tokenizer-
yadelimit
✓ TokenDelimitのバリエーション
✓ 使おうとしている
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 67
おまけ その他のプラグイン
✓ groonga-function-regex
https://github.com/naoa/groonga-function-regex
✓ RE2ライブラリを使って正規表現で
outputを整形
✓ Onigumoバンドルされたからそれ
使えばいい気がする
✓ 使っていない
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 68
おまけ その他のプラグイン
✓ groonga-normalizer-
yamysql
https://github.com/naoa/groonga-normalizer-
yamysql
✓ ハイフンとか漢字の異体字とかヴァ
とかを正規化
✓ フレーズ除去とか
✓ 盛大にバグっている なおったら使
う予定
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 69
おまけ その他のプラグイン
✓ groonga-column-hole
https://github.com/naoa/groonga-column-hole
✓ カラムにデータをいれたらデータが
消えるかも
✓ 転置索引はつくられる
✓ hook apiがあることを知ったので試
しただけ使っていない
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
Page: 70
おまけ その他のプラグイン
✓ groonga-word2vec
https://github.com/naoa/groonga-word2vec
✓ コピペしただけGroongaのプラグ
インである意味はない
✓ 自動的にクエリ展開とかあるかも
✓ 使っていない
Groonga改良型Ngramトークナイザー
Powered by Rabbit 2.1.2
