Centroid Path Decompositionを使ったトライでダブル配列と勝負してみた - Preferred Networks Research & Development
釣りタイトルを付けたかったのですがさっぱり思いつかないのでもう諦めました。徳永です。 今回はCentroid Path Decomposition（以下CPD）についての話を書きます。直訳すると重心パス分解となるでしょうか。Trieを実現するためのテクニック（普通のツリーにも使えるのかな？なかなか難しそうですが…）の一つです。CPDは一年前の弊社岡野原の記事に出てきますが、私のような素人にはあれだけでは理解できない部分があったので、今回はちょっと論文を読んでみました。 Trieの実装によくある問題 Trieを実現するためのデータ構造というとダブル配列とかが挙げられますが、こういった高速なデータ構造にも、ランダムアクセスが多いという弱点があります。メモリはHDDなどと比べるとランダムアクセスに耐えうる記憶媒体ですが、とは言えランダムアクセスは避けられるに越したことはありません。CPDを使うこ
簡潔トライの実装に含まれる簡潔ビットベクトルの性能比較 - やた＠はてな日記
はじめに 先日（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/
ACL2011論文「Faster and Smaller N-Gram Language Models」を読んだ - EchizenBlog-Zwei
ACL2011の論文で「Faster and Smaller N-Gram Language Models」というのが気になったので読んでみた。 ACL Anthology » P11 Faster and Smaller N-Gram Language Models Adam Pauls, Dan Klein; 2011 本論文はこれまで提案されている言語モデルの圧縮・高速化の手法を実装して比較したよ、というもの。各種法が丁寧に解説されており、性能比較もよく知られているツールであるSRILMをベースラインとして行っているので参考になる。サーベイ論文として優れていると感じた。 本論文で紹介されている手法はモデルのサイズ圧縮と高速化の2点に関するもの。 まずはサイズ圧縮について。これはTRIEを使うことで各Nグラムの共通したプレフィクスを圧縮するのが基本らしい。でTRIEについてはノードの持
最近のtrieの話（xbwなど） - Preferred Networks Research & Development
ブログの更新がとまっていましたが、また少しずつ更新してきたいと思います。 今回はtrie（トライ）の最近の話をしたいと思います。 trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情報を扱ったり、最近だと、KVS（Key Value Store)のようにキーを介してデータを保存、読み込みをしたりと様々な場面で利用されます。 同じようにキー集合を格納するデータ構造としてハッシュを利用する方法があります。キーからハッシュ値を計算し、その場所に文字列へのポインタを格納しておくデータ構造です。ハッシュを利用した場合とtrieを利用した場合の一番の大きな違いは、trieの場合だと、ある文字列から始まるキーを全て列挙する、いわゆる接頭辞探索ができることです。例えば”te”で始まる文字列を網羅的に調べることができます。木をたどって、”te”の下
An Implementation of Double-Array Trie
Contents What is Trie? What Does It Take to Implement a Trie? Tripple-Array Trie Double-Array Trie Suffix Compression Key Insertion Key Deletion Double-Array Pool Allocation An Implementation Download Other Implementations References What is Trie? Trie is a kind of digital search tree. (See [Knuth1972] for the detail of digital search tree.) [Fredkin1960] introduced the trie terminology, which is
marisa-0.2.0-beta3 の公開と技術的なお話 - やた＠はてな日記
先日の記事（検索時間が短くなりました - やた＠はてな日記）で述べたように，キャッシュの導入によって検索の高速化を実現しました．思い付いた時点ではブレイクスルーになると考えていたものですが，今となっては当たり前のアイデアのように感じてしまいます． marisa-0.2.0-beta3 では，キャッシュへのマップ方法とキャッシュのサイズを調整したことにより，先日の段階と比べて辞書が小さくなり，検索は速くなっています． プロジェクト http://code.google.com/p/marisa-trie/ ソースコード http://marisa-trie.googlecode.com/files/marisa-0.2.0-beta3.tar.gz 概要 基本的な考え方は，辿る確率の高い遷移に関する情報をキャッシュに保存しておくというものです．具体的には，遷移元と遷移先のノード番号，さらにラ
Succinct Data Structures: Cramming 80,000 words into a Javascript file.
I know how to make and sell software online, and I can share my tips with you. Email | Twitter | LinkedIn | Comics | All articles Let's continue our short tour of data structures for storing words. Today, we will over-optimize John Resig's Word Game. Along the way, we shall learn about a little-known branch of computer science, called succinct data structures. John wants to load a large dictionary
perl - Text::Tx now released! : 404 Blog Not Found
2009年02月22日00:15 カテゴリ perl - Text::Tx now released! 以前作って放置してあったText::Tx を、CPAN にも Release したのでお知らせします。 /lang/perl/Text-Tx/L/trunk - CodeRepos::Share - Trac Dan Kogai / Text-Tx/ - search.cpan.org http://www.dan.co.jp/~dankogai/cpan/Text-Tx-0.02.tar.gz 404 Blog Not Found:perl - Text::Tx も一応作った CPANにまだ上げない理由その一。txはlibraryとして素直に使うにはちょっと問題があるのです。 もう一つは、なぜか Mac OS X v10.4.11 の gcc 4.0できちんとcompileしないこと。
tx-ruby - namespace gimite
FrontPage This is a Ruby 1.8/1.9 binding of Tx, a library for a compact trie data structure. For details of Tx, see: Tx: Succinct Trie Data structure How to install † $ sudo gem install tx Or $ wget http://gimite.net/archive/tx-ruby-0.0.5.tar.gz $ tar xvzf tx-ruby-*.tar.gz $ cd tx-ruby $ sudo ruby setup.rb If your Ruby is 1.8.x mswin32, you don't need compilers (binary is bundled). Tx library is b
marisa-trie の解説まとめ - やた＠はてな日記
どのような読者を想定しているのか甚だ疑問な連載と化していましたが，とりあえず，今までの記事をまとめておきます． marisa-trie における rank/select の実装 http://d.hatena.ne.jp/s-yata/20110118/1295288559 rank/select の索引については，ブロック単位で rank/select の値を保存するという基本的な構造を使用しています．後は，PopCount の使い方を少し工夫してみたり，あらかじめ計算しておいたテーブルを使って効率化してみたりという内容です．rank/select の効率は検索時間に対する影響が大きいので，とても大事なところです． 世の中には二種類の文字列がある… http://d.hatena.ne.jp/s-yata/20110127/1296061436 0 を終端とする文字列と，始点と長さにより
二バイトコード(UTF-16)を用いてDoubleArrayを構築する際のトライ探索方法 - sileのブログ
これまではDoubleArrayを構築する際には、ソースとなるトライのノードを深さ優先順で探索しDoubleArrayへと変換していた。 トライのキーセットとなる文字列のエンコーディングがUTF-8等の一バイトコード(?)の場合は深さ優先順探索でも特に問題はないが、UTF-16等の二バイトコード文字列に同様の探索順を採用すると、最終的な配列(DoubleArray)中に占める空き要素(未使用要素)の数が多くなる、という問題がある。※ 少なくとも自分の経験上は。 優先順位探索 二バイトコード文字列をキーとする場合は深さ優先ではなく、各ノードの子ノードの数の多い順にトライを探索(+DoubleArrayに変換)した方が、サイズ効率が良くなる(ように思う)。 以下は、深さ優先探索と子ノード多い順探索でのDoubleArrayのサイズの違い。 ※ DoubleArray構築にはjada-0.1.3
marisa-trie におけるラベル・リンクの格納方法 - やた＠はてな日記
概要 marisa-trie では，1 byte のラベル（Single-byte（SB）ラベル）は各トライに格納し，2 bytes 以上のラベル（Multi-byte（MB）ラベル）は次のトライもしくは TAIL に格納するようになっています．そのため，SB/MB ラベルを区別するためのフラグを各ノードに持たせるとともに，SB ラベルを格納する領域と MB ラベルへのリンクを格納する領域を用意しています． 以下は，もう少し詳しい内容です． ノード単位での実装 フラグ・ラベル・リンクを格納する簡単な方法は，これらの要素を各ノードに区別なく持たせることです．しかし，SB ラベルを持つノードと MB ラベルを持つノードでは割り当てるべき領域の大きさが異なるため，かなりの無駄が発生します．例えば，SB ラベルの格納に 8 bits，リンクの格納に 20 bits を使うのであれば，フラグも併せて
marisa-trieを使ってみた - nokunoの日記
id:s-yata さんの新作trieライブラリが公開されていたので使ってみました。環境はMac OS Xです。やた＠はてな日記 marisa-trie - Project Hosting on Google Code インストール普通にGoogle Codeからダウンロードしてインストールします。 $ wget http://marisa-trie.googlecode.com/files/marisa-0.0.1.tar.gz $ tar xfz marisa-0.0.1.tar.gz $ cd marisa-0.0.1/ $ ./configure $ make $ sudo make install 動作確認Wikipedia N-gram（nokunoの日記）よりbigramを格納し、marisa-predictによって前方一致検索を行いました。 $ cat bigram.txt
トライ（ダブル配列，簡潔データ構造）と STL コンテナの比較（最新版） - ny23の日記
[2011/11/30 更新; std::(unordered_)map でメモリ使用量を見積もる - ny23の日記に従い，STL コンテナのメモリ使用量を計測] [2011/02/21 更新: marisa-trie 0.1.3; 発表資料（Prefix/Patricia Trie の入れ子による辞書圧縮） - やた＠はてな日記 にてこの記事の実験結果を引用されているので，以後原則更新しないこととする．なお，marisa-trie は 検索時間が短くなりました - やた＠はてな日記 にあるように，marisa-0.2.0-beta3 以降ではさらに検索が速くなっています．] [2011/02/18 更新: marisa-trie の仕様変更に伴い，追記の記述を整合性が取れるよう変更; 最新版では未確認] id:s-yata さんが marisa-trie を公開されたので，例によってベ
新しいトライのライブラリを公開しました - やた＠はてな日記
概要 トライのライブラリを公開しました．ドキュメントはまったく用意できていませんが，とりあえず使えます．（追記 2011-01-09）ドキュメントを追加しました． http://code.google.com/p/marisa-trie/ ドキュメント ベンチマーク 使い方 インタフェース ツール インストール ビルド・インストールの方法は configure と make です．以下のようにすればインストールできます． ./configure make make check sudo make install インストールせずに試したいという方は，make install を省略して，tools/ 内部のツールを使うなり，lib/marisa/trie.h を見て使い方を確認するなりしてください．インストールせずにライブラリを利用するには，lib/ 以下のヘッダすべてと lib/libm
多層トライの実験結果 - やた＠はてな日記
概要 ux-trie に影響されて，複数のトライを使った辞書の実験をしてみました．具体的には，「トライの数」，「TAIL の有無」，「ノード順序（ラベル順・頻度順）」を切り替えて，辞書のサイズや構築・検索にかかる時間を比較しました． 実験に使ったソースコードは公開するつもりですが，パッケージ化したり，ドキュメントを用意したり…ということを考えると，しばらく先になると思います． トライの数 トライの数というのは，辞書を構成するトライの数です．通常の辞書であれば，トライの数は 1 になります．ux-trie であれば，トライの数はデフォルトで 2 つになります． （追記 2010-12-24）トライを複数にすると，TAIL に相当する部分をトライとして持つことになります．トライが 2 つの場合，1 つ目のトライは TAIL を持たせたときのトライと同じになり，2 つ目のトライは TAIL に格
Sux: Implementing Succinct Data Structures
Sux in an umbrella nickname for the results of my fiddling with the implementation of basic succinct data strucures. The resulting code is rather sparse. The main highlights are: a novel, broadword-based implementation of rank/select queries for up to 264 bits that is highly competitive with known 32-bit implementations on 64-bit architectures (additional space required is 25% for ranking and 12.
トライの実験に使えるちょっとしたツール - やた＠はてな日記
トライを構築したときのノード数が分からない，TAIL を導入したときにサイズがどのくらい小さくなるのか分からない，そんな悩みに答えるちょっとしたツールのソースコードです． 各ノードのサイズとノード数が分かればトライのサイズは簡単に求まるので，トライについて少し試してみようという段階で便利かもしれません． 例えば，ダブル配列であればノード数 n に対して 4n bytes か 8n bytes が基本です．ただし，以下のツールは終端文字による遷移をカウントしないことに注意してください．後，TAIL の長さが m であれば，m bytes を追加することになります． また，LOUDS Trie であれば，木の表現に 2n bits，ラベルの保存に n bytes，終端フラグの保存に n bits，後は rank/select の索引に…という具合で 1.5n bytes くらいになると思います
オープンソースの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
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Evaluation - darts-clone - 性能評価 - Project Hosting on Google Code