« September 2007 | Main | November 2007 »

2007.10.28

Bep: 最小完全ハッシュ関数を用いた連想配列

Bepという連想配列のライブラリを公開しました。BSDライセンスです.

キーは文字列限定で,前もって大量のキーと値のペアが前もって分かっている場合(1千万個とか)、使ってもらえるよう最適化しています。(一応、アドホックな方法で一個ずつキーを登録する方法もサポートしています)
特徴は内部に最小完全ハッシュ関数を利用しており少ない作業領域量でありながらそこそこ高速に動くところです.今のところ1千万キーぐらいで動作するのは確認しています.1キーあたり必要な作業領域量は大体3bit + キー自体の長さになります.

最小完全ハッシュ関数の構築自体も面白い問題です.最小完全ハッシュ関数はキー同士が衝突せず、さらにキーの数がn個のときハッシュ値は[0...n-1]が返されるもので、ぎっしり詰まった連番が返されると思ってもよいです。この実現には以下の論文での手法を使いました.3-ハイパーグラフの頂点割り当て問題を解くことで完全ハッシュ関数を作ってます.
各キー3つのハッシュ値、a,b,cを独立に計算し、その3つのハッシュ値を頂点として持つ枝を作ります.で、この頂点、枝からなるグラフを作ります.このグラフが閉路を持たない場合、各キーに枝中の一つの頂点を他のキーと重複しないように割り当てていくことができます.でこの頂点番号をハッシュ値として使います.
Botelho, F.C., Pagh, R. and Ziviani, N. "Simple and Space-Efficient Minimal Perfect Hash Functions" 10th International Workshop on Algorithms and Data Structures (WADS07) August 2007, 139-150
これ(pdf)を使いました).

あと中でいろいろチューニングしてます。

コンパイルできない、結果間違ってる、バグってる、使いづらいとかありましたら連絡ください。できるだけ改善するようにします。よろしくお願いします。

txも地味にアップデートしてます。こちらもいろいろ使ってもらっているようです。

| | Comments (55) | TrackBack (0)

2007.10.12

統計科学

今月の数学セミナーは「統計科学のすすめ(その2)で最近のベイズ理論っぽい話がいろいろと書かれてます(献本ありがとうございます)。

伊庭さんは相変わらず抽象的なことを分かりやすく説明するのが上手ですし、持橋さんは言語モデルの最前線の話を解説しています。数学のバックグラウンドを持った人とか中/高校生がこの本を読んでどう思うかが興味深いです。


| | Comments (0) | TrackBack (0)

2007.10.06

本の紹介

最近読んだ中で良かった本

・Mind パフォーマンス Hacks ―脳と心のユーザーマニュアル

Mind Hacksに続く続巻でどのようにすれば精神的なパフォーマンスを発揮できるかという方法
記憶法、呼吸法、瞑想、自己催眠、計算法、リスク計算などなど
最初の記憶法で英単語ばっかりなのが残念。まぁ、ちょっと工夫すればいいのかもしれないけど

・The Minimum Description Length Principle

目次とか
最小記述原理:データを表すモデルを選ぶ選ぶ際、モデル上での符号長だけでなくモデル自身を記述する長さも含めて最も短いものを選ぶとよいよ、という話の最新の進展。結構知らない話が盛りだくさんありましたが、内容は私にはむずかしめ。ざっと読んでみたけど、消化するためにはもうちょっとじっくり読まないといけなさそう

・Predicting Structured Data

出版社のページ
機械学習の中で出力側が構造を持ったもの(出力がラベル列、ツリー、グラフなど)の研究の最前線。ここ数年分のトピックと、この本で書き下ろされた記事もいろいろあるみたいです。読みやすく面白い。

| | Comments (1) | TrackBack (0)

« September 2007 | Main | November 2007 »