文字列マッチングのためのLCP Arrayを構築する - $shibayu36->blog;

2017/01/06 15 users $shibayu36 アルゴリズム 文字列マッチング 構造

2017 - 01 - 06 文字列マッチングのためのLCP Arrayを構築する tech algorithm 前回のブログ記事で、文字列マッチングをするための Suffix Array という構造を構築した。この Suffix Array という構造だけでも、テキスト長をn、パターン長をmとして、 の計算量で文字列マッチングできるようになった。 suffix arrayを一番簡単なアルゴリズム... 続きを読む

Suffix ArrayをRustで実装した - Islands in the byte stream

2016/12/30 27 users rust Array アルゴリズム $shibayu36 以下

2016 - 12 - 30 Suffix ArrayをRustで実装した suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6) - $shibayu36->blog; を読んで、ちょうど自分も何らかの形で全文検索を一部実装してみようと思っていたのでRustで真似してみました。 Rustを選んだ理由は、以下の理由からです。 実際に全文検索を実装するのに耐えうる... 続きを読む

404 Blog Not Found:Algorithm - Suffix Array を JavaScript で再発明してみた

2012/01/16 87 users algorithm 小飼 キー 以下 通常

The requested blog was not found -- unless you requested that of Dan Kogai (小飼 弾). Suffix Arrayは何が画期的だったのか? 以下は、計算機科学者でなくても直感的に理解できると思います。 ソートされていない通常のデータの中にあるサブデータ(キー)を検索しようとすると、データの大きさに比例した時間(O(n))が... 続きを読む

ビームの報告書: Suffix Array を作る - SA-IS の実装

2011/08/19 33 users ビーム 実装 省メモリ 若者 オシャレ度

2011年8月19日金曜日 Suffix Array を作る - SA-IS の実装 Suffix Array は今若者の間で人気のデータ構造です． マイ suffix array を実装することで，オシャレ度がアップしてモテ系になり，女子力も上がると言われています． その中でも今特に，手軽でクールな SA-IS (アルファベットサイズ固定の下で線形時間で省メモリで suffix array が作... 続きを読む

[を] Perl による Suffix Array の実装

2006/04/10 31 users perl algorithm 実装 mississippi

Perl による Suffix Array の実装 2006-04-10-2 [Programming][Algorithm] 昔作った「Perlによるsuffix arrayの実装」を発掘したので公開しておき ます。 ソースコードです。 #!/usr/bin/perl -w use strict; my $t = "mississippi"; # Text - 対象テキスト my @sa = (... 続きを読む

[を] Suffix Array の解説文書のリンク集

2006/04/10 48 users 解説文書 algorithm リンク集 Tools 文書

Suffix Array の解説文書のリンク集 2006-04-10-3 [Algorithm] Suffix Array について解説している日本語による文書のうち、 Webで閲覧できるもののリンク集。随時更新予定。 - 用語解説: Suffix Array (PDF) via http://nais.to/~yto/tools/sufary/ - Suffix Array の解説 in D論 ... 続きを読む

suffix array

2005/03/24 138 users

更新履歴 2004/01/07 　O(N) 構築アルゴリズム三種追加（Ko &Alulu, Kim & al., Karkkainen & Sanders) Suffix Arrayは、最近注目を集めているデータ構造です。その理由として、 (1)大規模なデータに対して、高速に検索、情報抽出を行うことができる (2)BWTとしてデータ圧縮に用いることができる。 ことが挙げられます。(1)に関しては自... 続きを読む