algorithm - 基数木 + 平衡二分探索木 = 三分探索木 : 404 Blog Not Found
2012年01月22日16:36 カテゴリアルゴリズム百選翻訳/紹介 algorithm - 基数木 + 平衡二分探索木 = 三分探索木 珠玉のプログラミング Jon Bentley /小林健一郎訳 最有力候補は、これかも。 Ternary search tree - Wikipedia, the free encyclopedia 三分探索木 - Wikipedia 404 Blog Not Found:algorithm - Patricia Trie (Radix Trie) を JavaScript で最近のTrie研究の傾向は、要素の動的変更が自在にできる一般向けのものではなく、一旦作成したら要素の追加と削除が困難な代わりにものすごくコンパクトになる、簡潔データ構造の応用手段の方に偏っていると素人目に感じるのですが、そろそろJudyたんのごとくハッシュテーブルとガチで闘うとか、逆
トライ（ダブル配列，簡潔データ構造）と STL コンテナ - ny23の日記
以前実装した構築速度重視の動的ダブル配列 (表中 dda) の構築速度を Darts, darts-clone (0.32g beta5, 0.32e5), DASTrie (1.0), doar (0.0.10)，簡潔データ構造を利用したトライ (tx 0.16) ，STL コンテナ (std::map, std::tr1::unordered_map) 辺りと比べてみた．キー集合としては，中規模で疎な集合（Wikipedia 英語版記事タイトル）と小規模で密な集合（郵便番号辞書）を用いた． ====================================================================== Wikipedia-en 記事タイトル | Build | Search | Search* | Size [bytes] =================
algorithm - PATRICIA に一番似合う姓は Crit-Bit かも : 404 Blog Not Found
2013年02月14日04:30 カテゴリアルゴリズム百選Math algorithm - PATRICIA に一番似合う姓は Crit-Bit かも 高速文字列解析の世界 岡野原大輔 「高速文字列解析の世界」を読んだら、熱がぶりかえしてきたので。 ハッシュテーブルや平衡二分木に代わる連想配列を実装するにはどうしたらよいのかという、知恵熱が。 すべてのハッシュ衝突を、生まれる前に消し去りたい。すべての宇宙、過去と未来の全てのハッシュ衝突を、この手でなくてもいいから。 ハッシュテーブル - Wikipedia ハッシュテーブル (hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の最も効率的な実装のうち1つである ハッシュテーブルはあまりに愛用されてきたため、連想配
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
Double-Array Articles
ダブル配列のライブラリを公開しているページです． An Implementation of Double-Array Trie URL: http://linux.thai.net/~thep/datrie/datrie.html Darts: Double-ARray Trie System URL: http://chasen.org/~taku/software/darts/ Dame URL: http://www.void.in/wiki/Dame Tiny Double-Array Library URL: http://nanika.osonae.com/TinyDA/index.html Dynamic Double-Array Library URL: http://nanika.osonae.com/DynDA/index.html
To Trie or not to Trie – a comparison of efficient data structures
Since my discussion thread on the efficiency of the in-memory data structure of ZeroMQ with Martin Sustrik, I have been reading up a bit by bit on efficient data structures, primarily from the perspective of memory utilization. Data structures that provide constant lookup time with minimal memory utilization can give a significant performance boost since access to CPU cache is considerably faster
MARISA: Matching Algorithm with Recursively Implemented StorAge
MARISA: Matching Algorithm with Recursively Implemented StorAge Abstract: Matching Algorithm with Recursively Implemented StorAge (MARISA) は Trie をコンパクトに表現する程度の能力を持つデータ構造です．libmarisa は MARISA を C++ で実装したライブラリであり，MARISA による辞書を構築したり，辞書からの検索をおこなったりできます．libmarisa の基本的な機能に対応するコマンドラインツールを用意しているので，辞書のサイズがどのくらいになるのか，検索にどのくらい時間がかかるのか，などを手軽に試すことができます． 概要 Matching Algorithm with Recursively Implemented Stor
オープンソースの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
JavaでTrieデータ構造を実装する
WEB+DB PRESS vol.42の特集「アルゴリズム＆データ構造」でもとりあげられていたTrie(とらい; p34-37)について調べてみたので、忘れないようにメモです。 Trie(s)というのは単語を辞書のなかから見つけ出すときに人がふつうに行っている探し方のアルゴリズムです。例えば、poolならまず、pのところに行って、次にoのところに行って、、、つまり、p -> o -> o -> lと探していきます。続いてprizeを見つけるとしたら、p -> r -> i -> z -> eですが、先頭の文字が同じpなので、pの付近からはずれたところから始めたりはしません。この二つの単語の場合pをprefixと見なすのがTrieです。poolとpoleだったらprefixはpoにのびていきます。prefixがのびていけばいくほど候補は減っていきます。ちょうどIDEのメソッド補完機能のように
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
Google Code Archive - Long-term storage for Google Code Project Hosting.
GitHub - rkapsi/simple-patricia-trie: A simple PATRICIA Trie implementation that's more "hackable".