転置インデックスを実装しよう - mixi engineer blog
相対性理論のボーカルが頭から離れないmikioです。熱いわっふるの声に応えて今回はTokyo Cabinetのテーブルデータベースにおける検索機能の実装について語ってみたいと思います。とても長いのですが、最後まで読んだあかつきには、自分でも全文検索エンジンを作れると思っていただければ嬉しいです。 デモ モチベーションをあげていただくために、100行のソースコードで検索UIのデモを作ってみました。Java 6の日本語文書を対象としているので、「stringbuffer」とか「コンパイル」とか「倍精度浮動小数」とかそれっぽい用語で検索してみてください。 インデックスがちゃんとできていれば、たった100行で某検索エンジン風味の検索機能をあなたのデータを対象にして動かすことができます。ソースコードはこちら（テンプレートはこちら）です。 でも、今回はUIの話ではないのです。ものすごく地味に、全文検索
3行でできる超お手軽全文検索 - mixi engineer blog
梅雨。部屋干しした洗濯物による異臭騒ぎに苦しむmikioです。今回は、Tokyo Cabinetのテーブルデータベースで超お手軽に全文検索をする方法について説明します。 使い方 テーブルデータベースについてまずおさらいしておきましょう。PerlやRubyのハッシュのようにコラム名とその値を関連づけた構造を、主キーを識別子として保存するデータベースです。例えばRubyからデータを保存するに以下のように行います。データベースであることをほとんど意識させないというのが素敵ポイントです。APIはCでもPerlでもRubyでもほとんど同じなので、言語にかかわらず同じようにレコードを操作できます。 require 'tokyocabinet' include TokyoCabinet # データベースを開く tdb = TDB::new tdb.open("casket", TDB::OWRITER
String::Dictionary - naoyaのはてなダイアリー
String::Dictionary という Perl のライブラリを作ってみました。 http://github.com/naoya/perl-String-Dictionary/tree/master String::Dictionary は検索エンジンその他を作る時に必要になる「辞書」のためのデータ構造 + API です。辞書は単語の集まりですが、これを配列やハッシュなどで持つのではなく、単語をすべて繋げた一つの大きな文字列として保持することでメモリ領域を節約したものです。単語は単に文字列連結で持つだけでなく、Front Coding で圧縮しています。以下簡単な解説です。 辞書は例えば [0] ･･･ jezebel [1] ･･･ jezer [2] ･･･ jezerit [3] ･･･ jeziah [4] ･･･ jeziel ...という風に単語を配列で持つことで実現でき
統計ソフトRのブログ 共起性尺度
共起尺度について説明します。 共起とは、まさに ある一組の「共に起きる」程度を表したものです。 例えば、 amazonで本を検索するときに、 この商品を買っている人は、この本も買っています と紹介されますが、それは、過去の購買データから、 共起が高い商品を勧めているのです。 共起尺度として、 主なものは、 共起頻度、Jaccard係数、Simpson係数、コサイン距離があります。 これらの指標について、「X」と「Y」という一組の共起性がどう測られるか示します 「X」と「Y」の単独での出現数を|X|、|Y|、 どちらか一方が出現した回数を|X∪Y|、 両方が出現した回数を|X∩Y|とします。 A)共起頻度 共起の回数であり、 |X∩Y|で計算される。 B)Jaccard係数 どちらかが出現したうち、何回同時に出現するかで、 |X∩Y|/|X∪Y|で計算される C)Simpson係数 Jacc
Logarithmic merging - naoyaのはてなダイアリー
IIR の第4章 Dynamic indexing では検索用のインデックスにおいて対象とする文書に頻繁に更新が発生する場合にどうそれを扱うべきかという話題を扱っています。ここで "Logarithmic merging" という話が出てきます。以前に読んだ際に良く理解できなかったので、改めて復習してみました。 Dynamic indexing 頻繁に検索対象の文書群に更新が発生する場合の問題点は、(postings ファイルはディスク上にあるので) 転置インデックスをその都度構築し直すコストが高くなってしまうというところです。かといって更新をしないと、検索結果が古いままでヒットすべきものがヒットしなくなってしまいます。そこで Dynamic indexing の戦略を採ります。ディスク上の大きなインデックスであるメインのインデックスに加えて、インメモリの小さな補助インデックスを用意し、更
ウェブ系の研究をするなら Microsoft に行くべき - 武蔵野日記
SIGIR 2009 の採択論文が発表されていたようだ。SIGIR というのは情報検索に関する世界で一番権威ある国際会議で、情報系の国際会議ランキングでもトップ10にランクインしている。その採択数が一番多いのは Microsoft、二番目が Yahoo! 次いで Google (でも3本だけ)という結果に。 なぜ採択数(率)が問題になるかというと、情報系の国際会議というのは最新の研究成果を発表する場であり、投稿された論文に2人以上の査読者がついて各項目について点数をつけ、一定点数以上のものだけを採択するので、国際会議のランクに応じてそれなりのクオリティの論文が書けないとそもそも通らないし、1人で書ける論文の量にも限界があるので大量に通せる研究機関は研究者の層も厚いことが分かるからである。 上記リンク先でも書いてあるが再度引用すると、 38% of the papers have at le
HITS, 主成分分析, SVD - naoyaのはてなダイアリー
ウェブグラフのリンク解析によるページの評価と言えば PageRank が著名ですが、もうひとつ Jon Kleinberg による HITS (Hyperlink-induced topic search)も有名です。最初の論文 Authoritative Sources in a Hyperlinked Environment は 1999年です。IIR の 21章で、この PageRank と HITS についての解説がありました。 HITS HITS はウェブページの評価に二つの軸を用います。一つが authority スコア、もう一つが hub スコアです。 例えば「Perl の情報が欲しい」という検索要求に対しては CPAN や 開発者である Larry Wall のホームページなどが重要度の高いページかと思います。これらのページは「Perl に関して信頼できる情報源」ということ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
