IR
今日はmixiでLuceneソースコードリーディングに参加して、Scorerの部分を読んでました。 Scorerについて Scorerは与えられたクエリに対して文章をidの昇順で返すような抽象クラスです。 検索で使われるメインの部分は以下のようになっており、collectorに対…
NIPS 2009で発表された論文"Polynomial Semantic Indexing" [1]を読んだ。これは低ランク近似を用いた教師ありの情報検索に関する手法である。 情報検索について 与えられたクエリに関して適当な重みづけをおこなって順位づけして、適切な文章を返却するとい…
MG勉強会の発表があるため4.6ランキング検索の部分を読むついでに、最後のサブセクションの上位r個の要素を取り出す部分について実装してみた。情報検索において、N個の候補集合から上位r個の要素を取り出すことが多い。 値が配列に格納されているとするとこ…
最近simhashの実装を行っていて、データの次元が高いとsimhashを計算するのに必要なランダムなベクトルをメモリ上に乗らないという事態が生じたのでad hocな方法で回避していたけど、論文[1]をよく見直すとほぼ同じ方法でより計算コストが少ない方法が紹介し…
今日のInterpolative codingの話が面白かったのと復号の部分のコードが必ずしも自明ではないかと思ったのでメモ。Interpolative codingは長さと出てくる値の最小値、最大値が分かっている狭義単調増加な自然数のリストを圧縮する方法である。 ここで最大値と…
前回に引き続き転置インデックスの圧縮を実装してみる。今回紹介するのは[2]で提案されているSimple-9というアルゴリズムである。Simple-9は32bitのwordにできるだけ数字を詰めていくという圧縮アルゴリズムである。例えば2bitの数が16個ならんでいれば32bit…
Managing Gigabytes勉強会で転置インデックスの圧縮の話が出たので実際に圧縮を行った場合にどれくらいのサイズになるかを計測してみた。利用したデータは英語版Wikidiaの全記事で 文書数 2,872,589 単語数 2,735,620 転置インデックスのポインタの数 397,60…
