渋日記@shibu.jp

by efilpera under CC BY-NC-SA

tk0miyaさんから、Python Web フレームワークアドベントカレンダーのパスが回ってきました。ちなみに当方、現在、The Art of Communityの翻訳直しが佳境なのと、本田技術研究所を辞めて転職することにしたのと、それに伴って引っ越しの準備やらで首がまったく回っていません。Pythonのアドベントカレンダーは、なぜか遅れるとバリカンという殺伐した話になっていて、恐怖で禿げそうです。あ、退職の話は年末に落ち着いたら書くかも。

今回のネタは、僕がユーザグループの会長をやっている、Sphinxのお話にしようと思います。Sphinxに関しては、@r_rudiさんが実用系の話を既に書いてくださっていますので、僕はハック方面で話をします。ちょうど冬休みですし、Pythonを使った入門 自然言語処理の本が最近出たり、前にも集合知プログラミングという面白い本が出ていたりして、空前の検索エンジン自作ブームが訪れようとしているのかもしれないけど、やっぱり自分でゼロから作るのはなぁ・・・という人向けのエントリーです。はい。読者少なそうですね。気にせずに進んで行きましょう。

Sphinxの検索の仕組み

もしかしたら、Sphinxというツールについて知らない方もいるかもしれないので、軽く紹介しておくと、ファラオのピラミッドパワーのご加護によってモテモテ間違いなし品質の高いドキュメントが素早く作成できるようになる、ドキュメントジェネレータです。PDFやHTMLで出力できますし、ePub出力や、清水川先生の開発中のWord2007出力、僕が作成中のKindleファイル出力など、夢がいくらあっても足りない！というステキツールです。「ステキすぎる！今年のクリスマスにはSphinxが欲しいわ！」と思われた方も片手で数えられないぐらいいると思いますが、サンタさんにお願いする必要はありません。なんとタダでダウンロードできます！BSDライセンスです。すばらしいですね！

SphinxではHTML出力ができるということは紹介しました。静的HTMLが出ますが、なんと検索窓が付いています。通常は、検索を実現するには、ウェブサーバ上で、CGIなりウェブアプリケーションサーバを動かし、検索して結果をHTMLで整形して返す、といったことが行われていますが、Sphinxは単なる静的ファイルのみが出てきます。どのように動作しているのでしょうか？

ヒミツはsearchindex.jsというファイルにあります。これは、make htmlを実行したときに生成されるファイルです。中には何が書かれているんでしょうか？一部抜粋してみます。

Search.setIndex({
   terms:{
    jsmath_path:38,
    autoclass_cont:[36,21],
    get_object:39,
    sourcelink:16,
    four:[0,1,26],
    objtyp:39,
    prefix:[0,7,36,30,8,39,22,35,16,27,6,17]},
  filenames: 
    ["templating","markup/para","rest","intro","examples",
     "ext/refcounting","tutorial","ext/tutorial","ext/extlinks",
     "ext/coverage","ext/graphviz","ext/autosummary"]})

Search.setIndex()という関数に、何やらオブジェクトを渡しています。オブジェクトには、termsとfilenamesというキーがありますね！感の鋭い方は気づかれたかもしれませんが、termsは、キーワードから、指定されたドキュメントのインデックスをマッピングする辞書になっています。filenamesが、そのIDに該当する、ファイル名の一覧です。SphinxのHTMLフォームで検索をかけると、そのキーワードから、そのキーワードが含まれるドキュメントのIDを見つけて、そのページを表示する、という仕掛けです。実際には、単語はもっと大量にありますし、単語以外にもtitlesや、objnamesといった、グループで、単語とドキュメントIDへのマッピングが何種類か登録されています。

もうちょっと詳しい検索の流れは次の通りです。

1. 検索キーワードのステミング処理をかける

例えば、 books と入れました。本の複数形です。ステミング処理というのは、現在形など、辞書に載っている形式に戻す処理です。辞書には特殊な単語意外は複数形では載っていませんよね？ここではbookに変わります。ちなみに、Sphinxがオフラインで作成したインデックスのsearchindex.jsにも、ステミングされた処理が入っています。つまり、原文がbooksで、検索ワードがbookでも、両方ともステミングされた後の状態で比較されるため、マッチします。

ちなみにこのステミングアルゴリズムは「ポーターステマー」という名前のアルゴリズムが使われていますが、ここの処理は結構重い処理らしく、Pythonのドキュメント1つ分をまるごとビルドすると、ここがボトルネックになってしまいます。エキスパートPythonプログラミングを一緒に翻訳した稲田さんが、ここのパッチをSphinxに送って組み込まれているのですが、現在では、もしポーターステマーのC言語の拡張モジュールがあれば、高速化のためにそれを呼ぶようになっています。

2. searchindex.jsを検索する

辞書が入っていますので、ステミングした単語を入れて検索します。このbookが含まれているドキュメントのID一覧がゲットできました。ドキュメントIDがゲットできたら、今度は実際のファイル名を調べます。

3. source/XXX.txtを調べる

目的の単語が入っているファイルが分かりました。次に、このドキュメントのソースのreSTファイルを調べに行きます。SphinxはHTMLを見るときに「ソースを見る」で、ビルドしたソースのreSTファイルが読めるようになっています。検索の詳細表示では、このファイルを利用するようになっています。このソースコードを読み込み、目的の単語を探し、その前後のテキストをくりぬいてきて、検索したファイル情報と一緒にユーザに表示します。見た目はこんな感じになります。

これらは全部JavaScriptで記述されており、クライアントのブラウザ上で検索機能が動作しています。ちょっと検索とかやったことがある方は、これだけでもビックリですよね？

検索機能をパワーアップしてみる

さてさて、単にSphinxの実装の紹介では、バリカンで襲われてしまう恐れがあるので、ちょっと手を加えてみます。文章の重要度が高いほど、上位に表示されるようにしてみます。

検索のランクを計算する方法は色々あります。表題に使われた場合には重みを増やすとか、多くのページからリンクされたら、などなど。とりあえず、今回は簡単な方法として、たくさん単語が表示されているページほどランクが高くなる、というルールを設定します。

まずはsphinx/search.pyを見てみましょう。HTMLにビルドすると、IndexBuilderクラスのfeedメソッドが呼ばれ、単語が登録されていきます。今までは単なるドキュメントのリストだったのを、単語数の重み情報つきの情報にしなければなりません。

        # 変更前。feedの内部関数のadd_term。
        def add_term(word, stem=self._stemmer.stem):
            word = stem(word)
            if len(word) < 3 or word in stopwords or word.isdigit():
                return
            self._mapping.setdefault(word, set()).add(filename)

self._mappingというのが、単語をキーにして、ファイル名のセット型を値に持つ辞書になっているようです。重要度を保持するということで、単語の出現回数を保持したいと思います。そこで、セット型の代わりに辞書型を持たせて、カウンタとします。

        # 変更後。feedの内部関数のadd_term。
        def add_term(word, stem=self._stemmer.stem):
            word = stem(word)
            if len(word) < 3 or word in stopwords or word.isdigit():
                return
            files = self._mapping.setdefault(word, {})
            files[filename] = files.get(filename, 0) + 1

次に、出力部をいじります。freeze()メソッドの結果が、JavaScriptのコードに埋め込まれますが、この中で、get_terms()メソッドを呼び出し、単語とドキュメントIDの辞書を出力しています。

    # 変更前
    def get_terms(self, fn2index):
        rv = {}
        for k, v in self._mapping.iteritems():
            if len(v) == 1:
                fn, = v
                if fn in fn2index:
                    rv[k] = fn2index[fn]
            else:
                rv[k] = [fn2index[fn] for fn in v if fn in fn2index]
        return rv

forループの行を書き換えます。本来はセット型だったのですが、今は辞書が入っています。これを単語出現数でソートして、キーだけの配列を生成するようにしました。試しに、この周辺にprint文でも仕込んでみると、動きが良く観察できるでしょう。

        for k, v_with_rank in self._mapping.iteritems():
            sorted_v = sorted(v_with_rank.items(), key=lambda i: -i[1])
            v = [i[0] for i in sorted_v]

さて、make htmlしてみると・・・エラーが出ました。Sphinxは複数のソースをまとめてビルドしますが、余計なファイルを削除するコードがあり、現在のドキュメントのsetと積集合をとることでゴミを削除しています。ただ、このメソッドはセット型のメソッドで、辞書にはないので、なんとなく動きをエミュレートします。

    def prune(self, filenames):
        """Remove data for all filenames not in the list."""
        new_titles = {}
        for filename in filenames:
            if filename in self._titles:
                new_titles[filename] = self._titles[filename]
        self._titles = new_titles
        for wordnames in self._mapping.itervalues():
            # 変更前はこの一行
            # wordnames.intersection_update(filenames)
            for filename, rank in list(wordnames.iteritems()):
                if filename not in filenames:
                    del wordnames[filename]

とりあえず、一番最初にあげたサンプルでは、prefixという単語がいっぱい使われているようです。実際にこのコードを走らせて、prefixという単語の出現数とファイル名のペアの配列を表示してみると、次のような感じです。

prefix [('domains', 8), ('ext/extlinks', 7), ('ext/intersphinx', 2), ('markup/inline', 2), ('templating', 2), ('markup/toctree', 1), ('ext/tutorial', 1), ('changes', 1), ('ext/appapi', 1), ('ext/inheritance', 1), ('config', 1), ('tutorial', 1)]

domainsという所にいっぱいあるみたいですね。ノーマル状態のSphinxで検索をかけてみると、changes、ext/appapi, tutorialという順番に表示されます。ここで、手を加えたエンジンを使って検索をかけてみると・・・・

緊急事態発生

あれ？ノーマルのSphinxと同じ順序で表示される(汗・・・現在23:53。調査突入・・・あ、日付変更線が頭を越えた。

その後、調査した結果、JavaScript側で、ファイル名でソートをかけている、ということが判明。敵はJavaScriptにあり。ということでごにょごにょ修正した結果は↓ここに置いておきます。JavaScript側の修正と、それ以外の修正のdiffはまとめてこちらに掲示しましたので、参照してください。

• http://paste.pocoo.org/show/305624/

簡単に書くと、検索結果のファイル一覧を辞書に格納しているので、キーの順番を保持する配列を用意(351行目のfileMapKey)して、検索時の単語数順の配列の順序を保持するようにしたのと、ファイル名でのソートの行を消しました。これで、希望通りの順番で表示されるようになりました。一時間のタイムロス・・・すみませんすみません。

今後の遊び方

さて、トラブルはありましたが、検索機能のハックが完了しました。登場単語の多い順で検索ができるようになりました。ブラウザで検索するため、インデックスが巨大になってしまうn-gram方式はSphinxではちょっと難しかったり、さまざまな制約はあります。ですが、今回みたいにインデックスされる順番を工夫することで検索の性能を上げることができます。集合知プログラミングを読んだけど、検索インデックス作る材料がないなぁ、という人は、ぜひSphinxの検索機能をネタにハックしてみてください。

例えば、多くのページから参照されている場合にはランクを上げる(ページランク)、同じ単語が集中的に表示されるパラグラフのスコアを上げるなど、少ないデータながら、工夫のしがいはあります。また、同じようなページベクトルを持つ単語は類似の単語として、ユーザにリコメンドしたりできるする余地もあります。

Sphinxは文章を書くツールとしても優秀ですが、文章情報をプログラム的にさまざまに加工する、文書プロセッサとしても利用可能です。今後はこのあたりのノウハウも増やしていきたいと思います。

え？どこがウェブのフレームワークだって？

SphinxはHTMLが生成できて、ブラウザ側で検索もできちゃうんですよ。静的ファイルだけを配布するサーバを用意すればそれでOK。パフォーマンスなんてそんなにいらないです。なんか、CO2を25%減らすとか外に約束してしまった政治家の先生とかいるし、SphinxをCMSとして使ってCO2削減！と売り込めないかなぁ、と画策中。ストレージが全部メモリで、CPUがARMとかで、静的ファイル配信専用のウェブサーバーとかってないんですかね？

次は@RyoAbeさんにバトンを渡したいと思います。