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ページを開く
