Algorithm::MTF / BWT → MTF → Range Coder によるデータ圧縮 - naoyaのはてなダイアリー
先日言及した Burrows Wheeler Transform (id:naoya:20081016:1224173077) による変換後のテキストは圧縮に使えたり、全文索引に利用できたりと応用範囲は広いです。 BWT により変換したテキストを圧縮するには、そのまま圧縮するのではなく先頭移動法 (Move-To-Front http://ja.wikipedia.org/wiki/Move_To_Front) を適用することでより情報に偏りを持たせてから圧縮するのがセオリーです。 今日は先頭移動法の Perl 実装を作ってみました。Algoritm::MTF です。 http://github.com/naoya/perl-algorithm-mtf/tree/master に置いています。 use Algorithm::MTF; my $encoder = Algorithm::MTF
Integer::Elias - Elias gamma/delta coder - naoyaのはてなダイアリー
Perl でγ符号、δ符号で整数を符号化するためのモジュールを作りました。(ω符号はまだサポートしていませんが) Elias 整数符号のモジュールなので Integer::Elias という名前にしています。 http://github.com/naoya/perl-integer-elias/tree/master γ符号、δ符号は整数の可変長符号です。バイト単位での可変長符号は ASN.1 BER (id:naoya:20080906:1220685978 参照) がありますが、γ符号、δ符号はビット単位での可変長符号で、より短いビット数で小さな整数を符号化することができます。 例えば 6 という数字があったとします。 6 の二進数での表現は 110 で 3 ビットです。110 の先頭ビットを除いたビット 10 で 2ビットあります。このビット数 2 を α符号 (Unary code
Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |i i| }! }} /／| |l､{ j} /,,ｨ//｜ 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' } ,ﾉ _,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ , ﾀ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ おれも何をされたのかわからなかった… ,ﾞ ／ )ヽ iLﾚ u' | | ヾｌﾄﾊ〉 |／_／ ﾊ !ニ⊇ '／:} V:::::ヽ 頭がどうにかなりそうだった… /／ 二二二7'T'' ／u' __ /:::::::/｀ヽ /'
Perl で Range Coder - naoyaのはてなダイアリー
練習がてら、圧縮符号化の手法のひとつである Range Coder を Perl で実装してみました。 http://github.com/naoya/perl-algorithm-rangecoder/tree/master Range Coder は算術符号を実数ではなく整数で実現した手法です。高速な算術圧縮を実現する「Range Coder」 (1/2)：CodeZine（コードジン） に詳しい解説があります。今回の実装も、この記事にあるソースコードを参考に実装しました。参考、というか結局ほとんど移植に近くなってしまいました。 インタフェースは以下のようになっています。入力文字列における各記号の出現頻度、累積出現頻度をあらかじめ算出して RangeCoder オブジェクトにセットしてから、encode することで圧縮結果が得られます。(出現頻度表をバイナリに添加する実装は行っていませ
GNU screen いろいろまとめ。 - naoyaのはてなダイアリー:
先日人力検索で GNU screen の設定TIPSについて質問してみたところ、かなーり役立つ設定とかをたくさん教えてもらうことができました。みなさん感謝。 そんで、教えていただいた通りにカスタマイズした結果、こんな感じのスクリーンショットが撮れました。MacOSX のターミナルです。 おかげさまでかなり便利になって作業効率が上がったと思います。いろいろ教えてもらったお礼とまではいきませんが、やった設定とかをはまりどころとかも交えて紹介してみます。名付けてリバースNDOメソッド。ちなみに、知ってる人にはごく当然のことが当たり前のように書いてるので、あんまり役に立たないかもしれません。 hardstatus alwayslastline で最終行にウィンドウ一覧を表示 これは今回の質問とは直接関係ないのですが、やるとやらないとでかなり使い勝手が違うので。 hardstatus alwaysl
Hadoop Streaming - naoyaのはてなダイアリー
id:naoya:20080511:1210506301 のエントリのコメント欄で kzk さんに教えていただいた Hadoop Streaming を試しています。 Hadoop はオープンソースの MapReduce + 分散ファイルシステムです。Java で作られています。Yahoo! Inc のバックエンドや、Facebook、Amazon.com などでも利用されているとのことです。詳しくは http://codezine.jp/a/article/aid/2448.aspx (kzk さんによる連載記事)を参照してください。 Hadoop Streaming 記事にもあります通り、Hadoop 拡張の Hadoop Streaming を使うと標準入出力を介するプログラムを記述するだけで、Hadoop による MapReduce を利用することができます。つまり、Java 以外
Kansai.pm での発表資料 (Hadoop Streaming で MapReduce) - naoyaのはてなダイアリー
Kansai.pm に参加しました。とても楽しかったです。自分も "Hadoop Streaming で MapReduce" という題目で発表しました。取り急ぎ、資料を以下に公開します。 http://bloghackers.net/~naoya/ppt/080530kansaipm.ppt MapReduce は Google のバックエンドで動いている分散並列バッチ処理システムです。GFS は Google の分散ファイルシステムです。Google ウェアのクローンとしてオープンソースで開発されているのが Hadoop。Hadoop は Yahoo! Inc や Facebook, Amazon.com などでも利用されているとのこと。Hadoop は Java ですが、Hadoop Streaming を使うと Java 以外でも MapReduce できます。 以下のエントリも合
naoyaのはてなダイアリー - 負荷とは何か
調べごとをしたので blog に書いて理解を深めようのコーナーです。長文です。 Linux でシステム負荷を見る場合にお世話になるのが top や sar (sysstat パッケージに同梱されてるコマンド) などのツールです。 top ではシステム統計のスナップショットを見ることができます。今システムがどういう状態かなーというときは top が便利。 top - 08:16:54 up 3 days, 14:43, 6 users, load average: 0.18, 0.07, 0.03 Tasks: 43 total, 2 running, 41 sleeping, 0 stopped, 0 zombie Cpu(s): 18.2% us, 0.0% sy, 0.0% ni, 81.8% id, 0.0% wa, 0.0% hi, 0.0% si一方の sar では10分ごとのシ
はてな記法が使えるTropyクローン - Haropy - naoyaのはてなダイアリー
結城さんが作った Tropy が何だか面白い。氏曰くWeb 0.5としてのTropy。ここでいう Web 0.5 というのは揶揄としての Web 0.5 ではなく、ちゃんと意味をもった 0.5。 クローンもすでにいくつか生まれているようだし、僕も暇つぶしがてら作ってみた。はてな記法が使えるTropyクローンということで、Haropy。 http://haropy.bloghackers.net/help サニタイズとかほとんどしてないのでアレなんですが、その辺は近藤タンに相談しつつ Text::Hatena でのやり方を聞いてから実装しよう。とりあえずこんなものが動きました程度に。 中の実装は Catalyst で作ってあります。実は、はじめは 10分で作る Catalyst アプリケーション実演をやろうと思ってたんだけど、つくりはじめたらちょっと面白くなったのでちゃんと作ってしまったとい
naoyaのはてなダイアリー - 刺激を受けた本5冊...プラスで技術本5冊
「読書」とひと口に言っても、仕事用に要点のみ読むものもあれば、味わうように精読するものもある。また、本には特定目的のために「使える」ものもあれば、人生を変えるような書もある。彼らがエンジニアとしてどんな本を読み、どんなことを考えてきたか、参考にしてみよう。 Tech総研さんから取材をしていだきました。刺激を受けた本を5冊、とのことですのでハッカーと画家とかを中心にピックアップしてみました。「参考になった」ではなくて「刺激を受けた」というテーマだったので、気づいたら自己啓発本とマーケティング本のみになっていて、いわゆる技術書が入ってませんでした。 じゃあ参考になった技術書、というので挙げるとしたらどれかなあということでリストアップしてみる。5冊に絞るのはなかなか難しいのですが。 リファクタリング―プログラムの体質改善テクニック (Object Technology Series) 作者: マ
Dampening, Buffering, OpenSearch, Ajax な Hack - naoyaのはてなダイアリー
ちょっと前に Six Apart の Anil Dash の blog で Web Development Trends for 2006 なんて話題があって、来年のウェブ開発トレンドはこれだ! なんてことを彼の独断でリストアップしてました。氏曰く AtomPP, XHTML, JSON, E4X, Ruby ... などなど。 このリストがほんとにトレンドになるかですが、Ruby は Rails の勢いがますます加速しているし、AtomPP は今年末に仕様が確定する他 RESTful なアプリケーション設計が注目を集めています。あと JSON が熱いのはいわずもがな...ということで結構いいところを突いてる気がします。 この中で聞きなれないれない言葉として Dampening と Buffering というのが出てきます。どちらも Rails を開発した DHH がいる 37signal
prototype.js でデザインパターン - Bridge
結城さんのデザパタMLでも紹介されてしまった手前、さぼるわけにもいくまい、ということで「機能の階層と実装の階層を分ける」 Bridge パターンです。 使いどころはたくさんありそうでなさそうでありそうな(どっちだ)、個人的には結構好きなパターンです。プログラムを拡張するには、クラスを追加するわけですが、あらかじめ「機能」を追加するのか、「実装」を追加するのかという視点で二つの階層に分けて実装しておくことで、拡張しやすい構成にしましょうというパターンです。 +-------------+ |Hello, Japan.| +-------------+ +-------------+ |Hello, World.| +-------------+ +----------------+ |Hello, Universe.| +----------------+こんな感じの出力を作りたい場合、まず
prototype.js でデザインパターン - Abstract Factory
ようやく8つめ。まだ残り 15 あります。8つめは「関連する部品を組み合わせて製品を作る」Abstract Factory パターン。複数のオブジェクトを正しい組み合わせで生成されるようにしたい、といったときに使うパターンです。 デザパタ本の題材は階層構造を持ったリンク集ページを作る、というものですね。 LinkPage * 新聞 o 朝日新聞 o 読売新聞 * サーチエンジン o Yahoo! + Yahoo! + Yahoo! Japan o Excite o Google -- 伊藤 直也こんな感じの出力を HTML で出してみましょう、というもの。 集合を扱う Tray クラスと、各個別のリンクを扱う Link クラスを用意してそのインスタンスを操作しページに相当する Page クラスに追加していくことでこの出力を作ります。ただ、出力は ul/li によるリスト構造による出力とか
prototype.js でデザインパターン - Builder パターン
7つめは、「複雑なインスタンスを組み立てる」Builder パターンです。 var Main = Class.create(); Main.prototype = { initialize : function () {}, main : function () { var builder; if (arguments[0] == 'plain') builder = new TextBuilder(); else builder = new HTMLBuilder(); director = new Director(builder); director.construct(); document.writeln(builder.getResult()); } } というクライアントがあり、その出力は引数が plain なら ============================ 『G
prototype.js でデザインパターン - Prototype パターン
続きまして「コピーしてインスタンスを作る」Prototype パターンです。デザパタ本では6章にあたります。 var Main = Class.create(); Main.prototype = { initialize : function () {}, main : function() { var manager = new Manager(); var upen = new UnderlinePen('~'); var mbox = new MessageBox('*'); var sbox = new MessageBox('/'); manager.register("strong message", upen); manager.register("warning box", mbox); manager.register("slash box", sbox); docum
prototype.js でデザインパターン - Singleton
次は「たった1つのインスタンス」Singleton パターンです。あるクラスがあって、そのクラスのインスタンスは実行アプリケーションのライフサイクルを通じて唯一に制限したい、何回生成しても同じインスタンスである、というものです。 var Main = Class.create(); Main.prototype = { initialize : function() {}, main : function() { document.writeln('Start.<br>'); var obj1 = Singleton.getInstance(); var obj2 = Singleton.getInstance(); if (obj1 == obj2) { document.writeln('obj1 と obj2 は同じインスタンスです。<br>'); } else { document
prototype.js でデザインパターン - Factory Method
お次は「インスタンス作成をサブクラスにまかせる」Factory Method パターン。これまた定番。 var Main = Class.create(); Main.prototype = { initialize : function() {}, main : function() { var factory = new IDCardFactory(); var cards = new Array( factory.create('Erich Gamma'), factory.create('Richard Helm'), factory.create('Ralph Johnson'), factory.create('John lissides') ); for (var i = 0; i < cards.length; i++) { cards[i].use(); } } } とい
prototype.js でデザインパターン - Template Method
次は「具体的な処理をサブクラスにまかせる」Template Method パターン。定番ですね。 var Main = Class.create(); Main.prototype = { initialize : function () {}, main : function () { var d1 = new CharDisplay('H'); var d2 = new StringDisplay('Hello, world.'); var d3 = new StringDisplay('Oh! JavaScript'); d1.display(); d2.display(); d3.display(); } } みたいなクライアントがあります。出力結果として、 [[HHHHH]] +-------------+ |Hello, world.| |Hello, world.| |Hel
prototype.js でデザインパターン - Adapter
Iterator に続きまして、「一皮かぶせて再利用」な Adapter パターンです。クライアントは var Main = Class.create(); Main.prototype = { initialize : function() {}, main : function () { var p = new PrintBanner("Hello, World"); p.printWeak(); document.writeln('<br>'); p.printStrong(); } } といった感じ。PrintBanner クラスは別のレガシーなクラスのアダプタで、インタフェースを肩代わりしてやっていると。 実行結果は (Hello, World) *Hello, World*となります。 今回もやっぱり interface に相当するものは作らずにやってみます。(Adapter
prototype.js でデザインパターン - Iterator
Ruby on Rails や Catalyst のプラグインなんかでは prototype.js という JavaScript のライブラリを使って、Ajax サポートを実現しています。prototype.js とフレームワークが必要な Ajax の JavaScript コードを吐き出してくれるので、Ruby プログラマや Perl プログラマは JavaScript の実装を意識しなくても Ajax なインタフェースが作れる、という風になっています。 こんな感じで prototype.js は Ajax な部分に注目が集まっていますが、ほかにも "Class-style OO" なフレームワークも内包してます。 JavaScript はプロトタイプベースのオブジェクト指向言語で、C++ や Java のようなクラスベースのオブジェクト指向言語とはちょっと実装が異なります。プロトタイプ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
