好きなアルゴリズムなあに？

はてな村民の好きそうなテーマです．
あなたが一番好きなアルゴリズムを教えてください。 また、その.. - 人力検索はてな

回答一覧に僕の好きなのはあるかな？
ちら見してみると一つ目からヒット．エディットグラフ？数学的に高度な知識？一瞬なんのことかわかりませんでしたが，リンク先を見てみると編集距離の話でした．文字列と文字列がどれくらい異なっているかを表す編集距離は4年のときにお世話になりました．レーベンシュタイン距離については昔の日記にちらりと書いています．
[id:tomoemon:20060512]

このアルゴリズムに感銘を受けた理由の一つに力技でやろうにもどうにもならなかった過去があるからという点を挙げることができます．2年ほど前に変換込みで後から入力結果を評価するタイプのタイピングソフトを作ろうとして，入力した文字列と正解の文字列を比較しようと考えた挙句ろくなものができあがらなかったのは過去の日記にも書いてある通りです．

世の中にはいくつもの処理（ソート，探索，数値計算）があって，それぞれの処理を実行する複数のアルゴリズム（クイックソート，マージソート）が存在します．アルゴリズムの中にはクイックソートのように少々ややこしいものもありますが，挿入法のようにすぐに思いついて実装できる「単純で遅いアルゴリズム」があるときもあります．要するに人間はあまり考えないで済むけどコンピュータには負担がかかるアルゴリズムです．

編集距離のようなものを実装しようとしたときは「単純で遅いアルゴリズム」すら作れなかったのが悔しかったこともあって，レーベンシュタイン距離を知った時はこれまでに感じたことのない衝撃を受けました．アルゴリズムもシンプルで美しいのですが，それ以上に文字列と文字列の違い（距離）を「置換」「挿入」「削除」の3つの操作の回数で定義したことに頭が下がります．

このアルゴリズムを知った時から文字列処理アルゴリズムっておもしれーなーと思うようになりました．残念ながら今読んでいるネットワーク系の論文ではなかなか面白いアルゴリズムにお目にかかることはありませんが，「好き」な内容と「向いてる」研究は違うようで，おそらく自分には今やっている方が研究テーマとしてはあっている気がします．文字列処理は趣味でやっていきたいなと思う今日この頃．

とりあえずサフィックスツリーを実装できるようになりたい．．