オープンソースの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
ブルームフィルタ - Wikipedia
この項目では、確率的データ構造について説明しています。画像にぼかし効果を付加する画像フィルタについては「川瀬のブルームフィルター」をご覧ください。 ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の
スプレー木 - Wikipedia
スプレー木（スプレーき、英: splay tree）は、平衡2分探索木の一種で、最近アクセスした要素に素早く再アクセスできるという特徴がある。挿入、参照、削除といった基本操作を O(log(n)) の償却時間で実行できる。多くの一様でない一連の操作において、その順序パターンが未知の場合でも、スプレー木は他の探索木よりもよい性能を示す。スプレー木はダニエル・スレイターとロバート・タージャンが発明した。 2分探索木の通常のあらゆる操作は、「スプレー操作」という1つの基本操作と組み合わせられる。スプレー操作とは、特定の要素が木の根に位置するよう再配置を行うことである。そのためには、まず通常の2分探索木での要素の探索を行い、次にその要素がトップになるように木の回転を行う。別の方法として、トップダウンアルゴリズムで探索と木の再配置を単一フェーズに統合することもできる。 スプレー木の性能がよいのは、頻
Transwiki:B+ tree - Wikibooks, collection of open-content textbooks
From Wikibooks, the open-content textbooks collection [edit] Overview In computer science, a B+ tree is a type of tree data structure. It represents sorted data in a way that allows for efficient insertion and removal of elements. It is a dynamic, multilevel index with maximum and minimum bounds on the number of keys in each node. A B+ tree is a variation on a B-tree. In a B+ tree, in contrast to
B+-Tree Indexes
Storage structure of records All records of a table in a RDBMS are stored on disk to guarantee their permanence in case of software and/or hardware failures. The records in a table are organized in files that are managed by the DBMS -- not by the OS. Whenever a query is submitted to the RDBMS, the query is processed and the records in the relational database table(s) that satisfy the query are ret
検索エンジンはいかにして動くのか？ 記事一覧 | gihyo.jp
運営元のロゴ Copyright © 2007-2025 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
Double-Array
ダブル配列（ Double-Array ）は， トライ（ Trie ）のデータ構造の一種であり， 小さい辞書で高速に検索できるという特長を持っています． 実際に，茶筌（ ChaSen ）や 和布蕪（ MeCab ）などの 形態素解析器で利用されているという実績があります． ダブル配列では，配列を使ってトライを表現します． 配列の各要素が BASE, CHECK という二つの整数を持つので，頭文字をとって配列 BC と呼ぶことにします． 以降の説明では，配列 BC の要素 x の BASE, CHECK を それぞれ BC[x].BASE, BC[x].CHECK と記述します． 通常，BASE, CHECK は個別の配列として紹介されますが， 特に分割して考える必要がないので，このような説明にしました． 基本的に，配列 BC の各要素は トライの節と一対一で対応します． そのため，対応する
)
トライ (データ構造) - Wikipedia
"A", "to", "tea", "ted", "ten", "i", "in", "inn" というキー群によるトライ木 トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。 キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
jemalloc() ～ Firefox 3.0 爆速の理由 ～
itworld2.com
プログラミングコンテストでのデータ構造
