簡潔トライの実装に含まれる簡潔ビットベクトルの性能比較 - やた＠はてな日記
はじめに 先日（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/
N-gram 言語モデルを圧縮するには - やた＠はてな日記
はじめに 今回の記事は，以下の論文に関するものです．他にも紹介記事（ACL2011論文「Faster and Smaller N-Gram Language Models」を読んだ - EchizenBlog-Zwei）があるので，そちらでは特に触れられていない部分を（独断と偏見により）解説しています． http://nlp.cs.berkeley.edu/pubs/Pauls-Klein_2011_LM_paper.pdf Adam Pauls and Dan Klein. Faster and Smaller N-Gram Language Models. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pp. 258--267, 2011. 概要 こ
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 概要 基本的な考え方は，辿る確率の高い遷移に関する情報をキャッシュに保存しておくというものです．具体的には，遷移元と遷移先のノード番号，さらにラ
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 を終端とする文字列と，始点と長さにより
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 を使うのであれば，フラグも併せて
世の中には二種類の文字列がある… - やた＠はてな日記
今回の内容は，0 を終端とする文字列と，長さを別に持つ文字列の扱いに関する小ネタです． 検索用のインタフェースを用意するとき，どちらか一方を選択するのであれば，後者にすると思います．しかし，できれば前者も提供したいと思うのが人情というものでしょう． という理由から，marisa-trie では，どちらも使えるようになっています．とはいえ，別々に実装するのは甚だ面倒です．検索用の関数は lookup(), find() 系列, predict() 系列と大量にあり，ほとんど同じになるものを別々に実装するなんて正気の沙汰ではありません．以降の修正でどちらか一方だけ直し忘れたなんてのも，実にありそうな話です． シンプルな対策は，0 を終端とする文字列を受け取ったとき，まず長さを求めてやるというものです．しかし，長い文字列が与えられる可能性がある場合，この手は危険です．100MB くらいのテキスト
std::string の正体（gcc-4.4.3）と細かい話 - やた＠はてな日記
# 環境依存な内容な上，無駄に細かい話なので，「そういうこともあるかもねー」くらいに流しちゃってください． （追記 2011-01-11）新しい規格では std::string の Copy on Write（CoW: 書き込み時に複製）が実質禁止になるとのことです．後，gcc 4.5 の時点で CoW はやめてしまうみたいですし，「そんな時代もあった」くらいに軽く流しちゃってください．id:gintenlabo さん，コメントありがとうございます． （追記の続き）個人的には，std::string の CoW 動作は挙動が分かりにくくなるので止める方に賛成です．でも，std::vector なんかを拡張するときはどうするのかな…？コピーしてしまうのか，swap() を使うようにするのか…． （さらに追記 2011-01-11）おおっと，ムーブコンストラクタにムーブ代入演算子なんてものが…
新しいトライのライブラリを公開しました - やた＠はてな日記
概要 トライのライブラリを公開しました．ドキュメントはまったく用意できていませんが，とりあえず使えます．（追記 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 に格
トライの実験に使えるちょっとしたツール - やた＠はてな日記
トライを構築したときのノード数が分からない，TAIL を導入したときにサイズがどのくらい小さくなるのか分からない，そんな悩みに答えるちょっとしたツールのソースコードです． 各ノードのサイズとノード数が分かればトライのサイズは簡単に求まるので，トライについて少し試してみようという段階で便利かもしれません． 例えば，ダブル配列であればノード数 n に対して 4n bytes か 8n bytes が基本です．ただし，以下のツールは終端文字による遷移をカウントしないことに注意してください．後，TAIL の長さが m であれば，m bytes を追加することになります． また，LOUDS Trie であれば，木の表現に 2n bits，ラベルの保存に n bytes，終端フラグの保存に n bits，後は rank/select の索引に…という具合で 1.5n bytes くらいになると思います
頻度計数における unordered_map の調整（C++） - やた＠はてな日記
形態素の頻度をカウントするというシンプルなタスクで std::tr1::unordered_map の性能について実験してみました．std::string より const char * の方がメモリを節約できるというような軽い内容です． 実験概要 実験環境は以下のとおりです． 実験環境 CPU：Core 2 Duo U9600 1.60GHz コンパイラ：gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5) 入力として使用したのは，ウェブコーパスから抽出した形態素を改行区切りで保存したファイルです． 入力 サイズ：815,793,701 bytes 形態素数：133,940,786 異なり数：516,612 形態素の入力については，std::ios::sync_with_stdio(false) を呼び出した後で std::getline() を使うようにし
C/C++ におけるデータ入力の速度 - やた＠はてな日記
100 万行のテキストファイル（test-data）を C/C++ で作成したプログラムで読み込むとき，どのくらいの時間がかかるかを調べた結果です． データ入力がボトルネックになるような状況では，std::fgets(), std::fread(), std::istream::read() を使った方が良さそうです．std::istream については特に極端な差が出ていますので，速度面を重視する場合，便利なインタフェースを封印しないとダメっぽいです．実に惜しい…． 追記（2010-07-28）：id:metaboles さんより，std::ios::sync_with_stdio(false) を使えば std::cin.getline() や std::getline() も std::fgets() と同じくらい速くなるというコメントをいただきました（後述）． $ wc test-
テキスト抽出と N-gram コーパス作成のツールを公開（nwc-toolkit 0.0.1） - やた＠はてな日記
日本語ウェブコーパスを作成するために開発したツールを改修したものを公開しました．テキストの抽出と N-gram コーパスの作成くらいしかできませんが，何かに使えるかもしれません．テキストの抽出については，http://s-yata.jp/apps/nwc-toolkit/text-extractor の中身になっています． プロジェクト Google Code Archive - Long-term storage for Google Code Project Hosting. ドキュメント http://nwc-toolkit.googlecode.com/svn/trunk/docs/index.html ライブラリをインストールする方法が環境によって異なることもあり，ドキュメントの作成には思いのほか手間がかかりました． 追記（2010-11-03）：バグを修正しました．修正したもの
頻度の閾値と N-gram 異なり数の関係 - やた＠はてな日記
ある程度のテキストを入力として，頻度の閾値を変更したときに N-gram 異なり数がどのように変化するのかを表にしてみました．上端が Xgms の列は，1-gram から X-gram までの N-gram 異なり数を示しています．左端が N の行は，頻度 N 以上の N-gram 異なり数を示しています． 表の右端が見えないかもしれませんが，あまり細かい数値を気にしても仕方がないので，次の表をご覧ください．それでも見たいという方はコピペでどうぞです． 閾値 1gms 2gms 3gms 4gms 5gms 6gms 7gms 1 264,806 4,543,431 18,061,399 39,874,275 64,656,088 89,045,647 111,814,193 2 158,703 2,003,823 5,756,043 9,816,157 13,315,304 16,216
マージ用に優先順序付きキューを少しだけ効率化 - やた＠はてな日記
データの規模が大きくなってマージのコストが見過ごせなくなってきたため，少しでも効率を良くするべく，優先順序付きキュー（std::priority_queue）に手をつけてみました． # 最後のマージは並列化できないので深刻な問題です．後，ヒープは実装が楽だから，というのも理由の一つです． std::priority_queue を用いたマージで気になる点は，ヒープキューなら pop() と push() をまとめて処理できるはずなのに，pop() と push() を別々に呼び出さなければならないことです． pop(): 先頭の要素を削除します． 先頭の要素を取り除いた後，下にある要素を上にずらすことで隙間を埋めます． push(): 新しい要素を追加します． 末尾に新しい要素を付け足した後，その要素を上に移動することでヒープにおける要素の大小関係を維持します． pop() + push(
今度は文字 N-gram コーパスを作成しました - やた＠はてな日記
追記（2010-09-22）：完成版がこちら（N-gram コーパス - 日本語ウェブコーパス 2010）にあります． 前回は形態素 N-gram コーパスを作成したので，今回は文字 N-gram コーパスを作成してみました．正確には，Unicode のコードポイント N-gram です． ダウンロード 文字 N-gram コーパス（頻度 100 以上） ファイル名（URL） サイズ [bytes] http://dist.s-yata.jp/2010/0807/over99/1gms/1gm-0000.xz 27,932 http://dist.s-yata.jp/2010/0807/over99/2gms/2gm-0000.xz 3,086,292 http://dist.s-yata.jp/2010/0807/over99/3gms/3gm-0000.xz 21,169,168 ht
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Darts clone 0.32g に関する資料 - やた＠はてな日記