カテゴリー別アーカイブ: 自然言語処理

検索エンジン自作入門/ wiserのPython移植(7)

検索エンジン自作入門/ wiserのPython移植(5)で作ったmerge_postings を呼び出す側の、二つの関数 merge_inverted_index と update_postingsを実装します。

最初に update_postings から。これはストレージ上のポスティングリストとメモリ上のポスティングリストをマージして、その結果をストレージに保存します。引数はメモリ上の転置インデックスのエントリです。書籍は77ページ。

fetch_postings は、トークンIDでトークンに紐づくポスティングリストをストレージから検索します(2行目)。ストレージに該当するトークンがなければエラーを返します(13、16行目)。あれば、メモリ上のポスティングリストとマージした結果でdb_update_postings でストレージを更新します(8行目)。

次にmerge_inverted_indexです。ふたつのメモリ上の転置インデックスをマージします。引数はマージするふたつの転置インデックスです。書籍は79ページ。

書籍ではマクロ HASH_FIND_INT  で行っているマージ先からのトークンの検索は、関数 find_token_from_index で行っています(3行目)。merge_postings でポスティングリストをマージしているのは、update_postings と同じです(7行目)。

これで、転置インデックスの構築する部分で残るは、検索対象の文書(書籍と同じようにWikipediaにしようと思ってます)をインポートする処理だけとなりました。だいぶかかってしまった・・・。次回はWikipediaで提供するXMLをlxmlを利用してインポートする処理を作ります。

正直、設計にしろPythonの使い方にしろこれでいいのかなと思いながら作ってますが、Wikipediaから転置インデックスが作れればまずはOKということにします。

検索エンジン自作入門/ wiserのPython移植(6) 修正

前回、ポスティングリストのエンコードとデコードの処理を、pickleモジュールを使って作りました。

ところが、MySQLに保存するときポスティングリストはTEXTのカラムに格納することを忘れてました。そこで、pickle化したものをさらにbase64エンコードして返すように修正しました。

エンコード処理です。

デコード処理はbase64デコードします。

このシリーズはPythonの勉強を兼ねてやっているんですが、検索エンジンは言語の勉強にとてもいいです。いろんな要素を動員しますから。

検索エンジン自作入門/ wiserのPython移植(6)

久しぶりの更新になってしまいました。

今回は merge_inverted_index と update_postings のはずだったのですが、update_postings でデータベースにポスティングリストを保存したり取り出したりするときにエンコード処理が必要になるので、それを先に作ることにします。これは書籍でいうと第5章「転置インデックスを圧縮しよう」にありまして、今回は圧縮なしで取得・保存する処理だけ作ります。ページはP109からP113になります。

まずはエンコード処理。引数は、ポスティングリストと圧縮するかしないかの指定です。

pickleモジュールを用いてシリアライズを行います。

Python2.7の場合、シリアライズを行う pickle.dumps メソッドの第2引数で protocol=2 を指定する必要があるようです。

続いてデコード処理。

やってることは単純です。

後で圧縮を行うときは、encode_postings_golomb などに圧縮処理を実装することになります。

検索エンジン自作入門/ wiserのPython移植(5)

今回は、書籍のページ順と前後しますが、ふたつのポスティングリストのマージを行うmerge_postings です。書籍のページは80ページです。

引数は、マージするポスティングリストふたつです。

merge_postingsは、document_id の小さい方のポスティングを選んで結果のリストにマージしていくというC言語版の処理を、ジェネレータ関数のnext_pl_entry を呼び出しながら行っていく作りにしてあります。

ジェネレータをきちんと使ったことがなかったのですが、今回勉強になりました。繰り返しをスッキリ書けてよいですね。

次回は、今日作った関数を呼び出す merge_inverted_index と update_postings です。メモリ上のテンポラリ転置インデックス同士や、ストレージ上の本体の転置インデックスとをマージします。

検索エンジン自作入門/ wiserのPython移植(4)

前回実装した text_to_postings_list 内で呼んでいる、token_to_postings_list を実装します。書籍のページは75ページです。この関数は、一つのトークンを受け取ってテンポラリ転置インデックスに登録します。

引数は、

  • document_id : 文書ID
  • token : トークン
  • position : トークン出現位置
  • ii_buffer : テンポラリ転置インデックス

となっています。

オリジナルはマクロでトークンに紐づいたポスティングリストを探しますが、Python版では関数 find_token_from_index により検索します(7行目、コード略)。

その後は、紐づいたポスティングリストの有無によりパラメータをインクリメントしたり、新しくインデックスやポスティングリストのエントリを生成したりします。エントリの生成はC版で専用に関数を作ってますが、Python版ではインスタンスの生成で行うことになります。

ところで、Pythonのユニットテスト界隈はどうなっとるんじゃと調べてみたのですが、unittestから始めてみるのが無難みたいですね。こうやってコードを掲載していってますが、ngram_next 以外はテスト結果を載せてませんね。今日の token_to_postings_list もお手製のテストは通過してますが、そろそろ unittest を使ってみようかと思ってます。

次回は、text_to_postings_list から呼び出される merge_inverted_index です。メモリ上の二つの転置インデックスをマージします。

検索エンジン自作入門/ wiserのPython移植(3)

前回作成した add_document で呼び出している未実装の関数を実装していきます。

add_document の4行目と5行目で呼び出している、db_add_document と db_get_document_id は、データベースを扱う処理です。転置インデックスの本体はDBに格納します。wiser では SQLite を使用していますが、移植にあたって MySQL を利用することにします。Python からの MySQL の利用は、MySQL Connector/Python を利用することにしました(簡単なので)。

https://dev.mysql.com/downloads/connector/python/

これらの関数のコードについては、検索エンジンの本筋ではないので省略します。

次に、12行目で呼んでいる転置インデックスの構築処理 text_to_postings_list に入って行きます。

渡された文字列(文書の本文)をトークンに分解し、それを token_to_postings_list (未実装)に渡してポスティングリストを作成します。既存のテンポラリ転置インデックスがあれば、できたポスティングリストとマージします。なければ新規にテンポラリ転置インデックスを生成します。

Python のドキュメントスタイルなどはまだよくわからないので、ここで引数の説明をしておくと、document_id はデータベースに登録された文書のID、text は処理対象の文書の本文、n は何-gram で切り出すか、ii_buffer はテンポラリ転置インデックスになります。

文書をN-gramに分解する関数 ngram_next を中で呼んでいます。ここは、C版では for 文の条件部で逐一呼び出す形になってますが、Python版では一回の呼び出しで文書内のすべてのトークンを返す作りに変えてあります。

is_ignored_char は検索対象外文字列を弾くためのものです。コードは省略します。

ngram_next はこれで実行できるようになりましたので、bi-gram で動かしてみます。

結果は以下の通りです。bi-gram に分解できました。

未実装の token_to_postings_list と merge_inverted_index を、次回実装していきます。

検索エンジン自作入門/ wiserのPython移植(2)

転置インデックスの構築のエントリポイントの関数 add_document です。書籍のページは69ページになります。

文書をN-gramトークンに分解し、転置インデックスを構築していきます。まずメモリ上のテンポラリ転置インデックスが更新され、それがある程度大きくなればストレージ上の本体の転置インデックスとマージされます。

テンポラリ転置インデックスは、C言語版ではwiser全体の環境情報を保持する構造体にあります。Python版ではクラスを作成します。

wiserは、Wikipediaの情報のXMLを解析して転置インデックスを構築します。

C言語版では、add_document は XML のロード処理のコールバック関数として実装してあります。Python版では、呼び出し側がまだ決まってませんので、とりあえず引数としてテンポラリ転置インデックスのインスタンスを渡すようにしておきました(tmp_ii)。

いくつかの関数は未実装なのでこのままでは動きませんが、この後実装していきます。

検索エンジン自作入門/ wiserのPython移植(1)

2014年に発売された技術評論社の「検索エンジン自作入門」という本があります。しばらく放置していたのですが、この本のC言語で書かれたコードをPythonに移植してみます。

C言語は学生時代に普通に勉強して以来あまり読むこともなかったのですが、ポインタ以外は何とかなるものですね。ポインタも文字列の扱いがほとんどですし。

書籍のサンプルコードのダウンロードはこちらからできます。

まずは、胆となる転置インデックスとポスティングリストのデータ構造です。

構造体をクラスに変更しただけになります。

次回から、転置インデックスの構築の処理を移植していきます。