2012年度 電気電子ネットワークコース 大学院実験(森研究室)

情報検索に関するプログラミング演習

森 辰則

環境情報研究院

Last modified: "2012/06/27 14:57:14 (JST)"


目次

1. はじめに

2. 演習内容

3. 報告書の提出

4. 付録


1. はじめに

今年度の実験では,情報検索に関する簡単なプログラミング演習を行なう.

情報検索は利用者が持つ情報要求に合致する文書を文書集合から捜し出してくる技術である. 詳しくは環境情報学府「言語情報処理原論」の講義資料2009年度版(PDF, 292KB)もしくは2012年度版(PDF, 3.5MB)を参照されたい.

本実験では,情報検索システム全体を構築するのではなく, そこで必要となるいくつかの要素技術について,段階を追ってプログラミングを行なう.

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

※ 注意: 著作権上の制約のため,サンプルファイルは本学内からしかアクセスできない.また特に断らない限り各ファイルの文字コードはEUC-JPである.


2. 演習内容

演習は「その1」から「その7」まである. できるところまで行ないなさい. 成績は内容に応じて判断する.

2.1 演習その1

chasen-output.txtというファイルを考える. これは ChaSen という形態素解析プログラム(付録参照)の出力である (chasen-input.txtから作られた). この出力は

	形態素\t読み\t形態素原形\t品詞情報\n
という形式をもつ行の並びである.ただし,「\t」はタブ,「\n」は改行を表す. このファイルから文字列「名詞-」で始まる品詞情報を持つ行の形態素原形のみを抜きだし,
	形態素原形\n
という行の並びからなる出力をだすプログラムを作成せよ.

なお,このプログラムに,chasen-output.txtを入力した時には, サンプル出力ファイル exercise-1-output.txtと同じものになるはずである.


2.2 演習その2

演習その1のプログラムで得られた出力から,語ごとにその出現回数を数え て出力するプログラムを作成せよ. ただし,出力の各行は次の形式をしていること.

	語\t出現回数\n

たとえば,このプログラムに,exercise-1-output.txtを入力した時には, サンプル出力ファイル exercise-2-output.txtと同じものになるはずである(行の出現順序は変わり得る).


2.3 演習その3

ファイル sample1.sgmlのような形式で記述された新聞記事群があったとする. タグ<DOC...>から</DOC>までが一記事である.この形式のファイルを入力として, 適宜改行を補って一行一文の形式で出力するプログラムを作成せよ. ただし,

たとえば,このプログラムに,sample1.sgmlを入力した時には, サンプル出力ファイル exercise-3-output.txtと同じものになるはずである.


2.4 演習その4

演習その3の出力をChaSenで処理した結果を入力とするプログラムを考える (例えば,ファイル exercise-4-input.txt). 各記事(タグ<DOC...>から</DOC>まで)について,その本文(タグ<TEXT>から</TEXT>まで)に現れる名詞(品詞が「名詞-」で始まるものの形態素原形)とその頻度(出現回数)を求め,以下の形式で出力せよ. ただし,「記事番号」は元のSGML形式ファイルにおいて,<DOCNO>と</DOCNO>の間に挟まれた文字列である.

  <DOC ID="記事番号A">\n
  語1\t頻度1\n
  語2\t頻度2\n
   :    :
  語k\t頻度k\n
  </DOC>
  <DOC ID="記事番号B">\n
  語1\t頻度1\n
  語2\t頻度2\n
   :    :
  語k\t頻度k\n
  </DOC>
  :
  :

たとえば,このプログラムに,exercise-4-input.txtを入力した時には, サンプル出力ファイル exercise-4-output.txtと同じものになるはずである(ただし,頻度の行は順序が入れ変わり得る).


2.5 演習その5

演習その4の出力を入力として, 各名詞の「文書頻度」を求めるプログラムを作成せよ. 文書頻度とは,各語が幾つの文書に出現したかである. (文書の数,である点に注意. 例えば,ある語がある文書だけに登場している場合, その文書中のその語の出現回数が多くても少なくても,その語の文書頻度は1である.) ただし,出力の各行は次の形式をしていること. 先頭行にある'NO_OF_DOC' はその通りの文字列とする.

	NO_OF_DOC\t全文書数\n
	語1\t文書頻度\n
	語2\t文書頻度\n
         :
	語k\t文書頻度\n

たとえば,このプログラムに,exercise-4-output.txtを入力した時には, サンプル出力ファイル exercise-5-output.txtと同じものになるはずである(ただし行の順序は入れ変わり得る).


2.6 演習その6

演習その4の出力ならびに演習その5の出力から,各文書の文書ベクトルを求る プログラムを作成せよ. ただし,文書ベクトルの各成分は各名詞に対応し,その値は, 次のように定義される,その文書におけるその語のtfidf値である.

	tfidf(d,w) = tf(d,w) * idf(w)
	tf(d,w)    = log_2(freq(d,w)) + 1
	idf(w)     = log_2(Nd / df(w)) + 1

	freq(d,w)  = 文書dにおける語wの出現頻度
	df(w)      = 語wの文書頻度
	Nd         = 全文書数
また,出力形式は以下のとおりとする.
  <DOC ID="記事番号A">\n
  語1\ttfidf1\n
  語2\ttfidf2\n
   :    :
  語k\ttfidf_k\n
  </DOC>
  <DOC ID="記事番号B">\n
  語1\ttfidf1\n
  語2\ttfidf2\n
   :    :
  語k\ttfidfk\n
  </DOC>
  :
  :

たとえば,このプログラムに,exercise-4-output.txtexercise-5-output.txtを入力した時には, サンプル出力ファイル exercise-6-output.txtと同じものになるはずである(ただし行の順序は入れ変わり得る.また,tfidf値の有効桁数も変わり得る.).


2.7 演習その7

演習その7の出力(文書ベクトル)を入力とし,各文書間の類似度をベクトル間のcosine値により 求めるプログラムを作成せよ.

もしも余力があるならば,プログラムの起動時にキーワードのリストを与え,そ のキーワードリストを(短い)文書だとして文書ベクトルを生成し,各文書との類 似度を求めるプログラムも作成せよ.その出力を降順に整列すると,文書検索シ ステムとなる.


3. 報告書の提出

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

3.1 報告すべき項目

3.2 提出方法


4. 付録

4.1 形態素解析器 ChaSen

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

4.1.1 ChaSen

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

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

4.1.2 ChaSenの入手方法

ChaSenの公式Webページ (http://chasen-legacy.sourceforge.jp/)から入手可能である.

4.1.3 ChaSenの使い方

文書を一行一文形式にし,標準入力やファイル名等で与えると,上記の処理を行なった結果を標準出力に出力してくれる.

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

chasen -h
と -h オプションをつけてChaSenを起動すると説明が表示される.