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