Suffix Arrayの簡単な説明
最終更新日: 2000-11-14 (公開日: 2000-11-14) Suffix Arrayは巨大なテキストを高速に検索するためのデータ構造 です。テキストのサフィックスを辞書順 (ABC順) に並べ、それに 対するポインタを配列として格納したものが Suffix Array です。 サフィックスとはテキスト中のある位置からテキスト末尾までの文 字列のことをいいます。テキストへの検索は Suffix Array を用い て 2分探索の要領で行います。 では、 Suffix Arrayの構築に移りましょう。ここでは ``abracadabra''というテキストに対して Suffix Array を作成す ることにします。 まず最初に、テキストに対してインデックスポイントを割り当てる 必要があります。インデックスポイントは、検索が行える位置を指 定したものです。この例では、どの位置からでも
テキスト圧縮はこれ一冊でOK！？な優良書籍「The Burrows-Wheeler Transform」を読んだ - EchizenBlog-Zwei
以前より気になっていた書籍「The Burrows-Wheeler Transform Data Compression, Suffix Arrays, and Pattern matching」を読む機会を得ることができた。それなりに高額な本だったので購入が躊躇っていたのだけど、これは自分用に購入してもいいかも。というくらいの良書だったので紹介しておく。 本書はタイトルのとおりBWT(Burrows-Wheeler変換)に関する書籍。サブタイトルにあるようにデータ圧縮やSuffixArrayによる全文検索についても充実した内容になっている。最後のPattern matchingはテキストから検索キーとexactにマッチした、もしくは類似した箇所を取り出すよ、という話。2008年の本なので比較的新しい話題も扱っていて満足度が高い。 また本書の特色は圧縮ありきで始まり、そこから全文検索可能な
演習３ 今井研 第一回(04/04/28) Compressed Suffix Trees Random-Decodable Compression
演習３ 今井研 第二回 第三回 Compressed Suffix Trees Compressed Suffix Arrays 04/04/28 04/05/12 岡野原 大輔 調べる題材 CST (Compressed Suffix Trees) CSA (Compressed Suffix Arrays) CSA [Grossi, Vitter 00] [Sadakane 03] [Grossi, Guputa, Vitter 03] FM-index [Ferragina, Manzini 00] 括弧木の表現及び操作 rank及びselectに関わる話 全体を並行に調べていく Suffix Trees、Suffix Arraysについて Suffix T[1…n]の時、Tの各部分列Ti = T[i…n]をTのSuffixと呼ぶ。 Suffix Trees Tの全ての
sary: a suffix array library and tools
What is sary? sary is a suffix array library and tools. It provides fast full-text search facilities for text files on the order of 10 to 100 MB using a data structure called a suffix array. It can also search specific fields in a text file by assigning index points to those fields. Table of Contents What's New Characteristics Brief Introduction to Suffix Array libsary Reference Manual Using the I
[を] Suffix Array の解説文書のリンク集
Suffix Array の解説文書のリンク集 2006-04-10-3 [Algorithm] Suffix Array について解説している日本語による文書のうち、 Webで閲覧できるもののリンク集。随時更新予定。 - 用語解説: Suffix Array (PDF) via http://ta2o.net/tools/sufary/ - Suffix Array の解説 in D論 (PDF) via http://ta2o.net/tools/sufary/ - 横着プログラミング 第9回: sary: Suffix Array のライブラリとツール http://0xcc.net/unimag/9/ - Suffix Arrayの簡単な説明 http://sary.sourceforge.net/docs/suffix-array.html - Suffix Trees and
![[を] Suffix Array の解説文書のリンク集](https://cdn-ak-scissors.b.st-hatena.com/image/square/af37977ee866988286b95e74fff98500a190545c/height=288;version=1;width=512/https%3A%2F%2Fchalow.net%2Fimages%2Ftcl-logo-25.png){kind=logo}
横着プログラミング 第9回: sary: Suffix Array のライブラリとツール
最終更新日: 2002-12-18 (公開日: 2002-12-18) Unix Magazine 誌に 2002年1月号から 2003年2月号にかけて連載し ていた記事の元の原稿です。 私にフローチャートだけを見せて、テーブルは見せないとしたら、 私はずっと煙に巻かれたままになるだろう。逆にテーブルが見せて もらえるなら、フローチャートはたいてい必要なくなる。 -- Frederick P. Brooks Jr. *1 プログラミングにおいてはデータ構造が重要であり、正しいデータ 構造を選択すればアルゴリズムは自明なものとなる、という主張が ある。Rob Pike*2 の "Notes on Programming in C" *3 によると、現実的なプログラムに必要なデータ構造は次の 4つであ るという。 配列 (array) 連結リスト (linked list) ハッシュテーブル
クライアント最前線 作って理解するAjax（第3回）
前回は，インクリメンタル検索を実現するAjaxアプリケーションのクライアント・サイドの実装を紹介しました。今回は，サーバーとして稼働するCGIプログラムを作成します。このCGIプログラムは，クライアントから送られてきたクエリーに基づいてテキストを検索し，その結果を返送します。Ajaxアプリケーションは通常のWebアプリケーションに比べて，サーバー・アクセスが増加しがちです。このためサーバーをいかに効率よく実装できるかが，サービスを快適に提供できるかどうかを左右します。サーバー負荷を下げる手法についても考えてみましょう。 テキスト検索にsaryを使用 みなさん，テキスト検索といえばどんな方法を思いつくでしょうか。単純なところではgrepコマンドの利用が考えられますし，データをMySQLやPostgreSQLなどのRDBMSで管理して，そのRDBMSの検索機能を利用する手もあります。また，N
お手軽PerlでSuffixArrayに挑戦
試しにPERLでSuffixArrayついでにソートの勉強 下記のページを参考にしている http://www.namazu.org/~satoru/unimag/9/ ここに記述されているコードは、実験のために書かれているので、 へんなところはご容赦を... インデックスを作ってみる Cで書かれたサンプルをperlでかいてみた。 PERLでもquicksortの関数はあるが、一応PERLでかいてみた。 バイナリー形式でインデックスファイルを書き出している。 テストのためのサンプルプログラムなので、書き出したあとよみだして表示している。 pushを使って配列を拡大しているが、これってスピード的にいいのだろうか？ pack,unpack関数はいろいろ使いでありそう！！ 1: #!/usr/bin/perl 2: 3: #2003/03/14 4: #UNIXマガジン2002 10月号 横着プ
Suffix Array
TopCoder SRM187、 DNAMultiMatcher は、 Stringが3つ(それぞれの長さは最大2500)与えられたとき、 3つ全てに含まれる最長のSubstringの長さを求めなさい。 という問題です。これに対して、 長さをBi...
Java で Suffix Array - odz buffer
なんか Java で Suffix Array なコードというリクエストがあったので簡単に。 とりあえず Suffix Array の構築だけ。効率とか一切無視で。 import java.io.IOException; import java.util.Arrays; import java.util.Comparator; import java.util.regex.Matcher; import java.util.regex.Pattern; public class SuffixArrayBuilder { public void build(String text, Integer[] sa) { Arrays.sort(sa, new SuffixComparator(text)); } private static class SuffixComparator imple
SuffixArray - みずぴー日記
30分プログラム、その580。id:Gemmaさんに借りたWEB+DB PRESS Vol.50に、suffix arrayの解説が載っていたのでやってみた。 解説を読んだときは「ちょう簡単じゃん。さくっと実装してやんよ」と思っていたけど、いざ始めたけど、けっこう大変だった。簡単とか言って、ごめんなさい。 そもそもararyとついてる時点で大変なことに気がつくべきだった。ボク、OCamlでarrayを使ったことなんてほとんどないじゃないか。 使い方 シグネチャはこんな感じ。 type t val make : string -> t val find : t -> string -> int list まず、suffix arrayを作る。 # let s = SuffixArray.make "abracadabra";; val s : SuffixArray.t = <abstr>
JavascriptでSuffixArray - やればできる子の日記
全文検索エンジンを試作してみたよ - やればできる子の日記とJavascriptを組み合わせてもうちょっとなにかできないかなあと思って、JavascriptでSuffixArrayを作ってみました。 上手い具合に組み合わせるアイデアが思いつけなかった(どうせ全文検索用のインデックスを保持しちゃうので、別途SuffixArrayを保持する意味がなさそう)ので、素のまま公開しちゃいます。 ちなみに、Javascriptも自信ないです。僕はJSでのべ2000行程度しか書いたことないはず。 /* Suffix Array構築のアルゴリズムは色々研究されています。 以下のコードはかなり最悪なアルゴリズムなので、実用の際は調査してください。*/ function genSA(text){ var sa = new Array(text.length) for(var i = 0; i < text.l
perlによる大規模データの取扱い
本ページでは，perlでどのようにして大規模なデータを保存するかついて 説明します．主にスタンドアロンで動くもの (クライアント<->サーバ型 でない，いわゆる組込み型) について紹介したいと思います． Menu Berkeley DB BerkeleyDB DB_File SDBM SDBM_File GDBM GDBM_File CDB CDB_File QDBM Depot Curia Villa TDB TDB_File SQLight DBD::SQLite SUFFIX ARRAY SUFARY SARY 複雑なデータ構造 Data::Dumper Storable MLDBM いろいろな比較 ファイルサイズ Benchmark Link サンプルデータについて Berkeley DB Berkeley DBは，組み込み向けデータベースです．通常データベースという とOracl
Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |i i| }! }} /／| |l､{ j} /,,ｨ//｜ 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' } ,ﾉ _,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ , ﾀ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ おれも何をされたのかわからなかった… ,ﾞ ／ )ヽ iLﾚ u' | | ヾｌﾄﾊ〉 |／_／ ﾊ !ニ⊇ '／:} V:::::ヽ 頭がどうにかなりそうだった… /／ 二二二7'T'' ／u' __ /:::::::/｀ヽ /'
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Suffix Arrayを用いたフレーズ抽出 - kuronekonacchan