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...