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()