Version 0.1.0 と Version 0.1.1 の検索時間を比較するついでに，索引の実装を少し修正したもの（Version 0.x.x）もまとめて比較してみました．Version 0.x.x については，索引のサイズが約 2 倍になったことにより，辞書のサイズが 2-4% 大きくなっています…

marisa-trie の実装を見直して，無駄に rank() を呼び出している箇所があったので修正しました．その結果，検索速度が向上しています．データ構造やインタフェースの変更はありません． marisa-trie - Project Hosting on Google Code http://code.google.co…

IPSJ の全国大会と NLP の年次大会に参加予定ということで，宿泊施設の確保と交通費の概算をしながら，交通費の高さに嘆いていました． 往路：徳島→東京 徳島から東京への移動については飛行機を使います．普通運賃では 29,600 円になりますが，スーパー旅割…

特に問題なさそうなので，正式版（0.32g）ということにしました．変更箇所は，README, COPYING の更新にコメントの修正のみです． darts-clone - Project Hosting on Google Code http://code.google.com/p/darts-clone/ # 正式版にするのを忘れていました．…

体調が戻りました ほとんどの症状は解消しました．鼻詰まりが残っているものの，行動には特に問題なしです．とはいえ，天候の方は下り坂，気温も低くなっているので，また体調を崩してしまわないように気をつけなくては…． プロセッサを支える技術 残り プロ…

昨日から風邪気味で，本を読んでもまったく頭に入ってこないので，MARISA を略称とするようなフレーズを考えて時間を潰していました．思い付いたのが以下のフレーズです． MARISA: Matching Algorithm with Recursively Implemented StorAge これだけ見ても…

第 2 章は「プロセッサの変遷」です． コンピュータ以前 まずはコンピュータ以前の計算装置ということで，そろばんの説明から始まっています．とあるゲームでは武器として使われていましたが，計算の道具として馴染み深い存在です*1．むしろ，最近のいわゆる…

言語処理学会の論文〆切前後から少し放置状態になっていた RSS Reader を片付けるべく，いろいろヴァーッと読んでいました．後，言語処理学会第17回年次大会(NLP2011)ワークショップ 「自然言語処理における企業と大学と学生の関係」 の原稿もヴァーッと読ん…

どうも届いて半月くらい寝かせた後で読むのが習慣化しつつあります．# 私が書いている部分は，なんとなく思ったことばかりで，ほとんど根拠なしです． 座談会 情報系学長，おおいに語る 学長という視点を持つ方々による座談会（2010 年 8 月）の内容で，とこ…

2 月 2 日は情報セキュリティの日だそうです．特に思うところがあるわけでもないけれど，何となく書かなければならないような気がしました…．

どのような読者を想定しているのか甚だ疑問な連載と化していましたが，とりあえず，今までの記事をまとめておきます． marisa-trie における rank/select の実装 http://d.hatena.ne.jp/s-yata/20110118/1295288559 rank/select の索引については，ブロック…

本日の内容は Predictive Search の実装についてです． 概要 marisa-trie には Predictive Search 用の関数が 3 種類あります． predict() キーの復元をおこなうときは predict_depth_first() を呼び出し，そうでないときは predict_breadth_fist() を呼び出…

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

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 でログインできません．こうなるとパ…