IME本の効果でLOUDSの認知度が高まってきた気がする。が、一方で難しいという意見もチラホラある様子。 というわけでLOUDSをどこまでわかりやすく説明できるか？ということに挑戦したくなったので記事を書いてみるよ。

ふと思い立って、LOUDSってビット列上の位置は不要で子ノードのIDだけわかればいいのでは、という気がした。この場合LOUDSの各種操作はselect()だけで良くなりrank()を使わなくなる。通常、簡潔ビットベクトルではselect()のほうが遅いのであまり効果は無い…

「日本語入力を支える技術(IME本)」で紹介されたことで一躍市民権を得た感のあるLOUDS(Level Order Unary Degree Sequence)。LOUDSとは木の簡潔データ構造で、小さいデータサイズで木が実現できるので日本語入力の辞書引きに使うトライ木をLOUDSで実装すると…

先日部屋を掃除していたら昔購入した「急に売れ始めるにはワケがある(原題: The Tipping Point)」という本が出てきた。購入したはいいけど読む時間がなくて積ん読していたことを思い出した。 せっかくなので読んでみたら面白かった。ブログを書いているとブ…

森田季節先生の「お前のご奉仕はその程度か？」が実は超面白いのではないかという気がしてきた。1巻を読んだときは独特の文体(これでも森田作品では普通な方らしい)に圧倒されたが気がついたら抜け出せない所まで来ていた。 なにやらドラマCDが出ていたり、…

せっかくFM-Indexを実装したので、以前作ったCompressed Suffix Arrayとの性能比較をしてみた。 私の実装の比較なので本来の手法の良し悪しとは必ずしも一致しない可能性がある。あくまで参考程度に。

ウェーブレット木ライブラリShellinfordのFM-Indexクラスに文書検索機能を追加実装したので公開しておく。 shellinford - shellinford: succinct document retrieval library - Google Project Hosting An alphabet-friendly FM-index P. Ferragina, G. Manz…

先日公開したウェーブレット木のライブラリshellinfordにFM-Indexの機能を追加した。 まだ基本的な機能しか実装していないけれど、とりいそぎ公開しておく。おいおい機能は追加していく予定。 shellinford - shellinford: succinct document retrieval libra…

自作ウェーブレット木ライブラリshellinfordのパフォーマンス測定をしてみた。 shellinford - shellinford: succinct document retrieval library - Google Project Hosting

@tkngさんの力作「日本語入力を支える技術」が2/8に発売される。既に秋葉原のヨドバシ有隣堂や池袋のジュンク堂本店では早売りされている様子。ってことで早速購入してきた。 本書が扱うテーマはGoogleIMEのような「日本語入力」のシステム。これだけだとさ…

参加してきました。簡単にメモ。 mixi Engineers' Blog >> mixi Engineers’ Seminar #3のお知らせ

ついかっとなってウェーブレット木のライブラリを作ってみた。せっかくなので公開しておく。LOUDSはerika-trieを作ったので今度はウェーブレット木を作りたかった。 ライブラリ名はおおかたの予想を裏切りshellinford。かびーん。 なお、ウェーブレット木で…

久々のミルキィコミック。アニメとゲームの中間っぽい印象の作品だった。これはなかなかよろしいのでは。二巻が楽しみです。

作ったプログラムのテストとかでまとまった数の乱数が欲しいことがある。値が重複しても良いならひたすら乱数を生成する関数(rand()とか)を呼べばいい。 ところが場合によっては同じ値が何回も出現すると困ることがある。こういう時のために重複のない乱数リ…

時代はテスト駆動開発(TDD)らしいので有名な単体テスト用フレームワークCppUnitを試してみた。 これまでテスト用コードは自前で書いていたのでフレームワークのありがたさを実感するなどした。ただCppUnitは「必ず書かないといけないコード」の量が何気に多…

アルゴリズムとデータ構造の優良な教科書として以前から大プッシュしていた「プログラミングコンテストチャレンジブック」の第2版がもうすぐ発売する・・・と思っていたら紀伊國屋書店新宿本店/新宿南店では1/23、つまり今週の月曜日から店頭に並んでいたこ…

「ナゾ！ナゾ？Happiness!!」購入しました。いい曲だー。 でも実はカップリングの「はいぱーみるきぃあわー」のほうが好きだったり。この曲はネロがいきいきしていて良いね。

というわけで1週目クリア。ゆっくり進めて25時間くらいだったので最近のゲームでは気楽に遊べる方だと思われる。 シナリオについては全部のルートを見てからでないとなんとも言えない部分が多そうなので(というか私が通ったルートは色々伏線が回収されずに終…

ちょっと興味があったので調べてみた。 全文検索には主に転置インデックス(Inverted Index)によるものと接尾辞配列(Suffix Array)/接尾辞木(Suffix Tree)によるものがある。 前者は効率的にデータを扱えるものの、キーワード単位でしかインデックスを付けら…

なにやらDan Kogai氏の以下の記事が話題になっている様子。 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? 連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これから…

はじめました。ゲーム進めるのに忙しいので取り急ぎメモ。 ネタバレしない方向で気づいたことを書いておく。ちなみにまだ序盤です(第5話)。念のため。

私はそんなにアニメには思い入れがないほうなのでアニメのDVD/BDに手を出すことは少ないのだが、時折すごい勢いでハマってしまい気がついたらDVD/BDを購入してしまうような作品と遭遇することがある。 そんな個人的に大ハマりしたアニメ3作品を紹介したい。…

テキストデータの言語的な特徴を知りたい場合、そのデータを使ってNgram統計を取ることがよくある。Ngram統計というのはテキスト中の連続したN文字それぞれが何回出現したかの統計をとること。 といわれてもピンとこない人もいるかも知れない。実例を見るの…

せっかくブログがあるので、あけましておめでとう的な記事を書いて見ることにしたよ(他の方の記事を見ていて真似したくなった)。 思わずラノベ風タイトルにしてみたけれど深い意味はない。 以下、去年を振り返りつつ今年はどうしようか的なことをつらつらと…

「PIANO OPERA FINAL FANTASY I/II/III」というものが発売されるらしい。 PIANO OPERA -FINAL FANTASY I/II/III | SQUARE ENIX FFでピアノというとPIANO COLLECTIONSというのがあったのだがIV以降のものしかなかったのでI,II,IIIのピアノアレンジ曲集が出る…

最近滞っていたラノベを読む作業を再開。久々にファンタジア文庫に手を出してみた。 この作品。もともと買う予定はなくて時間つぶしのために手にとって見たのだけど、読んだら結構面白かった。 主人公がヒロインと仲良くなるんだけど、いろいろあっていなく…

ミルキィ1.5の4ヶ月連続リリースも今回の第5話をもって終了。第6話がないので非常に不完全燃焼気味な終わり方をしているなー。 とはいえ1.5で補完されたシャロ話はとてもよいものでした。 探偵オペラ ミルキィホームズ公式サイト｜最新情報: 2011年9月28日(2…

rx-trieで使われている簡潔ビットベクトルの評価実験に用いたソースコードをおいておきます。rx-trieのbv構造体にはファイル読み書きの関数が無かったので構築と評価を同時にやってしまっています。

ux-trieで使われている簡潔ビットベクトルの評価実験に用いたソースコードをおいておきます。

評価実験に用いたソースコードをおいておきます。これを用意するときに気づいたのですが、rank/select呼ぶ度に標準出力に書き出してるせいでめちゃくちゃ遅くなってたっぽい。適当な実験で迷惑かけてすみませんでした。。。 というわけでまずはmarisa-trie用…