アルゴリズムイントロダクションの輪講で、第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 です。辞書は単語の集まりで…