連想配列はトライでしょ的な話がでていたので入門記事を書いてみた - EchizenBlog-Zwei
なにやらDan Kogai氏の以下の記事が話題になっている様子。 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? 連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これからはトライ(trie)木を使うのがイケてる！(意訳)という内容だった。 連想配列にハッシュテーブルを使うのが良いか悪いかについては色々と意見があると思うので特にこの記事では触れない。 今回は連想配列として使えると話題のトライ木とはなんぞ、という入門的な記事にしようと思う。 トライ木が持つ機能 最初にトライが持つ以下の3つの機能について説明する。 - lookup - common-prefix-search - predictive-searchまずトライは連想配列として利用できる。つまりキーワードと値のペアを登
最新の各種トライ速度比較
trie4jの最新の実装で、Wikipedia日本語タイトル127万件を格納する速度(build)、全件を照合する速度(contains)、消費サイズ(size)を測ってみました。 クラスbuild(ms)contains(ms)size(MB) java.util.HashSet417453160.4 java.util.TreeSet402261160.2 PatriciaTrie442244104.6 TailPatriciaTrie(SuffixTrieTail)1,220271100.8 TailPatriciaTrie(ConcatTail)51724186.0 MultilayerPatriciaTrie70438691.8 MultilayerPatriciaTrie(packed)2,82286682.9 DoubleArray47110648.5 TailDoubleA
LOUDSTrie実装してみた
よく考えたらblogに載せてなかった(TwitterやGoogle+でつぶやいて載せた気になってた・・)ので、改めて。 LOUDSはLevel-order Unary Degree Sequenceの略。詳しくは書籍「日本語入力を支える技術」(amazon)や下記サイトを参照してください。 情報系修士にもわかるLOUDS LOUDS(Level-Order Unary Degree Sequence)を調べたのでメモ 要は木構造を01のビット列で表そうというデータ構造で、遅いけどかなり小さく圧縮できる。ただでさえJavaではオブジェクトがメモリを食う(何もフィールド無くてもポインタ2個分消費する)ので、木構造がビット列で表現できれば、絶大なサイズ削減効果があります。 既に構築済みのトライからLOUDS Trieを構築するのは結構簡単で、幅優先でトライを辿り、子の数だけ1を追加、最後に0を追
オープンソースの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
簡潔データ構造 LOUDS の解説（全12回、練習問題付き）
「日本語入力を支える技術」（通称「徳永本」）や「高速文字列解析の世界」（通称「岡野原本」）で紹介されている LOUDS というデータ構造を、12回に分けて解説しました。 友達に教える時に使ったもので、練習問題付きです。 実際に紙に書いてやってみるとわかりやすいと思います。 詳解 LOUDS (1) LOUDS とは 詳解 LOUDS (2) ビット列を作ってみる 詳解 LOUDS (3) 0番ノード 詳解 LOUDS (4) ビットの意味 詳解 LOUDS (5) 木構造の復元 詳解 LOUDS (6) インデックスでノードを表す 詳解 LOUDS (7) ノード番号からインデックスを得る 詳解 LOUDS (8) インデックスからノード番号を得る 詳解 LOUDS (9) 子ノードから親ノード 詳解 LOUDS (10) 親ノードから子ノード 詳解 LOUDS (11) 木の検索 詳解
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - takawitter/trie4j: PATRICIA, Double Array, LOUDS Trie implementations for Java
