冪乗則と一様分布と遷移キャッシュ - やた＠はてな日記
これまでキーの参照頻度が一様分布に従うという無茶な仮定の下で実験をすることが多かったのですが，遷移キャッシュを導入したということもあり，冪乗則だとどうなるのかを調べてみました．実験に用いたデータは，日本語ウェブコーパスにおける頻度 1000 以上の単語 N-gram です． N-gram コーパス - 日本語ウェブコーパス 2010 http://s-yata.jp/corpus/nwc2010/ngrams/ 単語 N-gram コーパスの頻度情報を利用すれば，冪乗則が成立する状況を再現できます．すなわち，一部の高頻度な N-gram が全体に対して大きな割合を占め，ほとんどの N-gram は稀に出現するのみとなります． 遷移キャッシュの効果は高頻度の遷移を高速化することであり，参照頻度が冪乗則に従う状況であれば，より高い効果が期待できます． 実験結果（Google Document）
検索時間が短くなりました - やた＠はてな日記
辞書に対してキャッシュを埋め込むことにより，検索時間の短縮に成功しました． 概要 基本的な考え方は，到達確率の高いノードについて，遷移に必要な情報をダイレクトマップ方式で保存しておくというものです．到達確率については，辞書を構築するときに計算する重みを利用しました． キャッシュにヒットしたときは，rank() や select() が必要なくなるので，計算コストが小さくなります．また，本来なら別の領域にある情報をキャッシュにまとめたことにより，CPU キャッシュの利用効率も向上しています． 実験結果 以下，現状での実験結果です． ノードの並びを重み順にしたとき，デフォルトの設定（Normal cache）では，辞書のサイズが 2% くらい大きくなるものの，検索時間を 10-20% くらい短縮できました．悪くないバランスだと思います． さらにキャッシュを大きくして検索時間を短縮することも可能
実験に用いる実装はどうするべきかという疑問 - やた＠はてな日記
データ構造とアルゴリズム，あるいは何らかのシステムを提案するとなれば，実験による評価は欠かせない存在です．理論的な評価も大切ですが，最終的には，実環境に置ける性能を評価することが求められます．でも，公平な評価とは難しいものです． それぞれに利点・欠点，得意・不得意なデータ，環境の制限などがあるわけで，すべてを考慮して公平に評価することは不可能に近いことです．そんなわけで，環境を決めて，特徴的なデータを選択して…という具合に，実験設定を揃えることになります． そして，実験において重要な問題の一つだと私が思っていることの一つが実装です．どの実装を使うのか，あるいはどうやって実装するのか…．時間を評価するときは特に問題になります． 比較対象の実装が公開されていれば楽なのに…と思うこともありますが，それはそれで，悩みの種になる可能性があります．例えば，実装した人物のプログラミング・スキルがとても高
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 における rank/select の実装 - やた＠はてな日記
概要 rank/select は簡潔データ構造（Succinct Data Structures）の核になる関数です．ビット列の k ビット目までに含まれる 0, 1 の数を求めるのが rank，k 番目の 0, 1 の位置（Index）を求めるのが select であり，ビット列の密度（1 の割合）によって，いろいろな実装があります． marisa-trie では，0, 1 の割合が極端に偏らないビット列を想定するとともに，32-bit 環境における性能の劣化を防ぐために，64-bit 整数を使わないようにしました．そのため，ほとんどの部分は以前に開発したライブラリからの流用ですが，新しく書き直した部分もあります．ちなみに，索引のサイズはビット列の長さ n bits に対して (1/4)n bits です． 基本 ビット列の実装 ビット列の格納には 32-bit 整数の配列を使っています
新しいトライのライブラリを公開しました - やた＠はてな日記
概要 トライのライブラリを公開しました．ドキュメントはまったく用意できていませんが，とりあえず使えます．（追記 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
トライの実験に使えるちょっとしたツール - やた＠はてな日記
トライを構築したときのノード数が分からない，TAIL を導入したときにサイズがどのくらい小さくなるのか分からない，そんな悩みに答えるちょっとしたツールのソースコードです． 各ノードのサイズとノード数が分かればトライのサイズは簡単に求まるので，トライについて少し試してみようという段階で便利かもしれません． 例えば，ダブル配列であればノード数 n に対して 4n bytes か 8n bytes が基本です．ただし，以下のツールは終端文字による遷移をカウントしないことに注意してください．後，TAIL の長さが m であれば，m bytes を追加することになります． また，LOUDS Trie であれば，木の表現に 2n bits，ラベルの保存に n bytes，終端フラグの保存に n bits，後は rank/select の索引に…という具合で 1.5n bytes くらいになると思います
HTML からのテキスト抽出をウェブサービス化 - やた＠はてな日記
日本語ウェブコーパスを処理するためのプログラムを改修しているのですが，HTML アーカイブからのテキスト抽出までは問題なく動く状態になったので，HTML 文書からテキストを抽出するウェブサービスを公開してみました． http://s-yata.jp/apps/nwc-toolkit/text-extractor HTML の入力方法は，以下の 3 種類を用意しています． 入力方法 URL を入力：指定した URL からテキストを抽出します． ファイルを入力：アップロードした HTML ファイルからテキストを抽出します． HTML を入力：フォームに入力した HTML からテキストを抽出します． テキスト抽出の中身は，HTML 文書の文字コードを UTF-8 に変換してから，テキスト部分のみを切り出し，Unicode 正規化（NFKC）を施した後で，句点や感嘆符による文区切りをおこない，さら
Hadoop とか MapReduce とかはいい，メモリを使うんだ - やた＠はてな日記
http://d.hatena.ne.jp/nokuno/20100915/1284564957 のスライドを眺めながら，「メモリを有効利用するのは MapReduce でも重要だよね」などとぼんやりと思いました． 以前，N-gram コーパスの作成に MapReduce を試したとき，並列に実行されるプロセスの数と全体のメモリ容量を考慮して C++ で mapper を書かないと，効率が悪くて仕方がないという結論に落ち着いていたことが，「だよね」につながっています． とはいっても，大規模なデータに関しては，できる限りメモリ上で取り扱うべしというのは一つの基本ですから，なんだか伝統への回帰のような印象も受けました．これは，最近読んだ本に書いてあったからかもしれません． [Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB+DB PRE
大規模トライ用のライブラリを開発中 - 2010-01-30 - やた＠はてな日記
Succinct なトライをサポートする sumire-tries があるにもかかわらず，ここしばらく，大規模なトライ用のライブラリを開発しています．sumire-tries を何度も修正したのは，開発の途中でいろいろと気づいて，それらを反映させていたからです．いわゆるオマケという感じです． 今回の開発目的は，sumire-tries より大規模なトライを扱うことです．そして，新しいライブラリの特徴は，以下のようになっています． 64 ビット環境に最適化 32 ビット環境でも使えますが，本来の性能は出ません． トライのサイズ制限なし ノード数の上限は 2^38 = 2700 億です． 一時ファイルの利用 主記憶容量を超えるサイズのトライを構築できます． 構築するだけなら主記憶容量を超えても問題ありませんが，メモリ上に展開できないため，検索するときに mmap() を使うことになります．おそ
Succinct なトライの実験に用いたソースコード - やた＠はてな日記
いつものように，Google Code にアップロードしました．プロジェクトの名前は sumire-tries になっています．名前を sumire にした理由は，なんとなくです…． ドキュメントは準備中ですが，基本的な使い方は後述します． Google Code Archive - Long-term storage for Google Code Project Hosting. 右のメニューにある Featured downloads からアーカイブをダウンロードして，よくある手順を踏めば動作確認できます． ./configure make make check ヘッダのみで構成されているため，make install でインストールしなくても，ヘッダを格納しているディレクトリ（include/）をコピーすれば使えます． トライを構築する手順は，以下のようになっています． 基礎となる
2009-10-29 - やた＠はてな日記 Succinct なトライの実験
実験の概要 Succinct な木構造を用いてトライを実装すると，コンパクトな辞書を構築できます．しかし，検索速度の面では，その他のデータ構造に劣るという欠点を持ちます．そこで，いくつかのトライを C++ で実装し，ちょっとした性能テストをしてみました．今回のテストで実装したトライは，以下のとおりです． BasicTrie 各ノードに「一つ目の子ノードの ID」，「兄弟ノードが存在するか」，「ラベル」を持たせたトライ 兄弟ノードが隣接するように配置 探索時，子ノードを線形探索して移動先を決定 TernaryTrie BasicTrie の各ノードに「子ノードの数」を加えたトライ 探索時，子ノードを二分探索して移動先を決定 DaTrie ダブル配列によるトライ 探索時，ラベルにより移動先を一意に決定 SuccinctTrie 「一つ目の子ノードを左の子」，「兄弟ノードを右の子」とする二分木に
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
