はじめに 先日（12/10）DSIRNLP という勉強会で紹介されていた，簡潔トライの実装に含まれる簡潔ビットベクトルの実験結果が予想とかけ離れていたので，自身でも調べてみることにしました． partake.in DSIRNLP#2で発表しました「作ろう！簡潔ビットベクトル…

std::unordered_map に言及しているブログを見て，記事にするのを忘れていたことを思い出しました．重複のないデータセットがあるときは std::unordered_set/map に一つずつ登録するより，std::vector か何かに入れてから一気に std::unordered_set/map を構…

少し前に記事を書いたばかりと思っていたのに，気がついたら二週間も経っていました．最近，月日があっという間に過ぎていくことに驚きを感じます．先日（2011-11-29）は groonga を囲む夕べ 2 というイベントで発表をしました．発表資料は groonga のサイト…

お久しぶりです．前回の記事を投稿から 3 ヶ月も放置してしまいました．9 月末に引越しをしてから一ヶ月半ほどになり，新しい土地にも慣れてきました．家と会社にいる時間がほとんどなので慣れるも何もありませんが，生活は安定しているし，大きく体調を崩す…

はじめに 今回の記事は，以下の論文に関するものです．他にも紹介記事（ACL2011論文「Faster and Smaller N-Gram Language Models」を読んだ - EchizenBlog-Zwei）があるので，そちらでは特に触れられていない部分を（独断と偏見により）解説しています． ht…

以前から「調べなきゃー」と思いつつ忘れていた内容です．marisa-build を使って辞書を構築するときのメモリ消費（ピーク）を /usr/bin/time -v により計測してみました．# /usr/bin/time -v の Maximum resident set size (kbytes) を確認したわけですが，g…

これまでキーの参照頻度が一様分布に従うという無茶な仮定の下で実験をすることが多かったのですが，遷移キャッシュを導入したということもあり，冪乗則だとどうなるのかを調べてみました．実験に用いたデータは，日本語ウェブコーパスにおける頻度 1000 以…

Perl, Python, Ruby とバインディングを用意してみたものの，C++ と比べて驚くほど遅くなってしまうことに気づきました．原因としては，メソッドの呼び出しにおけるオブジェクトの相互変換が有力です．辞書の構築時間や検索時間を計測した結果を表にしてみま…

概要 marisa-trie に Perl, Python, Ruby バインディングを追加したものを marisa-0.2.0-beta5 としました．使い方は C++ とほぼ同じです． プロジェクト http://code.google.com/p/marisa-trie/ ドキュメント http://marisa-trie.googlecode.com/svn/trunk/…

marisa-0.2.0-beta3 のバグを修正したものを marisa-0.2.0-beta4 としました． プロジェクト http://code.google.com/p/marisa-trie/ ドキュメント http://marisa-trie.googlecode.com/svn/trunk/docs/readme.ja.html 変更点は以下のとおりです． Trie::mmap…

先日の記事（検索時間が短くなりました - やた＠はてな日記）で述べたように，キャッシュの導入によって検索の高速化を実現しました．思い付いた時点ではブレイクスルーになると考えていたものですが，今となっては当たり前のアイデアのように感じてしまいま…

辞書に対してキャッシュを埋め込むことにより，検索時間の短縮に成功しました． 概要 基本的な考え方は，到達確率の高いノードについて，遷移に必要な情報をダイレクトマップ方式で保存しておくというものです．到達確率については，辞書を構築するときに計…

std::sort() を使って文字列（バイト列）を整列していたところをマルチキークイックソートに切り替えたことにより，辞書の構築時間が 15-25% くらい短くなりました．アーカイブの方はまだですが，Subversion には更新版のソースコードをコミットしてあります…

Mac OS にてテストプログラムをコンパイルできないという問題が見つかったので，修正したものを marisa-0.2.0-beta2 として公開しました． プロジェクト http://code.google.com/p/marisa-trie/ ソースコード http://marisa-trie.googlecode.com/files/maris…

いつの間にか，ユーザー登録から本日までに日記をつけた日数が 300 日を超えていました．http://www.hatena.ne.jp/help/citizen次なるプラチナは 1000 日ということで，無理っぽいです．

# 書いている途中で寝てしまったので，一日遅れでお送りしています．LOUDS ベースの Patricia Trie を入れ子にするというコンセプトで開発された marisa-0.1 系と marisa-0.2 系ですが，インタフェースが大きく異なるという目に見える違いの他にも，いくつか…

ドキュメントを用意できたので，リポジトリの内容を marisa-0.2.0-beta に差し替えました．念のため，パッケージについては，いくつか他の環境で試してからアップロードする予定です． プロジェクト http://code.google.com/p/marisa-trie/ marisa-0.2.0-bet…

ほとんどの部分を作り直すという暴挙によって仕上がった代物を，近い内に marisa-0.2.0-beta として公開する予定です．旧版（marisa-0.1.x）と比べると，最大の違いはインタフェースです．原形が残っていないので，旧版を利用するソースコードの流用は無理で…

marisa-0.1.3 に少し修正を施したものを marisa-0.1.4 として公開しました． http://code.google.com/p/marisa-trie/ 今回の修正は，以前に報告されていた問題への対処になっています．基本的な動作やインタフェース，辞書のフォーマットには変更ありません…

いつもは説明的な資料を作成するのですが，今回は説明的でないスライド（発表資料（Prefix/Patricia Trie の入れ子による辞書圧縮） - やた＠はてな日記）を作成してみました．研究発表の資料としては，最低限のところから，さらに削った内容にしたつもりで…

ずーっと前から人が多い場所は苦手で，昨日は特別講演・招待講演が満員御礼な状態になっていたこともあり，かなり疲れてしまいました．懇親会が終わったところで力尽きて，コインランドリーに行くとき以外はほぼ寝ていました．# ホテル内にコインランドリー…

言語処理学会の発表で用いた資料に少しノートを加えたファイルです．もう少し詳しいものを用意できればよいのですが，優先順位は低めなので，あまり期待しないでください． PowerPoint http://sites.google.com/site/headdythehero/cabine/2011/0311/NLP2011…

言語処理学会年次大会のチュートリアルが終了して，無事ホテルに到着しました．チュートリアルの途中で何度も意識が飛んでいたあたりダメダメですが，ずっと寝ていたわけではありませんよ…？それにしても，お腹が空きました．（追記 2011-03-07）先週だけで…

木構造の簡潔表現について，get_parent() は LOUDS より Fully-Functional Succinct Trees の方が速いということを教えてもらったので，第 1 階層の Trie には LOUDS，第 2 階層以降の Trie には Fully-Functional Succinct Trees を使うように改修すること…

情報処理学会全国大会の最終日でしたが，今日はセッション以外の方が重い一日になりました．午前のセッションが終わった後，時間を潰しに訪れたカフェで昨日に知り合った人物と話すことになり，それから約束をしていた人物と合流して，ご飯を確保するべく大…

半年ほど前に報告したバグ（範囲外の数値文字参照に対するエラー）の状態が，つい先日，Fix Commited に変更されました．どうやら，Beautiful Soup 4 にて解決されたもようです． In Beautiful Soup 4, out-of-range charrefs are ignored (when using lxml …

情報処理学会全国大会の懇親会で夕飯を済ませてしまおうと思っていたものの，のんびりしている内にメニューのほとんどが空っぽに…．どうにも足りないので，早目に切り上げてホテルに戻り，ラーメンを食べに行ってきました．ラーメンはおいしくいただけました…

皆さん待望？の東京リージョンができたようです．連絡がきていました． We are excited to announce the immediate availability of our new Asia Pacific (Tokyo) Region! お値段 お値段の方は，やはり少し高くなっています．デフォルトのインスタンスは，…

ちまちまと更新しました．バージョンは 0.1.3 になっています．辞書のフォーマットが 0.1.1 から変化しているため，再構築が必要になります． marisa-trie - Project Hosting on Google Code http://code.google.com/p/marisa-trie/ 0.1.0 と 0.1.3 を比べる…

概要 昨日の実験結果（marisa-trie の高速化と実験結果 - やた＠はてな日記）では索引のサイズを変更した結果を表にしていたわけですが，索引のサイズ以外にも変更した部分があったため，その部分のみを適用した結果を調べてみました． 変更箇所 select() の…