2000年度 電子情報工学特別実験 森研究室

情報検索システムを作成しよう!

森 辰則

横浜国立大学 工学部 電子情報工学科

最終更新日: 平成12年12月15日(金)


目次

1. はじめに

2. プログラムの仕様

3. 設計方針

4. 報告書の提出

5. 付録


1. はじめに

今年度の実験では,簡単な情報検索システムを作成する.

情報検索は利用者が持つ情報要求に合致する文書を文書集合から捜し出してくる技術である.詳しくは「ディジタルドキュメント論」の第9回講義資料(PostScript形式,3.2MB)を参照されたい.

情報要求の形式には様々な段階・表現があるが,本実験では,単語の並び(集合)として与えるものとする.すなわち,単語の並びを与えると,その単語群と関連する文書の識別子(ファイル名や文書番号など)を関連度の高い順に提示するシステムを作成する.

なお,この実験に関する特別な説明会は開催しないが,質問等があれば,随時, 森(mori@forest.dnj.ynu.ac.jp)まで連絡のこと.


2. プログラムの仕様

作成するプログラムは次の2つのサブプログラムから構成される.

2.1 索引情報作成プログラム

以下の入出力関係を満足するものとする.

2.1.1 入力

以下の書式を持つ文書情報の繰り返しを内容とするファイルである.

<DOC>
<DOCID> 文書識別子</DOCID>
<TEXT>
本文
</TEXT>
</DOC>

ただし,<名前> は「タグ」であり, これと</名前>との間に挟まれた部分が「名前」で識別される情報である. 以下にその説明を示す.

<DOC> ... </DOC>1文書情報
<DOCID> ... </DOCID>文書ID
<TEXT> ... </TEXT>本文

実際の記事の例を示す.

[記事の例,1.4MB](学内利用のみ.他人に再配布しないこと.)

これを実験で用いても良いが,入手可能であれば, 英語の新聞記事を用いてもよい.

2.1.2 出力

任意形式の索引情報ファイル. 具体的には,単語をキーとして,それに対応する以下の情報を得ることができる情報構造を持つ「転置ファイル」である.すなわち,このファイルは以下の写像を与えるものである.

単語 → 文書頻度,《文書識別子1,頻度1》,《文書識別子2,頻度2》,《文書識別子3,頻度3》,...

詳しくは「ディジタルドキュメント論」の第7回講義資料(PostScript形式,752KB)ならびに第9回講義資料(PostScript形式,3.2MB)を参照されたい.

2.2 検索プログラム

2.2.1 入力

入力は以下のものである.

2.2.2 出力

出力は以下の書式を持つファイルである.ただし,スコアは入力で与えた キーワードの集合と各文書の間の関連性に関するスコアである.文書識別子は 対応するスコアの降順に整列されているとする.


文書識別子1  スコア1
文書識別子2  スコア2
文書識別子3  スコア3
  :
  :

3. 設計方針

以下に設計方針を述べるが,かならずしもこれに従わなくとも良い.

3.1 索引情報作成プログラムの設計方針

プログラムの主な仕事は,以下の二つである.

  1. 個々の文書について,単語に分解し,単語毎に頻度を求める.
  2. 得られた頻度情報から転置ファイルをつくる.

1 における単語列への分解は,形態素解析を行なう既存のプログラムをつうとよい. 切り出された単語のうち,品詞が名詞となっているもののみをとりだし, 頻度を求めればよいであろう. 詳細については,付録: 形態素解析器 JUMANを参照のこと.

2 の転置ファイルにおいては,単語すなわち文字列をキーとして対応する情報を高速に検索する仕組みが必要とされる. これについては,ハッシュ機能を自作してもよいが,Unix環境で開発するのであれば,dbm,ndbm,gdbm, BerkeleyDB等,各種DBMライブラリを使うほうが簡単である. これらのDBMライブラリはC言語等ではもちろん Perl でも利用できる.特にPerlにおいては,Perlのデータ構造の一つであるハッシュと結びつけることができるので,非常にプログラミングが楽である. 詳細については,付録: DBMライブラリを参照のこと.

3.2 検索プログラムの設計方針

TFIDFによる語の重みづけと,ベクトル空間法による類似度尺度を用いて, 与えられたキーワード集合と各文書の類似度を求める.

転置ファイルが完成していれば,検索キーワードが含まれる各文書について, この類似度を求めるのは難しくない. 具体的には「ディジタルドキュメント論」の第9回講義資料(PostScript形式,3.2MB)で示したアルゴリズムによる. ただし,上記の形式の転置ファイルでは文書ベクトルの長さをもとめづらいので, 類似度計算には文書ベクトルと質問ベクトルの内積を用いてもよい. (一般的には文書ベクトルと質問ベクトルのなす角のcosine値を類似度として用いる)


4. 報告書の提出

作成したプログラムについて,以下の点を含む報告書を提出せよ. 用紙はA4とし,表紙には,報告書の題目,報告者の学籍番号ならびに名前を記述すること.

4.1 報告すべき項目

4.2 提出方法


5. 付録

5.1 形態素解析器 JUMAN

日本語の場合,語と語の間に空白がないので, 語の切れ目を見つけること自身が一仕事である. その作業を行ないつつ,各語の品詞などを解析するのが形態素解析器である. ここでは,京都大学で開発されたJUMANを紹介する.

なお形態素解析一般については,「ディジタルドキュメント論」第6回講義資料(PostScript形式,1.8MB)を参照されたい.

5.1.1 JUMAN

JUMANは一行一文形式の文書を入力すると,単語に分割し,品詞情報などを付加してくれる.

出力例を次に示す.[出力例]

この例のように,品詞詳細情報の中に「人名」という分類が現れるので, これを有力な情報として使うことができる.

ただし,品詞解析が必ず成功しているとは限らない. たとえば,「名詞 人名」と解析すべきところが,「名詞 普通名詞」や「名詞 地名」などと解析されることも多い.

5.1.2 JUMANの使い方

まず,/usr/local/share/lib/juman3.61/jumanrc というファイルを ファイル ~/.jumanrc にコピーし,設定ファイル ~/.jumanrc を作成する.

juman の本体は /usr/local/share/lib/juman3.61/bin/juman であるので, /usr/local/share/lib/juman3.61/bin にパスを通しておくと便利である.

JUMANには幾つかのオプションがあるが,それについては,

juman -h
と -h オプションによりjumanを起動するとオプションの説明が表示される.

5.2 DBMライブラリ

5.2.1 Perlでの利用方法

Perl5 では,tie() という関数によって,DBMファイルとPerlのハッシュを簡単に結びつけることが出来る.
[NDBMによるサンプルプログラム]

5.2.2 C言語での利用方法

C言語で NDBMを使うことを例にとると, 関数dbm_open(), dbm_store(), dbm_fetch(), dbm_close() などにより, DBMを扱うことが出来る. [NDBMによるサンプルプログラム]