転置インデックスを用いた全文検索
検索システムというものに興味を持ったので調べました。
検索と言ったら
「sqlのSelect文でwhere句にキーワード指定して」
などとやるものかと思ったら違いました。
大量の文章（検索対象）の中からキーワードに合致する文章を取ってくる場合それではものすごい時間がかかります。
そこで現在ほとんどの検索システムは転置インデックスという索引構造を利用して速い検索を実現しています。
今回はこれについて簡単にまとめさらに簡単に実装してみたいと思います。
転置インデックス
特定の単語を含む文章を探す際に個人的に一番素直だと思う方法はすべての文章を片っ端から調べあげることだと思います。
grepコマンドがこの方法をとっているようです。
ですがこの方法だと文章の数が膨大になると、答えを得るまでにかなりの時間がかかってしまいます。
商用で利用されている検索システムのほとんどは転置インデックスというものを利用しています。
これは単語ごとにその単語が出現する文章の一覧を作成し、
検索する際にこの一覧を参照して文章を取得する方法です。
この一覧をポスティングリストというようです。
事前に一覧を作成しておく必要がありますが、全走査にくらべて短時間で文章を取得することができます。
少し適当かもしれませんが、例えば次のような３つの文章があります。
- I like Python
- You like Java
- We like C and Java and Python
この文章に足して転置インデックスの仕組みを適用するとこのような一覧が出来上がります。
2列めの数字は文章を表しているIDのようなものです。
| 単語 | 文章 |
| I | 1 |
| like | 1,2,3 |
| Python | 1,3 |
| You | 2 |
| Java | 2,3 |
| We | 3 |
| C | 3 |
| and | 3 |
この一覧を使って単語から文章を取得してきます。
例えばPythonという単語を指定して文章を検索した場合、文章１と文章３が取得できます。
複数の単語からなるフレーズで検索する場合、単語の並びも考慮する必要があります。
ちなみにここでは取得対象を文章と読んでいますが、これはシステムによって変わってきます。
web検索エンジンであればwebページですし、書籍の検索システムであれば書籍が検索対象になります。
ポスティングリストをなんとか作成する
ポスティングリストをどのように持つかを決める必要があります。
以下のようなフォーマットでテキストファイルに保存することにしましょう。
{文章ID:単語の出現場所},{文章ID:単語の出現場所}…
「単語の出現場所」は文章の中で単語が出現する場所を0から数えた数です。
文章をいちからたくさん用紙するのは面倒なので、
webページをスクレイピングしてそれを素材に短い文章をできるだけたくさん作っていきましょう。
htmlのpタグごとに文章を抽出します。
一応ポスティングリストのサイズもファイルに出力しておくようにしました。
素材はリーナスさんに関する記事でやってみましょう。
import glob
import re
import urllib.request
import sys
import os
url = "https://www.techrepublic.com/article/linus-torvalds-git-proved-i-could-be-more-than-a-one-hit-wonder/"
doc_dir = "./document/{}"
doc_file = "./document/{}/document_{}"
index_dir = "./index/{}"
index_file = "./index/{}/index"
index_size = "./index/{}/size"
def gen_index(data, doc_id):
if os.path.exists(doc_dir.format(doc_id)) == False:
os.mkdir(doc_dir.format(doc_id))
f = open(doc_file.format(doc_id, doc_id), "w")
f.write(data)
f.close()
words = re.findall("[a-zA-Z0-9]+", data)
for i in range(len(words)):
if os.path.exists(index_dir.format(words[i])) == False:
os.mkdir(index_dir.format(words[i]))
f = open(index_file.format(words[i]), "a")
index_data = "{}:{},".format(doc_id, i+1)
f.write(index_data)
f.close()
if os.path.exists(index_size.format(words[i])) == False:
f = open(index_size.format(words[i]), "w")
f.write(str(len(index_data)))
else:
f = open(index_size.format(words[i]), "r")
size = f.read()
f.close()
size = str(int(size) + len(index_data))
f = open(index_size.format(words[i]), "w")
f.write(size)
f.close()
def scrape(url):
headers = {"User-Agent": "Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:47.0) Gecko/20100101 Firefox/47.0",}
request = urllib.request.Request(url=url, headers=headers)
response = urllib.request.urlopen(request)
encoding = response.info().get_content_charset(failobj='utf-8')
return response.read().decode(encoding)
html = scrape(url)
datas = re.findall(r'<p.*?</p>',html,re.DOTALL)
for i in range(len(datas)):
word = re.sub('<.*?>','', datas[i])
gen_index(word.lower(), i+1)
このスクリプトが同一階層にdocumentディレクトリとindexディレクトリを作成します。
document内に文章ID名を持つディレクトリが格納されており、
その中に実際の文章が置かれています。
$ ls document
1 11 13 15 17 19 20 22 24 26 28 3 31 4 6 8
10 12 14 16 18 2 21 23 25 27 29 30 32 5 7 9
$ ls document/6
document_6
$ cat document/6/document_6
however, they'd likely be a bit more impressed had they heard the same thing come from the mouth of linus torvalds, founder of the linux operating system. 省略
そしてindex内に単語の名前を持つディレクトリが作成されその中にポスティングリストがテキストファイルで格納されています。
検索してみる
ポスティングリストを作成できればあとは簡単だと思います。
文章IDを取得してくる段取りはだいたい以下の通りです。
- 単語ごとにポスティングリストを取得
- 取得したポスティングリストから共通集合を取得
- キーワードがフレーズの場合は単語の並びを調べ、合致していればIDを取得する
これらをやってくれるスクリプトを書けばいいということです。
こういうのは少しくらい適当でいいんですよ。
import sys
def fetch_document_id(query):
p_list = []
index_path = "./index/{}/index"
words = query.split(" ")
for word in words:
f = open(index_path.format(word), "r")
data = f.read()
p_list.append(data.split(","))
word_match = []
phrase_match = []
for p in p_list[0]:
word_match_cnt = 1
phrase_match_cnt = 1
if len(p) == 0:
continue
id_off = p.split(":")
docid = int(id_off[0])
off = int(id_off[1])
for i in range(1,len(p_list)):
for j in range(len(p_list[i])):
if len(p_list[i][j]) == 0:
continue
t_id_off = p_list[i][j].split(":")
t_docid = int(t_id_off[0])
t_off = int(t_id_off[1])
if docid == t_docid:
word_match_cnt +=1
if off+1 == t_off:
phrase_match_cnt+=1
docid = t_docid
off = t_off
break
if phrase_match_cnt == len(p_list) and len(p_list) > 1:
if docid not in phrase_match:
phrase_match.append(docid)
elif word_match_cnt == len(p_list):
if docid not in word_match:
word_match.append(docid)
return [word_match, phrase_match]T
query = sys.argv[1]
print("Query: {}" .format(query))
res = fetch_document_id(query)
print("Intersection: ",res[0])
print("Phrase Match: ",res[1])
fetch_document_id関数はキーワードに指定した単語全てに合致した文章IDの配列と、
フレーズに合致した文章IDのの配列を返してくれます。
実際に動かすとこうなりました。
$ python search.py "operating system"
Query: operating system
('Intersection: ', [])
('Phrase Match: ', [6])
operating systemをキーワードにすると文章ID6が返ってきました。
どうやらフレーズが合致したようです。
この答えが正しいかgrepコマンドでdocument配下を検索してみましょう。
$ grep ./document -r -e "operating system"
./document/6/document_6:however, they'd likely be a bit more impressed had they heard the same thing come from the mouth of linus torvalds, founder of the linux operating system. in a fireside chat at the open source summit europe, torvalds was asked how he spends his time as the kernel maintainer. "i read email," was torvalds' reply. but not just any email. the email torvalds answers helps to keep over 25 million lines of code humming for the hundreds of millions of linux-powered devices worldwide. so it kind of matters if he replies.
次はlinusと指定して検索してみましょう
$ python search.py linus
Query: linus
('Intersection: ', [3, 4, 6, 25])
('Phrase Match: ', [])
今度は共通集合を取得してきました。
grepで確認してみましょう。
問題ないみたいです。
$ grep ./document -r -e "linus"
./document/4/document_4:linus torvalds (l) and dirk hohndel (r) at the open source summit europe
./document/25/document_25:linus torvalds offers the secret to linux's long-term success (the answer won't surprise you) (techrepublic)
./document/3/document_3: linus torvalds: "git proved i could be more than a one-hit wonder."
./document/3/document_3: "@id": "https:\/\/www.techrepublic.com\/article\/linus-torvalds-git-proved-i-could-be-more-than-a-one-hit-wonder\/"
./document/3/document_3: "headline": "linus torvalds: \"git proved i could be more than a one-hit wonder.\"",
./document/3/document_3: "description": "commentary: the world rightly lauds linus torvalds for linux, but git will arguably have a bigger impact."
./document/3/document_3: commentary: the world rightly lauds linus torvalds for linux, but git will arguably have a bigger impact.
./document/6/document_6:however, they'd likely be a bit more impressed had they heard the same thing come from the mouth of linus torvalds, founder of the linux operating system. in a fireside chat at the open source summit europe, torvalds was asked how he spends his time as the kernel maintainer. "i read email," was torvalds' reply. but not just any email. the email torvalds answers helps to keep over 25 million lines of code humming for the hundreds of millions of linux-powered devices worldwide. so it kind of matters if he replies.それで何がしたいのか
特に何かがしたいわけではありません。
検索システムに少し興味が湧いてきたので調べてみただけです。
全文検索ライブラリーとしてApacheLuceneがあります。
それをつかってなにか作ってみるものいいかもしれません。
商用のシステムは大量のアクセスが来るので、ここから更に工夫を凝らして検索を効率化しているのでしょうか。
Googleとかものすごいことしてそう。
検索エンジンの作り方をテーマにした参考書は意外と少ないでが、
以下の書籍では検索エンジンに使われている技術やアルゴリズムを垣間見ることができます。
もちろん転置インデックスについてものっています。
また検索エンジンの理解のためのサンプルも用意されており、
ソースコードがダウンロードできます。
とにかく検索エンジンの内部動作や実装方法などあまり知られていないこともあると思うので、自作に興味がある方は確認してみてはいかがでしょうか。