niamのブックマーク - はてなブックマーク

転置インデックスを実装しよう - mixi engineer blog

相対性理論のボーカルが頭から離れないmikioです。熱いわっふるの声に応えて今回はTokyo Cabinetのテーブルデータベースにおける検索機能の実装について語ってみたいと思います。とても長いのですが、最後まで読んだあかつきには、自分でも全文検索エンジンを作れると思っていただければ嬉しいです。デモモチベーションをあげていただくために、100行のソースコードで検索UIのデモを作ってみました。Java6の日本語文書を対象としているので、﹁stringbuffer﹂とか﹁コンパイル﹂とか﹁倍精度浮動小数﹂とかそれっぽい用語で検索してみてください。インデックスがちゃんとできていれば、たった100行で某検索エンジン風味の検索機能をあなたのデータを対象にして動かすことができます。ソースコードはこちら︵テンプレートはこちら︶です。でも、今回はUIの話ではないのです。ものすごく地味に、全文検索

niam 2009/07/05

リンク

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

niam 2009/06/24

リンク

軽量データクラスタリングツールbayon - mixi engineer blog

逆転検事を先日クリアして、久しぶりに逆転裁判1〜3をやり直そうか迷い中のfujisawaです。シンプルなデータクラスタリングツールを作成しましたので、そのご紹介をさせていただきます。クラスタリングとはクラスタリングとは、対象のデータ集合中で似ているもの同士をまとめて、いくつかのグループにデータ集合を分割することです。データマイニングや統計分析などでよく利用され、データ集合の傾向を調べたいときなどに役に立ちます。例えば下図の例ですと、当初はデータがゴチャゴチャと混ざっていてよく分からなかったのですが、クラスタリングすることで、実際は3つのグループのデータのみから構成されていることが分かります。様々なクラスタリング手法がこれまでに提案されていますが、有名なところではK-means法などが挙げられます。ここでは詳細については触れませんが、クラスタリングについてより詳しく知りたい方は以下の

niam 2009/06/11

リンク

データベースの動的デフラグ - mixi engineer blog

ノートPCの冷却ファンがうるさいのを対処しようとしてWebで調べたら、そのファンの設計者が﹁静音性へのこだわり﹂を語ったページにたどり着いて複雑な心境のmikioです。今回は、Tokyo Cabinet︵TC︶の最新バージョンで実装された動的デフラグ機能について長々と説明します。断片化とデフラグ任意のサイズのデータを管理する記憶装置においては、利用可能領域の断片化︵fragmentation︶の問題が常につきまといます。ファイルシステム上で任意のサイズのファイルを管理する際にも、データベースファイル内で任意のサイズのレコードを管理する際にも、C言語のmalloc/free関数群でメモリの管理をする際にも、様々なレイヤで断片化が起きうるのです。なぜなら、データを削除もしくは移動した際の空き領域を再利用するにあたって、その領域と同じサイズのデータが常に入ってくるとは限らないからです。特にデ

niam 2009/05/23

リンク

mixi Engineers’ Blog » 圧縮データベースを使おう

チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet︵TC︶のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。圧縮B+木 B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木︵multiway balanced treeの略であり、二分木︵binary tree︶とは違います︶の索引を張ったものです。理論的にはレコードの探索も更新も O(logn) の時間計算量で行え、内部ノード︵B木︶の操作をキャッシュすると実質的には O(1) の時間計算量で探索や更新が行えるという、かなり安定した性能を備えるデータ構造です。その上、レコードが一定の順序に基づいて並べられているので、数値の範囲検索や文字列の前方一致検索が高速に行えたり、カーソルによって順序に基

niam 2009/04/14

リンク

はてなブックマーク

タグ

ブックマーク / mixiengineer.hatenablog.com (5)

お知らせ

今週のはてなブックマーク数ランキング（2024年7月第1週）

月間はてなブックマーク数ランキング（2024年6月）

今週のはてなブックマーク数ランキング（2024年6月第5週）

公式Twitter

キーボードショートカット一覧

はてなブックマーク

公式Twitter

はてなのサービス