はじめに

これまで、転置索引の構造や具体的なデータ構造を見てきました。今回は、検索したいテキスト文書から、どのようにこの構造を構築するかを説明していきます。

ディスクベースの構築方法

第3回では、表を作成しそれを転置させることで転置索引を構築しました。実際にコンピュータに処理をさせる場合も、メモリ上の2次元配列で同様に構築することが可能となります。しかし、通常の転置索引は非常に疎な表となるため、この方法ではメモリを使いすぎてしまいます。また、リンクリストなどのメモリ上でのデータ構造を用いることにより、上記の方法と比較して少ないメモリ量で構築することもできます。

これらの方法はいずれも、対象とする文書集合を変換した転置索引が実メモリに収まる場合にのみ可能となる方法となります。しかし多くの場合、転置索引は実メモリよりも大きくなります。そのような場合はディスクを用いた構築方法が必要となり、効率的に行うには少し工夫が必要です。ここでは 後者の場合を想定して[1]⁠、ディスクベースの構築方法について説明していきます[2]⁠。

今回はSort-based InversionとMerge-based Inversionと呼ばれる2つの方法を紹介します。

Sort-based Inversionによる構築

Sort-based Inversionによる構築手順は、リスト1に示す疑似コードのようになります。文書ごとにレコード<t, d, f(d,t)>を生成し、ディスクに追記していきます（9行目⁠）⁠。ここで、tは単語ID、dは文書ID、f(d,t)はdにおけるtの出現頻度となります[3]⁠。

その後、各レコードを単語IDの昇順に、単語IDが同じ場合は文書IDの昇順にソートします（12行目）（⁠※3⁠）⁠。あとは、ソート後のファイルを先頭から見ていくと各単語IDとそれを含む文書IDのリストを取得できるので、 それらで各ポスティングリストを構築します（14～16行目⁠）⁠。また、ポスティングリストを圧縮する場合は15行目の段階で行います。図1に、サンプルデータでの構築の様子を示します。

 1: file = NewFile()
 2: dictionary = NewHash()
 3: while all documents have not been processed do
 4:  D = GetDocument()
 5:  for all token ∈  do
 6:    if term(token) ∉ dictionary then
 7:       postings list = AddToDictionary(dictionary, term(token))
 8:    end if
 9:    WriteRecordToFile(TermID(token),DocID(token),Freq(token), file)
10:  end for
11: end while
12: ExternalSort(file)
13: inverted_file = NewFile()
14: for all term ∈ file do
15:   ConstructPostingList(term, inverted_file)
16: end for

Merge-based Inversionによる構築

Merge-based Inversionによる構築も同様に疑似コードを使って説明します（リスト2⁠）⁠。

この方法では、ソートベースの方法とは異なり、辞書ではターム自体をキーとし、メモリ上で可能な限り辞書と転置リストを構築します（6～19行目⁠）⁠。文書中の中にタームが存在しなければ、そのつど辞書に登録します（9、10行目⁠）⁠。また、ここでは各ポスティングリストは倍々に領域を増やしてポスティングを追加できるようにしています（14～16行目⁠）⁠。メモリ上での構築後、タームを辞書順にソートし、ディスクに書き出します（20、21行目）（⁠※4⁠）⁠。

この作業を全文書を処理できるまで繰り返し、最後に書き出された複数のファイルをマルチウェイでマージすることにより、最終的な索引が構築されます（23行目⁠）⁠。また、ポスティングリストを圧縮する場合は23行目のステップで行われます。図2に、マージベースの転置での構築処理の流れを示します。

 1: n ← 0
 2: while all documents have not been processed do
 3:   n ← n ＋ 1
 4:   filen = NewFile()
 5:   dictionary = NewHash()
 6:   while free memory available do
 7:     D = GetDocument()
 8:     for all token ∈ D do
 9:       if term(token) ∉ dictionary then
10:          posting_list = AddToDictionary(dictionary, term(token))
11:       else
12:         posting_list = GetPostingList(dictionary, term(token))
13:       end if
14:       if full(posting_list) then
15:          posting_list = DoublePostingList(dictionary, term(token))
16:       end if
17:       AddToPostingsList(posting_list, docID(token))
18:     end for
19:   end while
20:   sorted terms ← SortTerms(dictionary)
21:   WriteBlockToDisk(sorted terms, dictionary, filen)
22: end while
23: MergeBlocks(file1,...,filen, filemerged)

Sort-based Inversion vs. Merge-based Inversion

ここではアルゴリズムの細かい解析は省略しますが、両者を比べた場合、一般的にはMerge-based Inversionによる構築方法の方が効率的であると考えられています。Sort-based Inversionではすべての辞書をメモリ上に保持するため、扱う文書数が多くなる場合には問題となり、また、ディスクベースでソートを行うためI/Oコストも大きくなります。

構築方法の種類

転置索引の構築には、大きく分けて以下の2種類の構築方法があります。

• 静的な構築方法（offline index construction, offline approarch）
• 動的な構築方法（online index construction, online approarch）

静的な構築方法では、入力データに対して構築処理を行い、それらの処理の完了時に検索可能となるように構築する方法となります。一方、動的な構築方法では、索引構造を常に検索可能、かつ、最新の状態に保つように構築する方法になります。

つまり、静的な方法は文書の到着(作成)から索引への反映までに多くの時間が許容できる場合に用いられ、動的な方法は、検索可能になるまでの待ち時間をほんの少ししか許容できない場合に用いられる方法であると言えます。これまで説明してきた方法は、静的な構築方法となります[5]⁠。文書集合があまり変化しない場合や、変化してもそれが反映されるまでに時間がかかっても良い場合は通常、静的な方法で索引の構築を行います。

一方、新鮮度（freshness）が重要な文書集合も存在します。たとえば、Web上のニュースやブログなどの場合、新しい記事は古い記事よりも重要度が高いので、新しい記事が追加されたら、すぐに索引に反映させたいと思います。そのような場合には動的な構築方法が選ばれます。動的な構築方法については、連載の後半の方で扱う予定です。

まとめ

今回は、文書から転置索引の構造を構築する方法について説明しました。多くの文書から索引を構築したい場合は、ディスクを使った構築方法が必要であり、代表的な2種類の方法について疑似コードを用いてアルゴリズムを紹介しました。これらの方法により、利用可能な実メモリよりも大きな転置索引が構築できるようになります。また、これらの方法は静的な構築方法と呼ばれ、一般的な文書集合で広く用いられています。

参考文献

• ［1］Inverted files for text search engines, Justin Zobel, Alistair Moffat, ACM Computing Surveys (CSUR), 2006
• ［2］Introduction to Information Retrieval, C. D. Manning, P. Raghavan, H. Schutze , Cambridge University Press, 2008
• ［3］Managing Gigabytes: Compressing and Indexing Documents and Images, Ian H. Witten, Alistair Moffat, Timothy C. Bell, Morgan Kaufmann Publisher, 1999