Wavelet Tree - naoyaのはてなダイアリー
圧縮全文索引の実装などでしばしば利用される Rank/Select 辞書と呼ばれるデータ構造があります。詳しくは参考文献を参照していただくとして、今回は一般の文字列に対して効率的に Rank/Select を可能とするデータ構造である Wavelet Tree (ウェーブレット木) のライブラリを作りました。 http://github.com/naoya/perl-algorithm-wavelettree/tree/master my $wt = Algorithm::WaveletTree->new("abccbbabca"); is $wt->rank(6, 'a'), 2; is $wt->rank(6, 'b'), 3; is $wt->rank(9, 'b'), 4; is $wt->select(0, 'a'), 0; is $wt->select(1, 'a'), 6;
wat-array : wavelet木を利用した高速配列処理ライブラリ - Preferred Networks Research & Development
こんにちは岡野原です。もう年末になりましたが、私の今年はこれからです。 wat-arrayというC++ライブラリを公開しました。 google code:wat-array wat-arrayはフリーソフトウェアであり、修正BSDライセンスに基づいて利用できます． wat-arrayはwavelet木と呼ばれるデータ構造を利用することにより、配列上の様々な処理を効率的に行うことができるC++ライブラリです。 例えば、 – 任意の連続した範囲内にある最大値 /最小値 / k番目に大きい値, またそれらの出現位置、頻度 – 任意の連続した範囲内にある指定した文字cの出現回数、c未満/より大きい文字の出現回数 – 任意の文字のi番目の出現位置 といったものを求めることが全て範囲長、入力長に対して定数時間で行うことができます。 例えば長さ10億、値の範囲が0から1000万であるような配列A中のA[
オープンソースのTrieライブラリまとめ - nokunoの日記
最近、趣味で開発しているStaKKのためにTrieライブラリを書いているのですが、参考にするためオープンソースのTrieライブラリについて調べました。簡潔データ構造を用いたものが中心です。 @hillbig氏によるもの tx LOUDSによる圧縮でメモリ使用量を削減したTrieライブラリ。 関連記事：Tx: Succinct Trie Data Structure Engineering the LOUDS Succinct Tree Representation - 射撃しつつ前転ux txの改良版。tailの圧縮によりtxの1/2くらいのサイズになるらしい。要チェック。 関連記事：ux... - ny23の日記id:s-yata 氏によるもの taiju LOUDSを含む簡潔データ構造を用いた大規模Trieライブラリ。sumire-triesインメモリの簡潔データ構造を実装した大規模T
青色3号
そうだな、たしかにあいつは、おれと同じ褪せ人だった。エビが好きなやつに悪人はいねえ。おれはそう思ってる……思ってはいるが、やっぱりものごとには例外ってものがあるんだろうな。……いや……そうだな、悪いやつだというのも違うかもしれねえ。けどやっぱりあいつは……うまく言えねえな。 あいつにはじめて会ったのは、おれがリエーニエの東屋でエビを茹でていたときのことだ。あのときあいつは、たしかに誰かのことを……とあるお嬢ちゃんのことを心配してたんだ。褪せ人なのに誰かのことを心配するなんて、甘っちょろいやつだと思ったよ。だけどとにかく、だからな、悪いやつじゃなかったのさ。なんたってエビも好きだって言うしな。……だけどそうだな、何があったのかってことは、あんまり話したくねえ。この狭間の地でやってくんだったら、そういう後ろ暗いことのひとつやふたつ、あるもんだろう？ とにかく、はじめて会ったときのあいつの印象っ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
kiyoka -- * kiyoka [img] オープンソース系好奇心先行型プログラマ。関数型プログラミングにハマりぎみ。
Welcome
NLP関係のリソースまとめ - nokunoの日記
Loading...