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

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

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

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

def update_postings(ii_entry) :
    old_pl = fetch_postings(ii_entry.token_id)
    if old_pl is not None and len(old_pl) > 0 :
        ii_entry.postings_list =  merge_postings(old_pl, ii_entry.postings_list)
        ii_entry.docs_count = ii_entry.docs_count + len(old_pl)

        ii_entry.postings_list = encode_postings(ii_entry.postings_list, 0)
        wiserdb.db_update_postings(ii_entry.token_id, ii_entry.docs_count, ii_entry.postings_list)

        return True
    elif old_pl is None :
        print "cannot fetch old postings list of token({0}) for update.".format(ii_entry.token_id)
        return False;
    else :
        print "cannot fetch old postings list of token({0}) for update.".format(ii_entry.token_id)
        return False

def update_postings(ii_entry) :

old_pl = fetch_postings(ii_entry.token_id)

if old_pl is not None and len(old_pl) > 0 :

ii_entry.postings_list = merge_postings(old_pl, ii_entry.postings_list)

ii_entry.docs_count = ii_entry.docs_count + len(old_pl)

ii_entry.postings_list = encode_postings(ii_entry.postings_list, 0)

wiserdb.db_update_postings(ii_entry.token_id, ii_entry.docs_count, ii_entry.postings_list)

return True

elif old_pl is None :

print "cannot fetch old postings list of token({0}) for update.".format(ii_entry.token_id)

return False;

else :

print "cannot fetch old postings list of token({0}) for update.".format(ii_entry.token_id)

return False

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

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

def merge_inverted_index(base_ii, to_be_added_ii) :
    for added_ii_entry in to_be_added_ii :
        base_ii_entry = token.find_token_from_index(added_ii_entry.token_id, base_ii)
        if base_ii_entry is not None :
            base_ii_entry.docs_count += added_ii_entry.docs_count
            base_ii_entry.positions_count += added_ii_entry.positions_count
            base_ii_entry.postings_list = merge_postings(added_ii_entry.postings_list, base_ii_entry.postings_list)
        else :
            base_ii.append(added_ii_entry)

    to_be_added_ii = None

    return base_ii

def merge_inverted_index(base_ii, to_be_added_ii) :

for added_ii_entry in to_be_added_ii :

base_ii_entry = token.find_token_from_index(added_ii_entry.token_id, base_ii)

if base_ii_entry is not None :

base_ii_entry.docs_count += added_ii_entry.docs_count

base_ii_entry.positions_count += added_ii_entry.positions_count

base_ii_entry.postings_list = merge_postings(added_ii_entry.postings_list, base_ii_entry.postings_list)

else :

base_ii.append(added_ii_entry)

to_be_added_ii = None

return base_ii

書籍ではマクロ 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エンコードして返すように修正しました。

エンコード処理です。

import pickle
import base64

def encode_postings(pl, alg) :
    if alg == 0 :
        return encode_postings_none(pl)
    elif alg == 1 :
        return encode_postings_golomb(pl)
    else :
        return None

def encode_postings_none(pl) :
    return base64.b64encode(pickle.dumps(pl, protocol=2))

def encode_postings_golomb(pl) :
    return pl

import pickle

import base64

def encode_postings(pl, alg) :

if alg == 0 :

return encode_postings_none(pl)

elif alg == 1 :

return encode_postings_golomb(pl)

else :

return None

def encode_postings_none(pl) :

return base64.b64encode(pickle.dumps(pl, protocol=2))

def encode_postings_golomb(pl) :

return pl

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

import pickle
import base64

def decode_postings(encoded_pl, alg) :
    if alg == 0 :
        return decode_postings_none(encoded_pl)
    elif alg == 1 :
        return decode_postings_golomb()
    else :
        return None

def decode_postings_none(encoded_pl) :
     return pickle.loads(base64.b64decode(encoded_pl))

def decode_postings_golomb(encoded_pl) :
    return encoded_pl

import pickle

import base64

def decode_postings(encoded_pl, alg) :

if alg == 0 :

return decode_postings_none(encoded_pl)

elif alg == 1 :

return decode_postings_golomb()

else :

return None

def decode_postings_none(encoded_pl) :

return pickle.loads(base64.b64decode(encoded_pl))

def decode_postings_golomb(encoded_pl) :

return encoded_pl

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

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

コメントをどうぞ

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

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

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

import pickle

def encode_postings(pl, alg) :
    if alg == 0 :
        return encode_postings_none(pl)
    elif alg == 1 :
        return encode_postings_golomb(pl)
    else :
        return None 

def encode_postings_none(pl) :
    encoded_pl = []
    for ple in pl :
        encoded_pl.append(pickle.dumps(ple, protocol=2))

    return encoded_pl

def encode_postings_golomb(pl)
    return pl

import pickle

def encode_postings(pl, alg) :

if alg == 0 :

return encode_postings_none(pl)

elif alg == 1 :

return encode_postings_golomb(pl)

else :

return None

def encode_postings_none(pl) :

encoded_pl = []

for ple in pl :

encoded_pl.append(pickle.dumps(ple, protocol=2))

return encoded_pl

def encode_postings_golomb(pl)

return pl

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

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

続いてデコード処理。

import pickle

def decode_postings(encoded_pl, alg) :
    if alg == 0 :
        return decode_postings_none(encoded_pl)
    elif alg == 1 :
        return decode_postings_golomb()
    else :
        return None

def decode_postings_none(encoded_pl) :
    decoded_pl = []
    for eple in encoded_pl :
        decoded_pl.append(pickle.loads(eple))

    return decoded_pl


def decode_postings_golomb(encoded_pl) :
    return encoded_pl

import pickle

def decode_postings(encoded_pl, alg) :

if alg == 0 :

return decode_postings_none(encoded_pl)

elif alg == 1 :

return decode_postings_golomb()

else :

return None

def decode_postings_none(encoded_pl) :

decoded_pl = []

for eple in encoded_pl :

decoded_pl.append(pickle.loads(eple))

return decoded_pl

def decode_postings_golomb(encoded_pl) :

return encoded_pl

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

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

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

コメントをどうぞ

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

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

def merge_postings(pl1, pl2) :
    result_pl = []

    # ジェネレータを使ってマージを行う
    for pl_entry in next_pl_entry(pl1, pl2) :
        result_pl.append(pl_entry)

    return result_pl

# ジェネレータ関数
def next_pl_entry(pl1, pl2) :
    pl1_idx = pl2_idx = 0
    pl1_len = len(pl1)
    pl2_len = len(pl2)
    while pl1_idx < pl1_len  or pl2_idx < pl2_len :
        if pl1_idx >= pl1_len :
            yield pl2[pl2_idx]
            pl2_idx += 1
        elif pl2_idx >= pl2_len :
            yield pl1[pl1_idx]
            pl1_idx += 1
        elif pl1[pl1_idx].document_id <= pl2[pl2_idx].document_id :
            yield pl1[pl1_idx]
            pl1_idx += 1
        elif pl1[pl1_idx].document_id >= pl2[pl2_idx].document_id :
            yield pl2[pl2_idx]
            pl2_idx += 1

def merge_postings(pl1, pl2) :

result_pl = []

# ジェネレータを使ってマージを行う

for pl_entry in next_pl_entry(pl1, pl2) :

result_pl.append(pl_entry)

return result_pl

# ジェネレータ関数

def next_pl_entry(pl1, pl2) :

pl1_idx = pl2_idx = 0

pl1_len = len(pl1)

pl2_len = len(pl2)

while pl1_idx < pl1_len or pl2_idx < pl2_len :

if pl1_idx >= pl1_len :

yield pl2[pl2_idx]

pl2_idx += 1

elif pl2_idx >= pl2_len :

yield pl1[pl1_idx]

pl1_idx += 1

elif pl1[pl1_idx].document_id <= pl2[pl2_idx].document_id :

yield pl1[pl1_idx]

pl1_idx += 1

elif pl1[pl1_idx].document_id >= pl2[pl2_idx].document_id :

yield pl2[pl2_idx]

pl2_idx += 1

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 : テンポラリ転置インデックス

となっています。

def token_to_postings_list(document_id, token, position, ii_buffer) :
    # DBよりトークンIDの取得
    (token_id, docs_count) = wiserdb.db_get_token_id(token)

    # 既存のテンポラリ転置インデックスがある
    if ii_buffer is not None :
        ii_entry = find_token_from_index(token_id, ii_buffer)
    else :
        ii_entry = None

    if ii_entry is not None :
        # トークンに紐づく既存のポスティングリストがある
        pl = ii_entry.postings_list
        exist = False
        for pl_entry in pl :
            # 既にそのトークンを含む文書がある
            if pl_entry.document_id == document_id :
                pl_entry.positions_count += 1
                pl_entry.positions.append(position)
                exist = True
                break
        # そのトークンが初登場の文書
        if not exist :
            pl_entry = InvertedIndex.PostingsListEntry(document_id, 1, position)
            pl.append(pl_entry)
            ii_entry.docs_count += 1
        ii_entry.positions_count += 1
        ii_entry.postings_list = pl
    else :
        # 紐づく既存のポスティングリストがない
        pl_entry = InvertedIndex.PostingsListEntry(document_id, 1)
        pl_entry.positions.append(position)
        ii_entry = InvertedIndex.InvertedIndexEntry(token_id, docs_count, 1)
        ii_entry.postings_list.append(pl_entry)
        ii_buffer.append(ii_entry)

    return ii_buffer

def token_to_postings_list(document_id, token, position, ii_buffer) :

# DBよりトークンIDの取得

(token_id, docs_count) = wiserdb.db_get_token_id(token)

# 既存のテンポラリ転置インデックスがある

if ii_buffer is not None :

ii_entry = find_token_from_index(token_id, ii_buffer)

else :

ii_entry = None

if ii_entry is not None :

# トークンに紐づく既存のポスティングリストがある

pl = ii_entry.postings_list

exist = False

for pl_entry in pl :

# 既にそのトークンを含む文書がある

if pl_entry.document_id == document_id :

pl_entry.positions_count += 1

pl_entry.positions.append(position)

exist = True

break

# そのトークンが初登場の文書

if not exist :

pl_entry = InvertedIndex.PostingsListEntry(document_id, 1, position)

pl.append(pl_entry)

ii_entry.docs_count += 1

ii_entry.positions_count += 1

ii_entry.postings_list = pl

else :

# 紐づく既存のポスティングリストがない

pl_entry = InvertedIndex.PostingsListEntry(document_id, 1)

pl_entry.positions.append(position)

ii_entry = InvertedIndex.InvertedIndexEntry(token_id, docs_count, 1)

ii_entry.postings_list.append(pl_entry)

ii_buffer.append(ii_entry)

return 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 はテンポラリ転置インデックスになります。

def text_to_postings_list(document_id, text, n, ii_buffer) :
    tokens = ngram_next(text, n)  # 入力文字列を N-gram に分解する
    for position, token in enumerate(tokens) :
        # 検索の場合は、最後のN-gramに満たない端文字のトークンを使わない
        if len(token) > n or document_id != 0 :
            # UTF-32 → UTF-8
            uni_text = unicode(token, 'utf-32')
            utf8_text = uni_text.encode('utf-8')

            # tokenからポスティングリストを構築
            buffer_ii = token.token_to_postings_list(document_id, utf8_text, position, ii_buffer)

    # テンポラリ転置インデックスに登録
    if ii_buffer is not None :
        postings.merge_inverted_index(ii_buffer, buffer_ii)
    else :
        ii_buffer = buffer_ii

def text_to_postings_list(document_id, text, n, ii_buffer) :

tokens = ngram_next(text, n) # 入力文字列を N-gram に分解する

for position, token in enumerate(tokens) :

# 検索の場合は、最後のN-gramに満たない端文字のトークンを使わない

if len(token) > n or document_id != 0 :

# UTF-32 → UTF-8

uni_text = unicode(token, 'utf-32')

utf8_text = uni_text.encode('utf-8')

# tokenからポスティングリストを構築

buffer_ii = token.token_to_postings_list(document_id, utf8_text, position, ii_buffer)

# テンポラリ転置インデックスに登録

if ii_buffer is not None :

postings.merge_inverted_index(ii_buffer, buffer_ii)

else :

ii_buffer = buffer_ii

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

def ngram_next(str, n) :
    token = ''
    tokens = []
    i = 0
    while i &lt; len(str) :
        for c in str[i:i + n] :
            if not is_ignored_char(c) :
                token += c
        tokens.append(token)
        token = ''
        i += 1

    return tokens

def ngram_next(str, n) :

token = ''

tokens = []

i = 0

while i < len(str) :

for c in str[i:i + n] :

if not is_ignored_char(c) :

token += c

tokens.append(token)

token = ''

i += 1

return tokens

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

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

from pprint import pprint

str = "abcdefghijklmnopqrstuvwxyz"
tokens = ngram_next(str, 2)
pprint(tokens)

from pprint import pprint

str = "abcdefghijklmnopqrstuvwxyz"

tokens = ngram_next(str, 2)

pprint(tokens)

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

['ab',
 'bc',
 'cd',
 'de',
 'ef',
 'fg',
 'gh',
 'hi',
 'ij',
 'jk',
 'kl',
 'lm',
 'mn',
 'no',
 'op',
 'pq',
 'qr',
 'rs',
 'st',
 'tu',
 'uv',
 'vw',
 'wx',
 'xy',
 'yz',
 'z']

['ab',

'bc',

'cd',

'de',

'ef',

'fg',

'gh',

'hi',

'ij',

'jk',

'kl',

'lm',

'mn',

'no',

'op',

'pq',

'qr',

'rs',

'st',

'tu',

'uv',

'vw',

'wx',

'xy',

'yz',

'z']

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

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

コメントをどうぞ

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

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

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

class tmp_ii :
    def __init__(self) :
        self.ii_buffer_count = 0 # 登録された文書数
        self.ii_buffer_count_threshold = 100 # ストレージの転置インデックスとマージする閾値
        self.ii_buffer = None # テンポラリ転置インデックス

class tmp_ii :

def __init__(self) :

self.ii_buffer_count = 0 # 登録された文書数

self.ii_buffer_count_threshold = 100 # ストレージの転置インデックスとマージする閾値

self.ii_buffer = None # テンポラリ転置インデックス

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

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

def add_document(title, body, tmp_ii) :
    if title and body :
        # DBに文書を格納し、その文書IDを取得する
        wiserdb.db_add_document(title, body)
        document_id = wiserdb.db_get_document_id(title)

        # utf8 から utf32 へ変換する
        uni_body = unicode(body, 'utf-8')
        utf32_body = uni_body.encode('utf-32')

        # テンポラリ転置インデックスを作成する
        tmp_ii.ii_buffer = token.text_to_postings_list(document_id, utf32_body, 2, tmp_ii.ii_buffer)
        tmp_ii.ii_buffer_count = tmp_ii.ii_buffer_count + 1

    # 一定数溜まったら本体の転置インデックスとマージ
    if tmp_ii.ii_buffer_count > tmp_ii.ii_buffer_count_threshold or title is None :
        for token in tmp_ii.ii_buffer :
            postintgs.update_postings(token)

def add_document(title, body, tmp_ii) :

if title and body :

# DBに文書を格納し、その文書IDを取得する

wiserdb.db_add_document(title, body)

document_id = wiserdb.db_get_document_id(title)

# utf8 から utf32 へ変換する

uni_body = unicode(body, 'utf-8')

utf32_body = uni_body.encode('utf-32')

# テンポラリ転置インデックスを作成する

tmp_ii.ii_buffer = token.text_to_postings_list(document_id, utf32_body, 2, tmp_ii.ii_buffer)

tmp_ii.ii_buffer_count = tmp_ii.ii_buffer_count + 1

# 一定数溜まったら本体の転置インデックスとマージ

if tmp_ii.ii_buffer_count > tmp_ii.ii_buffer_count_threshold or title is None :

for token in tmp_ii.ii_buffer :

postintgs.update_postings(token)

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

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

コメントをどうぞ

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

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

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

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

# 転置インデックス
class InvertedIndexEntry :
    def __init__(self, token_id=None, docs_count=None, positions_count=None, postings_list=None) :
        self.token_id = token_id
        self.docs_count = docs_count
        self.positions_count = positions_count
        if postings_list is None :
            self.postings_list = []
        else :
            self.postings_list = postings_list

# ポスティングリスト
class PostingsListEntry :
    def __init__(self, document_id=None, positions_count=None, position=None) :
        self.document_id = document_id
        self.positions_count = positions_count
        if position is None :
            self.positions = []
        else :
            self.positions = [position]

# 転置インデックス

class InvertedIndexEntry :

def __init__(self, token_id=None, docs_count=None, positions_count=None, postings_list=None) :

self.token_id = token_id

self.docs_count = docs_count

self.positions_count = positions_count

if postings_list is None :

self.postings_list = []

else :

self.postings_list = postings_list

# ポスティングリスト

class PostingsListEntry :

def __init__(self, document_id=None, positions_count=None, position=None) :

self.document_id = document_id

self.positions_count = positions_count

if position is None :

self.positions = []

else :

self.positions = [position]

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

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