Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
検索の仕組みを知ってみよう~入門編~
Search
yuki
January 28, 2023
Technology
0
170
検索の仕組みを知ってみよう~入門編~
yuki
January 28, 2023
Tweet
Share
Other Decks in Technology
See All in Technology
AWS アーキテクチャ作図入門/aws-architecture-diagram-101
ma2shita
29
11k
Amazon Bedrockで実現する 新たな学習体験
kzkmaeda
2
550
AIのAIによるAIのための出力評価と改善
chocoyama
2
550
生成AIで小説を書くためにプロンプトの制約や原則について学ぶ / prompt-engineering-for-ai-fiction
nwiizo
4
1.8k
Observability в PHP без боли. Олег Мифле, тимлид Altenar
lamodatech
0
350
Amazon ECS & AWS Fargate 運用アーキテクチャ2025 / Amazon ECS and AWS Fargate Ops Architecture 2025
iselegant
16
5.6k
Postman AI エージェントビルダー最新情報
nagix
0
110
SalesforceArchitectGroupOsaka#20_CNX'25_Report
atomica7sei
0
170
Agentic Workflowという選択肢を考える
tkikuchi1002
1
510
Oracle Cloud Infrastructure:2025年6月度サービス・アップデート
oracle4engineer
PRO
2
250
ひとり情シスなCTOがLLMと始めるオペレーション最適化 / CTO's LLM-Powered Ops
yamitzky
0
440
Lambda Web Adapterについて自分なりに理解してみた
smt7174
3
110
Featured
See All Featured
What's in a price? How to price your products and services
michaelherold
246
12k
Optimising Largest Contentful Paint
csswizardry
37
3.3k
Optimizing for Happiness
mojombo
379
70k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
35
2.3k
Keith and Marios Guide to Fast Websites
keithpitt
411
22k
For a Future-Friendly Web
brad_frost
179
9.8k
Code Reviewing Like a Champion
maltzj
524
40k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
3.9k
jQuery: Nuts, Bolts and Bling
dougneiner
63
7.8k
Rails Girls Zürich Keynote
gr2m
94
14k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
The Cult of Friendly URLs
andyhume
79
6.5k
Transcript
検索の仕組みを知ってみよう ~入門編~ 2020
自己紹介 名前: yuki (twitter: @yuki_pnn) しがないエンジニア 趣味: たまに同人漫画のシナリオ書き バドミントン
検索使ってますか?
ブログ記事の一覧から 「特定の単語」が含まれているものを検索したい SNSで過去の投稿一覧から 「特定の単語」が含まれている投稿を検索したい 例えば… などなど
検索ってどう実装されているか知っていますか?
注意点 ・ここから先の話は説明のために簡略化をしています ・知っている人は生暖かく見守っていてください ・間違った説明をしているかもしれません 何か指摘があれば登壇終了後に指摘をお願いします💦
検索ってどんなロジックで動いているの? 知りたいですよね…? というわけで検索のアルゴリズムやデータ構造のお話です 全文検索のお話をします
検索でよく使うOSS elasticsearch ・多分検索エンジンの中で一番有名 ・いろんなところで使われている ・分散型の検索エンジンで大規模サービスにも耐えれる solrなんかも検索エンジンとして有名
実はコア部分に同じOSSが使われています 「Apache Lucene」(アパッチ ルシーン) ・OSSの全文検索エンジン/ライブラリ(Java) ・検索に必要な機能が色々詰まっているやつ ・大体これを使って検索エンジン/サーバを実装している Apache Projectの守備範囲広い…
今日は以下の機能について話していきます ・全文検索を支えるデータ構造 ・全文検索でのスコアリング方法 ・「もしかして◦◦?」のサジェストを実現するには?
シンプルな検索を考えてみる クエリ:「晴れ」 文書1:「今日の天気は雨」 文書2:「明日の天気は晴れ」 文書3:「明後日の天気は曇り」 これくらいなら文書全てを総当たりしてもよさそう
じゃあ文書の数が100万件あった場合は?
高速に単語を検索するアルゴリズムを使う? いい感じに検索しやすいデータ構造に変える?
「明日の天気は晴れ」 「明日」「天気」「晴れ」 単語分割(形態素解析 + ストップワード除去) ① 全文検索を支えるデータ構造: 転置インデックス 単語から文書を引けるようにする 今日 :文書1
明日 :文書2 明後日 :文書3 天気 :文書1, 文書2, 文書3 晴れ :文書2 曇り :文書3 雨 :文書1 ② これで単語から文章を探すのが簡単になる
文書は探せるけど表示する順番はどう決めるか? いい感じのスコアを決めたい
単純に考えると 長い文章の一部だとあんまり重要じゃなさそう? たまに出現する単語だとそこまで嬉しくないかも? 文章の主題に調べたい単語があれば嬉しいかも
計算式 tf-idf(単語i, 文章j) = tf(単語i, 文章j) ・idf(単語i) 全文検索でのスコアリング方法: TF-IDF 特定の文章内の単語がどれくらい重要か示す値
文章j内での単語iの出現回数 文章jのすべての単語の出現回数の和 tf(単語i, 文章j) = idf(単語i, 文章j) = 全ての文章数 単語iが出現する文章数 log ( )
転置インデックス (調べたい対象の文章) tf-idf Query 転置インデックス(データ構造)と tf-idf(スコアリング)を組み合わせて高速な検索を実現 実際はtf-idfを拡張したBM25を使ったりクエリをもう少し解析したりする
単純な検索はそれっぽくできそうだけど… こんな感じでいい感じに近い単語をサジェストしたい
その前に一つ重要な考え方(技術?)を紹介 nGram bi-gram tri-gram 等…
例えば「国土交通省」のような単語があった場合 bi-gram 「国土」「土交」「交通」「通省」 tri-gram 「国土交」「土交通」「交通省」 のように文字数で分割する
すごくざっくりな「もしかして検索」の実装方針 n-gramでクエリを分割する 転置インデックスに対してn-gramが含まれる単語を検索する ヒットした単語とクエリの文字列編集距離を計算しスコアとする スコアが最も高い単語を「もしかして?」と表示する 1. 2. 3. 4. 他にも細かいところはあるけど大体こんな感じ(なはず)
編集距離って? 単語iを別の単語jに変形するのに必要な最小手順数 例 「ハックバー」 「テックバー」 編集距離: 2 「スコップ」 「コップ」 編集距離:
1 Levenshtein Distanceなんかが有名 実際はjaro-winkler Distanceなんかが使われる
普段よく使う検索機能 実際に中の処理を見てみると奥が深い! 今回説明をしたのもかなり簡略化したもの…
興味があればいろいろと調べてみてください! 検索だけでなく身近にある機能も仕組みを 調べると面白いものが多いはず
まとめ ・(全文)検索を実現するために「転置インデックス」なる構造がある ・検索のスコアを決めるために「tf-idf(BM25)」などのアルゴリズムがある ・n-gramや編集距離を使って「もしかして検索」を実現d