Python プログラム中で文書を検索する場合、 以下のクラスを使います。
Document
(ひとつの文書)
Corpus
(文書の集合)
Predicate
(述語 = ひとつの検索条件)
Selection
(検索条件に該当する文書)
Document
と Corpus
は抽象的な
文書および文書の集合を表すクラスです
(実際には HTMLDocument
や FilesystemCorpus
などの派生クラスを使います)。
Corpus
オブジェクトと複数の Predicate
オブジェクトから
Selection
(該当する文書) オブジェクトを作成します。
ここから Document
オブジェクトをひとつずつ取り出し、検索結果として表示します。
# 基底ディレクトリ /doc/Python-2.4-ja にある HTML 文書と、 # /tmp/index にあるインデックスを使って検索する例 from fooling.corpus import FilesystemCorpus from fooling.document import HTMLDocument from fooling.selection import Predicate, Selection # 検索する文書集合の基底ディレクトリとインデックス用ディレクトリ、および文書の種類を指定する: corpus = FilesystemCorpus('/doc/Python-2.4-ja', '/tmp/index', HTMLDocument) # 検索条件を作成する (これらは AND で結合される) : predicates = [ Predicate(u'Python'), Predicate(u'オブジェクト') ] # 該当する文書の一覧を得る: selection = Selection(corpus, predicates) # すべての該当文書のタイトルと snippet を表示する: for (found, doc) in selection: print found, doc.get_title(), doc.get_snippet(selection)
Selection
オブジェクトはリストとしても扱えますが、
内部ではイテレータになっており、
文書をひとつ取得するたびに次の文書を漸進的に検索します。
すべての文書を表示すると時間がかかるため、途中でやめてもかまいません。
Selection
オブジェクトは pickle
可能なので、
途中まで検索した Selection
オブジェクトを pickle 保存しておき、
あとで検索を再開することが可能です。
CGI から使う場合は SelectionWithContinuation
クラスを参照してください。
インデックスの際には Corpus
クラスと
Indexer
クラスを使います:
# 基底ディレクトリ /doc/Python-2.4-ja にある HTML 文書から # /tmp/index 以下のディレクトリにインデックスを作成する例 from fooling.corpus import FilesystemCorpus from fooling.document import HTMLDocument from fooling.indexer import Indexer # 検索する文書集合の基底ディレクトリとインデックス用ディレクトリ、および文書の種類を指定する: corpus = FilesystemCorpus('/doc/Python-2.4-ja', '/tmp/index', HTMLDocument) # 文書集合に対する Indexer オブジェクトを作成する: indexer = Indexer(corpus) # 文書をインデックスに追加する。 # これらは基底ディレクトリからの相対パス名で指定する: indexer.index_doc('a.html') indexer.index_doc('b.html') indexer.index_doc('c.html') # インデックスを完了する: indexer.finish()
最後の indexer.finish()
を実行した時点で
インデックスファイルがディスクに書き込まれます
(これ以前にも、文書数または単語数が規定の値を超えると
そこまでのインデックスファイルが順次、作成されていきます)。
Corpus
クラスは仮想的な文書集合を定義し、
各文書とそのインデックスにアクセスするためのインターフェイスを提供します。
各文書は location (位置) によって一意に指定されます。
Location は文字列で、この値はたとえば FilesystemCorpus
では文書ファイルのパス名として使われ、
BerkeleyDBCorpus
では文書データ (value) を取り出すためのキーとして使われます。
Corpus
クラスは fooling.corpus
モジュール内で定義されています。
Corpus
クラスは抽象クラスであるため、実際には以下のサブクラスのどれかを作成します。
これらすべての Corpus
オブジェクトは pickle が可能です。
FilesystemCorpus(basedir, idxdir, prefix='', doctype=None, encoding='euc-jp')
Document
クラス (後述) の
クラスオブジェクトを与える必要があります。
BerkeleyDBCorpus(dbfile, idxdir, prefix='', doctype=None, encoding='euc-jp')
CDBCorpus(dbfile, idxdir, prefix='', doctype=None, encoding='euc-jp')
SQLiteCorpus(dbfile, idxdir, prefix='', doctype=None, encoding='euc-jp',
table='documents', key='docid', text='doctext', mtime='mtime'):
(注意: 新山は SQLite をまともに使ったことがないため、このクラスは まだしっかりテストしていません。ぜひご協力を!)
以下の属性・メソッドはすべての Corpus
クラスで使えます:
index_mtime()
index_lastloc()
total_docs()
loc_indexed(loc)
loc
の位置にある文書がインデックスに含まれているかどうかを真偽で返します。
Predicate
オブジェクトは検索条件を表現します。
ひとつの検索フレーズがひとつの Predicate オブジェクトに相当します。
Predicate
オブジェクトの内部には単語列と正規表現パターンが含まれており、
ユーザは Corpus
オブジェクトと Predicate
オブジェクトのリストを
使って検索結果である Selection
オブジェクト (後述) を作成します。
Predicate
クラス自体は抽象クラスであり、これは
fooling.selection
モジュール内で定義されています。
ユーザは Predicate
から派生した、以下のクラスを作成できます。
KeywordPredicate(phrase)
フレーズ
、title:フレーズ
、
または |フレーズ|
という形式が使えます。
"フレーズ"
という形式はサポートしていません。
〜で囲まれたフレーズを
KeywordPredicate
オブジェクトのリストに分割するには
fooling.selection
モジュールにある parse_preds()
関数を使ってください。
StrictKeywordPredicate(phrase)
KeywordPredicate
オブジェクトと同じですが、検索フレーズ中の
記号や句読点まで (空白以外の) 一字一句にマッチする文書を検索します。
注意: Fooling では記号や句読点はインデックスされていません。
そのため、StrictKeywordPredicate
を使った検索では最初に「意味のある (約物以外の)」
フレーズ検索をしたあと、各フレーズの周囲を調べて与えられたパターンにマッチするかどうか
絞りこみが行われます。文書集合が特定のフレーズを大量に含んでおり、なおかつ
その中でパターンに正確に合致するようなものが非常に少なかった場合、これはほとんど
逐次検索と同じなるため、検索に非常に時間がかかる場合があります。
EMailPredicate(phrase)
KeywordPredicate
オブジェクトと同じく検索条件式を表現しますが、
この述語は電子メール (EMailDocument
オブジェクト) の検索専用です。
上にあげた通常のフレーズ検索に加えて、以下のような条件式をサポートしています:
subject:フレーズ
… Subject:
ヘッダを検索する。
from:フレーズ
… From:
ヘッダを検索する。
to:フレーズ
… To:
ヘッダ (複数あってもよい) を検索する。
cc:フレーズ
… Cc:
ヘッダ (複数あってもよい) を検索する。
rcpt:フレーズ
… To:
あるいは Cc:
ヘッダを検索する。(これらヘッダのどちらかにフレーズが含まれていればマッチする。)
addr:フレーズ
… From:
、To:
あるいは Cc:
ヘッダを検索する。(これらヘッダのどちらかにフレーズが含まれていればマッチする。)
message-id:メッセージID
… メッセージIDを検索する。
references:メッセージID,メッセージID,...
… Reference:
ヘッダ、
In-Reply-To:
ヘッダ、Message-ID:
ヘッダのどれかに含まれているメッセージIDを検索する。
ある議論のスレッドを検索するときに便利。
YomiKeywordPredicate(phrase)
KeywordPredicate
オブジェクトと同じですが、
漢字をふくむ日本語文字列の読みがなにマッチする文書を検索します。
phrase
はローマ字あるいはひらがな、カタカナで
書かれた読みがなとみなされます。
ローマ字変換で使用する規則は、現在のところ romm.py
内の
PARSE_DEFAULT
値で直接指定されています。ここには
PARSE_OFFICIAL
(訓令式 + "nn"で「ん」を入力)、
PARSE_OFFICIAL_ANNA
(訓令式 + "n"で「ん」を入力)、
PARSE_ENGLISH
(英語式)、のいずれかの値を指定できます。
YomiEMailPredicate(phrase)
EMailPredicate
オブジェクトに
読みがな検索の機能を加えたものです。
Selection
オブジェクトは、与えられた Corpus
オブジェクトと
Predicate
オブジェクトに対する検索結果の一覧を表現します。
実際にはこのオブジェクトは最初からすべての該当文書を含んでいるわけではなく、
ユーザが要素を参照するに従って漸進的に構築されていきます。
Selection
クラスは fooling.selection
モジュール内で定義されています。
Selection
オブジェクトはこれまでに見つかった文書 (の location) 一覧を含んでおり、
Document
オブジェクト (後述) のリストまたはイテレータとして扱うことができます。
また、Selection
オブジェクトは pickle が可能です。
Selection
クラスの使い方については
fooling/selection.py
の main
関数も参照してください。
Selection(corpus, predicates, doc_preds=None, safe=True, start_loc=None, end_loc=None, disjunctive=False)
Corpus
オブジェクト corpus と、
Predicate
オブジェクトのリスト predicates に対する
検索結果の一覧を作成します。引数 doc_preds
が指定されている場合は、
得られた各文書の location に対して doc_preds 内の各関数を呼び出し、文書のさらなる絞り込みを行います。
引数 safe
が True
の場合、インデックスの最終更新時刻よりも後に
変更された文書は検索結果から除かれます。
disjunctive
が True
の場合、検索条件は and ではなく or として組み合わされます。
Selection
オブジェクトは __iter__
や __getitem__
を
サポートしており、リストと同様に扱えますが、リストとして参照したときと
イテレータとして使用したときでは返す結果が違うので注意してください。
リストとして参照したときは i番目の Document
オブジェクトを返しますが、
イテレータとして使用すると (順位, Documentオブジェクト)
という形式のタプルを返します。
SelectionWithContinuation(corpus, predicates)
Selection
オブジェクトを pickle 保存しておくことで
「次の 10件」のような機能を提供することができますが、
Webアプリケーション上でサービスを提供する場合はこの方法は不便です。
SelectionWithContinuation
クラスには、
Selection
オブジェクトを pickle 保存しなくても続きから検索が再開できるような
メソッドを追加してあります。これらのメソッドは現在の Selection
オブジェクトの状態を、
文字列として符号化・復号します。pickle で保存したのとは異なり、
この文字列にはこれまでに見つかった文書の一覧は保存されていませんが、
この情報を使うことで「続き」から検索を再開できます。
ただし、Selection
オブジェクトと違い、
SelectionWithContinuation
オブジェクトはイテレータとしては使えません。
これは SelectionWithContinuation
オブジェクトが過去の検索結果を
保存していないため、検索結果を最初からすべて返すイテレータの意味論が適用できないためです。
途中から検索を再開するには iter_start()
メソッドを使ってください。
save_continuation()
Selection
オブジェクトの「継続 (continuation)」として、
base64 エンコーディングされた 12文字の文字列を返します。
この文字列は URL やフォームの値に含めることができます。
load_continuation(continuation)
save_continuation()
で得られた base64文字列を渡すと、
Selection
オブジェクトの以前の状態を復元します。
DummySelection(corpus, locations)
Document
オブジェクトの get_snippet()
メソッドを呼び出すと、
各文書の先頭 (あるいはそのクラスの default_snippet_pos
で指定された位置) からの
内容をデフォルトの snippet として表示します。
以下の属性・メソッドはすべての Selection
クラスで使えます:
iter_start(timeout=0)
timeout
を 0
以外の値 (秒数) に指定すると、
規定された時間後に検索をタイムアウトし SearchTimeout
例外を送出します。
これは Web アプリケーションなどで、意地悪な検索条件により計算時間が浪費されるのを防ぐためのものです。
Selection
オブジェクトを作成したばかりの状態
(つまり、検索結果がまったくない状態) では、これは通常のイテレータと同じですが、
通常のイテレータがつねに検索結果を最初から (キャッシュを使って) 返すのに対し、
このメソッドのイテレータはつねに次の検索結果を返そうとします。
iter(start=0, timeout=0)
__iter__()
メソッドに
開始位置 start
と timeout
を指定できるようにしたものです。
なお、SelectionWithContinuation
クラスではこのメソッドは使えません。
get(i, timeout=0)
__getitem__
メソッドに timeout
引数を追加したものです。
get_preds()
Selection
オブジェクトが使っている Predicate
オブジェクトのリストを返します。
status()
status()
では、該当文書が文書集合中に一様に分布していると仮定してこの値を計算します。
検索するフレーズが偏って分布している場合、この予測値は実際と大きくずれる場合があります。
matched_range(s)
b
' という文字列を検索した場合にこのメソッドに 'abbcc
' を与えると、
[(False, 'a'), (True, 'bb'), (False, 'cc')]
のようなタプルのリストが返されます。
このルーチンはおもに snippet の生成に使われますが、該当した文書自身を
ハイライト表示したいときなどにも使えます。
Document
オブジェクトはひとつの文書を表現します。
このクラスは必ずしも内部に具体的なデータを持っているわけではなく、
Corpus
オブジェクトから file-like オブジェクト (実際の file
オブジェクト
または StringIO
) を取得して文書データにアクセスします。
また、このクラスは各文書からインデックスするための単語列を抽出したり、
文書のタイトルを取得したりするインターフェイスを提供します。
検索機能を使うユーザは、通常 Selection
オブジェクトを介して
Document
オブジェクトを受け取り、以下のメソッドあるいは属性にアクセスします:
以下の属性・メソッドはすべての Document
クラスで使えます:
loc
Corpus
によって違っており、
ユーザはこの値から該当文書のパス名やリンクを表示します。
get_mtime()
get_snippet(selection, normal=lambda x:x, highlight=lambda x:x,
maxsents=3, maxchars=100, maxcontext=20)
lambda x: '<strong>'+escape(x)+'</strong>'
など) を与えます。
なお、マッチした部分が重なったりネストしている場合はもっとも外側の範囲が渡されます。
その他のキーワード引数 maxsents, maxchars, maxcontext には、 それぞれ snippet に表示する文の最大数、snippet 全体の最大文字数、 マッチした各部分の周辺を表示する最大文字数を指定します。
以下のクラスが fooling.document
モジュール内で定義されています。
ユーザが Document
オブジェクトを直接作成しては *いけません*。
Document
オブジェクトはつねに Corpus
オブジェクトによって作成されます。
ただし Corpus
オブジェクト を作成するさい、ユーザはその文書形式として
引数 doctype に以下のクラスオブジェクトのどれかを与える必要があります。
これらのクラスは、文書データ (生のバイト列) の解釈と snippet の表示方法が
異なっています。新しい Document
サブクラスを定義するさいは
新しい種類の文書 (Document) をサポートする
を参照してください。
PlainTextDocument
HTMLDocument
EMailDocument
SourceCodeDocument
PlainTextDocument
とほとんど同じ)
Indexer
オブジェクトは指定された Corpus
中の文書をインデックスし、
インデックスファイルを作成します。ユーザは作成した Indexer
オブジェクトの
index_doc()
メソッドを呼び出して文書を追加していきます。
文書数 (あるいはその合計単語数) がある既定値を超えると、 Indexer
は
随時インデックスファイルを (Corpus
オブジェクトで指定された) インデックス用ディレクトリに
書き出していきます。Indexer
クラスの使い方については、
fooling/indexer.py
の main
関数も参照してください。
Indexer(corpus, max_docs_threshold=2000, max_terms_threshold=50000)
Corpus
オブジェクト corpus を対象とした
Indexer
オブジェクトを作成します。オプション引数 max_docs_threshold は
1インデックスファイル中に含まれる文書の最大数を指定し、 max_terms_threshold は
1インデックスファイル中に含まれる単語の (おおまかな) 最大数を指定します。
毎回ひとつの文書をインデックスに追加したあと、Indexer
はこれらの値が
ここで指定されたスレッショルドを超えているかどうかを調べ、
超えていればそれまでの結果をひとつのインデックスファイル中に書き出し次に進みます。
デフォルトの値では、ひとつのインデックスファイルはだいたい 3〜10MBytes になり、 生成時にはその約2倍のメモリを必要とします。個々のインデックスファイルを大きくする (max_docs_threshold あるいは max_terms_threshold の値を上げる) と 場所の効率はよくなりますが、検索時間が必ずしも早くなるとはかぎりません (検索フレーズによってはかえって遅くなることもあります)。
index_doc(loc, maxpos=1000000, titleonly=False)
引数 maxpos にはインデックスをおこなう最大範囲を指定します
(一文書中で、この値より以降のオフセットに現れるデータは無視されます)。
デフォルトで 1000000 を指定すると、これはだいたい各文書の最初の 約1MBytes だけを
インデックスしますが、実際にはこのオフセット値の解釈は各 Document
クラスごとに
異なるため、正確に 1MBytes ぶんのテキストをインデックスするわけではありません
(たとえば EMailDocument
では、maxpos の値は各MIMEパート中で
インデックスする最大サイズを意味します)。
titleonly に真を指定すると、文書のタイトルのみをインデックスし、 文書の内容はインデックスしません。
finish()
Merger
オブジェクトは指定された Corpus
中に属する
インデックスファイルを統合・再構成します。ほとんどの操作は自動で行われるため、
ユーザはただ Merger
オブジェクトを作成して run()
メソッドを
呼び出すだけです。Merger
クラスの使い方については
fooling/merger.py
の main
関数も参照してください。
Merger(corpus, max_docs_threshold=2000, max_terms_threshold=50000)
Corpus
オブジェクト corpus を対象とした
Merger
オブジェクトを作成します。引数 max_docs_threshold、
max_terms_threshold の値は Indexer
オブジェクトと同じです。
run()
Fooling では以下のクラスを拡張して 新しい文書集合や文書の形式、検索方法などをサポートすることができます。
Corpus
クラスは文書の実体データにアクセスする手段を提供します。
また、このクラスは個々の文書に関連したメタ情報 (タイトル、更新日時など) や、
文書の形式を決定するのにも使われます。文書のデータを保存するコンテナとして
別のものが利用したい場合や、ひとつの文書集合中で異なる文書形式・文字コードを
混在させたい場合は、Corpus
のサブクラスを定義してください。
loc_exists(self, loc)
loc_fp(self, loc)
Document
オブジェクトから呼び出され、
Document
オブジェクトはその文書形式に応じてこのデータを解析し、
単語の抽出や snippet の生成を行います。なお、文書データの文字コードとして
loc_encoding(self, loc)
の値が使われます。
get_doc(self, loc)
Document
オブジェクトを返します。
このメソッドは Document
オブジェクトの種類を決定するためのもので、
デフォルトではすべての文書が同一の形式をもつと仮定しているため、
これはただ単に self.default_doctype
に
格納されているクラスオブジェクトを使ってインスタンスを作成するだけです。
ひとつの文書集合に複数の異なる形式の文書が格納されている場合には、 loc の値に応じて異なるクラスを選択するようにしてください。
loc_default_title(self, loc)
SourceCodeDocument
クラスなど) ではそうなっていません。
このメソッドはそのような場合に利用されます。文書の位置からタイトルが推測できる場合は
その文字列を返すようにしてください。
(たとえば FilesystemCorpus
では、
このメソッドは文書のファイル名を返すようになっているので
SourceCodeDocument
と FilesystemCorpus
を使っているときは
タイトルとしてソースコードのファイル名が表示されることになります。)
loc_encoding(self, loc)
self.default_encoding
の値を返すだけです。
loc_mtime(self, loc)
Document
オブジェクトは Corpus
オブジェクトから
得られたバイト列データを解析し、検索単語の抽出や snippet の生成を行います。
あるバイト列データを特定の文書形式として解析したい場合は、このサブクラスを作成します。
get_sents(self, pos)
(文ID, 文)
のようなタプルを
生成する必要があります。文ID は整数で、これはその文を一意に区別するためのものです。
通常これはその文の (文書データ中における) 開始バイトオフセットを表します。
各文は Unicodeオブジェクトである必要があります。
もっとも単純な get_sents()
メソッドは SourceCodeDocument
クラスのものです。
これは、self.open()
を呼び出して文書データにアクセスする file-like オブジェクトを
取得したあと、ファイル中の位置 pos まで seek
し、
そこから各行を 1文として返すものです。
なお、get_sents()
は通常ジェネレータのため、
自分自身では終了したかどうかを判定することができません。そのため
get_sents()
を呼び出すメソッド (通常は後述の get_terms
と
get_title
) は、終了時にかならず self.close()
を実行して
file-like オブジェクトを閉じる必要があります。
(さもないとファイルを一度に開きすぎて OS の制限を超える場合があります)
get_terms(self, maxpos)
(文ID, その文に含まれる単語のリスト)
のような
タプルを生成するイテレータを返します。これは内部で get_sents(0)
を呼び出し、
得られた文字列を fooling.util.isplit
関数を使って 2.2-グラム単語列に変換します。
各文書ごとのメタ情報 (電子メールのヘッダなど) をインデックスしたい場合は
この get_terms()
メソッドに追加の単語列を生成させるようにします。
get_title(self)
get_sents(0)
を呼び出し、
最初に得られた文をタイトルとして使用します。
EMailDocument
では Subject:
ヘッダの値を使用します。
get_mtime(self)
Date:
ヘッダなどで) 更新日時が文書中に記されている場合、
このメソッドをオーバーライドすることにより文書内から更新日時を取得できます。
デフォルトでは、これは Corpus
クラスの loc_mtime()
を呼び出した値を返します。
Predicate
クラスを拡張するためには、
Fooling の検索ルーチンでこれがどのように使われているかを理解している必要があります:
Selection
オブジェクトに渡されたひとつ (あるいは複数) の
Predicate
オブジェクトは、まず優先度高→優先度低の順にソートされます。
各 Predicate
オブジェクトは優先度 (priority
) をもっています。
これは AND 検索で複数の述語を使う場合、なるべく文書を絞りこめるような述語を先に
適用したほうが処理速度が上がるためです。
-
あるいは
!
が先頭についているもの) は後で処理されるよう並べ替えられます。
Fooling 検索では「まず肯定的な条件に合致する文書を集め、
そこから否定的な条件に合致する文章を引く」という戦略をとっています。
その述語が否定かどうかは neg
属性によって決定されます。
|日本-
または -日本-
どちらかのトークンを含む。
-本列-
のトークンを含む。
-列島-
または -列島|
どちらかのトークンを含む。
Predicate オブジェクト
の
pos_filter
関数に渡され、条件に合致しない文 ID はふるい落とされます。
たとえば電子メール (EMailDocument
オブジェクト) 中で
ヘッダに含まれる文字列だけを検索したい場合、ヘッダに現れる文字列は必ず 100未満の文 ID をもち、
ボディ中に現れる文字列は必ず 100以上の文 ID をもつようになっているので、
pos_filter
を lambda pos: pos < 100
に設定してやれば
ヘッダ内の文字列のみにマッチするような述語を作成することができます。
この判定は実際の文書ファイルにシークする前におこなわれるため、
これによって 5. の段階で文書ファイルを取得する回数を減らすことができます。
Predicate オブジェクト
の reg_pat
属性に格納された
正規表現オブジェクトが使われ、最終的にこの検索文字列に正確にマッチするかどうかがテストされます。
Predicate
オブジェクトの基本的なふるまいは、
ほとんど Predicate.__init__
メソッドが行います。
Predicate クラスを拡張する場合は setup
メソッドをオーバーライドしてください。
setup(self, s)
Predicate
オブジェクト中の属性値を設定する。
その後、以下のような 4要素のタプルを返す。
(正規表現パターン, 先頭のトークン列, 中央のトークン列, 末尾のトークン列)
正規表現パターン は Unicode 文字列オブジェクト、先頭・中央・末尾の各トークン列は
str 文字列のリストです。たとえば「日本列島
」という検索文字列を標準の
Predicate
オブジェクトに与えた場合は以下のようなタプルが返されます (模式図):
(u'日本列島', ['|日本-', '-日本-'], ['-本列-'], ['-列島-', '-列島|'])
実際には、各トークンは境界情報をふくんだ UTF-8 文字列で返されるので、 本当に返されるタプルは以下のとおりです (境界情報の記述方法については、 トークンの境界情報を参照)。
(u'日本列島', ['\x03\xe6\x97\xa5\xe6\x9c\xac', '\x01\xe6\x97\xa5\xe6\x9c\xac'],
['\x01\xe6\x9c\xac\xe5\x88\x97'], ['\x02\xe5\x88\x97\xe5\xb3\xb6', '\x01\xe5\x88\x97\xe5\xb3\xb6'])
各 Predicate
オブジェクトは以下のような属性をもっており、
Predicate.setup
メソッドはこれらのうちいくつかを設定する必要があります:
priority
Predicate
オブジェクトの優先度を表します。
優先度は、複数の Predicate
オブジェクトを検索に使う場合に使用され、
整数で表されます。検索開始時にすべての Predicate
オブジェクトは
優先度をキーとして降順にソートされ、大きな優先度をもつ述語が先に使われます。
デフォルトの優先度は 0 です。
pos_filter
eval
して関数オブジェクトが得られるような
文字列表現であり、関数オブジェクトではありません
(これは Predicate
オブジェクトを pickle 可能にするための措置です)。
通常は lambda
式が使われることになります。
実際にはこの値は eval
されて pos_filter_func
という属性に格納されます。
この値が None
の場合、文IDによる絞りこみは行われません。
neg
(変更不可)Predicate
オブジェクトが否定を表すものかどうかを表します。
検索キーワードの先頭に「-
」あるいは「!
」がついている場合、
この値は True
になります。なお、この属性値はユーザが変更してはいけません。
Predicate.__init__
メソッドは検索キーワードの先頭に
「-
」あるいは「!
」がついている場合、
neg
を True
に設定し、この部分を切り取って setup
メソッドに渡します。
reg_pat
(変更不可)setup
メソッドが返した値によって Predicate.__init__
メソッドが設定します。
この値が None
の場合、絞りこみは行われません。
narrow(self, idx)
idx
から、
この述語にマッチする文書IDと文IDの組を
[(文書ID,文ID), ... ]
のようなタプルの
リストとして返す。なお、リスト中の文書IDは必ず降順で
なければならず、同一文書中の異なる文IDも降順でなければならない。
このメソッドは従来は Selection クラス中に含まれていたが、fooling 標準の
cdb 以外のインデックスを使って絞りこみを行いたい場合の拡張用に
分離され、Predicate
クラスの中に収められた。
Webアプリケーションなどから不特定多数のユーザに Fooling の検索サービスを提供する場合、 以下のことに注意する必要があります:
Webアプリケーション上で「次の 10件」のような機能を提供する場合は
SelectionWithContinuation
クラスの
save_continuation()
メソッドを使って
次の検索開始位置を 12文字の base64 文字列として符号化します。
この文字列を URL またはフォームに入れておき、次の HTTPリクエスト時に
受けとって load_continuation()
メソッドを使うと、
それまでの続きから検索できます。なお、ここで保存・復元される情報は
検索の開始位置と「おおよその該当件数」を計算するために必要な
統計情報のみです。そのため、悪意あるユーザがこの文字列を改ざんしても
オブジェクトが不正な状態になることはありません。
Fooling は検索のたびに数百ミリ秒〜数秒の CPU 時間を消費するので、
状況によってはこれはマシンの負荷を増大させます。
そのため、あまり時間のかかる検索は避けたほうが無難です。
Selection
オブジェクト (または SelectionWithContinuation
オブジェクト)
でキーワード引数 timeout (秒数) を指定すると、一定時間後に検索は自動的にタイムアウトします。
上の項目と関連したことですが、StrictPredicate
オブジェクトを使った検索は、
場合によっては非常に時間がかかる場合があります。たとえば
JavaDoc 日本語版で「オブジェクト-
」という文字列を検索すると、
Fooling は「オブジェクト
」を検索したあと、各文書の該当部分が
「オブジェクト-
」というパターンにマッチするかどうかを調べるため、
実際には数千件の文書をスキャンすることになります。そのため Webアプリケーションでは
とくに必要がない限り StrictPredicate
は使わないほうがよいでしょう。
Fooling で使われている文字列検索の基本的なアイデアは、 ある文字列から、となりあった 2文字の組 (2-グラム) を単語列として 分解しインデックスするというものです。たとえば「東京都」という文字列は 「東京」と「京都」に分解されることになりますが、これに加えて Fooling では 各文字種 (漢字、ひらがな、カタカナ) の境界を考慮することにより 各単語をもう少し細かく区別するようにしました。たとえば:
-京都|
) 「ここは東京都です。」
-京都-
) 「東京都庁は新宿にある。」
|京都-
) 「ぼくは京都駅に着いた。」
|京都|
) 「べつに京都は好きじゃありません。」
「2.2-グラム」という名前は、これらの各トークンが通常の 2-グラムよりも 2ビット分余計な情報を含んでいることからつけました。
Fooling で使われているインデックスは、文中の各トークン (2.2-グラムで分割されたもの) に対して、それが現れる文書 ID と文 ID を羅列したものです。 Fooling における「文」とは、フレーズを検索する際の最小単位です。 異なる「文」をまたいだ文字列は一個のフレーズとはみなされません。 複数のトークンが同じ文中に現れていれば、 その文は検索フレーズを含んでいる可能性が高くなります。 しかしこの操作はインデックス中に含まれる文書 ID と文 ID の数が 多くなると遅くなるため、Fooling ではインデックスをいくつものファイルに分割し、 優先順位の高い方から検索していきます (これは、ランキングがあらかじめ 決まっていると仮定しているために可能になっています)。また文 ID として 文書ファイル中でその文が現れるバイトオフセットを使っているため、 snippets を表示するときもすばやく文中の該当する位置にシークできます。
Fooling ではインデックスファイルの形式として cdb を使っています。 cdb はある「キー」に対応する値をすばやく (ディスクの平均シーク回数が約3回で) 見つけることができます。 cdb は Berkeley DB などと比べてファイルサイズが小さく高速ですが、 いちど作成したら追加・修正ができないという欠点があります。そのため Fooling では 新しく追加された文書に対する cdb ファイルを毎回新たに作成します。 この方法では cdb ファイルは時間がたつにつれて増えていくので、 定期的にこれらをマージすることによってコンパクトなファイルを保持します。
以下の図はインデックスファイルの構造を示しています。
マージ操作の効率を上げるため、
すべてのキーは最後のひとつを除き辞書順にソートされています。
すべての文書には インデックスファイル中でローカルな文書 ID がつけられています。
最初に各文書 ID とその文書の location に対応するマッピングがあり、
そのあとに 2.2-グラムで分割されたトークンが続きます。
各トークンの前にある文字 c
は、トークンの境界情報を表します。
各トークンに対応する値は降順にソートされた (文書ID, 文ID) のリストであり、
最初にリストの要素数 n が記録されています。
Fooling では n が 4以上の場合、以後の文字列は zlib.compress
で圧縮されます。
つづいて文書の location から文書 ID へのマッピングがあります。
最後に、空文字列をキーとしてインデックスファイル全体の情報が記録されています。
キー | 値 | |||
'\x00'+docid1 | location1 | |||
'\x00'+docid2 | location2 | |||
... | ||||
c + トークン1 | (n, [(docid, sentid), ...]) | |||
c + トークン2 | (n, [(docid, sentid), ...]) | |||
c + トークン3 | (n, [(docid, sentid), ...]) | |||
... | ||||
'\xff'+location1 | docid1 | |||
'\xff'+location2 | docid2 | |||
... | ||||
'' | (総文書数, 総トークン数) |
インデックスファイル中の各トークンは、境界情報を表す 1バイトの文字のあとに UTF-8で表されたトークン本体の文字列が連結された形で表されています。 この境界情報を表す 1バイトの意味は以下のとおりです:
'\x01'
: このトークンの左右どちら側も境界でない。(-○○-
)
'\x02'
: このトークンの右側だけが境界である。(-○○|
)
'\x03'
: このトークンの左側だけが境界である。(|○○-
)
'\x04'
: このトークンの左右どちら側も境界である。(|○○|
)
読みがなを使ったインデックスの場合には、以下の識別文字が使われます。
'\x05'
: このトークンは読みがなの bi-gram を表す。
トークンの大きさは (この文字を含めて) つねに 3バイトであり、
残りの 2バイトはそれぞれ bi-gram の 1文字目と 2文字目の読みを
カタカナで表した Unicode の下位 1バイトが使われる。
例: 「アイ」という読みを Unicode のカタカナ文字列で表すと
U+30A2, U+30A4 となるため、ここでは
'\xa2\xa4'
というバイト列に変換される。
なお、境界情報が '\x10'〜 以上の文字である場合、 このトークンは文書に関するメタ情報を表す特殊なトークンとして扱われます。
'\x10'
: このトークンは電子メールの Message-ID を表す。(EMailDocument のみ)
'\x11'
: このトークンは電子メールが引用する Message-ID を表す。
この ID を In-Reply-To
あるいは References
ヘッダに含む
メッセージはすべてこのトークンを含む。(EMailDocument のみ)
'\x20'
: このトークンは文書の日付情報を表す。