文法圧縮を使った完備辞書(簡潔ビットベクトル)を作った - EchizenBlog-Zwei
@marugorithmさんの文法圧縮の解説資料(http://research.preferred.jp/2014/03/nlp2014_grammar/)があまりにも有益すぎて感動したので、文法圧縮を使った完備辞書(簡潔ビットベクトル)を作った。 文法圧縮の部分は実装の簡単さからRe-Pairアルゴリズムを使った。 https://github.com/echizentm/GCFID 作ってみて感じたメリット・デメリットをメモしておく。 簡単に言うと、rank、selectがO(1)でないという欠点があるものの理解のしやすさ、実装のしやすさを考えると利点が大きいように感じた。 文法圧縮を用いて完備辞書を作るメリット ビット列が変換規則(X1 => X2, X3みたいなの)の集合で表現できるのでpopcountとかのややこしいビット演算が不要 ビット演算が不要なのでperl,python
簡潔データ構造のためのx86/64最適化rank/select辞書 - maropuのメモ墓場
A x86/64-optimized rank/select dictionary for succinct data 年末/年始の時間を利用して簡潔データ構造（Succinct Data Structure，以下SDS）の 中核として利用されるビットベクトルのrank/select辞書のコード最適化 （x86/x64アーキテクチャ向け）をしていた． rank/selectはSDS内の処理で頻繁に呼び出されるため，ここの最適化は全体性能を 底上げするうえで非常に重要だと考えたためだ． 目標は1回のrank/selectを平均的に数十clkで実現すること． とりあえず出来たコードは以下． https://github.com/maropu/dsucBV ベースとして使わせていただいたコードは以下のCodezineの記事（2006）で PFIの岡野原氏がコーディングしたもの． http://c
簡潔トライの実装に含まれる簡潔ビットベクトルの性能比較 - やた＠はてな日記
はじめに 先日（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/
簡潔ビットベクトル性能評価実験のソースコード(ux-trie編) - EchizenBlog-Zwei
ux-trieで使われている簡潔ビットベクトルの評価実験に用いたソースコードをおいておきます。 簡潔ビットベクトル構築用コード(ux_make.cc) #include "rsDic.hpp" #include <iostream> using namespace std; using namespace ux; int main(int argc, char **argv) { try { BitVec bv; if (argc < 1) { cerr << "USAGE: ux_make < infile > bvfile" << endl; } uint64_t n = 0; uint64_t pos = 0; while (cin >> n) { while (pos < n) { pos++; bv.push_back(0); } pos++; bv.push_back(1);
話題の新技術、簡潔データ構造の入門用資料をまとめてみた - EchizenBlog-Zwei
最近私の周辺で簡潔データ構造に興味を持つ人が増えてきた。簡潔データ構造といえばGoogle日本語入力でも使われている話題の新技術。自然言語処理界隈で機械学習の次にブームになるのはこれだ！と個人的に思っている。 というわけで入門用の資料をまとめてみた。 簡潔データ構造では、すべての基礎である簡潔ビットベクトルがあって、その上に応用として簡潔木(LOUDSなど。Google日本語入力で利用されている)、簡潔文字列(ウェーブレット木など。FM-Indexに利用されている)がある。最近ではこれらより複雑なデータ構造に対する簡潔構造も研究されている。 ということをふまえて以下の資料を読むと良い。 Efficient dictionary and language model compression for input method editors Taku Kudo et al. Google日本語
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
SDSL - Succinct Data Structures Library - Universität Ulm