Algorithm - Suffix Array を JavaScript で再発明してみた : 404 Blog Not Found
2012年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を定数時間で作成でき
Compressed Suffix Arrayの記事まとめ - EchizenBlog-Zwei
一応CSAの記事を書き終えたので、各記事へのリンクリストを。 補足:記事を7つも読むの面倒くさい人は、↓にもう少し簡単な圧縮法の解説を書いておいたので参照されたい。 15分でわかる(とうれしい)Suffix Arrayの簡単な圧縮法 Compressed Suffix Arrayの解説(1) -Suffix Array- Compressed Suffix Arrayの解説(2) -SAの計算量- Compressed Suffix Arrayの解説(3) -圧縮の方針- Compressed Suffix Arrayの解説(4) -unary記法- Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- Compressed Suffix Arrayの解説(6) -B Vectorと Ψ Vector- Compressed Suffix
15分でわかる(とうれしい)Suffix Arrayの簡単な圧縮法 - EchizenBlog-Zwei
文字列が超長い場合SuffixArrayが大きすぎてメモリが一杯になってしまう。 ので圧縮して小さくしたい。基本的な圧縮法である差分圧縮を使った簡単なSuffixArrayの圧縮法を紹介する。 参考: 5分でわかる(かもしれない)圧縮の基本 5分でわかる(気がする)Suffix Array さて以下のSuffixArrayを差分圧縮したい。 文字列 : b a n a n a SuffixArray: 6 4 2 1 5 3SuffixArrayの差分を取る。 SuffixArray: 6 4 2 1 5 3 差分 : 6 -2 -2 -1 4 -2マイナスの数がたくさん出てきた。負の数があると差分圧縮できない。ので差分が正の数になるようにSuffixArrayをいじる。 SuffixArrayのそれぞれの数字に1から順に番号をふる。 Index : 1 2 3 4 5 6 SuffixA
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
