[B! trie] blueleのブックマーク

簡潔トライの実装に含まれる簡潔ビットベクトルの性能比較 - やた＠はてな日記

はじめに先日（12/10）DSIRNLP という勉強会で紹介されていた，簡潔トライの実装に含まれる簡潔ビットベクトルの実験結果が予想とかけ離れていたので，自身でも調べてみることにしました． partake.in DSIRNLP#2で発表しました「作ろう！簡潔ビットベクトル」 - EchizenBlog-Zwei 実験設定比較した実装は元の実験と同じです． ux-trie: http://code.google.com/p/ux-trie/ rx: http://code.google.com/p/mozc/ marisa-trie: http://code.google.com/p/marisa-trie/ 実験環境の CPU は Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz stepping 07 です．物理メモリの容量は十分にあり，ディスク I/

bluele 2012/07/10

trie
C++

リンク

簡潔データ構造 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) 木の検索詳解

bluele 2012/04/22

trie
LOUDS

リンク

オープンソースの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

bluele 2012/04/21

nlp
trie

リンク

Double Array 実装してみた - 木曜不足

今作りかけのもので、素性(文字列片)を格納するのに Trie を使っていたのだけど、50万件を超えたあたりからメモリに載らなくなってきて。まあ dict を使っためちゃめちゃナイーブな実装だったので、そろそろダメかなあとは思っていたんだけど(苦笑)。というわけで、それよりきっと省スペース＆きっと高速だろうと期待して Double Array を Python で実装してみた。参考にしたのは WEB+DB Press vol. 64 の徳永さんの記事。現時点での実装がこちら。 https://github.com/shuyo/iir/blob/master/trie/da.py ソート済みのテキスト列を与えると、Double Array を構築。 get を呼び出すと、最初に与えたテキスト列の中でのキー文字列のインデックスを返す。シンプル機能。 trie = da.DoubleAr

bluele 2012/04/07

Python
trie

リンク

情報系修士にもわかるダブル配列 - アスペ日記

最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。ありがたい。感銘を受けたので、この本を教材に友達と2人勉強会をした。この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。しかし、いざやってみるといろいろと難しい。次のようなところでひっかかるようだ。例のサイズが小さく、イメージを喚起するのが難しい。最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。単語終端について言及がないので、どのノードが単語を表しているかがわから