Data Compression Programs by Matt Mahoney As of July 23, 2009, this page is no longer maintained. The newest version can be found at http://mattmahoney.net/dc/ All software on this page is open source licensed under GPL and believed to be unencumbered by patents. All downloads include Windows executables and C++ source code for Windows or Linux/UNIX. The source code comments explain how the prog

更新履歴 2004/01/07 　O(N) 構築アルゴリズム三種追加（Ko &Alulu, Kim & al., Karkkainen & Sanders) Suffix Arrayは、最近注目を集めているデータ構造です。その理由として、 (1)大規模なデータに対して、高速に検索、情報抽出を行うことができる (2)BWTとしてデータ圧縮に用いることができる。 ことが挙げられます。(1)に関しては自然言語処理において、膨大な量のコーパスから情報（例えば、単語の出現回数など）を調べるときににSuffix Arrayを用いると非常に高速に求めることができます。 膨大な量のコーパスに基づいた自然言語処理が盛んになってきている今、Suffix Arrayが注目を集めています。 また、ゲノム情報を調べるバイオインフォマティクスにおいても、ここの配列と似ている部分（例えばCCAG）を調べるといった場合

_ [コンピュータ] Bayesian Sets何はともあれ一番目立つところにリンクをば。 ここのところちょっと時間が取れたので、以前から気になっていたBayesian Setsを実装してみました。Bayesian Setsは、ある単語を入力すると、それと関係が深い単語を推測して返してくれるというものです。Google Setsというサービスを聞いたことがある方もおられるかもしれませんが、やりたいことはあれと同じです。理論的な話に興味がある場合はここを参照するか、元論文に当たってください。 論文で「高速」と紹介されているだけあって、Wikipediaから17万文書を使って学習させたにも関わらず結構な速度で動いてくれています。辞書に登録されている単語数も44万と豊富。これだけのものを現実的な時間で捌いているというだけでも、かなり驚きです。無理やりアドホックに処理を端折って計算量を減らしている

原文: Thermodynamics and Garbage Collection. ACM Sigplan Notices 29, 4 (Apr 1994), 58–63. Henry G. Baker Nimble Computer Corporation 16231 Meadow Ridge Way, Encino, CA 91436 (818) 986–1436 (818) 986–1360 (FAX) Copyright (c) 1993 by Nimble Computer Corporation 日本語訳: 酒井 政裕 私たちは統計力学の原理とそのストレージ管理の問題への適用について議論します。 また、私たちは 情報, 状態, 可逆, 保守的 といった用語の不正確な用法による問題について指摘します。 A. はじめに 計算機科学者は抽象統計熱力学についての知識を持っている

Platform: All Version: 5.0 and Above このノートでは、Arrayオブジェクトにエレメントをランダムに並替えるメソッドを定義する上級者向けのサンプルを、ご紹介します。 1. Arrayオブジェクトにメソッドを定義する 'new'演算子を使ってインスタンスを生成するオブジェクト(クラス)には、'prototype'プロパティがあります。この'prototype'プロパティに'function'を設定すると、そのオブジェクト(クラス)にメソッドを追加して定義することができます。 Arrayもそうした定義のできるオブジェクトのひとつです。ArrayオブジェクトにメソッドnewMethodを定義するには、つぎのようなスクリプトを記述します。 Array.prototype.newMethod = xNewMethod; function xNewMethod ()

JavaScriptで配列をシャッフルする話を見て、そういえばArray#shuffleは以前書いた記憶があるなーと思って調べてみたらコピペだった。 http://www.fumiononaka.com/TechNotes/Flash/FN0212002.html Fisher-Yatesというアルゴリズムだそうです。 Array.prototype.shuffle = function() { var i = this.length; while(i){ var j = Math.floor(Math.random()*i); var t = this[--i]; this[i] = this[j]; this[j] = t; } return this; } a = [1,2,3,4,5]; a.shuffle() // 3,1,5,2,4 a // 3,1,5,2,4 ごく普通に実装

Ruby on Rails, Io, Lisp, JavaScript, Dynamic Languages, Prototype-based programming and more... Technoblog reader special: $10 off web hosting by FatCow! Wednesday, August 16, 2006 I am very happy to announce that Google's MapReduce is now available for Ruby (via gem install starfish). MapReduce is the technique used by Google to do monstrous distributed programming over 30 terabyte files. I have

_ 日本語と n-gram でも Zipf の法則は成り立つか Zipf の法則というのは以下のようなものです。英語で書かれた長編小説を用意します(小説でなくてもいいんだけど)。そして、本文中に出てくる英単語を頻度順に並べます。すると、第2位の単語の頻度は第1位の単語の頻度の半分になります。第10位の単語の頻度は第1位の単語の頻度の1/10です。第100位の単語の頻度は第1位の単語の頻度の1/100です。そんな感じの法則です。リンク先にもあるように対数グラフにプロットするときれいな直線になります。 さて、Zipf の法則は日本語に対して当てはまるでしょうか。とはいっても、日本語は英語みたいに単語毎に区切ることが簡単ではないので、ここでは n-gram を使います。2文字毎に文を区切って、その2文字を単語だと思って頻度を数えます。ひらがなと漢字だけを対象にしました。日本語のデータとしてはこの

━─────────────────────────────────── アセンブラ講座（番外編） 《万能数値表現法　ＵＲＲ》 鎌田　誠 ──────────────────────────────────── IEEE 754 で規格化されている浮動小数点数の表現方法は符号と指数部と仮数 部に整然と分けられていてわかりやすく、実装も容易なのですが、指数部と仮数 部を区切る位置を固定してしまったために、大きな数を扱いたい技術者には指数 部の範囲が狭すぎ、精度を要求する技術者には仮数部のビット数が少なすぎると いう問題点があります。 しかし、かつて日本人によって IEEE 754 よりも算術的に優れている浮動小数 点数の表現方法が考案されていたことを知る人はほとんどいないでしょう。その 数値表現法は考案された当時の技術では実装が困難だったために規格化されなか ったようですが、非常に興味深い数

キャッシュと更新 昨日の続き。 前にも書いたとおり、削除は哲学的な問題だ。更新も、削除ほどではないが、かなり哲学的だ。 研究レベルでは、「削除も更新もしない」というポリシーが大流行中らしい。すべて追記オンリーで済ませる。当然、HDDの記憶容量は消費する一方で、使い方によってはあっという間にゴミで埋まってしまうが、それは無視するのが研究レベルというものらしい。過去の状態がそのまま取り出せるので便利だが、ゴミで埋まるような使い方があることを考えると、MVCC的な方法のほうが汎用性がある。 私としては、もうひとつ疑問がある。 変化するデータを追記オンリーのストレージ上で表現しようとすると、なんらかの形で、アドレスの予約が必要になる。アドレスを予約できなければ、データが追記されたとき、そのデータのアドレスを知る方法がない。アドレスが予約されているということは、そのアドレスについて「まだデータが書き