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

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

せっかく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

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

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

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

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

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

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

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

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

レコメンデーションというのはamazonとかで見かける「XXXを買った人はYYYも買っていますよ」というサービスのこと。最近ではレコメンデーションは珍しいものではなく多くのサービスで導入されている。 またレコメンデーションを実現するレコメンデーションエ…

DSIRNLP#1に続いて今回の#2も発表の場をいただきました。今回は簡潔データ構造、とくに最も基本的なデータ構造である簡潔ビットベクトルについて発表しました。@overlastさん、@kimurasさん、@rindai87さんをはじめ関係者、参加者の皆様どうもありがとうござ…

最近私の周辺で簡潔データ構造に興味を持つ人が増えてきた。簡潔データ構造といえばGoogle日本語入力でも使われている話題の新技術。自然言語処理界隈で機械学習の次にブームになるのはこれだ！と個人的に思っている。 というわけで入門用の資料をまとめてみ…

機械学習の3大有名手法といえばSVM、CRF、LDAではないだろうか(と勝手に思っている)。 SVM(Support Vector Machine)については以前記事を書いたので今回はCRF(Conditional Random Fields)について書いてみたい。 機械学習超入門IV 〜SVM(サポートベクターマ…

香川県高松市にて開催されたALSIP2011(Second Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery)に参加してきた。 簡潔データ構造で有名なRajeev Raman先生、NIIの定兼先生、PFIの岡野原さんが招待講演をして下さると…

ちょっと気になったので"K^2-trees for Compact Web Graph Representation"という簡潔グラフの論文を読んでみたよ。 K^2-trees for Compact Web Graph Representation Nieves R. Brisaboa, Susana Ladra, Gonzalo Navarro; 2009

SPIREは文字列処理や情報検索に関する発表が行われる国際会議。今年も10/17から10/21にかけてイタリアでSPIRE2011が開催された。 SPIREで発表された論文については例年Springerからまとめた書籍が発売される。が、無料で済ませられるならそれに越したことは…

検索エンジンの転置インデックスなどデータ列を小さいデータサイズで持たせたい、という状況がある。こういう場合圧縮符号を使うのが一般的でunary符号やgamma符号、delta符号など様々な種類がある。 圧縮符号の中でイチオシなのがvertical code(vcode)。こ…

ALSIP2011のプログラムが公開されていたのでメモ。今回のALSIP2011で注目すべきは簡潔データ構造に関する招待講演。定兼(@ksadakane)先生、岡野原(@hillbig)さん、そしてRajeev Ramanというすごい御三方の講演があるとあってはどうあっても参加せざるをえな…

チュートリアル記事を書いていたら懐かしくなったので、思わず続きを読むなどした。 コラム2は以下の3つの問題を扱っている。 - ある範囲の数値で抜けているものを探す。(同じものは一回だけ出現) - 文字列の先頭のn文字を末尾にくっつける。 - ある単語とア…

先日｢自然言語処理を活用したwebサービスをつくるときに参考になる5冊の書籍｣というタイトルで本を紹介したら評判が良かった。本記事では最初の一冊である「珠玉のプログラミング」のコラム1を読みつつチュートリアル的な記事を書いてみる。 自然言語処理を…

自然言語処理を活用したwebサービス開発に関わって5年以上経った。いい機会なのでこれまでを振り返って役に立ったと思う5冊をメモしておく。

簡潔データ構造のサーベイ論文を探していたら良さそうなのを見つけたのでメモ。 Data Structures for Efficient String Algorithms Johannes Fischer; 2007

LOUDSトライを比較した記事を書いたところ@overlast氏からwikipediaタイトルのような偏りの少ないデータでも評価してはどうか、という賢明なアドバイスを頂いたので試してみた。 LOUDSトライのライブラリの性能を比較してみた - EchizenBlog-Zwei

LOUDSは木構造を非常に小さなデータサイズで表現することができる簡潔データ構造の一種。とくに自然言語処理ではトライ木という木構造が重要で形態素解析や日本語入力(IME)など多くの場面で利用されている。 トライ木としてはdouble arrayが有名。LOUDSはdou…

今回は集合の簡潔構造について話をする。今回で簡潔構造の初歩的な話は一段落となるので、いままでの話をまとめつつ集合の簡潔構造とは？どういうことに使えるのか？という話をする。 集合の簡潔構造は大変重要で、ここを理解すれば簡潔構造の基礎はだいたい…