どうも更新をサボりまくりの有末です。 本日はゲームなどのフラグ管理に使えるビット演算について書きたいと思います。 進数 日本人の100人にアンケートを取れば、おそらく9の次は10と答える人が大多数だと思います。 ただしこれは厳密には間違っていて9の次が10になるのは10進数で物事を考えているからです。 進数というのは簡単に言うと「いつ桁があがるか？」という事です。 例えば普段使用している10進数であれば0から数えて10個目（9）までは1桁で表せますが 11個目（10）からは2桁になります。 なかなかイメージがし難いと思うので以下2進数、8進数、10進数、16進数を見て行きます。 桁がいつ増えるか？に注目してください。 2進数 8進数 10進数 16進数 0 0 0 0 1 1 1 1 10 2 2 2 11 3 3 3 100 4 4 4 101 5 5 5 110 6 6 6 111 7

base-64よりもスペース効率の良い方法。 GitHub レポジトリ 1 概要 バイナリをテキストに変換するエンコード方式としての base-64 は、そのデータ量を33％増大させます。この記事では、UTF-8のテキスト変換方式であり、元のデータから14％増大するbase-122を紹介します。base22はWebを念頭において作られました。 実装 には、Javascriptのデコーダを使い、base-122でエンコードしたリソースをWebページに読み込ませる過程が含まれます。 免責事項 3で示すように、base-122は 大半のWebページが該当します gzip圧縮ページでの使用は推奨しません。ですが、base-122は一般的な文字エンコード方式として役に立つ可能性があります。 1.1 はじめに 画像、フォント、オーディオなどの外部のバイナリリソースは、base-64でエンコードする デ

釣りタイトルを付けたかったのですがさっぱり思いつかないのでもう諦めました。徳永です。 今回はCentroid Path Decomposition（以下CPD）についての話を書きます。直訳すると重心パス分解となるでしょうか。Trieを実現するためのテクニック（普通のツリーにも使えるのかな？なかなか難しそうですが…）の一つです。CPDは一年前の弊社岡野原の記事に出てきますが、私のような素人にはあれだけでは理解できない部分があったので、今回はちょっと論文を読んでみました。 Trieの実装によくある問題 Trieを実現するためのデータ構造というとダブル配列とかが挙げられますが、こういった高速なデータ構造にも、ランダムアクセスが多いという弱点があります。メモリはHDDなどと比べるとランダムアクセスに耐えうる記憶媒体ですが、とは言えランダムアクセスは避けられるに越したことはありません。CPDを使うこ

なにやらDan Kogai氏の以下の記事が話題になっている様子。 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? 連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これからはトライ(trie)木を使うのがイケてる！(意訳)という内容だった。 連想配列にハッシュテーブルを使うのが良いか悪いかについては色々と意見があると思うので特にこの記事では触れない。 今回は連想配列として使えると話題のトライ木とはなんぞ、という入門的な記事にしようと思う。 トライ木が持つ機能 最初にトライが持つ以下の3つの機能について説明する。 - lookup - common-prefix-search - predictive-searchまずトライは連想配列として利用できる。つまりキーワードと値のペアを登

はじめましてこんにちわ。 4月からPFIで働いているまるまる（丸山）です。最近のマイブームはスダチです。 リサーチブログの更新が再開されたので、私も流れに乗って初ブログを書いてみようと思います。 今回は社内の情報検索輪講で少し話題にあがったCompressed Permuterm Indexを紹介したいと思います。 Paolo Ferragina and Rossano Venturini. “The compressed permuterm index”, ACM Transactions on Algorithms 7(1): 10 (2010). [pdf] これを実装したので以下のgoogle codeに晒してみることにします。 http://code.google.com/p/cpi00/ 修正BSDライセンスです。ソースコードは好きにしてもらって構いませんが、完成度はまだまだな

ブログの更新がとまっていましたが、また少しずつ更新してきたいと思います。 今回はtrie（トライ）の最近の話をしたいと思います。 trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情報を扱ったり、最近だと、KVS（Key Value Store)のようにキーを介してデータを保存、読み込みをしたりと様々な場面で利用されます。 同じようにキー集合を格納するデータ構造としてハッシュを利用する方法があります。キーからハッシュ値を計算し、その場所に文字列へのポインタを格納しておくデータ構造です。ハッシュを利用した場合とtrieを利用した場合の一番の大きな違いは、trieの場合だと、ある文字列から始まるキーを全て列挙する、いわゆる接頭辞探索ができることです。例えば”te”で始まる文字列を網羅的に調べることができます。木をたどって、”te”の下

package search; /** * 文字列に対するマッチ処理を行うためのインターフェイス。 */ public interface Matcher { boolean match(String target); } package search; import java.util.HashMap; import java.util.Map; /** * マッチ対象の文字列集合を前処理し、ツリー構造で保持する。 * NGワードチェックなど、マッチ対象の文字列集合がほぼ静的に決定されるケースで高速に動作する。 */ public class TreeMatcher implements Matcher{ private CharTreeNode rootNode = null; public TreeMatcher(String[] words){ this.rootNode = ne