hiromarkのブックマーク - はてなブックマーク

Compressed Suffix Arrayの解説(1) -Suffix Array- - EchizenBlog-Zwei
< ---- < | > Compressed Suffix Arrayの解説(2) -SAの計算量- > ================================================ 最近(でもないか)話題のCompressed Suffix Array(CSA)について解説してみる。 CSAとはSuffix Array(SA)のインデックスを圧縮して小さくしたもの。大規模テキストデータに対する検索インデックスを作る場合など少しでもインデックスを小さくしたい場合に使われる。 CSAを知るにはSAから！ということで今回はSAの解説を。 Suffix Array(SA)とはデータ構造の一種で事前に(サイズがNの)テキストに対してインデックスを作っておくことでキーとなる文字列を入力として与えるとテキストに含まれるキーの位置をO(logN)で探索できる、というもの。たとえば
hiromark 2010/02/24
CSA の説明をがーっと読みたいときに。

compression

algorithm

suffixarray
リンク
Compressed Suffix Arrayの解説(4) -unary記法- - EchizenBlog-Zwei
< Compressed Suffix Arrayの解説(3) -圧縮の方針- < | > Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- > ================================================ まずは下準備。数値列をunary記法でbit列に変換する方法を説明。 unary(ユナリィ)記法というのは数値の数だけの0を並べて、最後に1を置くというもの。具体例を挙げると数値 unary 0 1 1 01 2 001 3 0001 4 00001 5 000001となる。 unary記法では1が数値間の境界を表すために各数値毎のbitサイズを固定長にする必要がない。例えば数値列 1 1 2 2 1 2は各数値をそれぞれ1byteで表したとすると全体で48bit(6byte)必要になる。一方で
hiromark 2010/02/24
compression

ir

algorithm
リンク
Naive Bayesの罠 - EchizenBlog-Zwei
< Naive Bayesの実装 < | > ---- > ================================================ Naive Bayes(NB,ナイーブベイズ)には気になる事があるよ、という話。前回、文書{バナナ,カレー}が「甘い」クラスと「辛い」クラスそれぞれに属する確率(対数尤度)をナイーブベイズ分類器で求めた。その結果、文書{バナナ,カレー}は「辛い」クラスに属することがわかった。しかしバナナもカレーも「甘い」クラスに入っているのに「辛い」クラスのほうが対数尤度が大きいというのはちょっと直感に反するかもしれない。以下ではこの点について考察する。前回求めた対数尤度の計算式は以下の通り。 lnP(甘い|{バナナ,カレー}) = lnP(カレー|甘い) + lnP(バナナ|甘い) + lnP(甘い) = 0.69 + 0.69 - (2 -
hiromark 2010/02/18
あとで読む。

algorithm
リンク
前のページ 1 2