Text
Page: 1
Groongaの可変型 Ngramトークナイザー について Naoya Murakami Groonga "Tokenizer" Talks 2015/3/20 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 2
自⼰紹介 ✓ Naoya Murakami ✓ 1⽉から知財のWeb系のスタートアッ プに転職 ✓ 東京に引っ越しました! ✓ その前は数年ほど関⻄の特許事務所勤務 ✓ 仕事でプログラミングするのは初めて twitter: @naoa̲y blog: http://blog.createfield.com Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 3
Groongaの おかげで転 職ができま した Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 4
✓ グローバルな知的財産権の流通市場プ ラットフォーム https://www.ipnexus.com ✓ IPの専門家と顧客とを繋げるサービス ✓ 個⼈発明家やスタートアップでも知財 を有効活用できるように ✓ まだ事業を⽴ち上げている段階 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 5
最近やっていること ✓ Railsとかその辺が多い 仕事ではまだGroongaを使っていない ✓ 圧倒的に⼈材不⾜ ✓ 事業内容や開発に興味がある⽅は気 軽に声をかけてください ✓ 個⼈的には検索技術やデータマイニン グとかに興味がある Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 6
個⼈でやっていたこと ✓ 特許の全⽂検索サービス http://patentfield.com ✓ 特許検索では内容を絞り込むための分類体系がた くさんある IPC, FI, FTERM, UC, CPC ... ✓ 特許⽂献では固有名詞はほとんど使われずあまり 特徴的なワードを取ることはできない パソコン⇒情報処理装置, バイオリン⇒弦楽器 etc ✓ 検索してすぐにそれっぽいものが⾒つかるよりも 検索漏れ防⽌のが重要 ⇒Ngramのトークナイザーが使いたい Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 7
個⼈でやっていたこと ✓ ⼀番大きな⽇本語のデータベースで ✓ 数百GiB超(カラム非圧縮時) ✓ ⼀千万レコード超 ✓ Ngramトークナイザーは検索漏れに 強いが ⼀般的に 速度DOWN サイズUP ⇒Ngramのトークナイザーを⾼速化 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 8
改良型Ngramトークナイザー ✓ YaNgram - Yet another Ngram tokenizer plugin https://github.com/naoa/groonga-tokenizer- yangram ✓ 検索時のオーバラップスキップ ✓ 静的な頻度情報に応じた可変Ngram (Vgram) ✓ 既知フレーズのグループ化 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 9
Groongaの全⽂検索の流れ Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 10
キー探索 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 11
キー探索 ✓ ハッシュ表やパトリシアトライなどを 使って語彙表のキーとして登録された トークンを探す ✓ いわゆる辞書引き・KVS ✓ Groongaではインデックス≠キー ✓ キー探索は非常に速くμsecオーダー Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 12
キーの種類数が増える要因 ✓ ⽂字の種類数が多いこと 組み合わせが増えるためキーの種類数は多くなる ✓ ⽇本語の⽂字の種類は多い ひらがなカタカナ50種 漢字いっぱい ✓ 英語の⽂字の種類は非常に少ない アルファベット26種 ✓ ⽂字数が多いこと 組み合わせが増えるためキーの種類数は多くなる ✓ NgramはNが大きいほどキーの種類数が多い Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 13
キーの種類数増によるキー探索速度への影響 パトリシアトライ(ADD後⇒GET) キー種類数 1万 1千万 Groongaの可変型Ngramトークナイザーについて キー1件取得秒数 21 μsec 37 μsec Powered by Rabbit 2.1.6
Page: 14
キーの種類数増によるキー探索速度への影響 ✓ キー探索はキーの種類が増えても線形 的に時間が増えない 例：ハッシュ表O(1)、パトリシアトライO(k) ✓ キー種類増による検索速度への影響は 非常に軽微 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 15
ポスティング探索 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 16
ポスティング探索 ✓ キー探索によって取得したポスティン グリスト中のトークンの出現位置と検 索クエリのトークンの出現位置の並び が⼀致するかどうかを⽐較 ✓ トークンの出現頻度が増えるとポステ ィングリストが⻑くなる ✓ ⼀番時間がかかるところ シーケンシャルサーチを除く Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 17
トークンの出現頻度が増える要因 ✓ キーの種類数が少ないほどトークン1 個あたりの出現頻度は大きくなる ✓ Unigramや英語の⽂章をBigramでトークナイ ズするとトークン1個あたりの出現頻度は非常 に大きい ✓ 「の、が、は」などの助詞は１⽂書中 にたくさん出現する Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 18
頻出トークンのポスティング探索速度への影 響 ✓ トークンの出現頻度の増加に応じて検 索時間が伸びる できるだけ⾶ばせるところはとばしているが、規模が大 きくなってくるとほぼ線形に検索速度に影響してくる ✓ 大抵の場合、ポスティングリストの 探索でCPUがボトルネック ✓ ⽂書数/サイズに応じて頻出トークン のポスティングリストが⻑くなる ✓ クエリ間の検索速度の差が広がる Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 19
Bigramトークナイザーの検索速度例 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 20
検索速度を⾼速に保つために重要なこと ✓ キーの種類数よりもポスティングリス トが⻑くなりすぎないようにする ✓ CPUクロック数を上げる ✓ なお、最新のGroongaでは頻出トークンとレアトークン の組み合わせ時に⼀部の探索をスキップする⾼速化処理 が組み込まれているが、このスライドの実験結果には反 映されていない http://sourceforge.jp/projects/groonga/lists/ archive/dev/2015-February/003097.html Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 21
Groongaのトークナイザー Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 22
Ngramトークナイザー ✓ 所定の⻑さのユニットサイズで1⽂字 ずつずらす 1:Unigram 2:Bigram 3:Trigram ✓ 「今⽇は⾬だ」 ⇒ 「今⽇/⽇は/は⾬/⾬だ/だ」 ✓ Groongaでは1⽂字でも検索できるよ うに末尾1⽂字も含まれる 検索時は末尾1⽂字は含まれない Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 23
Ngramトークナイザー ✓ デフォルトではアルファベット、記 号、数字はグループ化 ✓ 検索ノイズ低減、検索速度向上のため ✓ アルファベット、記号、数字も Ngramにしたいのであれば、 TokenBigramSplit系を使う Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 24
Ngramトークナイザーのメリット ✓ 原則 漏れのない検索が可能 ✓ 辞書のメンテナンスコスト不要 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 25
Ngramトークナイザーのデメリット ✓ 1⽂字ずつずらすためトークンの総数 が多くなり転置索引のサイズが大きく なる 転置索引のサイズはほぼトークンの総数によって決まる ✓ 検索ノイズが含まれることがある 例：東京都に対して京都でヒットする ✓ トークンの⽐較回数が多く形態素解析 よりも検索速度が遅くなることがある Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 26
形態素解析トークナイザー ✓ 形態素解析器を使って⽂脈に応じて単 語単位に分かち書き TokenMecab ✓ 分割ルールは学習モデルと辞書によ る Unidicであれば短く分かち書き ✓ 例：「今⽇は⾬だ」⇒「今⽇/は/⾬/だ」 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 27
形態素解析トークナイザーのメリット ✓ 検索ノイズの低減 例：東京都に対して京都がヒットしない ✓ 単語ごとにずらせるため転置索引のサ イズがコンパクト 形態素解析の場合「転置索引」⇒「転置索引」1つ Bigramの場合「転置索引」⇒「転置/置索/索引/引」4つ ✓ おおむね検索が⾼速 基本的に⽐較するトークンの数がNgramよりも少ない Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 28
形態素解析トークナイザーのデメリット ✓ 検索漏れ有 ✓ 辞書の追加やモデルの再学習などメンテナンスコ スト大 ✓ 検索クエリと⽂章中では⽂脈が異なり分割ルール が異なることがまれによくある チューニングが大変。検索クエリでは左の⽂脈がない ✓ クエリによって検索速度にムラがでやすい 形態素解析では1⽂字トークンもあり出現頻度の最大値が Ngramよりもかなり大きくなりやすい ⇒ストップワードが重要 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 29
Bigramトークナイザーの出現頻度例 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 30
形態素解析トークナイザーの出現頻度例 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 31
Ngramトークナイザーの⾼速化1 検索時のオーバーラップスキップ ✓ Ngramの⽂書追加時は1⽂字ずらしで すべてのポジションのキーを登録 ✓ 検索時も1⽂字ずらしでキー探索、ポ スティングリスト⽐較 ✓ 例：「今⽇は⾬だ」 ⇒ 「今⽇/⽇は/は⾬/⾬だ」 ✓ トークンの⽐較回数が多い ✓ 検索速度が劣化 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 32
Ngramトークナイザーの⾼速化1 検索時のオーバーラップスキップ ✓ Ngramの⽂書追加時は1⽂字ずらしで すべてのポジションのキーを登録 ✓ 検索時も1⽂字ずらしでキー探索、ポ スティングリスト⽐較 ✓ 例：「今⽇は⾬だ」 ⇒ 「今⽇/⽇は/は⾬/⾬だ」 ✓ トークンの⽐較回数が多い ✓ 検索速度が劣化 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 33
Ngramトークナイザーの⾼速化1 検索時のオーバーラップスキップ ✓ 検索時は開始位置が決まっているので 1⽂字ずらしする必要はない ✓ 原則:オーバラップ部分をスキップ 従来:「今⽇は⾬」⇒「今⽇/⽇は/は⾬」 改良:「今⽇は⾬」⇒「今⽇/ /は⾬」 ✓ トークンの⽐較回数が3回から2回に 減る ✓ ⾼速化 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 34
Ngramトークナイザーの⾼速化1 検索時のオーバーラップスキップ ✓ 例外:末尾や字種境界で短くなるとこ ろは1つ⼿前の⻑い⽅を採用する ✓ 短いやつはポスティングリストが⻑く検索が 遅い 「今⽇は⾬だ」⇒「今⽇/ 「今⽇は⾬だ」⇒「今⽇/ Groongaの可変型Ngramトークナイザーについて /は⾬/ /だ」 × /は⾬/⾬だ」 ○ Powered by Rabbit 2.1.6
Page: 35
Ngramトークナイザーの⾼速化1 検索時のオーバーラップスキップ ✓ これを追加実装したのが以下のトークナイザー ✓ TokenYaBigram ✓ TokenYaTrigram Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 36
TokenBigram/TokenYaBigram の速度⽐較 Wikipedia(ja)で1000回検索 トークナイザー 検索秒数平均 TokenBigram 0.0508 sec TokenYaBigram 0.0325 sec ※5⽂字以上の⽇本語のみのカテゴリ Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 37
TokenTrigram/TokenYaTrigram の速度⽐較 Wikipedia(ja)で1000回検索 トークナイザー TokenTrigram TokenYaTrigram Groongaの可変型Ngramトークナイザーについて 検索秒数平均 0.0146 sec 0.0063 sec Powered by Rabbit 2.1.6
Page: 38
TokenYaBigram/TokenYaTrigram の速度⽐較 ✓ YaBigramはBigramに⽐べ1.5倍ほど 速い ✓ YaTrigramはTrigramに⽐べ2倍ほど 速い ✓ オーバーラップ部分を⾶ばせる量が増える Bigram「今⽇は⾬だな」⇒「今⽇/ /は⾬/ /だな」3 Trigram「今⽇は⾬だな」⇒「今⽇は/ / /⾬だな」2 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 39
Ngramトークナイザーの⾼速化2 静的な頻度情報に応じた可変Ngram (Vgram) ✓ 原則、Nのサイズが大きくほどトーク ンの種類が増えてトークン１つあたり のポスティングリストは短くなる ✓ BigramをTrigramにすれば3⽂字以上 の検索で速くなる ✓ 2⽂字以下で検索する場合は速くはならない Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 40
Bigramトークナイザーの検索速度例 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 41
Trigramトークナイザーの検索速度例 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 42
TokenTrigramのデメリット ✓ TokenTrigramはTokenBigramに⽐ べキー数とキーサイズが増大 ✓ メモリ使用量が増大 ✓ キーサイズは⼩さいほうが望ましい Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 43
TokenBigram/TokenTrigramのキー Wikipedia(ja) トークナイザー TokenBigram TokenTrigram Groongaの可変型Ngramトークナイザーについて キーの数 5767474 28691883 キーサイズ 136.047MiB 684.047MiB Powered by Rabbit 2.1.6
Page: 44
Bigramトークナイザーの出現頻度例 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 45
Ngramトークナイザーの⾼速化2 静的な頻度情報に応じた可変Ngram (Vgram) ✓ トークンの出現頻度はNgramといえ 大きく偏っている ✓ 大半のトークンは出現頻度が⾼くなく ⼗分な検索速度が得られている ✓ Bigramでの出現頻度が⾼いトークン だけをTrigramにすれば良い Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 46
Ngramトークナイザーの⾼速化2 静的な頻度情報に応じた可変Ngram (Vgram) ✓ これを追加実装したのが以下のトークナイザー ✓ TokenYaVgram ✓ TokenYaVgramBoth ✓ TokenYaVgramQuad Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 47
TokenYaVgram ✓ 原則:管理テーブルのキーと⼀致するBigramトー クンのみを後ろに伸ばしてTrigramにする ✓ 「処理」を登録 「画像処理装置」をトークナイズ ✓ 「画像/像処/処理装/理装/装置/置」 ✓ 「処理装」が出現する頻度は「処理」よりも低い ✓ ⾼速化 ✓ 検索時は上記と同様にオーバラップを⾶ばす Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 48
TokenYaVgram ✓ 管理テーブルに出現頻度の⾼いBigramトークン のみを登録しておく ✓ あらかじめ、ある程度の⽂章量が必要 ✓ 同分野であれば頻出トークンの傾向はほぼ同じ ✓ 通常のBigramトークナイザーでインデックスを構築 しAPIを使えばBigramの出現頻度を取得できる ✓ Rroonga: https://gist.github.com/naoa/ fac2cff05fa9113bf5d6 ✓ C-API: https://gist.github.com/ naoa/8d862028e23e45e23304 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 49
TokenYaVgram ✓ 例外:検索クエリの末尾ではTrigram対象の Bigramトークンであっても後ろに伸ばせない ✓ 本⽂中では伸ばされている可能性がある ✓ この場合は強制的に前⽅⼀致検索させる ✓ vgram対象でも2⽂字で検索が可能 ただしTokenBigramのときより速くはならない ✓ 「処理」を登録 ⽂書登録:「画像処理装置」 検索クエリ:「画像処理」 ✓ ⽂書登録:「画像/像処/処理装/理装/装置/置」 ✓ 検索クエリ:「画像/ /処理*」 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 50
TokenYaVgraの速度 Wikipedia(ja)で1000回検索 トークナイザー TokenBigram TokenYaBigram TokenYaTrigram TokenYaVgram Groongaの可変型Ngramトークナイザーについて 検索秒数平均 0.0444 sec 0.0325 sec 0.0063 sec 0.0166 sec Powered by Rabbit 2.1.6
Page: 51
TokenYaVgramのキー Wikipedia(ja) トークナイザー TokenBigram TokenTrigram TokenYaVgr am Groongaの可変型Ngramトークナイザーについて キーの数 5767474 28691883 7425198 キーサイズ 136.047MiB 684.047MiB 172.047MiB Powered by Rabbit 2.1.6
Page: 52
TokenYaVgramの効果 ✓ キーサイズの増大を抑えつつ、検索の ⾼速化を実現 ✓ TokenYaTrigramほど速くはならな かった ✓ 検索クエリ末尾がVgram対象の場合、2⽂字 トークンで前⽅⼀致探索する必要がある Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 53
TokenYaVgramBoth ✓ 原則:管理テーブルのキーと⼀致するBigramトー クンのみを後ろに伸ばしてTrigramにする ✓ さらに:1つ後ろのBigramトークンが管理テーブ ルのキーと⼀致するトークンも後ろに伸ばして Trigramにする ✓ 「処理」を登録 ⽂書登録:「画像処理装置」 検索クエリ:「画像処理」 ✓ ⽂書登録:「画像/像処理/処理装/理装/装置/置」 ✓ 検索クエリ:「画像/像処理」 ✓ 「処理」じゃなく「像処理」で探索できる⇒⾼速化 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 54
TokenYaVgramBoth ✓ 例外:検索クエリの末尾では次のトークンがない ため判断できない ✓ 全ての場合で検索クエリ末尾のトークンは強制的 に前⽅⼀致検索させる せざるを得ない ✓ 前⽅⼀致が必要のないケースで前⽅⼀致をし たとしてもあまり影響はない vgram対象でないやつはもとより遅くないという想定 ✓ 「理装」を登録 ⽂書登録:「画像処理装置」 検索クエリ:「画像処理」 ✓ ⽂書登録:「画像/像処/処理装/理装置/装置/置」 ✓ 検索クエリ:「画像/ /処理*」 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 55
TokenYaVgramBotの速度 Wikipedia(ja)で1000回検索 トークナイザー TokenBigram TokenYaBigram TokenYaTrigram TokenYaVgram TokenYaVgramBoth Groongaの可変型Ngramトークナイザーについて 検索秒数平均 0.0444 sec 0.0325 sec 0.0063 sec 0.0166 sec 0.0065 sec Powered by Rabbit 2.1.6
Page: 56
TokenYaVgramBothのキー Wikipedia(ja) トークナイザー TokenBigram TokenTrigram TokenYaVgra m TokenYaVgr amBoth Groongaの可変型Ngramトークナイザーについて キーの数 5767474 28691883 7425198 キーサイズ 136.047MiB 684.047MiB 172.047MiB 8560779 200.047MiB Powered by Rabbit 2.1.6
Page: 57
TokenYaVgramBothの効果 ✓ 出現頻度が⾼いもののみTrigramにす ることでキーサイズの増大を抑えつ つ、検索速度の⾼速化を実現 ✓ TokenYaTrigram並の検索速度なが らもキーサイズをTokenTrigramの 1/3以下に抑えられた Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 58
TokenYaVgramQuad ✓ 3⽂字にしてもまだ速度が満⾜いかな かったケースがあったのでつくってみ た ✓ 管理テーブルに3⽂字のキーを登録し ておくと、その対象のみを4⽂字トー クンにする ✓ 現在はこのトークナイザーを適用中 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 59
既知フレーズのグループ化 ✓ あらかじめ既知のフレーズを管理テーブルに登録 しておき、そのフレーズのみをグループ化してト ークナイズ ✓ パトリシアトライのLCPサーチを利用して⾼ 速にフレーズ抽出 ✓ 「１２⽉は寒い」で「１２⽉」を登録 ✓ 「１２⽉／は寒／寒い」 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 60
既知フレーズのグループ化の効果 ✓ 検索ノイズの低減 ✓ ⾒出しタグや頻出語を含む複合語を登 録することにより頻出トークン数低減 ✓ ⾼速化 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 61
まとめ ✓ 検索速度を⾼速に保つのためにはポスティングリ ストが⻑くなりすぎないようにする ✓ Ngram検索時はオーバラップさせなくても良い ✓ Ngramといえどトークンの出現頻度は偏る ✓ 検索速度に影響のある頻出トークンのみを選択的 に伸ばすVgramトークナイザーを作った Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 62
今後の課題 ✓ Vgramは検索クエリが3⽂字以上のときは⾼速化 できるが2⽂字以下の場合の⾼速化にはならない 前⽅⼀致検索しないといけないのでむしろ少し遅くなる ✓ 前処理でいらないフレーズ除去、⼀部フレーズ化 やストップワードという対応⽅法もあるがどれも 制約が発⽣ ✓ 1⽂字、2⽂字があまり遅くならないように特化 したインデックスを別につくり検索クエリに応じ てそちらのインデックスを使うようにできないか と検討中 ✓ 形態素解析をスコアリングに特化した形で Vgramとハイブリッドで使えないか検討中 Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
Page: 63
TokenBigramと TokenYaVgramQuad の速度差デモ (時間があれば) Groongaの可変型Ngramトークナイザーについて Powered by Rabbit 2.1.6
