Google App Engineで全文検索(その2)

http://d.hatena.ne.jp/intheflight/20100107/p1
の続き
 前回のModelを見直してN-gram転置インデックスのModelが明らかに冗長な構造をしていることに気付いた。N=2として、その2文字をModelのkey_nameとして使えばもっとシンプルになるのではないか。N-gramのすべての2文字はユニークなんだし。幸いModelのkey_nameはUnicodeも大丈夫なようなので、Modelを以下のように書き換えた。ついでにテキストのModelキーと文字の位置情報を一つにまとめていたindex_listをまとめずにtext_listとposition_listに分割したまま保存することにした。
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):
    text_list = db.ListProperty(int)
    position_list = db.ListProperty(int)

後はModel変更に伴うインデックス作成と削除、検索の関数を書き換え。Datastoreからのクエリー取得はkey_nameを使うことからget_by_key_nameにする。

# make inverted index
class Indexer():
    def make_index(self, text=''):
        
        if len(text) == 0:
            return True
        elif len(text) <= 1:
            return False
        elif 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):
            while True:
                if self.put(text, id, i):
                    break
        
        return True
    
    def put(self, text, id, num):
        try:
            q = InvertedIndex.get_by_key_name(text[num:num+2])
            if q is None:
                q = InvertedIndex(key_name=text[num:num+2])
                q.text_list.append(id)
                q.position_list.append(num)
                q.put()
            else:
                q.text_list.append(id)
                q.position_list.append(num)
                q.put()
        except:
            return False
        return True

# 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 = InvertedIndex.get_by_key_name(query[i:i+2])
            if q is None:
                return None
            index_lists.append(zip(q.text_list, map(lambda x: x-i, q.position_list)))
        
        
        result = []
        for head in index_lists[0]:
            if len(index_lists) == 1:
                result.append(head)
                continue
            
            text_id = head[0]
            text_pos = head[1]
            search_flg = False
            for i in range(1, len(index_lists)):
                search_flg2 = False
                for j in range(len(index_lists[i])):
                    if text_id == index_lists[i][j][0] and text_pos == index_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

# delete old text and inverted index
class RefreshClient():
    def refresh(self, delete_time):
        texts = Text.all().filter('created <', delete_time)
        
        if texts is None:
            return
        
        for text in texts:
            id = text.key().id()
            for i in range(len(text.content)-1):
                q = InvertedIndex.get_by_key_name(text.content[i:i+2])
                if q is None:
                    continue
                for i in range(len(q.text_list)):
                    if id == q.text_list[i]:
                        q.text_list.remove(id)
                        p = q.position_list[i]
                        q.position_list.remove(p)
                        break
                if len(q.text_list) > 0:
                    q.put()
                else:
                    q.delete()
            
            text.delete()