Suffix Array を作る - SA-IS の実装
Suffix Array は今若者の間で人気のデータ構造です． マイ suffix array を実装することで，オシャレ度がアップしてモテ系になり，女子力も上がると言われています． その中でも今特に，手軽でクールな SA-IS (アルファベットサイズ固定の下で線形時間で省メモリで suffix array が作れる今最強のアルゴリズム) の実装がブームです． 僕もブームに便乗して，実装してみました． ところで，SA-IS は流行っているので，日本語でもすでに様々なところで記事が書かれています (日付順)． SAIS(Suffix Array - Induced Sorting) - EchizenBlog-Zwei SA-IS: SuffixArray線形構築 - sileの日記 SA-IS - (iwi) ｛ 反省します - TopCoder部 接尾辞配列(Suffix Array)の
BWTとInduced Sorting - 気ままなブログ
BWT(Burrows Wheeler Transform)を行うプログラムをJavaで書いてみた。一応、Unicodeのサロゲートペアの範囲でも問題なく動くので、あらゆる言語に適応できる。 BWTは、Suffix Arrayから定義に従って構築している。なので、実質的なメモリ使用量や構築時間は、Suffix Arrayのメモリ使用量や構築時間に依存する。 Suffix Arrayの構築にInduced Sortingを使ってみた。参考にしたものを以下に示します。 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 14人 クリック: 314回この商品を含むブログ (3件) を見る 原文: http://www.cs.sysu.edu.cn/nong/i
Run-Length Compressed Suffix Array
This web page will no longer be updated. See the author's web pages for further releases. RLCSA [4, 3, 7] is a compressed suffix array implementation that has been optimized for highly repetitive text collections. Examples of such collections include version control data and individual genomes. This implementation also serves as a testbed for many techniques used with compressed suffix arrays. The
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
