Google App Engineで全文検索
調べた限りGAEには(日本語を)全文検索する機能はついてない。なのでちょっくら作ってみました。一応動くのは出来たけど、いろいろ不満な点が多い。転置インデックスはN-gramでN=2で作成。サンプルをサイトで公開してますが、検索は完全一致で結果の順位は考慮してません。最もシンプルなシステムで、検索語句を入力すると、Datastoreに格納されているその語句が含まれる文章を表示し、検索語句を強調表示します。また、100文字以下の文章ならDatastoreに格納できます。何故100文字以下かというと、文字数が多くなるとそれに伴い転置インデックスの作成量を増えていきます。となると、処理時間も長くなってGAEの処理時間オーバーのエラーが発生してしまう。うーん、もっと効率のよい転置インデックスの作成方法がないものか。全文検索の心臓部分のコードは以下の通り。GitHubにも置いてます。
http://gist.github.com/270211
サンプルサイトはこちら。
http://yuribossa.appspot.com/zenbun/index
from google.appengine.ext import db class Text(db.Model): content = db.StringProperty(multiline=True) created = db.DateTimeProperty(auto_now_add=True) class InvertedIndex(db.Model): word = db.StringProperty(multiline=True) index_list = db.StringListProperty() # make inverted index class Indexer(): def make_index(self, text=''): if len(text) <= 1 or len(text) > 100: return False try: tx = Text(content=text) tx.put() id = tx.key().id() except: return False for i in range(len(text)-1): q = db.Query(InvertedIndex).filter('word =', text[i:i+2]) if q.count() == 0: q = InvertedIndex() q.word = text[i:i+2] q.index_list.append(str(id) + ' ' + str(i)) q.put() else: q = q.get() q.index_list.append(str(id) + ' ' + str(i)) q.put() return True
Indexerはテキストから転置インデックスを作るクラス。転置インデックスとは別にテキストはDatastoreに保存しておく。転置インデックスにはその保存したテキストのキーと文字の位置を一緒に格納します。コードからもわかるとおり、ここでDatastoreに大量のリクエストが発生するので、それが処理時間のボトルネックになってる。これはもう転置インデックスの格納方法を根本的に変えなければ速度アップは望めないと思う。
# search text by query class SearchClient(): def search(self, query): if len(query) < 2: return None index_lists = [] for i in range(len(query)-1): q = db.Query(InvertedIndex).filter('word =', query[i:i+2]) if q.count() == 0: return None index_lists.append(q.get().index_list) i = 0 id_pos_lists = [] for index_list in index_lists: list = [] for index_str in index_list: str = index_str.split() list.append((int(str[0]), int(str[1])-i)) id_pos_lists.append(list) i += 1 result = [] for head in id_pos_lists[0]: if len(id_pos_lists) == 1: result.append(head) continue text_id = head[0] text_pos = head[1] search_flg = False for i in range(1, len(id_pos_lists)): search_flg2 = False for j in range(len(id_pos_lists[i])): if text_id == id_pos_lists[i][j][0] and text_pos == id_pos_lists[i][j][1]: search_flg2 = True break if search_flg2: search_flg = True else: search_flg = False break if search_flg: result.append(head) return result
SearchClientは検索語句を受け取り検索結果の配列を返すクラス。返す配列の要素はテキストのキーと検索語句の位置情報のタプル。
# delete old text and inverted index class RefreshClient(): def refresh(self, delete_time): texts = db.Query(Text).filter('created <', delete_time) for text in texts: for i in range(len(text.content)-1): q = db.Query(InvertedIndex).filter('word =', text.content[i:i+2]) q = q.get() for index in q.index_list: x = index.split() if text.key().id() == int(x[0]): q.index_list.remove(index) break if len(q.index_list) > 0: q.put() else: q.delete() text.delete()
RefreshClientはTextモデルのcreatedを元にテキストと転置インデックスを削除するクラス。時間を引数で与えて、その時間よりも古いデータを削除する。
それで作りながら思ったことは、小さい全文検索システムなら正規表現で探したほうが速いんじゃないかということ。どうなんだろ。そもそもGAEのようなリソースに制限のある環境で全文検索は無謀なのか。そこら辺をもう少し突っ込んで調べてみたい。