(57)【要約】【課題】検索対象文書の逐次追加に伴うポスティングの追加が可能でコンパクトな転置インデックスのデータ構造を提供する。【解決手段】転置リストを格納するためのメモリ領域を３種類用意し、転置リストの長さにより使い分ける。ポインタ程度以下の長さの転置リストはポインタ領域301に書き込み、それよりもやや長い転置リストは長さに応じて獲得された連続メモリ領域302に格納し、ある閾値以上に長い転置リストはリスト構造で結合された複数のメモリ領域303に格納する。【選択図】図３
2008217122.tif 000002
【特許請求の範囲】
【請求項１】
それぞれに識別番号が割り当てられた複数の文書からなる文書集合の全ての索引語について、索引語毎に当該索引語が出現する文書の識別番号とその文書中での当該索引語の出現回数の組であるポスティングを集めた転置リストを格納した転置インデックスを記録したコンピュータ読みとり可能な記録媒体であって、前記転置リストを格納するために３種類のメモリ領域を使用し、
第一の種類のメモリ領域は連続したメモリ領域であって、前記索引語から前記転置リストへのポインタを格納する領域に配置され、
第二の種類のメモリ領域は連続したメモリ領域であって、その大きさはユーザが指定した値M以下であり、
第三の種類のメモリ領域は１つ以上の連続したメモリ領域をリスト構造によって接続したものであって、個々の連続したメモリ領域の大きさはユーザが指定した値Mに対しMバイト以上であること
を特徴とするコンピュータ読みとり可能な記録媒体。
【請求項２】
請求項１記載のコンピュータ読みとり可能な記録媒体において、前記第三の種類のメモリ領域の、リスト構造で結合されている先頭のメモリ領域に、末尾のメモリ領域の位置が記録されていることを特徴とするコンピュータ読みとり可能な記録媒体。
【請求項３】
請求項１または２記載のコンピュータ読みとり可能な記録媒体において、前記第二の種類のメモリ領域の大きさおよび、前記第三の種類のメモリ領域の個々のメモリ要素の大きさが、ユーザが指定した整数Bに対しBバイトの整数倍となっており、大きさBのメモリ領域からなる可変長配列から１つ以上の要素を獲得することで新規なメモリ確保を行なうことを特徴とするコンピュータ読みとり可能な記録媒体。
【請求項４】
請求項１、２、または３記載のコンピュータ読みとり可能な記録媒体において、前記Mの値が２のべき乗であり、かつ16以上4096以下であることを特徴とするコンピュータ読みとり可能な記録媒体。
【請求項５】
請求項３記載のコンピュータ読みとり可能な記録媒体において、前記Bの値が２のべき乗であり、かつ8以上2048以下であることを特徴とするコンピュータ読みとり可能な記録媒体。
【請求項６】
請求項５記載のコンピュータ読みとり可能な記録媒体において、前記Mの値が２のべき乗であり、かつ16以上4096以下であることを特徴とするコンピュータ読みとり可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大規模文書集合を対象に、高速な全文検索および文書データの逐次追加をするための、転置インデックスの圧縮方法に関する。
【背景技術】
【０００２】
今日、電子文書は経済活動のあらゆる場面において不可欠であり、膨大な量の電子文書が日々作成されている。インターネットの拡大も電子文書の量を爆発的に増加させる要因となった。これらの電子文書を最大限に活用するためには、欲しい文書を短時間で検索する文書検索技術が必須である。
【０００３】
文書検索の典型的なスタイルは、与えられた文書集合から、指定された単語を含む文書を、極力短時間で出力するというものである。この目的のために、転置インデックスと呼ばれるデータ構造が使用される。図１は、検索対象となる文書集合101と、それに基づき構築される転置インデックス102の概略図である。ある索引語103がある文書104に出現するとき、その文書の識別番号105と、その文書中の当該索引語の出現回数106から構成される情報をポスティング107と呼び、ある索引語に関するポスティングを全て集めて得られるリストを転置リスト109と呼ぶ。図１において、108は索引語ごとに割り当てられた、転置リスト109へのポインタである。検索対象文書の全索引語の転置リストを格納したデータ構造が、転置インデックス102である。
【０００４】
英語、フランス語、スペイン語のような単語がスペースで区切られている言語と異なり、日本語、韓国語や中国語では、文書を正確に単語に分割することが困難である。そこでn-gramと呼ばれる、連続するn文字からなる、文書中の任意の部分文字列を単語の代わりに用いて、転置インデックスを構築する場合があり、実用上有用であることが知られている(情報検索アルゴリズム、北研二他著、共立出版）。nは、主に1〜10の整数である。本明細書では、単語及び長さnの部分文字列を総称し、索引語と表記する。
【０００５】
検索対象文書の数あるいは大きさが増大するにつれ、転置インデックスも巨大なものとなる。したがって、サイズをコンパクトに抑えることが重要となる。高速なアクセスを実現つつ、高い圧縮率でポスティングを圧縮する技術も提案されている(I.H.Witten, A. Moffat, and T.C. Bell, Managing Gigabytes 2nd Ed.: Compressing and Indexing Documents and Images, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1998、および、F. Scholer, H. E. Williams, J. Yiannis, and J. Zobel.Compression of Inverted Indexes for Fast QueryEvaluation, In Proceedings of the 25th Annual International ACM SIGIR Conference on Researchand Development in Information Retrieval, pp222-229, 2002)。
【０００６】
文書検索における重要な課題のひとつが、新規に文書が与えられたときに、転置インデックスが新規文書を反映するように更新し、新規文書も検索可能とする差分更新技術である。差分更新技術に関しては、主にディスク上の転置インデックスの更新を目的とする技術が開発されてきた(J. Zobel and A. Moffat, Inverted files for text search engines, ACM Comput. Surv., 38(2), 2006)。しかし近年、計算機に搭載される主記憶が増大してきており、検索対象文書集合によっては、転置インデックスを複数の計算機に分散配置し、オンメモリで大規模な転置インデックスを扱うことが可能となってきた。また、ディスク上に転置インデックスを配置する場合であっても、更新部分を容量が許す限りメインメモリ上に記録し、メモリが不足するまでディスクへの書き込みを遅延させることで、ディスクアクセスの回数を減らしインデックスの更新に要する時間を短縮することが多い。したがって、オンメモリの転置インデックス差分更新技術の開発は、レスポンスの早い文書検索システムを提供する上で極めて重要である。ディスク上の転置インデックスを対象とする差分更新技術では、検索時のシーク時間を短縮するために、転置リストを連続性の高い領域に格納することが主要な課題となっている。一方、オンメモリの転置インデックスを対象とする場合、連続性はある程度犠牲にしてもよい。しかし、メモリはディスクに比べ容量が少ないため、転置リスト自体に付加されるポインタなどの付加的なデータの量を抑制する必要がある。
【０００７】
更新の必要がない静的な文書集合を検索対象とする場合、転置インデックスのサイズを必要最小限度に抑制するインデックス構築方法としては、もとの文書集合を２回読み直す２パス方式が有効である。２パス方式では、文書集合を初めに読むときは、各索引語の転置リストを格納するために必要な領域の大きさを計算する。この結果に基づき必要なメモリ領域を確保した上で、文書集合をもう一度読み直し実際に転置リストを作成する。２パス方式では、メモリの無駄がない転置リストを構築できるが、文書集合を２回読むコストが大きい。しかも、予め文書集合が完全に与えられる必要があり、新規文書の追加は、インデックス全体を再構築しない限り不可能である。
【０００８】
オンメモリで転置インデックスの差分更新を実現するデータ構造としては、図２に示すように、ポスティング107に次のポスティングの位置を表すポインタ201を付与するリスト構造が最も基本的である。リスト構造を採用することで各索引語の転置リストを、必要なときにいつでもメモリの許す限りの長さに拡張できる。しかし整数値・ポインタをいずれも同一のビット数で表現すれば、ポスティングが、文書識別番号、当該文書中の当該索引語の出現頻度の２つの整数から構成される場合、データ構造全体に占めるポインタの割合が33%以上となってしまう。したがって、リスト構造では消費するメモリの量が本来のデータ量の1.5倍に達し、ポインタを格納することによるオーバーヘッドが非常に大きい。
【０００９】
転置リストを連続するメモリ領域に配置すれば、ポスティング同士を連結するためのポインタが不要になる。この際、各転置リストの末尾に空き領域が残るよう多めにメモリを割り当て、新規のポスティングを追加できるようにする手法が知られている。過去の更新状況から将来転置リストが伸張する度合いを予測し、必要なメモリを多めに獲得する方法も提案されている(非特許文献１)。
【００１０】
一方、Buttcherらは、リスト構造による転置リストをベースとし、ポインタのオーバーヘッドを削減する方法を提案した(非特許文献２)。Buttcherらの方法では、連続メモリ領域内に複数のポスティングを格納し、これらの領域間をポインタで結合することにより、ポスティング１つあたりのポインタに起因するオーバーヘッドを削減している。さらに、頻繁にポスティングが追加される索引語の転置リストは将来も追加が多いと予想されることを反映し、新規に獲得するメモリ領域の大きさを指数関数的に増加させる。ただし、あまりに大きなメモリを確保してしまうと無駄な領域が多くなる可能性も考慮し、獲得するメモリ領域の大きさに上限を設けている。これらの技術を合わせて用いることにより、Buttcherらの方法は２パス方式に比べてデータ量の増加を5%以下に抑えられることが実験的に確認されている。
【００１１】
【非特許文献１】W.-Y. Shieh, C.-P. Chung, A statistics-based approach to incrementally update inverted files, Inf. Processing and Management, 41(2):275-288, 2005.
【非特許文献２】S. Buttcher and C.L.A. Clarke, Memory management strategies for single-pass index construction in text retrieval systems, University of Waterloo Technical Report CS-2005032/Wumpus Technical Report 2005-02, 2005.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
転置インデックスのデータ構造は、転置リスト自体を除く付加的なデータの量を極力少なく押さえつつ、どのような文書が与えられても短時間で更新可能でなければならない。非特許文献１の方法では、新規に追加される文書の数が多い場合、結局は獲得したメモリが不足し新しいメモリを確保する必要が生じる。したがって、多めにメモリを獲得することでデータ構造を更新するタイミングを遅らせることはできるが、メモリ容量の許す限り転置リストを任意の長さに伸張可能なデータ構造は結局必要である。非特許文献２の方法では、比較的単純なデータ構造にも関わらず、２パス方式と比べて十分にオーバーヘッドの少ない転置インデックスを実現している。しかし転置リストの先頭部分が大きさの異なる多数のメモリ領域に分割されてしまうため検索時の速度低下が起きるほか、転置リストへのアクセス方法が複雑化し、処理時間増加の要因となる。ポインタに必要なメモリにも、削減する余地がある。
【００１３】
本発明の目的は、高速な文書検索および転置インデックス更新のために、コンパクトでなおかつ任意の新規文書追加要求に対応可能な転置インデックスのデータ構造を提供することにある。
【課題を解決するための手段】
【００１４】
本発明は、転置リストを格納するメモリ領域を３種類用意し、転置リストの長さごとにこれらを使い分けることにより、ポインタに起因するメモリのオーバーヘッドが少なく、メモリ領域の細分化を防いだ転置インデックスのデータ構造を提供する(図３)。これらの３種類のメモリ領域を、本明細書ではタイプ１、タイプ２、タイプ３と表記する。本明細書では、特に断らない限り、領域の大きさはバイト単位で表現する。以下、
bは索引語ごとに割り当てられる固定サイズのメモリ領域の大きさを表す整数であるユーザパラメータ、
Bは索引語ごとに追加で割り当てられる最小のメモリ領域の大きさ表す整数であるユーザパラメータ、
rは追加で割り当てられるメモリ領域が不足した場合に新規に割り当てられるメモリ領域の大きさを調整する整数であるユーザパラメータ、
Mは索引語ごとに追加で割り当てられ連続性が保証される最大のメモリ領域の大きさを表す整数であるユーザパラメータ、
Wは獲得したメモリ領域の位置を表現するために必要な領域の大きさ、
W’は獲得したメモリ領域内のデータのビット長を表現するために必要な領域の大きさ、
NをB*rN≧Mなる最小の整数、
[x]はxを下回らない最小の整数、
c(x)=[(x+7)/8]とする。なお、c(x)は長さxのビット列を格納するために必要な領域のバイト単位での大きさである。
【００１５】
本明細書では対数logの底は２とする。さらに、新しく割り当てられるメモリ領域の大きさが元のメモリ領域より大きいことを保証するためにb＜B＜Mを仮定する。
【００１６】
タイプ１〜３のメモリ領域は、格納したい転置リストのビット単位での長さλにより、下記のように使い分ける。
【００１７】
(1)タイプ１のメモリ領域
c(λ)≦Wなる転置リストを格納するために用いる。従来技術では転置リストは、索引語ごとに用意されているポインタが指す領域に格納される。このポインタを格納する領域301に、本発明ではタイプ１のメモリ領域を確保する。これにより、全くポインタを使用せずに短い転置リストを格納できる。文書集合中に１〜２回しか現れない、非常に稀な索引語に対して、タイプ１のメモリ領域301は有効である。なぜなら、c(λ)≦Wの転置リストでポインタを使用すると、１つポインタを使用するだけでポインタの占める割合が50%を超えるためである。
【００１８】
(2)タイプ２のメモリ領域
W＜c(λ)≦B*rN-1なる転置リストを格納するために用いる。タイプ２のメモリ領域302は、索引語ごとに用意されているポインタが指す領域に確保する。長さλの転置リストに対しては、大きさがB*rn-1のメモリ領域を確保し、転置リストを記録する。ここに、nはc(λ)≦B*rn-1なる最小の整数である。
【００１９】
(3)タイプ３のメモリ領域
c(λ)＞B*rN-1なる転置リストを格納するために用いる。タイプ３のメモリ領域は、複数の、大きさMのメモリ領域 303(以下、セグメントと呼ぶ)をポインタで接続したリスト構造である。このリスト中でのi番目のセグメントを、以下ではA(i)と表記する。A(i)中で転置リストを記録するために利用可能な領域の大きさをM(i)とし、k≧1のときM’(k)=M(1)+...+M(k)と定義する。また、M’(0)=0と定義する。この定義により、M’(k)は、k個のセグメントからなるタイプ３のメモリ領域に記録できる最長の転置リストのバイト数となる。M(i)の具体的な値は本発明の方法の実装に依存するが、その一例について後述する。リスト構造を構成するためのポインタや他の情報を記録するために、各セグメントに記録できる転置リストのバイト数はMより小さく、M(i)＜Mである。
【００２０】
長さλの転置リストのために確保されるセグメントの数は、c(λ)≦M’(k)を満足する最小の整数kとなる。タイプ３のメモリ領域はリスト構造を取っており、ポインタが必要だが、Mを大きくとりM(i)を十分に大きくすれば、ポスティング１つ１つにポインタを用意する場合に比べポインタの占める割合が小さくなり、また転置リストを読み取る際のポインタアクセスの頻度も相対的に小さいため、ポインタに起因するアクセス時間およびメモリ消費を抑制できる。また、確保されるセグメントの大きさがMで一定のため、実装も容易である。
【００２１】
rが整数でかつMがBの倍数であれば、タイプ２〜３のメモリ領域で、連続する個々のメモリ領域の大きさは常にBの整数倍となる。したがって予め、多数のBバイトのメモリ領域を含む配列を獲得しておき、その中で何番目の領域であるかを表す整数をポインタの代わりに用いることによって、ポインタを直接用いるより少ないビット数でメモリ領域の位置を指定でき、Wを小さくできる場合がある。
【発明の効果】
【００２２】
本発明により、ポインタに起因するメモリオーバーヘッドが少なく、連続性の高いメモリ領域にポスティングが記録される、新規文書の追加が可能な転置インデックスのデータ構造が提供される。
【発明を実施するための最良の形態】
【００２３】
本発明によって提供される転置インデックスの作成および更新を実施する装置の一形態を説明する。装置全体の概観を図４に示す。中央演算装置(CPU)401に、メモリ(主記憶)402が接続されている。必要に応じ、補助記憶403、ＤＶＤ-ＲＡＭ等の書き換え可能なリムーバブルメディア404、ネットワーク405、ユーザ端末406が接続される。本実施形態の装置は、CPU 401により実行されるメモリ402上のプログラムとして索引語抽出手段S501、索引語出現回数取得手段S502、文書識別番号割り当て手段S503、ポスティング圧縮手段S504、転置インデックス更新手段S505を備える。
【００２４】
本装置におけるデータ及び処理の流れを、図５に示す。最初に、入力として新規の検索対象文書104を、CPU 401が必要に応じメモリ402、補助記憶403、リムーバブルメディア404、ネットワーク405のいずれかから取得する。前記文書104に、2通りの処理が行なわれる。まず、索引語抽出手段S501により、前記文書104中の索引語103が切り出される。前述のように、抽出手段として、公知の形態素解析方法又はn-gramが使用できる(情報検索アルゴリズム、北研二他著、共立出版)。さらに、それぞれの索引語が、前記文書104において出現する回数が、出現回数取得手段S502により取得される。出現回数を取得するためには、単純に索引語ごとに整数変数をひとつ用意して０に初期化した後、前記文書104中に当該索引語の出現が検出される度に１ずつ増加させればよい。さらに文書識別番号割り当て手段S503により、前記文書104に文書識別番号を割り当てる。
【００２５】
この手段の好ましい実施形態の１つは、１に初期化された整数変数を１つ保持し、新しい文書識別番号が必要な際にこの変数の値を割り当て、その直後に前記変数の値を１増やすことである。S501、S502、S503により、各々の索引語について、文書識別番号105及び索引語出現回数106からなるポスティング107が得られる。このポスティングは、ポスティング圧縮手段S504を用いて圧縮することが好ましい。圧縮されたポスティング506をメモリ402に構築した転置インデックス407中の、当該索引語に対応する転置リストに追記する。当該索引語に対応する転置リストの位置は、索引語ごとのポインタに記録する。必要に応じ、メモリ402上に構築した転置インデックスを、補助記憶403、リムーバブルメディア404、ネットワーク405に転送し保存してもよい。この処理は、新規の検索対象文書104が与えられる度に繰り返される。
【００２６】
本発明の方法による転置インデックスの一例を、図６を用いて説明する。このデータ構造は、基本領域601、拡張領域602、空き領域リスト記録領域603から成る。基本領域は、大きさbのメモリ領域を複数個格納可能な可変長配列である。同様に、拡張領域も大きさBのメモリ領域を複数個格納可能な可変長配列である。可変長配列の実施形態の一例を、後述する。空き領域リスト記録領域603は、N個の、大きさWの要素605からなる固定長配列である。この領域のn番目の要素empty[n] 605は、ある定数NULLに初期化されている。NULLの定義は後述する。基本領域601中の大きさbの個々のメモリ領域を、以下では基本スロットと呼ぶ。同様に、拡張領域602中の大きさBの個々のメモリ領域604を、以下ではスロットと呼ぶ。拡張領域中でk番目のスロットのスロット番号を、kとする。また、連続する複数のスロットが連続メモリ領域として使用される場合、最初のスロットのスロット番号を、このメモリ領域のスロット番号とする。
【００２７】
新規に獲得するメモリ領域がもとの整数倍でありかつ急激にサイズが増大することを防ぐために、r=2を仮定する。また、拡張領域602内に確保されるすべてのメモリ領域の大きさがB*rn(nは整数)と表現できるよう、MをM=B*rNに固定する。さらに、タイプ１のメモリ領域よりもタイプ２のメモリ領域に格納できる最長の転置リストが長くなり、タイプ２のメモリ領域よりも必ずタイプ３のメモリ領域に格納できる最長の転置リストが長くなることを保証するために、b≦B≦B*rN-1≦M(1)を満足するパラメータが与えられることを仮定する。
【００２８】
基本領域からは、索引語１つにつき基本スロットが１つ割り当てられる。基本スロットに記録される情報は、次の通りである。
(1)当該索引語の転置リストを記録するメモリ領域が、タイプ１〜３のどれであるか。
(2)-1 タイプ１の場合、転置リストのビット長λと転置リスト自体。
(2)-2 タイプ２の場合、転置リストのビット長λとメモリ領域へのポインタ。
(2)-3 タイプ３の場合、メモリ領域のリストの先頭要素へのポインタ。
【００２９】
基本スロットのデータ構造を、図７を用いて説明する。基本スロット７０１は、３つの部分領域R 702、L 703、C 704から成る。
【００３０】
●部分領域R 702
整数nを記録する。この整数nの意味は、次の通りである。
n=0:    この索引語の転置リストは、タイプ１のメモリ領域に格納されている。
1≦n≦N:この索引語の転置リストは、タイプ２のメモリ領域に格納されている。
そのメモリ領域の大きさは、B*rn-1である。
n=N+1:  この索引語の転置リストは、タイプ３のメモリ領域に格納されている。
●部分領域L 703
タイプ１または２のメモリ領域を使用する場合に、転置リストのビット長を記録する。タイプ３の場合、部分領域Lは意味をもたない。
●部分領域C 704
タイプ１のメモリ領域を使用する場合には、転置リスト自体を記録する。タイプ２の場合には、転置リストが記録されているメモリ領域のスロット番号を記録する。タイプ３の場合には、転置リストが記録されているメモリ領域のリストの最初のセグメントA(1)のスロット番号を記録する。
【００３１】
なお以下では、メモリ領域x中の部分領域yをx{y}と表記する。
【００３２】
次に、拡張領域602のスロット上に獲得したメモリ領域のデータ構造を説明する。
■タイプ２のメモリ領域(801)の場合
全体が転置リストを格納するために使用される(図8)。
■タイプ３のメモリ領域(901,902または903)の場合
データ構造を、図９を用いて説明する。
【００３３】
●部分領域P3 904
図９に示すリスト構造における、次のセグメントのスロット番号を記録する。但し、当該部分領域P3を含むセグメントがリスト構造の最後のセグメントである場合には、最後であることを表す特殊な数値NULLを記録する。特殊な数値NULLの選択として、好ましい例を２つ示す。
１．スロット番号を１から順に数えることとし、NULLを０とする。スロット番号を０から数え、スロット０を使用しないことにしてNULLを０としてもよい。
２．Wバイトで記録できる最大の数値をNULLとする。
なお、図６、９、１１においては、定数NULLを斜線606で図示した。
●部分領域L3 905
当該部分領域L3を含むセグメントに記録されている分の転置リストのビット長を記録する。
●部分領域P’3 906
リスト構造の最初のセグメントA(1) 901に限り、部分領域P’3 906を設ける。この部分領域には、リスト構造の最後のセグメントのスロット番号を記録する。この情報によって、転置リストの長さに関係なく、転置リストの末尾に一定の時間内でアクセス可能となり、転置リストへの新規要素の追加を迅速に行なえる。
●部分領域C3 907
転置リストを格納する。
【００３４】
以上のデータ構造では、部分領域P3、L3、P’3の大きさは、それぞれW、W’、Wとするのが好ましい。この場合、M(1)=M-(2W+W’)、M(i)=M-(W+W’) (i≧2の場合)である。
【００３５】
各パラメータの値および各部分領域の大きさの、選択基準について説明する。まず、Wはスロット番号を表すために必要なバイト数であればよい。64ビットアーキテクチャであれば最大W=8バイトだが、スロット番号がNULLも含めて最大でnであるとわかっていれば、W=c(log(n)+1)バイトで十分である。最低でもメガバイトクラスの転置インデックスを構築できるよう、nは220よりも大きく取ることが好ましい。したがって、Wは少なくとも3バイトであることが好ましい。一方、W’も８バイトとしてもよいが、タイプ１および２のメモリ領域およびセグメントの大きさはMで抑えられるので、W’=c(log(8*M)+1)バイトで十分である。W’=1バイトでもM＜32バイトならばセグメント内の転置リストの長さを表現できるが、この場合はW+W’が最低でも4バイトであり、Mの10%を超えてしまうため、転置リスト以外の付加的なデータ量を抑制するという当初の課題に対する解決手段として不十分となってしまう。W’=2ならばM＜213=8192未満であればよいため、Mを大きく取り、付加的なデータが占める割合を抑制できる。r=2であるべきことは、前述した。基本スロット701は部分領域C 704を包含し、この部分領域C 704の大きさはW以上であるため、b≧W≧3である。アドレス計算にシフトおよび論理演算を使用し、計算を高速化するためには、基本スロットの大きさbは２のべき乗であることが好ましいが、基本スロットは全ての索引語に割り当てられるため、可能な限り小さくする必要がある。
【００３６】
したがって、bの値としてはWが3以上であることを考慮し、４以上とすることが好ましい。Bも、bと同様に2のべき乗であることが好ましく、かつ、タイプ２のメモリ領域をタイプ１より大きくするためにb＜B、タイプ３のメモリ領域をタイプ２のメモリ領域よりも大きくするためにB＜Mをそれぞれ満たすことが好ましい。b＜Bより、Bは4*2=8以上とすることが好ましい。一方、M=B*rN、r=2であるため、Mも2のべき乗である。したがって、M≦4096=8192/2であることが好ましい。このため、B≦2048=4096/2であることが好ましい。さらに、M＞Bより、M≧16=8*2であることが好ましい。なお、部分領域R 703に記録すべき値はlog(M/B)≦log(8192/8)=10であるため10+1=11以下の整数であればよいため、部分領域R 703の大きさは0から11までの整数を表現可能な4ビットであれば十分であり、M, Bの選択によってはもっと少ないビット数であってもよい。部分領域L 704は[log|W|+1]ビット以上であればよい。
【００３７】
次に、このデータ構造を使用した転置リストの作成方法について詳細を述べる。
【００３８】
1. ある索引語の最初に、ビット長λの新規ポスティングを追加するときには、基本領域の未使用部分の先頭から新しい基本スロットa 701をひとつ獲得する。λに基づきメモリ領域の種類をタイプ１〜３の中から選択する。
1-1. c(λ)≦Wならば、前述のようにタイプ１が選択される。この場合は、前記基本スロットa内に、a{R}に0、a{L}にλを、a{C}に前記ポスティングを記録する。
1-2. W＜c(λ)≦B*rN-1ならば、前述のようにタイプ２が選択される。この場合は、B*rn-1≧c(λ)を満たす最小の整数nに対し、拡張領域からrn-1個の連続するスロットを獲得する。このrn-1個の連続するスロット内に、前記ポスティングを記録する。そして、a{R}にn、a{L}にλ、a{C}に前記連続するスロットの最初のスロット番号を記録する。
1-3. B*rN-1＜c(λ)ならば、前述のようにタイプ３が選択される。この場合は、まず拡張領域からrN個の連続するスロットを獲得し、A(1)として使用する。この領域の大きさは、M=B*rNバイトである。a{R}にN+1、a{C}にA(1)のスロット番号を記録する。さらに、λにより下記1-3-1または1-3-2のいずれかの処理を行なう。
【００３９】
1-3-1. c(λ)≦M(1)の場合
A(1){P3}にNULL、A(1){L3}にλ、A(1){P’3}にNULLを記録し、A(1){C3}に前記ポスティングを先頭から詰めて記録する。
【００４０】
1-3-2. c(λ)＞M(1)の場合
kをc(λ)≦M’(k)を満足する最小の整数とする。変数iを2にセットし、i≦kの間、下記の処理1-3-2-1〜4を行なう。
1-3-2-1. 拡張領域から新規にrN個の連続するスロットを獲得し、A(i)とする。
1-3-2-2. A(i-1){P3}にA(i)のスロット番号を、A(i-1){L3}にM(i-1)*8を、A(i-1){C3}に前記ポスティングのM’(i-2)+1バイト目からM’(i-1)バイト目までを記録する。
1-3-2-3. iに1を加える。
1-3-2-4. i≦kならば、1-3-2-1からの処理を再び行なう。
1-3-2-1〜4の処理が完了したら、A(k){P3}にNULLを、A(k){L3}に整数λ-M’(k-1)*8を記録し、さらにA(k-1){C3}に前記ポスティングのM’(k-1)+1バイト目以降を先頭から詰めて記録する。そして、A(1){P’3}にA(k)のスロット番号を記録する。
【００４１】
次に、ある索引語の既存の転置リストに新規ポスティングを加える方法について述べる。既存の転置リストのビット長をλ、新しいポスティングのビット長をλ’とする。
【００４２】
2.当該索引語に対応する、基本スロットa’を参照し、a’{R}に基づき既存の転置リストを格納したメモリ領域のタイプを取得する。
2-1. a’{R}=0のとき、すなわち既存の転置リストがタイプ１の場合、a’{L}から、既存の転置リストの長さλを取得する。
2-1-1. c(λ+λ’)≦Wの場合、更新後の転置リストもタイプ１のメモリ領域に格納する。単純に、既存の転置リストの末尾に新規ポスティングを追記し、a’{L}をλ+λ’に置き換える。
2-1-2. W＜c(λ+λ’)≦B*rN-1の場合、更新後の転置リストはタイプ２のメモリ領域に格納する。まず、拡張領域からrn-1個の連続するスロットを獲得する。ただし、nはB*rn-1≧c(λ+λ’)を満たす最小の整数である。このrn-1個の連続するスロット内に先頭から詰めて、既存の転置リストをコピーし、その直後に新規ポスティングを記録する。そして、a’{R}にn、a’{L}にλ+λ’、a’{C}に新たに獲得したメモリ領域のスロット番号を記録する。
2-1-3. B*rN-1＜c(λ+λ’)の場合、更新後の転置リストはタイプ３のメモリ領域に格納する。まず、「ビット長λの新規ポスティング」を「ビット長λの既存の転置リスト」、「a」を「a’」と読み替えて処理1-3を実行する。このとき、最後に獲得したセグメントをA(k)とする。以下、整数kは説明の都合上用いているが、実装にあたってはkの値が未知であっても、メモリ領域A(k)のスロット番号が把握されていればよい。次に、下記の処理2-1-3’を実行する。
2-1-3’. A(k){L3}+λ’≦M(k)ならば、A(k){C3}の末尾に新規ポスティングを追記し、A(k){L3}にλ’を加えれば追加処理は終了である。A(k){L3}+λ’＞M(k)の場合、まず、変数DにM(k)*8-A(k){L3}をセットする。このとき、DはA(k)に追記可能な転置リストのビット長になる。次に、新規ポスティングの先頭からDビットまでをA(k){C3}に追記し、A(k){L3}にM(k)*8を記録する。さらに、D＜λ’が成立する間、以下の2-1-3-1〜7の処理を繰り返す。
2-1-3-1. 拡張領域から新規にrN個の連続するスロットを獲得し、A(k+1)とする。
2-1-3-2. A(k){P3}に、A(k+1)のスロット番号を記録。
2-1-3-3. 変数dを、D+M(i)*8とλ’のうち、小さい方にセットする。
2-1-3-4. 新規ポスティングのD+1ビット目からdビット目を、A(k+1){C3}に先頭から詰めて記録する。
2-1-3-5. A(k+1){L3}に、d-Dを記録する。
2-1-3-6. kをk+1、Dをdで置き換える。
2-1-3-7. D＜λ’が成立すれば、2-1-3-1からの処理を再び行なう。
【００４３】
最後に獲得したセグメントをA(k’)とする。A(k’){P3}にNULLを記録し、A(k’)のスロット番号をA(1){P’3}に記録する。なお、A(1)のスロット番号はa’{C}を参照すれば得られる。
2-2. 1≦a’{R}≦Nの場合、すなわち既存の転置リストがタイプ2のメモリ領域に記録されている場合、a’{R}に書かれた整数nについてB*rn-1≧c(λ+λ’)ならば、既存の転置リストが書かれたメモリ領域中で、既存の転置リストの直後に新規のポスティングを追記し、a’{L}にλ’を加えて処理が終了する。B*rn-1＜c(λ+λ’)ならば、まず、2-1.と同様の処理を行って既存の転置リストと新規のポスティングを新たなメモリ領域に記録する。そして、これまで既存の転置リストが記録されていたメモリ領域は破棄し、再利用可能な状態とする。メモリ領域の破棄と再利用の方法は、後述する。
2-3. a’{R}＞B*rN-1の場合、すなわち既存の転置リストがタイプ3のメモリ領域に記録されている場合、a’{C}に書かれたスロットの位置にあるセグメントA(1)について、A(1){P3}を参照する。A(1){P3}がNULLならば、A(1)がリスト構造の最後のセグメントである。A(1){P3}がNULLでなければ、A(1){P3}に書かれたスロット番号の指すセグメントが最後のセグメントである。説明の都合上、この最後のセグメントがリスト中でk番目であると仮定する。実装にあたっては、最後のセグメントのスロット番号が把握されていればよく、kの値を取得する必要はない。この段階で、処理2-1-3’を実行すれば、新規ポスティングを追加できる。
【００４４】
上記手順に従えば新規のポスティングが何度も追加されると、最初に格納されたポスティングは、タイプ１または２のメモリ領域からタイプ２または３のメモリ領域へと何度もコピーされる。しかし、１つの転置リストに含まれる各バイトの平均のコピー回数mは、下記のように限られる。ただし、nは転置リストの長さλに対してc(λ)＞B*rn-1なる最大の整数nである。
【００４５】
m≦(b+B+B*r+B*r2+B*r3+…+B*rn-1)/c(λ)
≦(b+B+B*r+B*r2+B*r3+…+B*rn-1)/B*rn-1
＝ b/(B*rn-1)+(r-(n-1)+r-(n-2)+...+r-2+r-1+1)
≦ 1+r/(r-1)=2+1/(r-1)≦３
したがって、コピー処理の時間的コストは大きくない。
【００４６】
メモリ領域を破棄し、再利用可能な状態とする方法を説明する。ここで説明する方法では、破棄されたメモリ領域を図11に示すリスト構造で管理する。このリストは、破棄されるメモリ領域の大きさごとにN本用意されており、n番目のリストが大きさB*rn-1の空き領域を管理する。そして、再利用時は、適切な大きさのリストの先頭からメモリ領域を割り当てる。空き領域リスト記録領域603は、前述の通りN個の大きさWの要素605からなる。n番目(n=1,2,...,N)の要素605には、大きさB*rn-1の空き領域を接続するリストの最初の空き領域のスロット番号が記録される。各要素605は、処理の開始時にNULLに初期化する。大きさB*rn-1のあるメモリ領域Aが破棄されると、その先頭Wバイト部分1102に、これまでn番目の要素605に書かれていた値が複写され、前記n番目の要素605には新たに破棄された領域Aのスロット番号が記録される。このとき複写される値は、Aがリストの最初のメモリ領域になる場合はNULLとなる。一方、ポスティングを追加する際にrn-1個のスロットが連続するメモリ領域が必要になった場合には、まずn番目の空き領域リストからの獲得を試み、失敗したときに限り新しい未使用スロットを割り当てる。より詳細には、下記(1)(2)の通りである。
【００４７】
(1)空き領域リスト記録領域603のn番目の要素605がNULLで無い場合は、n番目の要素605に書かれたスロット番号のメモリAを割り当て、前記n番目の要素605には前記割り当てられたメモリAの先頭Wバイトの部分1102に書かれたスロット番号を複写する。
【００４８】
(2)空き領域リスト記録領域603のn番目の要素605がNULLの場合は、拡張領域のまだ使用されたことが無い部分の先頭から、連続するrn-1個のスロットを割り当てる。
【００４９】
なお、破棄されたメモリの再利用方法は、この方法以外にも、公知の任意のガーベージコレクションの方法を使用してもよい。
【００５０】
また、可変長配列の実装の形態としては、獲得済みのメモリで容量不足が生じた場合に、既存の領域の大きさにある比率Pを乗じた大きさの新しいメモリ領域を獲得して既存の配列の要素をすべてコピーする方法が一般的である。ただし、本発明の方法では可変長配列全体が連続するメモリ領域である必要はない。そこで、可変長配列を複数のブロック1002に分割し、さらに各ブロック1002へのポインタを別の可変長配列1001に格納して、このポインタを通じアクセスする(図10)。新規に連続スロットが必要になれば既存ブロック内から割り当てを試みるが、空きスロットの不足やスロットの断片化により指定された個数の連続スロットが確保できない場合がある。この場合には可変長配列1003に新たなブロックを追加し、そこから指定された個数の連続するスロットを割り当てる。また、可変長配列1003の長さに関係なく一定の時間で可変長配列の任意の要素にアクセスできるよう、前記ポインタの可変長配列1001は連続するメモリ領域に確保することが好ましい。このため前記の、既存の配列の要素をすべて新しいメモリ領域にコピーする方法でポインタの配列1001を実装することが好ましい。
【００５１】
領域P、C、P3、L3、P’3の大きさは、WあるいはW’バイトとしたが、バイト境界に揃える必要はなく、必要に応じてビット単位で切り詰めてもよい。
【００５２】
また、ポスティングの圧縮方法として個々のポスティングの境界がバイト境界に揃うvariable byte方式(F. Scholer, H.E. Williams, J. Zobel, Compression of Inverted Indexes for Fast Query Evaluation, Proc. 25th Ann. Int’l ACM SIGIR Conf. Research and Development in Information Retrieval, pp.222-229, 2002)の方法を使用する場合には、転置リストの長さをビット単位ではなくバイト単位で表現できるため、W’を１バイト分短くできる場合がある。
【００５３】
また、本発明のデータ構造は、例えばハッシュ表のように、複数の可変長バイト列を管理する場合にも適用可能である。
【産業上の利用可能性】
【００５４】
本発明により、検索対象文書の逐次追加が可能な転置インデックスのデータ構造が提供される。このデータ構造はポインタの数が少ないためメモリオーバーヘッドが少ない上、ある長さ以下の短い転置リストは連続するメモリ領域に配置されるため、高速アクセスが可能で実装も容易であるという特長を有する。
【図面の簡単な説明】
【００５５】
【図１】検索対象となる文書集合と、それに基づき構築される転置インデックスの概略図。
【図２】ポスティングをリスト構造で接続し構成された転置リストの説明図。
【図３】転置リスト用に割り当てられた３種類のメモリ領域を示す図。
【図４】本発明を実施する装置の１つの形態を示す概略図。
【図５】本発明によるデータ及び処理の流れの例を示す図。
【図６】転置インデックス全体のデータ構造の例を示す概略図。
【図７】基本スロットのデータ構造を示す図。
【図８】タイプ２のメモリ領域のデータ構造を示す図。
【図９】タイプ３のメモリ領域のデータ構造を示す図。
【図１０】可変長配列の概略図。
【図１１】空きスロットを管理するリスト構造の説明図。
【符号の説明】
【００５６】
101: 検索対象文書の集合
102: 転置インデックス
103: 索引語
104: 検索対象文書
105: 文書の識別番号
106: ある文書における、ある索引語の出現回数
107: ポスティング
108: 索引語ごとに割り当てられた、転置リストへのポインタ
109: 転置リスト
301: タイプ１のメモリ領域
302: タイプ２のメモリ領域
303: タイプ３のメモリ領域の１要素、すなわちセグメント
401: 中央演算装置(CPU)
402: メモリ(主記憶装置)
403: 補助記憶装置
404: リムーバブルメディア
405: ネットワーク
406: ユーザ端末
407: 文書の逐次追加が可能な転置インデックス
601: 本発明の転置インデックスのデータ構造中の、基本領域
602: 本発明の転置インデックスのデータ構造中の、拡張領域
603: 本発明の転置インデックスのデータ構造中の、空き領域リスト記録領域
604: 拡張領域中のスロット
605: 空き領域リスト記録領域の一要素
606: 定数NULLを表現する斜線
701: 基本スロット
702: 基本スロットにおいて、メモリ領域の種類およびタイプ２の場合に獲得するメモリ領域の大きさを格納する領域
703: 基本スロットにおいて、タイプ１またはタイプ２のメモリ領域中で転置リストが占める領域の長さを格納する領域
703: 基本領域中で１つの索引語に対応する領域において、タイプ１のメモリ領域を使用する場合には転置リスト、タイプ２または３のメモリ領域を使用する場合にはそのメモリ領域の位置を記録するための領域
801: タイプ２のメモリ領域で転置リストを格納する領域
802: タイプ２のメモリ領域に対応する基本スロット
901: タイプ３のメモリ領域を構成するリスト構造の、最初のセグメント
902: タイプ３のメモリ領域を構成するリスト構造の、最初と最後以外のセグメント
903: タイプ３のメモリ領域を構成するリスト構造の、最後のセグメント
908: タイプ３のメモリ領域に対応する基本スロット
1001: 可変長配列において、個々のブロックへのポインタを格納した配列
1002: 可変長配列において、実際のデータを格納するブロックの１つ
1003: 本発明で使用する可変長配列の一形態
1101: 破棄され、未使用領域となったメモリ領域
1102: 破棄され、未使用領域となったメモリ領域を接続するリスト構造において、次のメモリ領域のスロット番号を格納する大きさWの領域
【図１】
2008217122.tif 000003
【図２】
2008217122.tif 000004
【図３】
2008217122.tif 000005
【図４】
2008217122.tif 000006
【図５】
2008217122.tif 000007
【図６】
2008217122.tif 000008
【図７】
2008217122.tif 000009
【図８】
2008217122.tif 000010
【図９】
2008217122.tif 000011
【図１０】
2008217122.tif 000012
【図１１】
2008217122.tif 000013