データ構造とアルゴリズム，あるいは何らかのシステムを提案するとなれば，実験による評価は欠かせない存在です．理論的な評価も大切ですが，最終的には，実環境に置ける性能を評価することが求められます．でも，公平な評価とは難しいものです．それぞれに…

marisa-trie 0.1.0 を公開しました． marisa-trie - Project Hosting on Google Code http://code.google.com/p/marisa-trie/ 変更内容については，以前の記事（ライブラリの更新準備中 - やた＠はてな日記）に書いてある内容のほか，ツールの修正・拡張と p…

概要 marisa-trie にて選択できる TAIL の実装は，TAIL なし（MARISA_WITHOUT_TAIL），バイナリモード（MARISA_BINARY_TAIL），テキストモード（MARISA_TEXT_TAIL）の 3 種類です．それぞれの簡単な説明は以下の通りです．# marisa-0.0.1 ではテキストモード…

概要 marisa-trie では，1 byte のラベル（Single-byte（SB）ラベル）は各トライに格納し，2 bytes 以上のラベル（Multi-byte（MB）ラベル）は次のトライもしくは TAIL に格納するようになっています．そのため，SB/MB ラベルを区別するためのフラグを各ノー…

昨日の子ネタに続いて，本日は前向き文字列と後ろ向き文字列に関する内容になっています．前向き・後ろ向きという表現については，名前がないと不便なので，本記事のためだけに用意した造語です．前向き文字列というのは，前から順に参照する文字列を意味し…

今回の内容は，0 を終端とする文字列と，長さを別に持つ文字列の扱いに関する小ネタです．検索用のインタフェースを用意するとき，どちらか一方を選択するのであれば，後者にすると思います．しかし，できれば前者も提供したいと思うのが人情というものでし…

marisa-trie を 0.1.0 に更新するべく，テストを追加したり，Visual C++ 用のファイルを作成しなおしたり，ドキュメントを更新したりしていました．実装の方はほぼ完成したという状況なので，ドキュメントの更新が終われば公開できると思います．変更の内容…

昨日が言語処理学会年次大会の論文投稿締切りで，ちょいと無理をして完成させたため，今日は燃え尽きていました．ホテルの確保は終わったので，後は大会参加の事前登録と移動手段の確保かな…．スライドの作成こそは早目に終わらせたいけれど，そうは問屋が…．

ソースコードの調整なんぞに気を取られている内にどんどん時間が過ぎて，結局，論文の完成は締切り間際になってしまいました．実のところ，締切り間際で完成するよう，無意識の内に調整してしまっているのかもしれません．とりあえず，これで安心して眠るこ…

概要 rank/select は簡潔データ構造（Succinct Data Structures）の核になる関数です．ビット列の k ビット目までに含まれる 0, 1 の数を求めるのが rank，k 番目の 0, 1 の位置（Index）を求めるのが select であり，ビット列の密度（1 の割合）によって，…

まさしくチラシの裏…．考え中のインタフェースです． #ifndef _MSC_VER #include <stdint.h> #endif // _MSC_VER #ifdef __cplusplus #include <cstddef> #else // __cplusplus #include <stddef.h> #endif // __cplusplus #ifdef __cplusplus extern "C" { #endif // __cplusplus // Visu</stddef.h></cstddef></stdint.h>…

今年になってから入手した本は 2 冊です．1 冊目は「プロセッサを支える技術」です．タイトルに惹かれました．最近はプロセッサに対する興味がずいぶんと薄れていたので，この書籍は，昔に学んだ内容の復習と，新しい技術の良い勉強になりそうな予感がします…

センター試験の日は特に寒くて雪まで降る…，ことが多いような気がします．冬を通しても滅多と雪が降ることのない場所に住んでいるはずなのに，前日に冷え込んで路面が凍ったり，当日に雪が降ったりと，何が気にくわないのやら分かりませんが，センター試験の…

marisa-trie に C 言語用のインタフェースを加えようと画策していたのですが，今あるインタフェースにも多少は手を加えることになりそうです．# 今のインタフェースだと例外が放し飼い（投げっぱなし）なので，他のライブラリとの連携には使いにくいと思った…

いわゆるクラウド環境において，キャッシュの応答を観測することで，同居している仮想マシンがおこなっている処理を推定するという攻撃方法があると，情報処理学会会誌 12 月号の小特集で紹介されていました．おもしろいというか興味深いというか，ついでに…

情報処理学会第 73 回全国大会のプログラム（簡易版）が公開されています．場所は東京工業大学大岡山キャンパスで，日程は 3月2日（水）〜3月4日（金）です． プログラム｜情報処理学会 第73回全国大会 http://www.ipsj.or.jp/10jigyo/taikai/73kai/program.…

言語処理学会第 17 回年次大会（http://www.anlp.jp/nlp2011/）のプログラムが公開されています（http://www.anlp.jp/nlp2011/program.html）．思い直してみると，言語処理学会の年次大会については，ポスター発表で参加したことが一度あるだけです．前回は…

冬になって空気が乾燥してくると，指先がカサカサになってしまい，指紋認証が失敗するようになります．反応しなかったり，指紋として認識されなかったり，違う指紋と判断されたりで，ひどいときは何度試してもノート PC でログインできません．こうなるとパ…

# 環境依存な内容な上，無駄に細かい話なので，「そういうこともあるかもねー」くらいに流しちゃってください．（追記 2011-01-11）新しい規格では std::string の Copy on Write（CoW: 書き込み時に複製）が実質禁止になるとのことです．後，gcc 4.5 の時点…

概要 トライのライブラリを公開しました．ドキュメントはまったく用意できていませんが，とりあえず使えます．（追記 2011-01-09）ドキュメントを追加しました． http://code.google.com/p/marisa-trie/ ドキュメント ベンチマーク 使い方 インタフェース ツ…

昨年末の投稿から引き続いて，多層トライをライブラリ化していました．現在，ソースコードはほとんど完成していますが，ライブラリの名前はまだ決まっていません．パトリシア（PATRICIA: Practical Algorithm To Retrieve Information Coded In Alphanumeric…