Google App Engine には今のところ全文検索機能がないので、色々試してみた。
検索処理についての知識は、Web+DB Pressの53号を読んだ程度。
やりたいことは、
Twitterみたいな感じで各ユーザーが短い文章を登録するようなサービスで、その発言内容からキーワード検索したい。
できれば、スペース区切りで複数のキーワードを指定して絞り込みができるようにしたい。
appengineなので、インデックス作成や検索処理だけで割り当てがなくならない程度に効率的に。
下記の3つの方法を試してみた。
で、結果として、3番目のオーソドックスなn-gramが今のところうまく動いてるっぽい。
失敗パターンにも色々学ぶところはあったので、それぞれメモをまとめておく。
接尾辞配列もどき
まず最初に試したのがこれ。
接尾辞配列というのは今回のサービス例でいうと、
各発言の内容を1文字、2文字と先頭から文字を切り取った内容をインデックス化するというもの。
たとえば、「こんにちは」という発言があったら、
「こんにちは」「んにちは」「にちは」「ちは」「は」
みたいな感じでインデックスを作る。
このインデックス方法の詳細については僕も多分よく理解していないので各自調べてもらうとして、
とりあえずこの方法ならばappengineの前方一致検索を使って検索できるんじゃないかと思った。
多分できるんだけど、僕の失敗は、
「各発言にsufarrっていうリストプロパティを作ってそこにこの接尾辞配列を入れたらいいんじゃない」
と考えてしまったところ。
1つの発言のインデックス作成にput()を1回実行するだけで済むし、
新しいインデックス用クラスを作らなくていいし楽だと思ったんだけど、
どうやらリストプロパティの内容で前方一致検索ができないっぽい。（できるのかもしれないけど、うまく動作しなかった）
こんな感じで検索処理を書いてた。
... def search_tweet_list(search_words, limit=20): word_list = search_words.strip().split(" ") q = Tweet.all() for word in word_list: q.filter("sufarr >=", word) q.filter("sufarr <", word + u"\ufffd") q.order("-sufarr") tweet_list = q.fetch(limit) return tweet_list ...
リストプロパティの値がフィルタされるわけじゃないので、
これだと前方一致検索にはならん、ということだと思ってる。
n-gramもどき
次に試したのがこれ。
前方一致検索がだめなら、リストプロパティの値を完全一致検索すればいいんじゃない？
n-gramというのは、これもざっくりした理解だけど、
発言した内容をn文字ずつに分けてインデックス化する。
たとえば、「こんにちは」という発言を2-gramでインデックス化する場合、
「こん」「んに」「にち」「ちは」
みたいな感じでインデックスを作る。
で、検索する時も検索文字列を同じ2-gramで分割して、
同じ順番と組み合わせを持つ発言を抽出する。
ということで、
リストプロパティに2-gramでインデックスを入れて、
とりあえず順番は気にせず、検索された文字列が全て含まれてたらヒットさせちゃおう、
と考えた。
で、実際こんな感じで検索処理を作ってみた。
... def search_tweet_list(search_words, limit=20): def create_ngram(s, ngram_length): sa = [] for i,c in enumerate(s): sa.append(s[i:i+ngram_length]) return sa word_list = create_ngram(search_words.replace(" ", ""), NGRAM_LENGTH) if word_list and len(word_list[-1]) < NGRAM_LENGTH: word_list.pop() q = Tweet.all() for word in word_list: q.filter("sufarr =", word) q.order("-twid") tweet_list = q.fetch(limit) return tweet_list ...
実は一応ちゃんと検索できてるっぽかったんだけど、
この方法を使うと、検索文字列が長いほど、appengineのデータストアインデックスが必要になっちゃう。
これをインデックス爆発というのかな？
とりあえず他の方法を探すことにした。
オーソドックスn-gram
で、今採用している方法がこれ。
オーソドックスと書いてるけど、本当にオーソドックスかどうかは分からない。
単にWeb+DB Pressの記事に書いてあることをできるだけ守って作った。
前の2つの方法では、発言にインデックス用のリストプロパティを作成してたけど、
これはappengineのput()に時間がかかるので、最大500文字入る発言をput()しようとしたら
500個もエンティティを作成しなきゃいけないから、絶対無理なんじゃないの？と思ってたから。
でも調べてみると、バッチput（db.put）を使えば
パラレルでputが実行されるようなので、大量putでも
意外といけるかも、と考えなおした。
ここ参照。
http://googleappengine.blogspot.com/2009/06/10-things-you-probably-didnt-know-about.html
なので、こういうインデックス用モデルを作成。
... class TweetSearchIndex(db.Model): """key_name is (term)/(page from 1)""" term = db.StringProperty() twmap = db.BlobProperty() is_full = db.BooleanProperty(default=False) def set_twmap(self, twmap_dict, compress=True): self.twmap = serializer.dumps(twmap_dict, compress) def get_twmap(self): return serializer.loads(self.twmap) if self.twmap else None ...
エンティティはターム（2-gramなら、2文字の文字列）をキーとする。
twmapにはそのタームが含まれる発言とその出現位置を格納する。
発言キーをキーとして、出現位置リストを値として持つ辞書をシリアライズしたデータで格納。
1MBの制限があるので、ある程度twmapのサイズが大きくなったら
is_fullをTrueにして、pageをインクリメントしてエンティティを分ける。
cronでインデックス作成処理を呼び出し、
発言を数件ずつインデックス化していく。
エンティティの保存はdb.putで一括登録してるけど、
今ちょうどインデックス化処理を流してるところで、まだ使えるレベルかどうかは分からない。
3件ずつインデックス化してるけど、とりあえず30件分は5-10秒/3件で処理できてるみたい。
検索処理は
検索文字列をn-gramで分解して、ヒットしたタームからtwmapを読み込んでマージしてる。
とりあえずgetだけで発言リストが取得できてるので速いとは思うんだけど、
発言が増えるとメモリ使用量が結構大きくなりそうで対策が必要になりそう。
100MBくらいまでは使えるみたいだけど。
ひとまず動くのは動いてる。データストアインデックスも使わないし、複数キーワード検索にも対応できた。
ソースはまだグッチャグチャなので、またテストが終ったらまとめたい。
