ダブル配列の豆知識#ABC17 : Alphabet of Innovations, Academic Concepts and Emerging MovementsDuane Holland
スライド（重複レコードの多いトライ辞書の圧縮） - やた＠はてな日記
重複レコードの多い辞書については，トライから Directed Acyclic Word Graph (DAWG) への変換で大幅に圧縮できるかもしれません．…という内容のスライドです． 重複レコードの多いトライ辞書の圧縮（pptx） http://sites.google.com/site/headdythehero/cabine/2009/0905/fit-2009.pptx DAWG の利点は，検索時間を落とさずに辞書を圧縮できることです．内部データ構造にダブル配列を採用すれば，Darts と同等の検索時間を実現できます．というわけで，速度重視で重複レコードが多いという場面での活躍が期待されます． # URL のようにキーが長いと，Minimal Prefix (MP) トライの方が有利になるかもしれません．また，辞書のサイズを優先するのであれば，簡潔データ構造である Level-O
Darts clone のデータ構造 - やた＠はてな日記
トライをダブル配列で表現する Darts に対して，Darts clone は，基礎のデータ構造として Directed Acyclic Word Graph (DAWG) というグラフ構造を採用し，DAWG をダブル配列で表現するようになっています． Directed Acyclic Word Graph (DAWG) トライの共通部分木を併合することで得られるグラフ構造が DAWG です．トライからDAWG への変換では，登録するキーの末尾に共通性があるほど，多くのノードを取り除くことができます．これまでの実験により，日本語や英語の単語をたくさん登録する場合であれば，全体の 60 〜 70% 程度のノードを取り除けることが分かっています．特に有効なデータの例として，日本の郵便番号を DAWG に登録すると，そのサイズはトライの約 1/10 になります． DAWG はトライを圧縮したデー
ダブル配列の資料（更新に関する内容） - やた＠はてな日記
ダブル配列の資料にスターが付いているようなので，関連する資料も公開することにしました．今回の資料は，情報処理学会第 71 回全国大会で使用したスライドで，ダブル配列の更新に関する内容となっています． ダブル配列による動的辞書の構成と評価 http://sites.google.com/site/headdythehero/cabine/2009/0418/ipsj-2009-yata.pdf?attredirects=0 提案手法自体は，従来手法における最悪ケースに対処するための手法なので，使いどころが難しいと思います．でも，どういう手法があるのかを見る程度には役立つのではないでしょうか． 実験結果については，従来手法でうまくいかない状況を想定した内容になっています．同じコーパス（Google n-gram の 1-gram）を使っても，辞書順に登録する場合，これほど大きな差はありません．
トライ（ダブル配列，簡潔データ構造）と 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] =================
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
ダブル配列の実装方法
2013/1/9に統数研チャンネルにて、ウェーブレット木の解説をしました。岩波書店より出版されました「高速文字列解析の世界」の解説になっています。
Double Arrayの非常に効率的な圧縮 - 射撃しつつ前転 改
「ダブル配列におけるキャッシュの効率化」という論文を見付けた。FIT2006というフォーラムで発表されたものらしい。これはすごい。目から鱗が落ちた。なんかリンク張って良いものか迷うので、とりあえずはリンクしない。 この論文に書いてあることは2つあって、ひとつは配列サイズの削減で、もうひとつはできるだけキャッシュミスを減らすための方法である。配列サイズを削減するための方法がすごい。これまで誰も考え付かなかったのか、それとも考え付いたけどやらなかったのか？ まず、checkの要素サイズは1byteで十分である。なぜなら、遷移元のインデックスがわからなくても、遷移に使ったキーの値がわかれば十分なので。これでDoubleArray全体のサイズを5/8に減らせる。また、普通、1GBのDouble Arrayを作成したりすることは無い（せいぜい100MB程度だろう）ので、Baseにも4byteも割り当
ダブル配列におけるキャッシュの効率化
ダブル配列におけるキャッシュの効率化 Cache-Efficienct Double-Array 矢田 晋 森田 和宏 泓田 正雄 平石亘 青江 順一 Susumu Yata Kazuhiro Morita Masao Fuketa Wataru Hiraishi Jun-ichi Aoe 徳島大学工学部 Faculty of Engineering, Tokushima University 1. はじめに 辞書からキーを検索するという処理は，コンパイラ， 索引検索，フィルタリング，形態素解析などの様々な分 野で必要となるため，計算機処理における基礎技術の 一つとされている [1]．特に，文字単位で照合をおこな うトライは，理論的な検索時間がキーの長さで抑えら れる，入力に前方一致するキーを容易に検出できるな どの理由から，自然言語辞書を中心として幅広く利用 されている．このトライを実現す
連想配列はトライでしょ的な話がでていたので入門記事を書いてみた - EchizenBlog-Zwei
なにやらDan Kogai氏の以下の記事が話題になっている様子。 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? 連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これからはトライ(trie)木を使うのがイケてる！(意訳)という内容だった。 連想配列にハッシュテーブルを使うのが良いか悪いかについては色々と意見があると思うので特にこの記事では触れない。 今回は連想配列として使えると話題のトライ木とはなんぞ、という入門的な記事にしようと思う。 トライ木が持つ機能 最初にトライが持つ以下の3つの機能について説明する。 - lookup - common-prefix-search - predictive-searchまずトライは連想配列として利用できる。つまりキーワードと値のペアを登
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
最新の各種トライ速度比較
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
オープンソースの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
Dartsを試してみた - download_takeshi’s diary
ダブル配列なTrie構造を実装するためのライブラリであるDartsを試してみました。 DartsはMeCabの作者として知られる工藤 拓氏の作品で、もともとMeCabに組み込まれていたDouble-Arrayのコード部分を、工藤氏が改めてリパッケージしてものだそうです。 なおDartsそのものはC++ライブラリなので、これを他の言語から使うにはバインディングが必要となります。perlから使うにはCPANにText::Dartsというモジュールがあがっているので、これを使わせてもらいます。 なおText::Dartsは、これまた有名なid:dankogai氏の作品です。 で、これらを試してみたのですが、結論から言うと Dartsを使うには Text::Darts 0.03は現時点でDarts0.32に対応していないっぽい。makeでコケる。なのでDarts0.31を使うべし。 Dartsに付
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ページを開く
ダブルアレイのサイズ比較
GitHub - komiya-atsushi/darts-java: Java porting of Darts (Double ARray Trie System)
GitHub - digitalstain/DoubleArrayTrie: A Java implementation of a Double Array Trie
jada: DoubleArray Trieライブラリ - sileのブログ
GitHub - takawitter/trie4j: PATRICIA, Double Array, LOUDS Trie implementations for Java