転置インデックスの構成とブーリアン検索
転置インデックスの構成とブーリアン検索 2008-01-18-1 [IIR][Algorithm] 「Introduction to Information Retrieval」[1]の第一章[2008-01-12-1] の転置インデックスまわりの用語と検索手順などの解説です。 ちょっと前に書いた 『ウェブ検索を「本の索引」で説明する試み』[2007-06-17-6] という記事の続きでもあります。 「転置インデックスによる検索システムを作ってみよう！」 [2007-11-26-5]もご参考に。 § 転置インデックス (inverted index または inverted file) は、 dictionary と postings の二つの部分から構成されます。 dictionary は索引語 (term) の集合です。 term が登場する文書の ID を posting と呼びます
雲梯をすすむように - @m_seki の
Ruby/RBTreeの存在をいままでしりませんでしたが、これ、おもろい。RB木（SBB木?）を提供する拡張ライブラリで、当然だけどRubyで書いた誰かのSBB木よりも相当速いと予想されます。 例によって転置インデックスをつくるよ。 require 'rbtree' tree = RBTree.new while line = ARGF.gets line.scan(/(\w+)/) do |words| pos = Regexp.last_match.begin(0) key = [words[0], ARGF.path, ARGF.file.lineno, pos] tree[key] = true end end 単語、ファイル名、行番号、行内の位置のArrayをkeyとします。valueはどうでもいいのでtrueで。 RBTreeのboundメソッドを使うとある範囲の要素を順に辿れ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
