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
目的は主観的に、手段は客観的に考える - EchizenBlog-Zwei
ここ数年で色々な経験をした結果 目的は主観的に、手段は客観的に考えるのが良い気がしたのでメモしておく。 ある事をやろうとする。このある事を便宜上「目的」とよぶ。客観的に目的を検証すると、利点と欠点がリストアップされる。 だが大抵欠点の方が多いので目的を諦めるのが最適解になる。これだと何もしないのが最適になってしまい何も変わらない。 そこで目的を主観的に決定する。自分が「これはッ！」と思った事を目的にする。ここは決めたら曲げない。 そして目的を実行するための「手段」を考える。手段も便宜上の表現で、具体的な手段に加えて目的を達した時のリスクやリターンについても考える。リスクがある場合には、リスクは回避できるか、回避できないならダメージをリカバーするにはどうするか、を客観的に考える。 目的フェイズのポイントはとにかく自分の気持に正直になること。良いと思った部分にとにかく目を向けること。手段フェイ
Suffix Array向きのソートアルゴリズム - EchizenBlog-Zwei
Suffix Arrayのソートアルゴリズムは以前当ブログで紹介したSAIS(参考)など、Suffix Arrayの性質を生かしたものが多い。そして一般にSuffix Arrayはバイト単位でインデックスを与えるので、これを前提としている場合が多い。大抵の場合はそれでOKなのだが、問題がある場合がある。 それは、インデックスをUTF8の文字単位で与えたい場合や、単語単位で与えたい場合。この場合、大抵のSuffix Array向けソートアルゴリズムが使えない。そこで重要になってくるのが文字列に対する高速ソートアルゴリズム。これならばインデックスが飛び飛びでも使えるので汎用性がある(Suffix Arrayに特化した手法が使えないので速度面では劣るかもしれないが。) 例えば、SUFARY(参考)で使われているmultikey-qsortという方法は古くからある方法だがシンプルかつ高速で、とても
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
