Skip to content

Latest commit

 

History

History
59 lines (36 loc) · 3.17 KB

index.md

File metadata and controls

59 lines (36 loc) · 3.17 KB

2. ランキング

(想定実行時間:それぞれ1分以内)

0. 準備

転置インデックスを拡張する。product_title フィールドに関して、product_id ごとに単語の出現回数も保存するようにせよ。

1. 優先度つきキュー

サイズ10の優先度つきキューを用意せよ。

2. イテレータ

2つのポスティングリストを与えると、少なくとも片方に含まれる製品について、その product_id とそれぞれの単語の出現回数を返すイテレータを実装せよ。

3. TF

転置インデックスとイテレータを用いて、2単語 HDMICable の少なくとも片方を product_title に含む製品について、それらの出現回数 (TF) の和を優先度として product_id をキューせよ。

続いて、キューに残った製品の product_idproduct_title を優先度順に表示せよ。 また、このとき優先度も表示し、優先度の計算が正しいことを目視で確かめよ。 ただし、単語はスペースで区切られているものとしているので、例えば Cable, は計算に含まれないことに注意せよ。

4. TFIDF

3. では出現回数の和を優先度としたのに対して、ここではまず両単語についてそれぞれ出現回数とIDFの積 (TFIDF) を求め、その和を優先度として同じことを行え。 IDFの定義は複数あるが、この後の設問で再利用するため、BM25の定義の一部を構成するものを利用せよ。 この変更により、HDMI に関する製品も表示されやすくなったことを確かめよ。

5. フィールド長

転置インデックスはフィールドごと単語ごと製品ごとの情報を保存するデータ構造であった。 一般には、これに加えて、フィールドごと製品ごとの(単語に依存しない)情報を保存するデータ構造も必要である。 以下の連想配列を構築せよ。

  • キー:product_id
  • 値:その製品の product_title の延べ単語数(フィールド長

また、このフィールド長の平均を求めよ。

6. BM25

BM25を優先度として 4. と同じことを行え。 一般的なパラメータの値を調べ設定せよ。 この変更により、product_title が短い製品も表示されやすくなったことを確かめよ。

7. BM25F

BM25Fを優先度として 6. と同じことを行え。 このとき、product_brandAmazon Basics との完全一致を優先度の計算に含めよ。 ポスティングリストの走査には含めなくてよい。

このとき、フィールドの重みは product_titleproduct_brand の2倍とせよ。 また、完全一致をみる場合、b パラメータの値や(平均)フィールド長をどのように扱うべきかは考案して実装せよ。

8. パラメータチューニング

7. の問題設定において、パラメータの意味を調べ、値を変更して、product_brandAmazon Basics である製品と、それ以外の製品が適度に混ざるようにせよ。