検索の仕組みを知ってみよう~入門編~

Transcript

1. 検索の仕組みを知ってみよう
   ～入門編～
   2020
   

   View Slide

2. 自己紹介
   名前： yuki
   (twitter: @yuki_pnn)
   しがないエンジニア
   趣味：
   　たまに同人漫画のシナリオ書き
   　バドミントン
   

   View Slide

3. 検索使ってますか？
   

   View Slide

4. ブログ記事の一覧から
   「特定の単語」が含まれているものを検索したい
   SNSで過去の投稿一覧から
   「特定の単語」が含まれている投稿を検索したい
   例えば…
   などなど
   

   View Slide

5. 検索ってどう実装されているか知っていますか？
   

   View Slide

6. 注意点
   ・ここから先の話は説明のために簡略化をしています
   ・知っている人は生暖かく見守っていてください
   ・間違った説明をしているかもしれません
   　何か指摘があれば登壇終了後に指摘をお願いします💦
   

   View Slide

7. 検索ってどんなロジックで動いているの？
   知りたいですよね…？
   というわけで検索のアルゴリズムやデータ構造のお話です
   全文検索のお話をします
   

   View Slide

8. 検索でよく使うOSS
   elasticsearch
   　・多分検索エンジンの中で一番有名
   　・いろんなところで使われている
   　・分散型の検索エンジンで大規模サービスにも耐えれる
   solrなんかも検索エンジンとして有名
   

   View Slide

9. 実はコア部分に同じOSSが使われています
   「Apache Lucene」(アパッチ　ルシーン)
   　・OSSの全文検索エンジン/ライブラリ(Java)
   　・検索に必要な機能が色々詰まっているやつ
   　・大体これを使って検索エンジン/サーバを実装している
   Apache Projectの守備範囲広い…
   

   View Slide

10. 今日は以下の機能について話していきます
    ・全文検索を支えるデータ構造
    ・全文検索でのスコアリング方法
    ・「もしかして○○？」のサジェストを実現するには？
    

    View Slide

11. シンプルな検索を考えてみる
    クエリ：「晴れ」
    文書1：「今日の天気は雨」
    文書2：「明日の天気は晴れ」
    文書3：「明後日の天気は曇り」
    これくらいなら文書全てを総当たりしてもよさそう
    

    View Slide

12. じゃあ文書の数が100万件あった場合は？
    

    View Slide

13. 高速に単語を検索するアルゴリズムを使う？
    いい感じに検索しやすいデータ構造に変える？
    

    View Slide

14. 「明日の天気は晴れ」 「明日」「天気」「晴れ」
    単語分割(形態素解析 + ストップワード除去)
    ①
    全文検索を支えるデータ構造: 転置インデックス
    単語から文書を引けるようにする
    今日　　：文書1
    明日　　：文書2
    明後日　：文書3
    天気　　：文書1, 文書2, 文書3
    晴れ　　：文書2
    曇り　　：文書3
    雨　　　：文書1
    ②
    これで単語から文章を探すのが簡単になる
    

    View Slide

15. 文書は探せるけど表示する順番はどう決めるか？
    いい感じのスコアを決めたい
    

    View Slide

16. 単純に考えると
    長い文章の一部だとあんまり重要じゃなさそう？
    たまに出現する単語だとそこまで嬉しくないかも？
    文章の主題に調べたい単語があれば嬉しいかも
    

    View Slide

17. 計算式
    tf-idf(単語i, 文章j) = tf(単語i, 文章j) ・idf(単語i)
    全文検索でのスコアリング方法: TF-IDF
    特定の文章内の単語がどれくらい重要か示す値
    文章j内での単語iの出現回数
    文章jのすべての単語の出現回数の和
    tf(単語i, 文章j) =
    idf(単語i, 文章j) =
    全ての文章数
    単語iが出現する文章数
    log ( )
    

    View Slide

18. 転置インデックス
    (調べたい対象の文章)
    tf-idf
    Query
    転置インデックス(データ構造)と
    tf-idf(スコアリング)を組み合わせて高速な検索を実現
    実際はtf-idfを拡張したBM25を使ったりクエリをもう少し解析したりする
    

    View Slide

19. 単純な検索はそれっぽくできそうだけど…
    こんな感じでいい感じに近い単語をサジェストしたい
    

    View Slide

20. その前に一つ重要な考え方(技術？)を紹介
    nGram
    bi-gram
    tri-gram 等…
    

    View Slide

21. 例えば「国土交通省」のような単語があった場合
    bi-gram
    「国土」「土交」「交通」「通省」
    tri-gram
    「国土交」「土交通」「交通省」
    のように文字数で分割する
    

    View Slide

22. すごくざっくりな「もしかして検索」の実装方針
    n-gramでクエリを分割する
    転置インデックスに対してn-gramが含まれる単語を検索する
    ヒットした単語とクエリの文字列編集距離を計算しスコアとする
    スコアが最も高い単語を「もしかして？」と表示する
    1.
    2.
    3.
    4.
    他にも細かいところはあるけど大体こんな感じ(なはず)
    

    View Slide

23. 編集距離って？
    単語iを別の単語jに変形するのに必要な最小手順数
    例
    「ハックバー」
    「テックバー」
    編集距離: 2
    「スコップ」
    「コップ」
    編集距離: 1
    Levenshtein Distanceなんかが有名
    実際はjaro-winkler Distanceなんかが使われる
    

    View Slide

24. 普段よく使う検索機能
    実際に中の処理を見てみると奥が深い！
    今回説明をしたのもかなり簡略化したもの…
    

    View Slide

25. 興味があればいろいろと調べてみてください！
    検索だけでなく身近にある機能も仕組みを
    調べると面白いものが多いはず
    

    View Slide

26. まとめ
    ・(全文)検索を実現するために「転置インデックス」なる構造がある
    ・検索のスコアを決めるために「tf-idf(BM25)」などのアルゴリズムがある
    ・n-gramや編集距離を使って「もしかして検索」を実現ｄ
    

    View Slide