Google N-gram コーパスを丸ごとトライにすると，ノード数は 150 億程度になります．LOUDS を用いて表現した場合の想定サイズは約 22GB です．メモリ上に展開することも，不可能ではありません．※ バイト（Byte）を文字として扱いました．LOUDS 利用時の想定…

sumire-tries を 0.3.0 から 0.3.1 に更新しました． http://code.google.com/p/sumire-tries/ 変更点は以下のとおりです．使い方に関する変更はありません． バグの修正 sumire::BasicTrie::build() にて sumire::BasicTrie::MAX_VALUE_ORDER を指定したと…

sumire-tries のドキュメントを少しずつ更新しています． Google Code Archive - Long-term storage for Google Code Project Hosting. とりあえず，基本的な機能から順に更新していく予定です．各種トライの実装についても説明できればよいのですが，時間が…

キーボードの操作やマウスクリックを受け付けなくなり，編集中の文書を保存することもできずに電源を切ることになりました．マウスカーソルだけが動く状態になったときは，…どうすればよいのでしょうか．

以前の投稿（2009-08-28 - やた＠はてな日記）で述べたとおり，重み付きキー補完において，外部レコードを利用できるように拡張しました．ただし，とても使いにくいのでおすすめできません．やっつけ仕事っぽい仕上がりです． 使い方 キー補完用辞書の構築 d…

これまでの実験では単純なトライのみを対象としてきましたが，LOUDS や LOUDS++ による実装では子ノードへの移動時に呼び出す select() のコストが高いため，パトリシア（PATRICIA）の方が高速に検索できる可能性があります．※ パトリシアについては，トライ…

いつものように，Google Code にアップロードしました．プロジェクトの名前は sumire-tries になっています．名前を sumire にした理由は，なんとなくです…．ドキュメントは準備中ですが，基本的な使い方は後述します． Google Code Archive - Long-term sto…

そろそろドキュメントを用意してソースコードを公開しようと思っていたのですが，大切な実験を一つ忘れていたことを思い出しました．それは，子ノードの順番を変更したとき，検索時間がどのくらい変化するのかを調べるものです．これまでの実験（2009-10-29 …

先週の実験結果（2009-10-29 - やた＠はてな日記 と 2009-10-30 - やた＠はてな日記）では，select() の遅い実装を用いていたため，SuccinctTrie の方が LoudsTrie, LoudsPlusTrie より高速に検索できていました．一方，今回の実験結果では，Succinct Bit Ve…

昨日の実験結果（2009-10-29 - やた＠はてな日記）は assert() が有効な状態で計測していたため，assert() を無効にした状態で再計測しました．また，Google n-gram コーパスを用いた結果を追加してあります． ID コーパス キー数 平均キー長（bytes） jawik…

実験の概要 Succinct な木構造を用いてトライを実装すると，コンパクトな辞書を構築できます．しかし，検索速度の面では，その他のデータ構造に劣るという欠点を持ちます．そこで，いくつかのトライを C++ で実装し，ちょっとした性能テストをしてみました．…

Amazon Web Services からのメールにて，インスタンスタイプの追加と価格の更新についてのお知らせがありました．以下のページで確認できます． インスタンスについて http://aws.amazon.com/ec2/?ref_=pe_12300_13473310#instance 価格について http://aws.…

11 月 14 日に高知でオープンソースカンファレンスがあるそうです．情報処理学会のメーリングリストにて数日前に連絡が来ていました．四国には初上陸ということで，行ってみるべきかどうか考え中です． オープンソースカンファレンス2009 Kochi - いらっしゃ…

今月に入ってからサーバが 2 回ほどフリーズしました．ここ数カ月は安定していたのですが，データが多くなって配置が分散し，ディスクにかかる負荷が高くなったことが原因と考えられます．以前にもディスクに負荷をかけたタイミングでフリーズすることが何度…

大量のテキストファイルから特定のフレーズを含む文を検索するシステムです．Python の勉強が目的だったのか，システムの開発が目的だったのか，今となっては思い出せません．:Dブラウザからクエリの登録をしておいて，検索が完了したら結果をダウンロードで…

大量の HTML 文書を解析するために作成したライブラリとツールです．HTML 文書を解析して protocol buffers に変換したり，テキスト部分を抽出したり，リンクを抽出したりできます．入出力の文字コードは UTF-8 を想定しています．HTML 文書の解析といっても…

ずいぶんと久しぶりですが，その間に HTML の解析用プログラムを作成したり，大量の HTML 文書からテキストを抽出したり，簡易な検索システムを作成したり，お亡くなりになったサーバを片付けたり，他のサーバを引越しさせたり，DB をロールバックしたり，応…

メモ代わりに，sort -m と同じような動作をするプログラムのソースコードを貼り付けておきます．（行単位で）整列済みのファイルを複数マージして，一つの整列済みファイルを作成するためのプログラムです．入力の指定にはコマンドライン引数，出力には標準…

C++ でデータの圧縮・復元をする場合，boost C++ library に便利な Filter があります．gzip -c や gzip -cd などで対応できないときには，検討する価値があると思います． Gzip Filters # リンクするときにライブラリ libboost_iostream... を指定する必要…

21 世紀コンピューティング コンファレンスなるものが，11 月に慶応大学と京都大学で開催されるようです．主催者は Microsoft Research Asia だそうです． 日本語 http://www.microsoft.com/japan/events/21ccc/default.mspx 英語 http://www.msra.cn/labeve…

Python だと複雑な処理を書けないので（主に慣れていないため），C++ で Mapper と Reducer を開発でできないか確認してみました．結論は，「たぶん大丈夫」です．悩みどころは，基本的にバイナリの互換性がないと考えるべき Linux 環境において，「どうやっ…

個人でも，気軽に大規模並列処理を試せます．一般的な個人には MapReduce の使いどころがないかもしれませんが，研究をしている方々には面白い素材になるのではないでしょうか．これまでの簡単な実験では，コーパスから文字 n-gram を抽出するというタスクを…

ハッシュ表に挑戦したという意味ではなく，「ハッシュ表の上にトライを構築してみました」という話です．ダブル配列のアイデア（CHECK に遷移元のインデックスを保存）を利用しています．ダブル配列は，小さな整数（基本的に Byte）をラベルとする場合には高…

大規模なコーパスを本格的に処理することを考えて，MapReduce の勉強をしています．手元に MapReduce をおこなえる環境はないのですが，Amazon Web Services (AWS) のおかげで，思いのほか手軽に試すことができました． メモ代わりにリンク貼り付け Amazon E…

dawgdic::DawgBuilder のオブジェクトを再利用すると segmentation fault が起きるというバグがありました．Subversion の方は更新してあります．アーカイブ（Downloads）の方は，次のバージョンで対応することになると思います．

Google n-gram を使っての入力補完を英語版のコーパス全体に適用してみました．単体で約 2GB の辞書が 30 個以上で，すべての辞書を合計すると約 70GB になりました．さすがに，最初の入力についてはディスクアクセスのため数秒待たされますが，以降はそれな…

FIT2009 第8回情報科学技術フォーラム のイベントでクラウドに関するお話を聴いたのですが，専門家を集めてみても，やっぱり「クラウド」という言葉の定義は微妙なようです．「グリッドとクラウドは何が違うのか？」という質問があり，答えに窮する様子を見…

重複レコードの多い辞書については，トライから Directed Acyclic Word Graph (DAWG) への変換で大幅に圧縮できるかもしれません．…という内容のスライドです． 重複レコードの多いトライ辞書の圧縮（pptx） http://sites.google.com/site/headdythehero/cab…

dawgdic-0.4.0 から追加したキー補完機能について，ドキュメントを追加しました． dawgdic - Project Hosting on Google Code http://code.google.com/p/dawgdic/ Wiki の HowToComplete にキー補完用辞書の構築方法とキー補完の方法があります．また，Inter…

キーの補完時，候補をレコード降順に取得できるようになりました．ただし，現状では，レコードを ID として外部の情報により順序を決定するということはできません．将来的には，インタフェースの拡張により対応する予定です．おそらく，キー補完用の辞書を…