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のようなリソースに制限のある環境で全文検索は無謀なのか。そこら辺をもう少し突っ込んで調べてみたい。