昨日は年始の挨拶ついでに ELPA について脈絡もなく突然書きましたが、引き続き近頃の開発環境についてもだらだらと書いてみよう。 Mosh mosh というと一部の人間はひげなんとかさんが開発しているモナー的なあれを思い浮かべるかもしれないがそうではなく、mobile shell のことである。 思い切り簡略化して言うと「快適なssh」。回線が不安定な所でもエコー遅延など全く気にせず使えるし、Mac をスリープさせて復帰させたときもリモートホストにそのまま繋がりっぱなしのように見せかけてくれたりする。 詳しくはこの辺を。 mosh: MITからモバイル時代のSSH代替品 - karasuyamatenguの日記 インストールはリモートとローカル両方に必要ですが、まあ大概パッケージがあると思います。EC2 の Amazon Linux でも yum レポジトリの EPEL を有効にすれば y

以前にも Perl で Range Coder を実装した (http://d.hatena.ne.jp/naoya/20080927/1222512024) のですが、当時は理解も曖昧なまま速度にも気を遣わずに実装していました。 再度改めて、Range Coder を実装してみました。 http://github.com/naoya/perl-RangeCoder/tree/master README に記載した通り、静的 Range Coder*1、Binary Indexed Tree を用いた適応型 Range Coder、それからついでに 1-order の有限文脈モデルをもちいたものを作ってみました。いずれも Algorithms with Python の情報 (1, 2, 3)を参考に実装しています。 Canterbury Corpus の alice29.txt は 0-

アルゴリズムイントロダクションの輪講で、第24章の単一始点最短路問題を担当しました。発表に使った資料を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/090622_shortest_paths.ppt SlideShare はこちら。フォントの関係でグラフが崩れたりしているので、ppt で参照した方が見やすいかと思います。 Introduction to Algorithms#24 Shortest-Paths ProblemView more OpenOffice presentations from Naoya Ito. 単一始点最短路問題は、重み付き有向グラフの最短路木を求める問題です。各頂点に最短路重みを記録するのですが、はじめに各頂点の重みを∞として、「緩和」と呼ばれる操作により徐々に頂点の重みを最短路重みに近づけていく、というの

昨年の夏ははてなでもインターンシップを開催しました。フレッシュな学生のみなさんと充実した二ヶ月を過ごすことができました。 初めてのインターンシップ開催でしたが、学生が課題に取り組む横で講義資料を徹夜で作ったり、学生と一緒になって朝までプログラミングについて語ったり、課題を解いたり、新機能を作ったりと我々もたくさんの刺激をもらって、非常に盛り上がりました。最終日の打ち上げなんかはみんななんとなく感傷的になったりして、自分も若い頃を思い出すような気持ちでした。同じインターンに参加した学生同士のその後の交流も続いているようで、良い出会いを提供できたというのも良かったですね。 インターンシップはやってみたら凄く良かった･･･当然、じゃあ今年もやろう!! となりますよね。ということではてなサマーインターン 2009 です。先ほど応募を開始しました。 今年も昨年同様、期間は一ヶ月。前半に大規模ウェブア

Burrows Wheeler Transform (BWT, Block-sorting) と Prediction by partial matching (PPM) は本質的に同じ事をやっている、というお話です。 先日 Managing Gigabytes を読んでいたところ、P.69 で "block sorting is very closely related to the PPM* method, which is a variant of PPM that allows arbitrary-length contexts." という記述があり、どうにも気になったので調べてみました。 サマリとしては、BWT と PPM の一種である PPM* はいずれも文脈から次の1文字を一意に決定するという概念で見ると本質的に同じことをやっていると言える、というところです。 BWT のあら

昨年からはじめたアルゴリズムイントロダクションの輪講も終盤に差し掛かり、残すところ数章となりました。今週は第23章の最小全域木でした。辺に重みのあるグラフで全域木を張るとき、その全域木を構成する辺の合計コストが最小の組み合わせが最小全域木です。 アルゴリズムイントロダクションでは、クラスカルのアルゴリズム、プリムのアルゴリズムの二点が紹介されています。いずれも20世紀半ばに発見された古典的なアルゴリズムです。 二つのうち前者、クラスカルのアルゴリズムは、コスト最小の辺から順番にみていって、その辺を選んだことで閉路が構成されなければ、それは安全な辺であるとみなし、最小全域木を構成する辺のひとつとして選択します。これを繰り返しているうちに最小全域木が構成されるというアルゴリズムです。 今日はクラスカルのアルゴリズムを Python で実装してみました。扱うグラフは書籍の例を使ってみました。以下

圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更

String::Dictionary という Perl のライブラリを作ってみました。 http://github.com/naoya/perl-String-Dictionary/tree/master String::Dictionary は検索エンジンその他を作る時に必要になる「辞書」のためのデータ構造 + API です。辞書は単語の集まりですが、これを配列やハッシュなどで持つのではなく、単語をすべて繋げた一つの大きな文字列として保持することでメモリ領域を節約したものです。単語は単に文字列連結で持つだけでなく、Front Coding で圧縮しています。以下簡単な解説です。 辞書は例えば [0] ･･･ jezebel [1] ･･･ jezer [2] ･･･ jezerit [3] ･･･ jeziah [4] ･･･ jeziel ...という風に単語を配列で持つことで実現でき

週末に参加した Managing Gigabytes の読書会で第2章のハフマン符号を担当しました。この中で Canonical Huffman Codes の解説がありますが、そこにハフマン符号の符号長を効率的に求める手法の説明が含まれています。 輪講では時間切れのためこのアルゴリズムの解説が駆け足になってしまいましたので、改めて解説資料を作ってみました。2009 年の今に Managing Gigabytes を読んでいるという方はあまり多くないかもしれませんが、参考になれば幸いです。 https://www.dropbox.com/s/539fhyc7rf6b9ik/090518computing_huffman_code_length.ppt?dl=0 (PPT, 258K) 先日 Canonical Huffman Codes の習作を Python で実装しましたが、このコード

IIR の第4章 Dynamic indexing では検索用のインデックスにおいて対象とする文書に頻繁に更新が発生する場合にどうそれを扱うべきかという話題を扱っています。ここで "Logarithmic merging" という話が出てきます。以前に読んだ際に良く理解できなかったので、改めて復習してみました。 Dynamic indexing 頻繁に検索対象の文書群に更新が発生する場合の問題点は、(postings ファイルはディスク上にあるので) 転置インデックスをその都度構築し直すコストが高くなってしまうというところです。かといって更新をしないと、検索結果が古いままでヒットすべきものがヒットしなくなってしまいます。そこで Dynamic indexing の戦略を採ります。ディスク上の大きなインデックスであるメインのインデックスに加えて、インメモリの小さな補助インデックスを用意し、更

「シリコンバレーから将棋を観る」を読んだ。 はてなのオフィスが京都に移ってから一年以上が経った。はてなの米国オフィスが閉じてからシリコンバレーに行く機会は一度もなかったし、京都は東京よりも更にシリコンバレーには遠いこともあって、梅田さんと対面で話す機会は一頃に比べると少なくなった。そのためか、これまでの梅田さんの本を読むときとは少し違って、著者とのある程度の距離感と緊張を感じながら読み進めることになった。 書名どおりテーマは「将棋」だ。私は将棋は小中学生の頃に少し遊んだぐらいで、ほとんど素人だ。だから、梅田さんが将棋の本を執筆されたと最初に聞いたとき、これまでとは違って、自分は読者対象から外れるのだろうか? などと思ったりもした。とは言え「梅田望夫が"シリコンバレーから"を書名に冠した」というだけでも、自分にとって購入するのに十分な動機はあった。 まえがきと第一章とを読んで「なるほど」と思

昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ

適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと

昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが

部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog

昨日は第11回 Kansai.pm でした。 今回は無理を言って自分がホストを担当させていただきましたが、面白い発表が多く開催した自分も非常に満足でした。 PFI の吉田さんによる Cell Challenge での計算機に合わせたアルゴリズムのチューニング手法の発表 (発表資料) は圧巻でした。伊奈さんの本文抽出の話 (発表資料)、はこべさんのコルーチンの話 (発表資料)、いずれも難解になりがちなところを凄く分かりやすく解説されていて、さすがだなと思いました。各々ショートトークも、いずれも良かったです。 スペルミス修正プログラムを作ろう 自分も 20 分ほど時間をいただいて、スペルミス修正プログラムの作り方について発表しました。 スペルミス修正プログラムを作ろうView more presentations from Naoya Ito. スペルミス修正プログラムについてはずばり スペル

id:smly さんが PageRank や HITS を Python で実装 されているのに触発されて、自分も PageRank を Perl で実装してみました。 PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使える行列演算ライブラリがあると楽でしょう。 色々調べてみたところ、PDL (The Perl Data Language) が良く使われているようでしたので、これを選択しました。PDL では各種行列演算が簡単に行える他、文字列評価をオーバーライドして行列の文字列出力を良い具合で定義してくれていたりと、なかなかに便利です。PDL は行列計算以外にも色々な科学技術計算やグラフ描写などの操作をサポートしているようです。 さて、PDL を使った PageRank 計算のコードは以下のように

ウェブグラフのリンク解析によるページの評価と言えば PageRank が著名ですが、もうひとつ Jon Kleinberg による HITS (Hyperlink-induced topic search)も有名です。最初の論文 Authoritative Sources in a Hyperlinked Environment は 1999年です。IIR の 21章で、この PageRank と HITS についての解説がありました。 HITS HITS はウェブページの評価に二つの軸を用います。一つが authority スコア、もう一つが hub スコアです。 例えば「Perl の情報が欲しい」という検索要求に対しては CPAN や 開発者である Larry Wall のホームページなどが重要度の高いページかと思います。これらのページは「Perl に関して信頼できる情報源」ということ