« 頻出文字列発見問題 | メイン | MeCab 0.90 業務連絡 »
2005年01月21日
O(n) で suffix array を構築
研究業界の進展ははやく、 (multikey) quick sort をつかって
suffix array を作るのは遅すぎて過去の話のようだ。
ここに O(n) で作る話がある。むずかしすぎて追えない。
分割法の一種らしいが、3で割ってあまりが 0,1,2 の3種類の
index point で個別に array を作って、最後にマージする? みたい。
分割の方法でいろんな亜種があるようだ。
quick sort だと最悪 O(n^2) になる。とくに言語のように
特定のパターンが頻出する場合は（バイアスが大きい場合は）
その傾向が強くなる。さらに、いつでも O(n log n) になる手法など
いろいろ発展があるみたいだ。
投稿者 taku : 2005年01月21日 02:43
トラックバック
このエントリーのトラックバックURL:
http://chasen.org/~taku/blog/mt-tb.cgi/73