GETA 第2版 連想計算関数 wsh() の歩き方

趣旨

GETA 2 を使って連想検索を行う上で、もっともコアになる関数が libae.a にある wsh() である。しかし使い方がなかなか厄介である。ネットを探しても情報が少ないので、結局、$GETASRC/lib/ae/wsh.c というソースコードの解読を試みた。

wsh.c には wsh() という関数がひとつだけ定義されていて、おそらく高速化のためだろうが、関数呼び出しを極力行わないようにしている。$GETASRC/lib/ae/wt/*.f という類似度定義ファイルの内容も、最終的には wsh.c にインクルードして、wsh() に組み込む形で実行している。高速化重視で、やや可読性が失われているため、wsh() は相当読みづらかったが、なんとか解読に成功した。

wsh() の使い方について、具体例を交えて説明したい。

情報ソース

まず説明の前に、有益な情報ソースへのリンクを掲げる。

まずは、GETA 作者の西岡真吾氏による 汎用連想計算エンジンGETAの実装。これは、必読である。

wsh() のチュートリアルは libae を使って電子メール検索システムを作る。

Perlインタフェース活用術もわかりやすい。

読み進めるまえに、これらのリンクに目を通しておいたほうがいいかもしれない。

wsh の使い方

wsh() の宣言は以下の通り。

syminfo *
wsh(q, qlen, wam, dir_q, weight_type, rlen, totalp, cookie, ucompar)
syminfo *q ;  /* (IN) クエリ syminfo 構造体配列のサイズ */
int qlen;     /* (IN) クエリ syminfo 構造体配列 */
int dir_q;    /* (IN) クエリの軸が行なら WAM_ROW, 列なら WAM_COL を指定する。 */
WAM *wam;     /* (IN) 対象 WAM (データを表現した行列) へのハンドル */
int *rlen;     /* (IN/OUT) 入力としては、結果 syminfo 構造体配列の最大サイズ。出力としては、実際の結果 syminfo 構造体配列のサイズ（小さくなることがあるわけだ) */
int *totalp;  /* (OUT) 出力として、クエリに含まれる基準軸要素（ie 単語）が対立軸要素(ie 文書)と直交する回数(うーんなんて説明したらいいんだろう・・・) */
void *cookie; /* (IN) 一部の類似度定義で使用 */
int (*ucompar)(syminfo *, syminfo *); /* (IN) 結果個数が *ndp 以上になってしまった場合に、この比較関数でソートをして優先順位の低いものを切り捨てる。NULL を指定すると、syminfo 構造体の weight フィールドの比較が行われる。 */

wsh() の基本的なイメージは、syminfo 構造体の配列にクエリーを詰め込んで(仮引数q)、結果もまた syminfo 構造体の配列で返ってくる（戻り値)、と考えればいい。使う立場からすると、syminfo 構造体の意味が分かれば、とりあえずは十分だ。

struct syminfo {
        symbol_t id;
        int TF, TF_d;
        int DF, DF_d;
        double weight;
        int attr;
}

クエリの作り方

具体的に、次のような状況を考えてみよう。単語 A, B, C があるとして、これらを含む X, Y という文書があったとする。X, Y の文書は以下のとおりだとしよう。

X: AAB
Y: BBCCC

慣例に従って文書の軸を行、単語の軸を列と定める。つまり次のような頻度行列(WAM)を考えるのだ。

	A	B	C
X	2	1
Y		2	3

文書 X には A が 2回、文書 Y には C が3回出現している、などと読める。

このとき、A,B,B というキーワードで連想計算を試みるとしよう。連想計算の基本的な考え方は、このキーワード ABB からなる仮想文書があるとして、他の文書 X: AAB, Y: BBCCC のそれぞれについて、どれくらい似ているのか、ある公式（類似度定義）にしたがって計算するというものだ。

では早速、この状況でクエリを作ってみよう。

  syminfo *q = (syminfo*)malloc(2 * sizeof(syminfo));

  q[0].id = wam_name2id(wam, WAM_COL, "A");
  q[0].TF_d = 1;
  q[0].attr = WSH_OR

  q[1].id = wam_name2id(wam, WAM_COL, "B");
  q[1].TF_d = 2;
  q[1].attr = WSH_OR;

attr = WSH_OR は常套文句。wam_name2id() は name と呼ばれる人間用の識別子を id とよばれるシステム用の数値識別子に変換する関数だ。方向として単語の軸である列を表現する WAM_COL を指定する。おもしろいのは TF_d である。これは出現頻度を示す。ABB というクエリでは A が 1 回、B が 2 回登場する。そのため A, B で、それぞれ TF_d = 1, TF_d = 2 となっている。他にも TF, DF ... 等々いろいろあるが普通は設定する必要はない。

呼び出し＆結果

早速 wsh() を呼び出してみよう。

int rlen = 3;
syminfo *r = wsh(q, 2, wam, WAM_COL, WT_SMART, &rlen, NULL, NULL, NULL);

wsh の引数に WT_SMART と指定している箇所がおもしろい。ここで使用する類似度定義を決めるのだ。類似度定義には、他にも WT_TF, WT_TFIDF などさまざまなものがある。(詳しくは $GETASRC/lib/ae/wt/*.f を参照) 結果が r にやはり syminfo 構造体の配列へのポインタとして返ってくる。結果を見るには次のようにすればいい。

int i;
for(i = 0; i < rlen; i++) {
  printf("r[%d]: name = %s, TF = %d, TF_d = %d, DF = %d, DF_d = %d, weight = %f\n");
}

結果は以下のとおりになる。

r[0]: name = X, TF = 3, TF_d = 3, DF = 2, DF_d = 2, weight = 0.297064
r[1]: name = Y, TF = 5, TF_d = 2, DF = 2, DF_d = 1, weight = 0.000000

結果の各フィールドの意味は以下の通り。

• TF: 文書で単語が現れる回数。文書 X は AAB なので TF = 3, 文書 Y は BBCCC なので TF = 5 となる。
• TF_d: クエリを構成する単語が、当該文書で現れる回数。クエリを構成する単語はここでは A, B である。文書 X は AAB なので TF_d = 3, 文書 Y: BBCCC では B だけが該当するから、TF_d = 2。
• DF: 文書が含む単語の数（異なり数)。文書 X は A, B という2種類の単語から構成されるから、DF = 2。Y は B, C という2種類の単語から構成されるから、やはり DF = 2。
• DF_d: クエリを構成する単語を、当該文書が含む個数。クエリを構成する単語は A, B。文書 X の単語も A, B。2つの集合の共通部分は A, B であるから DF_d = 2。文書 Y の場合は、B, C という単語から構成される。そのためクエリを構成する単語 A, B との共通部分は B だけとなり、DF_d = 1。
• weight: これがミソで、類似度をあらわす。数字が大きいほど、クエリ仮想文書との類似度が高い。面白いのは上の例で文書 Y の weight が 0 になっていることだ。これは、WT_SMART という類似度定義では、すべての文書に現れる単語 B が評価から除外されることから生じている。ありふれた単語はなるべく連想計算には使わないようにしようとする WT_SMART の努力の現れである。

ソースコード

上の結果を導いたソースコードを下に掲げる。参考までにどうぞ。

/**
 
 連想計算関数 wsh() のテストプログラム (wsh_test.c)
 
 実行方法
 
 1. $GETAROOT/etc/ci.conf に "wsh_test" という WAM ハンドルを追加。
 
 2. 以下の WAM 外部表現(freqfile) を使って WAM を構築。(mkw コマンドを使用のこと)
 @X
 2 A
 1 B
 @Y
 2 B
 3 C

 3. コンパイル＆実行
 % gcc wsh_test.c -I$GETAROOT/include -L$GETAROOT/lib -lwam -lae -lm -lsrvmu -lgetamu
 % ./a.out
 
**/

#include <stdio.h>
#include <malloc.h>
#include <geta/wam.h>
#include <geta/ae.h>

int main() {
  wam_init(NULL);

  WAM *wam;
  wam = wam_open("wsh_test", 0);

  syminfo *q = (syminfo*)malloc(2 * sizeof(syminfo));

  q[0].id = wam_name2id(wam, WAM_COL, "A");
  q[0].TF_d = 1;
  q[0].attr = WSH_OR;

  q[1].id = wam_name2id(wam, WAM_COL, "B");
  q[1].TF_d = 2;
  q[1].attr = WSH_OR;

  int rlen = 3;
  syminfo *r = wsh(q, 2, wam, WAM_COL, WT_SMART, &rlen, NULL, NULL, NULL);

  int i;
  for(i = 0; i < rlen; i++) {
    printf("r[%d]: name = %s, TF = %d, TF_d = %d, DF = %d, DF_d = %d, weight = %f\n", i, wam_id2name(wam, WAM_ROW, r[i].id), r[i].TF, r[i].TF_d, r[i].DF, r[i].DF_d, r[i].weight);
  }

  free(q);
  free(r);

  wam_close(wam);

  return 0;
}