検索は、語から文書を引く
転置インデックスとは、「どの語が、どの文書に出てくるか」を語ごとにまとめた表です。検索エンジンは、この表を使って、たくさんの文書から一瞬で答えを出します。
学校の掲示板に、お知らせが何百枚も貼ってあるとします。「カフェ」の話を探すたびに、全部を読み直すのは大変です。先に語ごとの索引を作っておけば、すぐに見つかります。
このレッスンのゴール
メモ
転置インデックスを作り、語を使って、条件に合う文書を探すことができる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| 文書 | 検索される、1つの文章のまとまり | 1枚のお知らせ |
| トークン | 文書を切り分けた、数えるための1つの単位 | 駅、の、近く |
| 転置インデックス | 語から、その語を含む文書の番号を引く表 | |
| ポスティングリスト | 1つの語を含む文書の番号の並び | [1, 5] |
| ブール検索 | AND と OR で語の条件を組み合わせる検索 |
学生が入力するセルは、このプレビューでは空白です。
全部を読む検索は、文書が増えると遅い
最も単純な検索は、文書を1つずつ開いて、語があるか確かめる方法です。文書が5つなら、すぐ終わります。
文書が100万あれば、1回の検索で100万回開くことになります。しかも、検索は何度も行われます。そこで、先に索引を作ります。
例: 5枚のお知らせ
| 番号 | 文書（単語の間に空白を入れてあります） |
|---|---|
| 1 | 駅 の 近く の カフェ は 月曜日 が 休み です |
| 2 | 駅 の 近く の 図書館 は 月曜日 も 開き ます |
| 3 | 大雨 で 電車 が 遅れ ます |
| 4 | 電車 の 遅れ を 駅 で 知らせ ます |
| 5 | カフェ の 新しい メニュー は 雨 の 日 に 人気 です |
学生が入力するセルは、このプレビューでは空白です。
索引は、文書と語を逆にした表
文書の表は、「文書の番号から、その中の語」を引きます。索引は、これを逆にします。「語から、その語を含む文書の番号」を引くのです。
「逆」を意味する言葉から、転置インデックスと呼ばれます。語ごとの番号の並びがポスティングリストです。
例: 語ごとのポスティングリスト
| 語 | 含む文書の番号 |
|---|---|
| カフェ | 1, 5 |
| 駅 | 1, 2, 4 |
| 電車 | 3, 4 |
| 休み | 1 |
| 雨 | 5 |
学生が入力するセルは、このプレビューでは空白です。
索引を作って、重なりを直す
docs = {
1: "雨 の 日 は 傘 を 持つ",
2: "傘 の 店 は 駅 の 近く",
3: "駅 の 店 は 日曜日 が 休み",
}
index = {}
for number in docs:
for word in docs[number].split():
if word not in index:
index[word] = []
index[word].append(number)
print(index["店"])
print(index["の"])
# 「の」の番号が重なっています。append の前に if を足して、重ならないようにしてください。
よくある間違い
注意
1つの文書に語が何回も出たら、その回数だけ番号を並べると考えがちです。ポスティングリストには、文書の番号を1回だけ入れます。回数の数え方は、次の回で扱います。
AND は共通の番号、OR はすべての番号
複数の語で探すときは、ポスティングリストを組み合わせます。AND は、全部の語を含む文書で、リストに共通の番号だけが残ります。
OR は、どれかの語を含む文書で、すべての番号を重ならないように集めます。この組み合わせを、ブール検索と言います。
AND は共通の番号
docker exec jupyter python3 -c "print(sorted(set([1, 3, 4]) & set([3, 4, 5])))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
例: 5枚のお知らせを探す
| 検索 | 考え方 | 見つかる文書 |
|---|---|---|
| 駅 AND 月曜日 | [1, 2, 4] と [1, 2] に共通 | 1, 2 |
| 駅 OR 電車 | [1, 2, 4] と [3, 4] をまとめる | 1, 2, 3, 4 |
| カフェ AND 雨 | [1, 5] と [5] に共通 | 5 |
学生が入力するセルは、このプレビューでは空白です。
さらに挑戦: AND NOT 検索
「駅 AND NOT 電車」は、駅を含み、電車を含まない文書を探します。課題の search_and を参考に、search_not(index, word, banned) を作ってください。
5枚のお知らせでは、答えは 1 と 2 です。