定兼 邦彦 (Kunihiko Sadakane) - 簡潔データ構造講義資料 - researchmapresearchmapは、日本の研究者情報を収集・公開するとともに、研究者等による情報発信の場や研究者等の間の情報交換の場を提供することを目的として、国立研究開発法人科学技術振興機構（JST）が運営するサービスです。
ブルームフィルタ - Wikipedia
この項目では、確率的データ構造について説明しています。画像にぼかし効果を付加する画像フィルタについては「川瀬のブルームフィルター」をご覧ください。 ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の
Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
ダブル配列における動的更新の効率化アルゴリズム | CiNii Research
タイトル別名 Efficient Dynamic Update Algorithms for a Double-array Structure ダブル ハイレツ ニ オケル ドウテキ コウシン ノ コウリツカ アルゴリズム 自然言語処理 トライ構造はキーの表記文字単位に構成された木構造を用いて検索するキー検索技法の1つであり，自然言語辞書を中心として広く用いられている．このトライ構造を実現するデータ構造として高速性とコンパクト性を満足するダブル配列法があるが，この手法は，キーの更新が頻繁に生じない検索法として確立しているため，動的検索法に比べて追加時間は高速であるとはいえず，また削除で生じる不要なノードや未使用要素により記憶量に無駄が生じていた．本論文ではこれらの問題を解決し，ダブル配列を動的検索法として確立するため，未使用要素を連結することで追加処理を高速化する手法，削除時に生じる不要ノ
これからのDouble Arrayは動的更新に対応するべき - 射撃しつつ前転 改
Double Arrayのコードなんて1年以上いじってないくせになにを言ってるんだこの口はと言う感じですが、Double Arrayを作るのであれば、動的更新に対応させるべきであると、そう思うわけです。 Double Arrayのメリットは Trieである 速い (Ternary Search Treeとかと比べると)サイズも小さい という感じだった訳ですが、速度はともかく、サイズではTxが使っているようなLOUDSやLOUDS++などの圧縮しちゃう方式に勝てないので、静的な辞書としては、速度が超重要なところ以外ではLOUDSやLOUDS++を使った辞書を使うのがいいのかなと思う訳です。辞書引き以外の部分がボトルネックであることも多いだろうしね。 と言うわけで、簡潔データ構造に比較してDouble Arrayでなにか便利な事ができないかなというと、圧縮をかける方式ではやはり、動的な更新が難
DO++ : 透過的データ圧縮
可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。 これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。 例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます (一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる） このデータを圧縮したまま扱う
http://www.t3.rim.or.jp/~matsuuch/COMP/btree.htm
という大小関係になっています。また、ページを指していないbranchは、NULL値になっています。 厳密に言うとページは、次のようなキビしい条件を満たします。ページ１つについてのキーの個数が最大2M個だとすると、 ページ当たりのキーの個数n は M ≦ n ≦ 2M を満たす。つまり、各ページは少なくとも半分埋まっていなければいけない。ただし、根（一つだけある）については 0 ≦ n ≦ 2 Mでよい。 各ページ上のキーは昇順にならべる（ key[0] ＜ key[1] ＜…＜ key[n-1] ） ポインタ branch[k] （ k ＞ 0 ）の指すページが含むすべてのキーは key[k-1] より大きい ポインタ branch[k] （ k ＜ n ）の指すページが含むすべてのキーは key[k] より小さい 木の高さはいたるところ一定。つまり、根から末端のページ（葉）に至るポインタ
物理的な格納方式
□ 計算機で使われるデータは必ず何がしかの記憶媒体上に置かれる． □ レジスタ (registers) CPU 内部に置かれた記憶装置 プログラムからのアクセスは高速 (CPU の動作クロックに合わせる必要があるため．) アーキテクチャの一部なのでサイズは固定されている ( が普通) 揮発性 (volatile): つまり電源が切れると内容が消えてなくなる □ 主記憶 (main memory, MM) CPU の外に置かれた記憶装置 プログラムからは直接読み書き可能 読み書きにかかる時間は今のところ 60ns 程度が主流 容量は可変で，現在は 数百 MB 〜 数 GB 程度が普通 揮発性 (volatile) □ 二次記憶装置 (secondary storage) CPU の外に置かれた記憶装置であるが， プログラムからは直接読み書きできないもの． 例: フロッピーディスク (FD)，
Matzにっき(2008-03-17) 「MacRuby」
<< 2008/03/ 1 1. [Ruby] Ruby 1.9.0-1 snapshot released 2. 高木浩光＠自宅の日記 - 公開鍵暗号方式の誤り解説の氾濫をそろそろどげんかせんと 3. [Ruby] Lisa Awards: Biggest Hack for a Language Runtime on Dion Almaer's Blog 2 1. [教会] 第一安息日 3 1. [言語] CS 11: Python track: python idioms 2. [Ruby] Binary search algorithm - Wikipedia, the free encyclopedia 3. [OSS] Theological Cultural Analysis of the Free Software Movement 4. 小寺信良：正直、テレビはもうダメかも
Perl による Suffix Array の実装
Perl による Suffix Array の実装 2006-04-10-2 [Programming][Algorithm] 昔作った「Perlによるsuffix arrayの実装」を発掘したので公開しておき ます。 ソースコードです。 #!/usr/bin/perl -w use strict; my $t = "mississippi"; # Text - 対象テキスト my @sa = (0..length($t)-1); # Suffix Array - 初期設定 ### Suffix Array の作成 @sa = sort {substr($t, $a) cmp substr($t, $b)} @sa; # テスト出力 for (0..$#sa) { print "$_ $sa[$_] ",substr($t, $sa[$_]),"\n"; } ### バイナリサーチによる
Extendible hashing - Wikipedia
Extendible hashing is a type of hash system which treats a hash as a bit string and uses a trie for bucket lookup.[1] Because of the hierarchical nature of the system, re-hashing is an incremental operation (done one bucket at a time, as needed). This means that time-sensitive applications are less affected by table growth than by standard full-table rehashes. Extendible hashing was described by R
Algorithms and Data Structures
Code for some of the algorithms discussed exists in various programming languages such as Algol, C, Java, Pascal and Turing (e.g. `foo.t', for historical reasons). The Bibliography also contains references on algorithms and data structures in journals and books. Algorithm: a process or set of rules used for calculation or problem-solving, esp. with a computer. Program: a series of coded instructio
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
MIT OpenCourseWare OCW Home
DBH - Disk Based Hashtables
spiteful.com
http://swig.stanford.edu/pub/summaries/database/linhash.html
http://www.inf.unibz.it/dis/teaching/DMS/lecturenotes/dms03.pdf
サービス終了のお知らせ
Data Structures – Unraveling the Complexity of Data Organization
brpreiss.com