Algorithm - Suffix Array を JavaScript で再発明してみた : 404 Blog Not Found2012年01月16日16:30 カテゴリアルゴリズム百選Lightweight Languages Algorithm - Suffix Array を JavaScript で再発明してみた WEB+DB 総集編 [Vol. 1〜60] もう10年以上前に某社のCTOだったころ、Suffix array(接尾辞配列)の解説を毎週の技術者ミーティングでしたら一名を除いて「ハァ?」状態だったことを思い出しつつ。 Suffix Arrayは何が画期的だったのか? 以下は、計算機科学者でなくても直感的に理解できると思います。 ソートされていない通常のデータの中にあるサブデータ(キー)を検索しようとすると、データの大きさに比例した時間(O(n))がかかる。 ソート済みのデータであれば、二分探索でデータの大きさの対数時間(O(logn))でキーを検索できる。 さらにキーからIDを定数時間で作成でき
