Logarithmic merging - naoyaのはてなダイアリー
IIR の第4章 Dynamic indexing では検索用のインデックスにおいて対象とする文書に頻繁に更新が発生する場合にどうそれを扱うべきかという話題を扱っています。ここで "Logarithmic merging" という話が出てきます。以前に読んだ際に良く理解できなかったので、改めて復習してみました。 Dynamic indexing 頻繁に検索対象の文書群に更新が発生する場合の問題点は、(postings ファイルはディスク上にあるので) 転置インデックスをその都度構築し直すコストが高くなってしまうというところです。かといって更新をしないと、検索結果が古いままでヒットすべきものがヒットしなくなってしまいます。そこで Dynamic indexing の戦略を採ります。ディスク上の大きなインデックスであるメインのインデックスに加えて、インメモリの小さな補助インデックスを用意し、更
List::FrontCode - naoyaのはてなダイアリー
先日 Array::Gap という Variable Byte Codes による整列済み整数の圧縮の実装を作りました。(id:naoya:20080906:1220685978) 今日は Front Coding を使った同じような圧縮リストクラス、List::FrontCode を作ってみました。Front Coding は辞書式順に整列済みの文字列リストなどを圧縮する手法です。WEB+DB PRESS Vol.42 のアルゴリズム&データ構造の記事で PFI の岡野原さんによる解説があったので、それを参考に実装しました。 Front Coding Front Coding は http://www.hoge.jp http://www.hoge.jp/a.htm http://www.hoge.jp/index.htm http://www.fuga.com/ http://www.
Array::Gap - naoyaのはてなダイアリー
明日は一ヶ月ぶりのIIR輪読会 です。主催のたつをさんから「教科書の話題から何か適当に実装せよ」という課題が出ていたので、5章 のインデックスの圧縮の所で見た Variable byte codes (以下 VB code) を使った圧縮の実装を作ってみました。 整列済みの整数を圧縮する手法 ここでの圧縮のポイントは二つ。 昇順に並べられた整数を、整数そのままの数で扱うのではなく、一つ前の要素との差で扱う。差で扱うと 21,314,156 → 21,314,157 という数は "1" というより小さい数で表現することができる。(整列済みなので、差が分かれば逆の操作で復元が可能) 32 ビット int の整数を固定長 32 ビットで表現するのではなく可変長バイトで表現する。(これが VB code) VB code なら小さな数字は 32ビット = 4バイトよりも小さなビット数で表現できる
Introduction to Information Retrieval #5 の復習資料 - naoyaのはてなダイアリー
Introduction to Information Retrieval の5章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_05.ppt 5章はインデックス圧縮がテーマです。辞書の圧縮と postings files の圧縮に対するそれぞれのアプローチについての解説が主です。転置インデックスの振る舞いに特化した圧縮手法などが紹介されていて、とても面白い章でした。数値表現をビット単位で最適化する γ coding などは目から鱗です。 次回の輪読会は 6/8 予定です。次章の内容は、検索結果のスコアリングについて。tf-idf や Vector space model についての話が中心になります。 過去の章のアーカイブは同 URL のディレクトリ (http://bloghackers.net/~naoya
「Introduction to Information Retrieval」輪講第三回
「Introduction to Information Retrieval」輪講第三回 2008-02-16-4 [IIR][Book] 「Introduction to Information Retrieval」の輪講の第三回を開催しました。 - Introduction to Information Retrieval http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html 今回の会場は DeNA さん（笹塚）の会議室です。 場所提供ありがとうございました。 もうすぐ初台へオフィスを移転するそうなので、ここは最初で最後！ まずは、恒例の id:naoya による「前回の復習」プレゼン。 前回（二章の前半）は細かい話題が多かったので復習の分量も結構たくさん。 そして、前回の続きで私が第二章の後半を担当
「Introduction to Information Retrieval」輪講第一回
「Introduction to Information Retrieval」輪講第一回 2008-01-12-1 [IIR] 先日お知らせした「Introduction to Information Retrieval」の輪講の 第一回を開催しました。(ref. [2007-12-03-2]) - Introduction to Information Retrieval http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html 場所は、当初予定していたコントロールプラスさんが工事のため、 渋谷の株式会社はてなさんの会議室に変更になりました （ありがとうございました！）。 大学の会議室っぽい雰囲気で懐かしめでよい感じでした。 今回は第一章を私が担当しました。 けっこうグダグダでしたが、みなさんのフォローもあ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
