ここで花札といっているのは一組48枚で、12か月折々の花とかが4枚ずつに書き込まれているあれのことです。全ての札を区別して扱うとして、それぞれの札に0~47の番号を割り振ると、札の有無をuint64_tで表すことができます。『手札にi番目の札がある⇔i番目の…
FM-Indexのことが懐かしくなったので実装してみました。github.com高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)作者:岡野原 大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本 3種類のビットベクト…
ベイジアンにとってMCMCは非常に強力な手法です。例えば観測データを元にパラメータの事後分布を推定したいときに使えます。しかし、事後分布の形状によっては十分なサンプルサイズを得るまでに非常に大きな計算量を必要とする欠点があります。具体的には、…
文字列の全文検索を(Suffix Arrayを使って)実装する際に、「文字列の先頭から文字の中に文字がいくつあるか」を数えたいことがあります。文字列が自然言語の場合はウェーブレット行列というデータ構造を使うのが良いようです。ウェーブレット行列なら文字の…
waifu2xは不可逆圧縮されたり縮小されたりした画像を元に戻すためのツールです。deep learningの一種であるCNN(Convolutional Neural Network)が使われており、良い感じに復元されると評判です。原著論文はarXivにあるので自由に読むことができます。 [1501.…
画像を可逆圧縮する方法にはいくつかありますが、多くの場合は(1)ある画素の輝度値を周りの画素から予測する→(2)予測誤差を符号化する という2ステップから成り立っています。今回は、(1)にLOCO-I予測を使い、(2)にLZMAを使って実際に可逆圧縮を行ってみまし…
SOR法とは連立一次方程式を反復的に解く方法の一つです。SOR法はハイパーパラメータとして加速パラメータωというものを必要とします。教科書的にはωは予め定数として与えておくものらしいですが、今回は誤差が最小になるようなωを各ステップごとに求めながら…