以前に Latent Semantic Indexing (LSI) や HITS 絡みで SVD や主成分分析について少し書きました。 http://d.hatena.ne.jp/naoya/20090212/latent_semantic_indexing http://d.hatena.ne.jp/naoya/20090301/hits LSI では SVD を使って単語文書行列を分解し…

大阪にて。しかし、なんで巨大アヒルなんでしょうねえ。大変、和みました。

オライリー・ジャパン から実践ハイパフォーマンスMySQL 第2版が発売されました。第2版の出版にあたって、弊社の id:stanaka, id:hideoki と自分の3人で監訳を担当させていただきました。実践ハイパフォーマンスMySQL 第2版作者: Baron Schwartz,Peter Zaits…

月曜日に、東大の安田講堂で開催された第1回ウェブ学会シンポジウムで発表しました。以下、発表資料です。Web-Gakkai Symposium 2010View more presentations from Naoya Ito.会場の様子などは、今回の発表をファシリテートしてくださったたつをさんの、たつ…

"97 Things Every Software Architect Should Know" という洋書の邦訳が、"ソフトウェアアーキテクトが知るべき97のこと" (www.oreilly.co.jp, www.amazon.co.jp)というタイトルで 10月5日、オライリーから発売です。ソフトウェアアーキテクトが知るべき97の…

2日目の発表も終えました。資料を公開します。はてなブックマークのシステムについてView more presentations from Naoya Ito.今日も少し駆け足気味でした。YACP::Asia 2009、今年も楽しかったです。Hackathon 出ずに京都に戻らなければならなかったのが悔や…

1日目の発表を終えました。資料を公開します。Perlで圧縮View more presentations from Naoya Ito.発表の方は少し駆け足になってしまいました。明日ははてなブックマークのシステム事例の話をしたいと思います。 発表の様子 via: http://yapcasia2009.ficia.…

来週 9月10, 11日は、東京は東工大で開催される YAPC::Asia 2009 に行く予定です。スピーカーとして2枠、いただきました。 9月10日 「Perlで圧縮」 10日には Perlで圧縮 と題して、データ圧縮の概論と Perl でデータ圧縮を行うに当たっての TIPS 的なところ…

通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。Variable Byte Code (Byte Aligned 符号とも呼ばれます) は整数の符…

先日実装した Range Coder (id:naoya:20090724:1248433187) は Perl が use integer すると整数を signed int で扱う関係から low を 24 ビットで妥協し、整数32ビットの上位1バイトを使わない実装を行っていましが、signed int の場合でも 32 ビットの最上…

以前にも Perl で Range Coder を実装した (http://d.hatena.ne.jp/naoya/20080927/1222512024) のですが、当時は理解も曖昧なまま速度にも気を遣わずに実装していました。再度改めて、Range Coder を実装してみました。 http://github.com/naoya/perl-Range…

アルゴリズムイントロダクションの輪講で、第24章の単一始点最短路問題を担当しました。発表に使った資料を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/090622_shortest_paths.ppt SlideShare はこちら。フォントの関係でグラフが崩れ…

昨年の夏ははてなでもインターンシップを開催しました。フレッシュな学生のみなさんと充実した二ヶ月を過ごすことができました。初めてのインターンシップ開催でしたが、学生が課題に取り組む横で講義資料を徹夜で作ったり、学生と一緒になって朝までプログ…

Burrows Wheeler Transform (BWT, Block-sorting) と Prediction by partial matching (PPM) は本質的に同じ事をやっている、というお話です。先日 Managing Gigabytes を読んでいたところ、P.69 で "block sorting is very closely related to the PPM* met…

昨年からはじめたアルゴリズムイントロダクションの輪講も終盤に差し掛かり、残すところ数章となりました。今週は第23章の最小全域木でした。辺に重みのあるグラフで全域木を張るとき、その全域木を構成する辺の合計コストが最小の組み合わせが最小全域木で…

圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累…

String::Dictionary という Perl のライブラリを作ってみました。 http://github.com/naoya/perl-String-Dictionary/tree/master String::Dictionary は検索エンジンその他を作る時に必要になる「辞書」のためのデータ構造 + API です。辞書は単語の集まりで…

週末に参加した Managing Gigabytes の読書会で第2章のハフマン符号を担当しました。この中で Canonical Huffman Codes の解説がありますが、そこにハフマン符号の符号長を効率的に求める手法の説明が含まれています。輪講では時間切れのためこのアルゴリズ…

IIR の第4章 Dynamic indexing では検索用のインデックスにおいて対象とする文書に頻繁に更新が発生する場合にどうそれを扱うべきかという話題を扱っています。ここで "Logarithmic merging" という話が出てきます。以前に読んだ際に良く理解できなかったの…

1999年出版と少し古い書籍ですが Managing Gigabytes を読んでいます。理解のために 2.3 で出て来る Canonical Huffman Codes の習作を作りました。ハフマン符号は情報圧縮で利用される古典的なアルゴリズムで、圧縮対象データに出現するシンボルの出現確率…

「シリコンバレーから将棋を観る」を読んだ。はてなのオフィスが京都に移ってから一年以上が経った。はてなの米国オフィスが閉じてからシリコンバレーに行く機会は一度もなかったし、京都は東京よりも更にシリコンバレーには遠いこともあって、梅田さんと対…

昨日、はてなブックマークFirefox拡張をリリースしました。おかげさまでベータ版からダウンロード数は累積で1万ダウンロードを突破し、アクティブユーザー数も伸びています。 はてなブックマークFirefox拡張で新しいインターネットを体験しよう http://b.hat…

昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です…

適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ…

昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿…

部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言いま…

昨日は第11回 Kansai.pm でした。今回は無理を言って自分がホストを担当させていただきましたが、面白い発表が多く開催した自分も非常に満足でした。PFI の吉田さんによる Cell Challenge での計算機に合わせたアルゴリズムのチューニング手法の発表 (発表資…

現実逃避をしながらウェブを眺めていたら ダイクストラ法（最短経路問題） にたどり着きました。単一始点最短路問題におけるダイクストラ法の解説です。何を思ったのか、図を眺めていたところ動かしたい衝動に駆られて、気付いたらパワポでアニメーションが…