● wsh による類似度計算の概要 wsh() は、weight_type が WT_NONE でなければ、以下の手順により q と d (d は wsh() の戻り値 dp のそれぞれの要素、dp-> でアクセスできる)との類 似度、sim(d|q) を計算し、dp->weight に格納する。類似度の計算式は以下の 通り。 sim(d|q) = (1.0 / norm(d)) \sum_t { wq(t|q) * wd(t|d) } ^^^^^^^ -- step 2 で計算 ^^^^^^^^^^^^^^^^^^^^^ -- step 3 で計算 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ -- step 3 を囲むループで計算 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ -- step 4 で計算 wsh() は、この式を以下の手順で計算する。 Step 1: Step 2 以降で不変な値を計算しておく Step 2: foreach (t in q) { /* q に現れる全ての t について */ wq(t|q) を計算する } 次の Step 3 と Step 4 はq とのインターセクションが空にならない全ての 文書 d について呼びだされる。 Step 3: q と d のインターセクションを計算し、配列 qvec_h に格納する。続いて s = 0.0; foreach (t in qvec_h) { wq(t|q) * wd(t|d) を計算し, s に足し込む } を実行。この結果、s に各 d についての \sum... の部分が計算される。 Step 4: norm(d) を計算し、Step 3 で計算した s に反映される。すなわち、 s /= norm(d); wq(t|q) や wd(t|d) の(Step 3 での)ループ不変部は、 \sum の外にくく り出しておき、ここで計算すれば、(わずかだが)速い。ただし、可読性は落ち る。 以上で各 d についての sim(d|q) が計算されるので、その大きい順に要求 あれた個数だけ集める。(残りは捨てられる) また、実装では Step 3 で qvec_h が計算された直後に、必須/除外ID (主 に単語から文書を連想するときに必須の語や含んではならない語を指定するこ とを想定した機能) についての判定が行われる。この動作をユーザが定義する ことも可能である(Step 5)。 ● wsh による類似度計算の実装 前節で説明した各ステップの計算式は、実際には wt/*.f というファイルに 記述する。そして、wt/*.f は wt/f2c というコマンドにより C 言語に変換さ れ、それを wsh.c が include することで wsh() に組み込まれる。 ★ *.f に記述する式の目的: 0: global variable を宣言する 1: loop constants を計算する 2: wq(t|q) を計算する 3: wd(t|d) を計算する 4: norm(d) を計算する 5: 3: の計算を実行するかどうか判断する ★ *.f の書式: *.f は名前定義行と 0, 1, 2, 3, 4 の 5 つのパートから構成される。全て のパートが必須で、(使用しないパートにつては空の記述を行う)この順に *.f に現れなければならない。 名前定義行はそのファイルで記述される類似度に名前を付ける。この行は行 頭から書き始める。書式は以下の通り。 name: <名前> <改行> 各パートはパート開始行から次のパートの直前までである。パート開始行は 行頭から書き始める。その書式は以下の通り。 <パート名>: <改行> パート開始行の次の行からがそのパートの記述になる。ここには各ステップ の計算式を記述する。ここには ; (セミコロン) で終了された数式、または C のソースコードを書くことができる。なお、*.f の保守性と可読性を高めるた めに、f2c は、特定のパターンについては置換を行う(後述)。 ★ 各パートでの注意点: パート2 では wq(t|q) を計算することが目的である。そしてその結果は(通 常、このパートの最後の行で) wq(t|q) = ...; という式で示されなければならない。実は f2c によってこれが C の代入文に 変換され、wsh() が仮定している変数への代入が起こることになる。 パート3 では wd(t|d) を計算することが目的である。そしてその結果は(通 常、このパートの最後の行で) wd(t|d) = ...; という式で示されなければならない。 パート4 では norm(d) を計算することが目的である。そしてその結果は(通 常、このパートの最後の行で) norm(d) = ...; という式で示されなければならない。なお、この記述を省略した場合、 norm(d) は 1 に等しくなる。 ★ f2c により生成される C のコードの目的: 0: 記述式の目的 0 に同じ 1: 記述式の目的 1 に同じ 2: wq(t|q) を計算し、C の変数 wq に格納する。 wq は後に、qvecp->wq に格納され、 3: 以降で使用可能になる 3: wd(t|d) を計算し、C の変数 wd に格納する 後に、wd に 2: で計算した wq(t|q) を掛けたものが変数 w に加えられる 4: norm(d) を計算し、C の変数 norm に格納する 後に、dp->weight /= norm が実行される 5: このパートは、3: のループの直前に挿入される id に発見した文書の ID、 qvec_h に文書 id に含まれる q 中の全ての単語の配列、 qvec_h_len にその要素数を与えられる。 これらの情報から、この文書を結果 d に加えるかどうかの判断を行ない、 「加えない」、と判断した時は、s5_break というラベルに飛ぶ。 ★ wsh への引き数の条件 wsh() と f2c は、wsh() の第1引き数 q についていくつかの条件を仮定している。 この仮定により、後述する f2c による変換で well known な名前の使用が可 能になる。 条件: 各 q[t] のメンバは以下の値にセットされていること。 symbol_t id; q の ID int TF_d; TF(ID|current_document_set) (*1) 語 t の q での頻度を与える int TF; TF(ID|source_corpus) (*1) 語 t の、ソース WAM 中での頻度を与えること 語 t の由来が検索対象となっている WAM とは異なる WAM から来ている場合に対応できるようにするため double weight; 語 t のおもみを与える(*2) int attr; WSH_OR, WSH_AND, WSH_NOT のいずれかを与える その他; wsh() では使われないので不定値で良い(*2) (*1) TF, TF_d はそれぞれ wsh() の出力 dp の TF, TF_d に対応する。 (*2) このメンバは特にユーザが自由に使うことを目的としており、 wsh() 自体 はこのフィールドの存在は認知しない。そのため *.f ファイルの記述により 自由な使用が可能。また、f2c もこのフィールドについては変換のための知識 を持たないため、*.f ファイルでは C コードによりアクセスすることになる。 ● f2c によって書き変えられる項と C コードでの表現の対応について f2c は以下のルールに従って *.f の中身を書き変え、C のソースコードに 変換する。また、*.f の記述で以下のパターンに合致しないものについては f2c はそのまま出力するため、以下のパターンを含まない任意の C コードを *.f に記述することができる。 f2c はパートごとに置換するパターンが異なる。以下では各パートごとにそ の置換パターンを示す。 置換される 置換後 説明 パターン パターン 0: なし 1: なし 2: TF(t|q) ((double)qp->TF_d) 入力リストで与えられた語 t の q での頻度(*3) TF_s(t) ((double)qp->TF) 入力リストで与えられた語tのソース WAM 中での頻度(*3) DF(t) ((double)qvecp->vec->rec_num) 語 t のターゲット WAM での DF、全文書中でこの語がいくつの記事に現れたか TF(t) ((double)qvecp->vec->freq_sum) 語 t のターゲット WAM での TF、全文書中でこの語が何回使われたか idf(t) (log(N_wam_d / (double)qvecp->vec->elem_num)) wq(t|q) wq wq(t|q) を格納するCの変数 (後に、3: で使用) (*3) 上述した wsh() への入力の条件に依存。 3: TF(t|d) ((double)qvecp->elemp->freq) 発見した文書 d 中の t の TF (頻度) TF(.|df) ((double)dp->TF) 発見した文書 d の TF DF(q|d) ((double)dp->DF_d) 発見した文書 d に現れる q 中の単語の数 DF(.|d) ((double)dp->DF) 発見した文書 d の(異なり)長さ wq(t|q) (qvecp->wq) 2: で計算した wq(t|q) へのアクセス wd(t|d) = wd wd(t|d) を格納するCの変数 (後に、wd * wq(t|q) が変数 w に加えられる) 4: TF(.|d) (p_TF) (== wam_get_freqsum(wam, dir_d, dp->id)) 文書 d の総単語数、または長さ DF(.|d) (p_DF) (== wam_get_recnum(wam, dir_d, dp->id)) 文書 d に現れる異り単語数 norm(d) norm norm(d) を格納するCの変数 5: なし ● 変数一覧 *.f で利用可能な C の変数をパートごとに示す。 (指定無き限り、変更してはならない) 全般: q: wsh() の第1引き数 qlen: wsh() の第2引き数 wam: wsh() の第3引き数 dir_q: wsh() の第4引き数 weight_type: wsh() の第5引き数 ndp: wsh() の第5引き数 (アクセス不可) totalp: wsh() の第7引き数 (アクセス不可) cookie: wsh() の第8引き数 ucompar: wsh() の第9引き数 (アクセス不可) dir_d: (dir_q と逆方向が指定されている) N_wam_q: q->id で引ける方向の WAM のサイズ N_wam_d: q->id で引けるのと逆(つまり出力のIDで引ける)方向の WAM のサイズ TF_q: q の TF TF_wam_q: q が属するコーパス(WAM)の総 TF num_and_q, num_not_q: read only. q の中で、 attr が WSH_AND および WSH_NOT であるものの数 qvecp, qvec_h, s5_break: 指定無き限りアクセス不可 以下は、常にアクセス不可 total, d, dh, nd, nnd, a, na, have_cache, qvec, qveclen 0: 1: 2: // ここでは、wq(t|q) を計算しようとしている // なお、t == qp->id qp: 計算しようとしている q のある要素 t を指している qvecp: qvecp->vec: qp->id で wam を引いたもの qvecp->elemendp: qvecp->vec->elems + qvecp->vec->elem_num wq: wq(t|q) を格納する (read/write, 初期値は0.0) e: qvecp->vec->elem_num と同じ qvecp->*, flags, qe: アクセス不可 以下は、 3, 4, 5 でアクセス可能 M_LN2i: 1/log_e(2) log_N_wam_q: log((double)N_wam_q) id: 発見した文書のID qvec_h: 文書 id に含まれる q 中の全ての単語のポインタの配列、 長さは qvec_h_len アクセス可能なメンバは、3: の qvecp と同じ (条件付きで read/write、 すなわち qvec_h の要素をソートするなど 中身の順序を入れ替えることが許可される) qvec_h_len: 発見した文書のDF(q) num_and_d, num_not_d: 発見した d に関わる q のうち attr が WSH_AND および WSH_NOT であるものの数 ただし、 num_and_d は num_and_q に常に等しく、 num_not_d は常に 0 である 3: // ここでは、 wq(t|q) * wd(t|d) の第2因子を計算しようとしている // なお、t == qvecp->elemp->id, d == id wd: wd(t|d) を格納する変数 (read/write, 初期値は 0.0) qvecp: 計算しようとしている q qvecp->wq: 2: で計算した wq(t|q) qvecp->elemp: この文書を発見した単語 qvecp->q: 引き数 q の対応する要素へのポインタ dp: 出力の要素を指している dp->DF: 発見した文書のDF(.) dp->TF: 発見した文書のTF dp->DF_d: 発見した文書のDF(q) (qvec_h_len と同じ値) qvecp->*, dp->*, finish, dp_TF_d, dp_weight, i: アクセス不可 4: // ここでは norm(d) を計算しようとしている // d == *dp norm: norm(d) を格納する変数 (read/write, 初期値は 1.0) p_DF: DF(.|d) p_TF: TF(.|d) p_DF_d: 発見した文書 d に現れる q 中の単語の数 p_TF_d: 発見した文書 d 中の t の TF (頻度)の合計 dp: 出力の要素を指している dp->weight: これに norm を掛けるコードがこのパートの直後に存在する finish: アクセス不可 5: s5_break: ラベルとして使用可 このラベルに goto した場合、 発見した文書は wsh の結果に含まれなくなる この文書に関するステップ 3, 4 もスキップされる dp, finish: アクセス不可 qvecp: 一時変数として使って良い (read/write) プログラム例: { int i, *ng, idx; ng = cookie; /* cookie は、q と同じ長さの int の配列。 このプログラム例では、不要語なら 1、そうで なければ 0をセットしていると仮定している */ /* qvec_h には、発見した文書に含まれる全ての q に関する * 構造体 qvec がセットされている。その要素数は qvec_h_n。 * (つまり、qvec_h[0] .. qvec[qvec_h_len-1]) * qvec から q に戻すには (*qvec_h)->q とする。 * その順序はランダムである。(引き数 q の順序との関連は無い) */ for (i=0; iq - q; /* q の idx 番目の要素だった */ if (ng[idx]) { /* 不要語を1つでも含む結果は捨てる */ goto s5_break; } } } ● 注意 現在の実装では、全ての *.f の記述がマージされ、1つの関数に挿入される。 特に、パート 0: は単純に連結されるので、同じ変数を異なる *.f で宣言す ると、変数の再定義エラーになる。 (wsh では、わざと パート 0: をインクルードした後に変数を定義している。)