Share
Embed
Transcript
222 slides
-
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
1. アルゴリズムの設計と解析 検索ってどんな分野? The Art of Computer Programming, Volume 3:
Sorting and Searching • 1968年から刊行 • 全7巻予定 • 2019年現在第4巻まで -
2. 情報検索(Information Retrieval) Introduction to Information Retrieval Modern Information Retrieval
スタンフォード大学の授業 CS 276 Information Retrieval and Web Search の教科書 http://web.stanford.edu/class/cs276/ 検索ってどんな分野? -
Java で実装された 検索ライブラリ 利用 $ grep $ awk $ sed
の index の index 今日のターゲット 検索を実現するアプリケーションは? -
特徴\タイプ 逐次検索 Index 型検索 事前処理 なし(コスト小) あり(コスト大) 検索速度 時間大 時間小
メモリー使用量 メモリー小 メモリー大 典型的な手法 • grep • Knuth–Morris– Pratt 法 • Boyer-Moore 法 • 転置インデックス • N-gramインデックス • 形態素インデックス 2つの検索タイプ ★ 今日のターゲット -
Java で実装された 検索ライブラリ 利用 $ grep $ awk $ sed
の index の index 検索を実現するアプリケーションは? 逐次型 Index 型 -
Java で実装された 検索ライブラリ 利用 $ grep $ awk $ sed
の index の index 検索とは何か? 逐次型 Index 型 -
AND 検索 Index Index 型検索:Search=検索実行 Linux カーネル リリース 1 1
2 2 Linux AND カーネル ∩ Merge 1 2 2 1 -
OR 検索 Index Index 型検索:Search=検索実行 Linux カーネル リリース 1 1
2 2 ∩ Merge 2 1 リリース OR カーネル 1 2 -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
特性 Inverted Index (転置インデックス) 1. ドキュメントに含まれる特性を キー (全文検索などでは Term) にして、集合を紐付ける
(リスト構造=Posting List) 2. ドキュメントのリストをソート済み 3. 通常は単語の現れた位置情報も 格納 (フレーズ検索) Index Linux カーネル リリース 1 1 2 2 -
特性 Inverted Index (転置インデックス) 1. TAAT = Term At A
Time 2. DAAT = Document At A Time Index Linux カーネル リリース 1 1 2 2 -
特性 Inverted Index (転置インデックス) 1. TAAT = Term At A
Time = 一品ずつ食べる = 洋食 2. DAAT = Document At A Time = 全部少しずつ食べる = 和食 -
50,241件 10,320件 520件 30,483件 500,020件 【戦略】Term At A Time(訳:一度にタームを) •
Term (転置インデックスのキー) 毎にリストを取得してマージ • ひとつのキー毎に処理 • 洋食 UNIX BSD mmap kernel Linux ① ② TAAT (Term At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 -
50,241件 10,320件 520件 30,483件 500,020件 【戦略】AND 検索(Linux AND mmap) •
件数の少ないキーから accumulator (マージ用リスト) を作成 • AND 検索の場合、accumulator のサイズは、もっとも件数の少ない リストより大きくなることはない。 UNIX BSD mmap kernel Linux TAAT (Term At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 ① ② -
50,241件 10,320件 520件 30,483件 500,020件 【戦略】AND 検索(Linux AND mmap) 1.
「mmap」のリストから accumulator を作成 = [1, 5, …] 2. 「Linux」のリストを accumulator にマージ 「1」はある?⇒ある!⇒ stay 「5」はある?⇒ある!⇒ stay (「3」はもう見ない) UNIX BSD mmap kernel Linux TAAT (Term At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 ① ② -
50,241件 10,320件 520件 30,483件 500,020件 【戦略】OR 検索(Linux OR mmap) 1.
どれでもよいのでキーから accumulator を作成 2. 重複を除いて全てのキーから全部のリストをマージする UNIX BSD mmap kernel Linux TAAT (Term At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 ① ② -
特性 Inverted Index (転置インデックス) 1. TAAT = Term At A
Time = 一品ずつ食べる = 洋食 2. DAAT = Document At A Time = 全部少しずつ食べる = 和食 -
50,241件 10,320件 520件 30,483件 500,020件 【戦略】Document At A Time(訳:一度にドキュメントを) •
Document (転置インデックスのリストのアイテム) 毎にリストを取得してマージ • ひとつのドキュメント毎に処理 • 和食 UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 -
50,241件 10,320件 520件 30,483件 500,020件 【戦略】AND 検索(mmap AND Linux) •
Term (mmap と Linux) 毎にカーソルを準備 • 各カーソルを移動し、共通のドキュメントを発見を発見したら、 accumulator に追加 UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 -
50,241件 10,320件 520件 30,483件 500,020件 【戦略】AND 検索(mmap AND Linux) accumulator
= [] UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 -
50,241件 10,320件 520件 30,483件 500,020件 【戦略】AND 検索(mmap AND Linux) accumulator
= [1] UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 -
50,241件 10,320件 520件 30,483件 500,020件 【戦略】AND 検索(mmap AND Linux) accumulator
= [1, 5] UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 -
50,241件 10,320件 520件 30,483件 500,020件 【戦略】OR 検索(mmap AND Linux) •
なんでも良いので、accumulator を作る • カーソルを動かして、全ての要素を重複なく追加 UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 -
特性 TAAT and DAAT • メモリ使用量が多いのは TAAT • だた、OR 検索ではほぼ差はない
• かなりプリミティブな作り -
今でも効率的なアルゴリズムの研究が続 いている TAAT and DAAT S. Ding and T. Suel.
Faster top-k document retrieval using block-max indexes. In Proceedings of the 34th Annual International ACM SIGIR Conference on Research and development in Information Retrieval, pages 993-1002, 2011. ↑の成果は Lucene 8 (2019/3/14 リリース) で実装 参考 https://fosdem.org/2019/schedule/event/apache_lucene_solr_8/attachments/slides/3325/export/events /attachments/apache_lucene_solr_8/slides/3325/SchindlerLucene8Slides.pdf 参考: https://medium.com/@mocobeta/lucene-8-%E3%81%AE-top-k- %E3%82%AF%E3%82%A8%E3%83%AA%E3%83%97%E3%83%AD%E3%82%BB%E3%83%83%E3%82%B7%E3%83%B3%E3 %82%B0%E6%9C%80%E9%81%A9%E5%8C%96-1-%E5%B0%8E%E5%85%A5%E7%B7%A8-5a6387076e8e -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • ハイブリット index とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
Lucene • 転置インデックスを提供 – DAAT(Document At A Time) • 非常にネイティブな検索の機能のみ提供
– 様々な検索機能 • RangeQuery、FuzzyQuery、BooleanQuery – スコアリング機能 -
50,241件 10,320件 520件 30,483件 500,020件 【戦略】Document At A Time(訳:一度にドキュメントを) •
Document (転置インデックスのリストのアイテム) 毎にリストを取得してマージ • ひとつのドキュメント毎に処理 • 和食 UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
4,820,483件 93,832,732件 car book Posting List (Skip List) 1 3
3 53395 53395 0件 100,000件 -
4,820,483件 93,832,732件 car book Posting List (Skip List) 1 3
3 53395 53395 0件 100,000件 100,000 回見て回る!! -
4,820,483件 93,832,732件 car book Posting List (Skip List) 1 3
3 53395 53395 53395 53395 53395 53395 18395 291295 18395 291295 0件 100,000件 -
4,820,483件 93,832,732件 car book Posting List (Skip List) 1 3
3 53395 53395 53395 53395 53395 53395 18395 291295 18395 291295 見回る回数が少ない!! ※ スキップの段数に依存 ※ スキップの間隔に依存 0件 100,000件 -
Posting List (Skip List) • lucene-8.0.0/core/src/java/org/apache/lucene/codecs/MultiLevelSkipListReader.java • lucene-8.0.0/core/src/java/org/apache/lucene/codecs/MultiLevelSkipListWriter.java * Example
for skipInterval = 3: * c (skip level 2) * c c c (skip level 1) * x x x x x x x x x x (skip level 0) * d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d (posting list) * 3 6 9 12 15 18 21 24 27 30 (df) * * d – document * x - skip data * c - skip data with child pointer -
インデックスのデータ構造: B+木 • 葉ノード(葉ブロック)がデータを表す • 内部ノード(内部ブロック)は index(データをもたない) • 各ノードは a
個以上 b 個以下(例では2個以上3個以下)のエントリを必ずもつ 条件を満たすように、木の構造を変形する • 範囲指定のクエリに対して、強力に動作 • ブロックデバイス(葉ブロックと内部ブロックを格納)との相性が抜群 30 50 7 12 22 30 39 52 55 73 ブロック 15以上 -
• ブロック単位で読み書き • ブロックの大きさはブロックサイズ • ブロックサイズは結構大きい(Linux のデフォルトは 4 KB) •
1 bit 書き換えても、ブロックごと書き換えられる 残念ながら SSD も ブロックデバイス ブロックデバイス -
無邪気にメモリー上に置く、が現実的ではいくつかの理由 • ロードに時間がかかる • スワップアウトし、更に再ロードされるような場合、 激烈な性能劣化 • 膨大なコンテクストスイッチ (ユーザー空間 vs
カーネル空間) • ディスクのファイルキャッシュと、Java のヒープでの間の 膨大なやり取り -
mmap • システムコール • システムムコールだけど、ユーザープロセスの仮想アドレス空間に作成さ れるので、コンテクストスイッチが少ない: (ユーザー空間 vs カーネル空間) •
メモリマップトファイルとして扱えるので、追加・削除・更新が楽 • 複数のプロセス間で共有もできる • 【注意】Java の世界から逸脱している(Java のヒープ外でアロケートされ てる) • 【おまけ】C で malloc すると内部では mmap が呼ばれる -
Elasticsearch の推奨設定 “The standard recommendation is to give 50% of
the available memory to Elasticsearch heap, while leaving the other 50% free. It won’t go unused; Lucene will happily gobble up whatever is left over.” 【注意】Java の世界から逸脱している(Java のヒープ外でアロケートされてる) -
Lucene の index 格納 https://lucene.apache.org/core/8_0_0/core/org/apache/lucene/store/FSDirectory.html org.apache.lucene.store(3種類選べる) 1. SimpleFSDirectory.java • java.nio.ByteBuffer
2. NIOFSDirectory.java • java.nio.ByteBuffer 3. MMapDirectory.java • java.nio.MappedByteBuffer mmap -
util-mmap: Indeed の mmap • https://jp.engineering.indeedblog.com/blog/2015/02/util-mmap- %E3%81%A7%E3%83%A1%E3%83%A2%E3%83%AA%E3%83%9E%E3%83%83%E3%83%94%E3%83%B3%E3%82%B0/ • https://github.com/indeedeng/util/tree/master/mmap MappedByteBuffer
の既知の制約を克服: – 安全にアンマップできない – サイズが 2GB (int) を超えるファイルをマップできない – スレッドセーフではない -
圧縮のトレードオフ 読み込み完了 100MB/s 5,000KB 50ms 25ms 30GB/s =30,720MB/s 2,500KB 50%圧縮
読み込み完了 15ms 10ms=解凍 -
Lucene で利用できる圧縮形式 LZ4 https://lz4.github.io/lz4/ lucene-8.0.0/core/src/java/org/apache/lucene/codecs/compressing/LZ4.java https://gigazine.net/news/20120824-dragonquest-backstage-cedec2012/ • 圧縮率は弱いが、圧縮速度が速い • 色々なところで使われている:
– OS: Linux, FreeBSD – Hadoop, Cassandra – Nintendo Switch – ドラゴンクエストXのセーブデータ -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • ハイブリット index とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
50,241件 10,320件 520件 30,483件 500,020件 1. 同じキーが同じサーバーにいる必要がない ⇔ BSD が別のサーバーにあっても良い
2. マージさえできればよい ⇔ BSD が複数のサーバーにあってもよい UNIX BSD mmap kernel Linux 分散検索 1 1 1 2 3 3 4 4 5 5 6 6 7 -
50,241件 10,320件 520件 30,483件 500,020件 UNIX BSD mmap kernel Linux
分散検索: indexing 1 1 1 2 3 3 4 4 5 5 6 6 7 UNIX mmap Linux UNIX mmap Linux UNIX mmap Linux -
分散検索 • 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) •
負荷分散(Load Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第! -
分散検索 • 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) •
負荷分散(Load Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第! Node Node Node -
分散検索 • 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) •
負荷分散(Load Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第! Node Node Node A Shard C Shard B Shard C Shard A Shard B Shard -
• 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) • 負荷分散(Load
Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第! シャード A, B, C 全部が生存 欠損なしで 検索続行 分散検索: 可用性(Availability) Node Node Node A Shard C Shard B Shard C Shard A Shard B Shard -
Node Node Node A Shard C Shard B Shard C
Shard A Shard B Shard 分散検索: 負荷分散(Load Balance) • 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) • 負荷分散(Load Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第! シャードA と B に関する 検索 シャードA と B に関する 検索 シャードA と B に関する 検索 -
Node Node Node A Shard C Shard B Shard C
Shard A Shard B Shard • 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) • 負荷分散(Load Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第! hash(XXX) mod (# of Shard) = C 分散検索: ルーティング Doc ID: XXX -
分散検索 • 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) •
負荷分散(Load Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第! Node Node Node A Shard C Shard B Shard C Shard A Shard B Shard -
分散検索: Index の構成 Shard A アイスクリーム 200円 50円 850円 120円
Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 • サーバー(シャード)は本来非常に多い(数万台、ここでは3台) • シャードに含まれるドキュメント数には上限有り(100万等) • どのサーバーも、自分の担当の検索は非常に高速(対象が100万位しかないから) • 入り切らなくなってきたら、サーバーを足す (スケールアップではなく、スケールアウト) < 1000,000 < 1000,000 < 1000,000 -
分散検索: Two Phase Search, query and fetch Shard A アイスクリーム
200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 • query phase: どのサーバーにマッチする結果がどれだけあるのか? ⇒ メモリ上+ネットワークトラフィック小で解決 • fetch phase: 見つけた結果を整形(スニペット生成、等)して返却結果を作成 ⇒ 高負荷な処理を実行 -
分散検索: Two Phase Search, query and fetch 【重要】各サーバは他のサーバーの安いアイスクリームを知らない!! クエリー:アイスクリーム ORDER
BY 安い順 LIMIT 3 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 -
分散検索: Two Phase Search, query and fetch クエリー:アイスクリーム ORDER BY
安い順 LIMIT 3 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 [50, 120, 200] [10, 220, 320] [300, 500, 720] [10, 50, 120] -
分散検索: Two Phase Search, query and fetch クエリー:アイスクリーム ORDER BY
安い順 LIMIT 3 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 [10, 50, 120] -
分散検索: Two Phase Search, query and fetch Q: 100位〜102位まで取ってくるには? クエリー:アイスクリーム
ORDER BY 安い順 LIMIT 3 OFFSET 100 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 A: 各サーバーから102件取得してくる -
分散検索: Two Phase Search, query and fetch Q: 嘘でしょ? クエリー:アイスクリーム
ORDER BY 安い順 LIMIT 3 OFFSET 100 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 A: 本当です。 -
分散検索: Two Phase Search, query and fetch Q: 事前に準備とかできないの? クエリー:アイスクリーム
ORDER BY 安い順 LIMIT 3 OFFSET 100 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 A: できないです… -
分散検索: Two Phase Search, query and fetch クエリー:(アイスクリーム AND すいか味)ORDER
BY 安い順 LIMIT 3 OFFSET 100 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
50,241件 10,320件 520件 30,483件 500,020件 UNIX BSD mmap kernel Linux
転置インデックス 1 1 1 2 3 3 4 4 5 5 6 6 7 -
Lucene の世界の Term と Token Token = Term(= 文字列 +
フィールド) + 開始位置 + 終了位置 • lucene/core/src/java/org/apache/lucene/index/Term.java • lucene/core/src/java/org/apache/lucene/analysis/Token.java これはどう作るの?! Lucene の世界では Tokenizer が分割をしてくれる! -
Lucene の Tokenizer • ClassicTokenizerFactory • EdgeNGramTokenizerFactory • HMMChineseTokenizerFactory •
ICUTokenizerFactory • JapaneseTokenizerFactory • KeywordTokenizerFactory • LetterTokenizerFactory • LowerCaseTokenizerFactory • NGramTokenizerFactory • PathHierarchyTokenizerFactory • PatternTokenizerFactory • StandardTokenizerFactory • ThaiTokenizerFactory • UAX29URLEmailTokenizerFactory • UIMAAnnotationsTokenizerFactory • UIMATypeAwareAnnotationsTokenize rFactory • WhitespaceTokenizerFactory • WikipediaTokenizerFactory -
Lucene の Tokenizer • ClassicTokenizerFactory • EdgeNGramTokenizerFactory • HMMChineseTokenizerFactory •
ICUTokenizerFactory • JapaneseTokenizerFactory • KeywordTokenizerFactory • LetterTokenizerFactory • LowerCaseTokenizerFactory • NGramTokenizerFactory • PathHierarchyTokenizerFactory • PatternTokenizerFactory • StandardTokenizerFactory • ThaiTokenizerFactory • UAX29URLEmailTokenizerFactory • UIMAAnnotationsTokenizerFactory • UIMATypeAwareAnnotationsTokenize rFactory • WhitespaceTokenizerFactory • WikipediaTokenizerFactory -
Lucene の Tokenizer • ClassicTokenizerFactory • EdgeNGramTokenizerFactory • HMMChineseTokenizerFactory •
ICUTokenizerFactory • JapaneseTokenizerFactory • KeywordTokenizerFactory • LetterTokenizerFactory • LowerCaseTokenizerFactory • NGramTokenizerFactory • PathHierarchyTokenizerFactory • PatternTokenizerFactory • StandardTokenizerFactory • ThaiTokenizerFactory • UAX29URLEmailTokenizerFactory • UIMAAnnotationsTokenizerFactory • UIMATypeAwareAnnotationsTokenize rFactory • WhitespaceTokenizerFactory • WikipediaTokenizerFactory -
英語の Tokenize は超簡単 “Elasticsearch is a distributed, RESTful search and
analytics engine capable of solving a growing number of use cases.” WhitespaceTokenizer “Elasticsearch is a distributed, RESTful search and analytics engine capable of solving a growing number of use cases.” -
Lucene の Tokenizer • ClassicTokenizerFactory • EdgeNGramTokenizerFactory • HMMChineseTokenizerFactory •
ICUTokenizerFactory • JapaneseTokenizerFactory • KeywordTokenizerFactory • LetterTokenizerFactory • LowerCaseTokenizerFactory • NGramTokenizerFactory • PathHierarchyTokenizerFactory • PatternTokenizerFactory • StandardTokenizerFactory • ThaiTokenizerFactory • UAX29URLEmailTokenizerFactory • UIMAAnnotationsTokenizerFactory • UIMATypeAwareAnnotationsTokenize rFactory • WhitespaceTokenizerFactory • WikipediaTokenizerFactory -
Ngram Tokenizer 一定の長さの文字列単位で分割 「敵に塩を送る」 • Unigram: 1文字単位 ⇒ 「敵」「に」「塩」「を」「送」「る」 •
Bigram: 2文字単位 ⇒「敵に」「に塩」「塩を」「を送」「送る」 • Trigram: 3文字単位 ⇒「敵に塩」「に塩を」「塩を送」「を送る」 Q: Bigram で「塩」を検索可能?! A: No… 検索できない ⇒ N-gram ならば 2-1gram -
Ngram Tokenizer Unigram vs Trigram 「敵に塩を」 • 長さ3以上の term ならできることに変わりはなし(「塩」は検索できない)
• どんどん大きくなると、完全一致のようになり、検索とは何か? という問題になる(6-gramでは「敵に塩を送」さえ検索できない) • 速度には差がでる(Unigram より Trigram の方が速い) 4個タームのマージ vs 2個のタームのマージ 「敵」「に」「塩」「を」vs 「敵に塩」「に塩を」 ※「に」「を」のPosting List などは非常に大きい(はず) -
Japanese Tokenizer(Kuromoji) 形態素解析エンジン。辞書ベースで分割。 「敵に塩を送った」 Surface form Part-of-Speech Base form Reading
Pronunciation 敵 名詞,一般,*,* 敵 テキ テキ に 助詞,格助詞,一般,* に 二 二 塩 名詞,一般,*,* 塩 シオ シオ を 助詞,格助詞,一般,* を ヲ ヲ 送っ 動詞,自立,*,* 送る オクッ オクッ た 助動詞,*,*,* た タ タ -
Ngram vs 形態素解析 効果\方法 Ngram 形態素解析 取りこぼし: 「目黒」で「中目黒」 hit! =
Good! No hit. = Bad… レレバンシー: 「京都」で「東京都」 hit! = Bad… No hit. = Good! Indexのサイズ 大 = Bad… 小 = Good! それぞれ、良いところと悪いところがある 解決策:両方をもつハイブリッド index -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
B+木の数値に対するクエリー • Q: 15以上のアイテムがほしい! • 更にQ: 価格が1000円以下のアイテムがほしい! • またまたQ: 年式が2013以降で、色は赤っぽくて、高さが200…
30 50 7 12 22 30 39 52 55 73 15以上 -
コサイン類似度 価格 色 鮮度 商品A 商品B 商品C クエリー cos の値が
• 1 に近ければ、類似している • 0 に近ければ、類似していない -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
理想の検索結果 C 実際の検索結果 B 再現率 A 再現率= C A 意味:どれほど網羅しているか?
理想の検索結果(C)の内、実際の検索索結果とし て取得できた(A)割合 -
理想の検索結果 C 実際の検索結果 B 適合率と再現率 A 再現率= C A 適合率=
B A • 適合率:正確性=ノイズを含まない比率 • 再現率:網羅性=取りこぼしが少ない比率 -
C B 適合率と再現率 A 適合率↓ 再現率↓ 再現率= C A 適合率=
B A 実際の検索結果 理想の検索結果 クエリー「東京都」 -
C B 適合率と再現率 A 適合率↓ 再現率→ 再現率= C A 適合率=
B A 実際の検索結果 理想の検索結果 クエリー「京都」 -
C B 適合率と再現率 A 適合率↑ 再現率→ 再現率= C A 適合率=
B A 実際の検索結果 理想の検索結果 クエリー「京都」 -
C B 適合率と再現率 A 残念ながら、適合率と再現率はトレードオフ 再現率= C A 適合率= B
A 実際の検索結果 理想の検索結果 -
C B 適合率と再現率 A • 適合率を上げれば再現率は下がり、 • 再現率を上げれば適合率が下がる。 再現率= C
A 適合率= B A 実際の検索結果 理想の検索結果 -
理想の検索結果 C 実際の検索結果 B A 再現率= C A 適合率= B
A =1 • 実際の検索結果が 全て理想の検索結果 • ただし、取りこぼしが非常 に多い =理想の検索結果の一部 しか返却できていない なんでも正しい1件しか返却しない! ⇒ 最高 極端な適合率 • 適合率を上げれば再現率は下がり、 • 再現率を上げれば適合率が下がる。 -
理想の検索結果 C 実際の検索結果 B A =1 • 実際の検索結果が全ての 理想の検索結果が含まれ る
• ただし、非常にノイズが多 い =理想の検索結果以外の 結果が多く含まれている 極端な再現率 • 適合率を上げれば再現率は下がり、 • 再現率を上げれば適合率が下がる。 適合率= B A 再現率= C A なんでも全件返却する! ⇒ 最高 -
理想の検索結果 C 実際の検索結果 B 適合率と再現率 A 再現率= C 適合率= B
適合率(正確性)と再現率(網羅性)のバランスが重要 A A -
F-measure:適合率と再現率のバランス F-measure の値が大きければ、バランスのとれた良い結果 F-measure = 適合率 ( 1 + 再現率
1 ) 2 適合率= B A 再現率= C A -
適合率と再現率の非現実性 • そもそも「理想の検索結果」とは? – 機械的に作ることが可能ならば、それを検索結果してしまえば良い • 実際に10万件の結果がある場合、評価可能?! – メジャーなクエリー1万件ある場合、評価が必要な件数は10億件 •
検索にヒットしなかった結果も評価しないといけない… – 全部で100万件あり、10万件ヒットしたとしても、 残りの90万件も「理想の検索結果」か否かを評価… -
0 5000000 10000000 15000000 20000000 25000000 1 2 3 4
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 検索結果の順位 (x軸)とクリック数 (y軸) のサンプル -
検索結果の一般的な評価? • クエリー「目黒」で、検索結果に「中目黒」を含めるべきか否か?! – なかなか分からない • クエリー「京都」で、検索結果に「東京都」を含めるべきか?! – 含めるべきではない(だろう) •
答えはあるのか? – 多分、一般的な解はない • どうすればいいのか? -
結果:目黒 { "_score" : 656.68774, "_source" : { "nikki_kuromoji" :
"雪の目黒", "nikki_ngram" : "雪の目黒“ } }, { "_score" : 23.361103, "_source" : { "nikki_kuromoji" : "雨の中目黒", "nikki_ngram" : "雨の中目黒“ } } -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
TF-IDF and Okapi BM25b • 何なの? – アルゴリズム • 入力は?
– 文章の集合 • 出力は? – 各文章の各単語にスコアを付与 • スコアは何を表すの? – 各文章の各単語の重要度 -
TF-IDF and Okapi BM25b • 何なの? – アルゴリズム • 入力は?
– 文章の集合 • 出力は? – 各文章の各単語にスコアを付与 • スコアは何を表すの? – 各文章の各単語の重要度 Linux: 0.3 Windows:0.1 ぶり: 4.2 Linux: 1.3 Windows:2.3 まぐろ: 3.8 Linux: 5.4 FreeBSD:10.3 大根: 2.1 -
2つの文章での「Linux」 Linux Linux(リナックス、他 の読みは後述)は、 UnixライクなOSカーネ ルである)。 OS オペレーティングシステム(英語: Operating System、
OS、オーエス)とは、 コンピュータのオペレーション(操作・運 用・運転)のために、ソフトウェアの中で も基本的、中核的位置づけのシステム ソフトウェアである。通常、OSメーカーが 組み上げたコンピュータプログラムの集 合として、作成され提供されている。 … フリーなOSは、Linux、FreeBSD… … どちらの文章が「Linux」に関して重要度が高いか?! < 直感的 ? 定量的 -
TF-IDF • TF=Term Frequency=Termの頻度 あるドキュメントの中で、どれだけそのTerm が出現したか? ⇒ いっぱい出てくる単語は重要だ • IDF:IDF=Inverse
Document Frequency=逆文章頻度 あるTerm が全体の中でどれほどレアか? ⇒ レアな単語は重要だ • TF-IDF = TF×IDF あるドキュメント D の中の、Term T がどれほど重要か?は、 (TF: D の中でのT の頻出度)×(IDF: T の全体でのレア度) -
TF-IDF:TF=Term Frequency=Termの頻度 Linux Linux(リナックス、他 の読みは後述)は、 UnixライクなOSカーネ ルである)。 Linux: 2 リナックス:
1 読み: 1 Unix: 1 一つの文章に現れる Term の出現回数 沢山出現すれば それだけ重要 -
TF-IDF:IDF=Inverse Document Frequency=逆文章頻度 • Linux • である IDF = log
Term T が現れる文章数 総文章数 • 野菜 • である • 野菜 • がある • Linux • がある • 肉 • である IDF(Linux) = log 2 5 = 0.39 IDF(である) = log 3 5 = 0.22 > 定量的 Linux である -
TF-IDF:IDF=Inverse Document Frequency=逆文章頻度 • 逆である意味は?! – 現れるドキュメントが、多ければ多いほど、重要度を下げたい (逆比例:「である」等は小、「しめ鯖」等は大) • log
を取る意味は?! – 非常に大きな総文章数の場合のためのノーマライズ (ノーマラナイズしないとTFの意味がなくなる) IDF = log Term T が現れる文章数 総文章数 -
TF-IDF あるドキュメント D の中の、 Term T がどれほど重要か?は、 (TF: D の中での
T の頻出度) × (IDF: 文章全体での T のレア度) -
TF-IDFの注意(良いところ) あるドキュメント D に対して Term が異なれば、TF-IDFも異なる しめ鯖 ⇒ 0.8492 Linux
⇒ 0.0234 月刊 Linux 2018/04/24 号 今月の月刊 Linux では、 カーネルの特集を… …ところでしめ鯖は美味し いですね。僕も… -
BM25: TF-IDFが不都合な場合 Linux Linux(リナックス、他 の読みは後述)は、 UnixライクなOSカーネ ルである)。 Linux Linux Linux
Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux … TF(Linux) = 14,352 TF(Linux) =2 > これは不都合 注)IDFはどちらも一緒 -
BM25: TF-IDFが不都合な場合 Linux Linux(リナックス、他 の読みは後述)は、 UnixライクなOSカーネ ルである)。 Linux Linux Linux
Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux … TF(Linux) = 14,352 TF(Linux) =2 > これは不都合 注)IDFはどちらも一緒 何が問題?! 単語数! 14,352 > 23 -
BM25の定義 Linux Linux(リナックス、他 の読みは後述)は、 UnixライクなOSカーネ ルである)。 ・TF = 単語(Linux)の出現数 ・IDF
= 単語レア度(Linuxのレア度) ・DL = ドキュメントの単語数(23) ・avgDL = 全てのドキュメントの単語数の平均 (=320) ・2つのパラメータk1, b k1 は 2 が最も最適と言われている b は 0.75 が最も最適と言われている BM25(Linux) =TF × IDF × TF+k1 ×(1-b+b× ) k1 + 1 avgDL DL -
BM25の意味 BM25(Linux) =TF × IDF × TF+k1 ×(1-b+b× ) k1
+ 1 avgDL DL 単に単語を沢山もつ場合は 減点↓ 単語を沢山もつ場合は 一つの単語の価値を減点↓ 単語を沢山もつ場合は減点だが それが平均に対して小さければ 加点↑ ・TF = 単語の出現数 ・IDF = 単語レア度 ・DL = ドキュメントの単語数 ・avgDL = 全てのドキュメントの単語数の平均 -
BM25 and TF-IDF Linux はフリー のOSカーネル であり、… FreeBSDは Unix系のオー プンソースの
… 今年のじゃがい もはとても不作 だった。 日本ではこの時 期のブリを特に 「寒ブリ」と呼ぶ • Linux: 23 • OS: 11 • カーネル: 17 • は: 0.331 • あり: 3.65 • の: 0.003 • です: 0.0001 • は: 0.000053 • の: 0.023 • FreeBSD: 65 • OS: 9 • カーネル: 5 • じゃがいも: 42 • 不作: 58 • 今年: 2 • だった:0.003 • は: 0.00428 • の: 0.00084 • 寒ブリ: 90 • 日本: 3 • 時期: 1.8 • 特に: 0.2 • の: 0.00189 レアではないワードはスコア小 特徴的 Term はスコア大 -
検索結果の一般的な評価? • クエリー「目黒」で、検索結果に「中目黒」を含めるべきか否か?! – なかなか分からない • クエリー「京都」で、検索結果に「東京都」を含めるべきか?! – 含めるべきではない(だろう) •
答えはあるのか? – 多分、一般的な解はない • どうすればいいのか? -
結果:目黒 { "_score" : 656.68774, "_source" : { "nikki_kuromoji" :
"雪の目黒", "nikki_ngram" : "雪の目黒“ } }, { "_score" : 23.361103, "_source" : { "nikki_kuromoji" : "雨の中目黒", "nikki_ngram" : "雨の中目黒“ } } -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
nDCG • nDCG (= normalized Discounted Cumulative Gain) • 直訳すると「正規化された効果減少の累積報酬」
• ランキングの精度評価指標 • ランキングを行うシステムの評価に利用できるので、 特に、検索だけがターゲットではない。 例)レコメンドシステム、広告システム • nDCG も理想のランキングとの乖離具合を数値化 -
nDCG:実際の検索結果 クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!
【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 -
nDCG:実際のカスタマーの行動 クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!
【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
nDCG:実際のカスタマーの行動 クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!
【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 -
nDCG:実際のカスタマーの行動 クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!
【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 2位なのに 頑張っている 4位なのに 断トツ 1位なのにたいしたことない ③が上って どういうこと?! -
nDCG:実際の結果 クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!
【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 -
nDCG:理想の結果 クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!
【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 -
nDCG:理想の結果(並べ替えだけでは不十分) クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!
【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 元々1位だったアド バンテージを考慮し ていない -
nDCG:スコア ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子! 【送料無料】てんこ盛り
訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 1. 各順位の結果はスコアをもっている (例 クリック数+購入数×100) S1=150 S2=110 S3=45 S5=60 S4=250 -
nDCG:Top5 の DCG ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1
明太子! 【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 2. 各順位に応じて、ペナルティ を与え、全体のスコアを計算 DCG5= S1 + + + … log2 S2 log3 S3 -
nDCG:理想の結果のDCG=iDCG (ideal DCG) ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1
明太子! 【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 3. スコア順のDCG = iDCG を求める ⇒ DCG が MAX -
現実の DCG ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!
【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 DCG5= S1 + + + … = 439.23 log2 S2 log3 S3 -
理想の DCG ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!
【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 DCG5= S1 + + + … = 518.78 log2 S2 log3 S3 -
ちょっと改善した DCG ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!
【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 DCG5= S1 + + + … = 489.23 log2 S2 log3 S3 -
nDCG の違い クリック 購入 クリック 購入 クリック 購入 クリック 購入
クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 nDCG=0.84 nDCG=0.94 -
定量的に評価 できることが大事で、 手法はサービスによって選べば吉 • nDCG • Precision@k • MAP (Mean
Average Precision) • MMR (Maximal Marginal Relevance) -
MLR= Machine Learning Ranking クリック 購入 クリック 購入 クリック 購入
クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 nDCG=0.84 nDCG=1.00 理想を目指してパラメータ調整 -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か? -
ジャンルにヒットしたらスコアを上げる • filter がメインの検索 (「鈴木」さんを検索) • bool が関連のあるワードとのマッチによるスコアアップ (「野球」や「MLB」に関連する方) {
"query": { "bool": { "should": [ { "match_phrase": { "contents": { "boost":1000, "query": "野球" } } }, { "match_phrase": { "contents": { "boost":1000, "query": "MLB” } } } ], "minimum_should_match": 0, "filter": { "bool": { "should": [ { "match_phrase": { "contents": "鈴木" } } ] } } } } } -
アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •
Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?