全文検索エンジンを試作してみたよ
今日は奥様とタイ料理&タイ式マッサージの日でした。マッサージはちょっと素晴らしいなあ。
表題のように、全文検索エンジンをGAE上で試作してみました。GAEはGoogle様提供のサービスにもかかわらず「なんで全文検索機能がないねん」という声が上がっていたんですよね。主にtwitter界隈から。
「Introduction to Information Retrieval」という本のドラフトPDFと、たつをさんのところのIIR輪講の資料を参考に作りました。つっても、第1章の一部の知識しか使ってないですが。論理和検索もスキップリストも使ってないし(論理和検索はクエリ式のパーサを書くのが面倒だった)。
import logging import re from urllib import urlencode import wsgiref.handlers from google.appengine.ext import db from google.appengine.ext import webapp from google.appengine.api import urlfetch #設定情報 class Registry(db.Expando): pass #ドキュメント class Document(db.Expando): text = db.TextProperty() #ドキュメントのテキスト docid = db.IntegerProperty() #docid #インデックス class Index(db.Expando): termref = db.ReferenceProperty() #termへの参照 docid = db.IntegerProperty() #ドキュメントへの参照 #ターム class Term(db.Expando): term = db.StringProperty() #タームの表現 indexCnt = db.IntegerProperty() #タームの出現回数 class SearchEngine: def tokenGenerator(self, text): """ インデクサとして機能するジェネレータ。 インデクサはプラグイン式にしたほうが本当はよいハズ。 Yahooの形態素解析器で形態素を取得し、形態素をトークンとして認識する。 副詞など検索に使われないだろうPOSは除外している。 """ #形態素解析器に問い合わせ。 #POSTメソッド時は、payload指定が必要。 #payloadはurlencodeする必要有り。urlencodeの引数はencodeする必要有り???よくわからない。 #headersに以下の指定が必要。 res = urlfetch.fetch("http://api.jlp.yahoo.co.jp/MAService/V1/parse", method=urlfetch.POST, headers={'Content-Type':'application/x-www-form-urlencoded'}, payload=urlencode({ 'appid': 'gae_search', 'sentence' : text.encode('utf-8'), 'results' : 'ma', 'response' : 'surface', 'filter' : '1|2|3|4|5|6|7|8|9|10'})).content #surface要素の中のテキストを抽出 for surface in re.finditer(r"<surface>(.*?)</surface>",res): logging.info("token; %s" % surface.group(1)) yield unicode(surface.group(1), 'utf-8') def registerDocument(self, text): """ ドキュメントの登録 """ #レジストリを取得。なければ生成。 registry = Registry.get_or_insert("instance") try: #いまから作成するドキュメントのdocid docid = registry.docid except: registry.docid = 0 docid = registry.docid #ドキュメント作成 doc = Document() doc.docid = docid doc.text = text doc.put() #ドキュメントをトークナイズし、トークンごとにインデックスを作成する。 tokens = {} for token in self.tokenGenerator(text): #トークンに対するタームが既に作成済みなら、ループをスキップ if tokens.has_key(token): continue tokens[token] = True index = Index() index.docid = docid #トークンに対応するタームを取得。なければ作成。 term = db.GqlQuery("SELECT * FROM Term WHERE term=:1", token).get() if term == None: term = Term() term.term = token term.indexCnt = 0 term.put() #インデックスにタームを結びつけて、登録。 index.termref = term index.put() term.indexCnt += 1 term.put() #最新のdocidを+1。本当はトランザクション内でやらないとダメ。 registry.docid += 1 registry.put() return doc def search(self, query): """ 検索。 queryを形態素解析して得られたトークンで検索をかける。 """ #queryから得られたトークンでTermクラスインスタンスを検索し、termsに格納 #リスト内包を怖々と使ってみる terms = [db.GqlQuery("SELECT * FROM Term WHERE term=:1", q).get() for q in self.tokenGenerator(query)] #termsをインデックスの少ない順に並べ替え。検索結果にintersectionかけるときに有利なるため。IIR本参照。 #lambdaを怖々と使ってみる。 #Rubyと違ってsortは破壊的で、処理結果を返値にしない(ので、for term in terms.sort(....)とは書けない) terms.sort(lambda x, y: int(x.indexCnt - y.indexCnt)) #各タームに対応するインデックスを取得し、intersectionしていく。 indices = None for term in terms: indices = self.intersection(db.GqlQuery("SELECT * FROM Index WHERE termref=:1 ORDER BY docid", term).fetch(1000), indices) #この時点で、indicesには解となるドキュメントへのインデックスが集まっている return [db.GqlQuery("SELECT * FROM Document WHERE docid = :1", index.docid).get() for index in indices] def intersection(self, lhs, rhs): """ リストlhsとrhsのintersectionをとる。 IIR本参照 """ if rhs == None: return lhs result = [] il = ir = 0 while il < len(lhs) and ir < len(rhs): idl = lhs[il].docid idr = rhs[ir].docid if idl < idr: il += 1 elif idl > idr: ir += 1 else: result.append(lhs[il]) il += 1 ir += 1 return result engine = SearchEngine() class Register(webapp.RequestHandler): def post(self): doc = engine.registerDocument(self.request.get("text")) self.response.out.write("registered(id=%d); %s" % (doc.docid, doc.text)) class Search(webapp.RequestHandler): def get(self): self.response.out.write("<html><body>") results = engine.search(self.request.get("query")) for doc in results: self.response.out.write("%s<br>" % doc.text) self.response.out.write("</body></html>") application = webapp.WSGIApplication([ ('/register', Register), ('/search', Search) ], debug=True) def main(): wsgiref.handlers.CGIHandler().run(application) if __name__ == '__main__': main()
ローカルサーバだとこのまま動きますが、GAEにアップロードするときには日本語で書かれたコメントを全部除去しないと動きませんでした。なんでだろ。
Yahoo!形態素解析サービスを使ってトークナイズしているため、GAEサーバよりタイムアウトで蹴られてしまう(GAEサーバ内のリクエスト処理が数秒以上かかると処理が強制中断されてしまう)んじゃないかと心配していましたが、あんまり心配ないようです。よかった。
ここでのお勉強のまとめ。
- GAE的なもの
- Python的なもの
- IR的なもの
- Yahooの形態素検索サービス、いいなあ。解を品詞でフィルタできたりとか、そういうのも便利。
- 基本形も解として返してくれるので、インデックスを作るときには基本形もインデックスに入れたほうがいいだろう。
- GAEのクエリでは解を最大1000個しか返してくれないので、全文検索の処理速度を上げても実はあんまり意味ない。処理速度が問題になるほど多くの文書を登録できない。
- このプログラムを拡張していくなら、インデクサはプラグイン式にすべき。
- 形態素解析器をインデクサとして使う検索エンジンに共通の弱点だが、解析結果によってインデックスの作られ方が意図しないものになってしまう。ノーマライズやらquey expansionやらしないと品質が低いまま。あんまりインデクサに手を入れられないのであれば、N-gramでインデックスを作ったほうが良い解が得られるだろう。GAE上で検索エンジン作るなら、形態素とN-gramを併用するんだろうな。
