第7回MG輪講

日曜日はMG輪講に参加しました．今日は3章の残りと4章を4.2まで読みました．

3.6 Comparison of indexing methods

• signature fileフルボッコ
• まぁ転置リストが長い単語同士のAND検索はsignature fileの方がいいかもね
• ハイブリッドもあるで
• "Compressed inverted files are without a doubt the most useful method of indexing a large collection of variable-length text documents." でしめくくられている．

3.7 Case folding, stemming, and stop words

これらの処理によって得られる恩恵は現在のディスク容量，メモリ容量を考えると大したことない，という結論．IRの教科書ではとりあえずやるっしょ？みたいな空気を醸しているけれど，

• ステミングを行う場合，インデクスに用いるterm IDを他のもの (例えば本文をterm IDで保持する場合) と共有できないから二度手間だよね

4 Querying

Querying = クエリ処理または検索処理 だろうか．今までインデクスの話をしてきたので，実際に検索を行うために具体的にどのような処理を行うのかについて書かれている．

• boolean queryとranked query
  • 最近のIRではboolean検索の結果をランキングしているので，この二つに分けるのに少々違和感
  • boolean retrieval vs. vector space modelの名残だろうか?

4.1 Accessing the lexicon

転置リストの話はしたけれど，転置リストを引っ張ってくるためのlexiconをどのようなデータ構造で保持するのかという具体的な話．IIR 5.2 Dictionary compression (p.82-) あたりの復習．最小完全ハッシュ関数の作り方についてかなり詳しく書かれている．これについてはIIRでも記述がない．

• Fixed-length string (固定長配列)
• Terminated strings (a.k.a. dictionary-as-a-string in IIR)
• Four-entry blocking (a.k.a. blocked storage in IIR)
• Front coding
• Minimal perfect hashing
  • 最小完全ハッシュ関数の作り方．2つの異なるハッシュ値から最終的なハッシュ値を計算．
  • 2部グラフを用いた解説が秀逸．おー，と感動した．
  • hillbig氏作の連想配列ライブラリBepは，3つのハッシュ値を用いた最小完全ハッシュ関数の構築手法を実装したもの．

4.2 Partially specified query terms

lab*といったワイルドカードを用いたクエリ処理を行う方法．IIR p.49,50あたりで書かれているので，復習

• Brute-force matching
• Indexing using n-grams
• Rotated lexicons

感想と残った疑問

• lexiconのデータ構造にはPAT木やDouble配列のようなトライ木が利用されるのかなぁと勝手に思っていたので，出てこなかったのは意外．
• 文字列に対するハッシュ法はハッシュ値の計算に時間がかかるイメージがあったので，今度比較してみよう．
• (p.160)のfront codingの効果について，帰ってからもウンウン悩んでみたけれど未だ理解できず．．．