2013-01-09 ウェーブレット木の世界

  • 講演メモ

計算量がデータサイズに対して線形より大きかったら
並列化はほとんど意味がない。
n^3 なら 10000台並べても 10倍にしかならない
→
1. ちゃんとしたアルゴリズム、データ構造、分析手法を使う。
2. それから分散並列化


完備辞書は n+O(n) bit をもちいて rank,select を O(1)時間で実現出来る。

ウェーブレット木
全部入りの根から、代償に応じて二分木に分ける。
そのとき、０、１を右左に対応させて各ノードにラベルを付ける。


ウェーブレット木の高さは log Σ でいいのかな？

「値方向と添え字方向でソートされているデータ構造だ。」
「機械学習、近傍探索さえよければ何でも解けちゃいますね。」

実数値データは、順位空間へ変換する。
異なりがないようにする。
二次元データは、x を固定して、yの値の列とする。
→ 三次元は苦手(方法は存在するけどきれいじゃない)

グラフへの利用
頂点リストをすべてつなげて文字列を作る。
各頂点リストがどこから始まっているかは完備辞書で記録。

ウェーブレット行列 (去年の夏くらいに出た)
ウェーブレット木の問題点は、値の範囲が大きいときにサイズが大きくなってしまう。

1bit目が0であるものを左に、1であるものを右に。
2bit目が0であるものを左に、1であるものを右に。(高速フーリエ変換のシャッフルに似ている)
ウェーブレット木と同じ接点があるが位置は交差している。

完備辞書 rsdic 秒間100万クエリ可能。
fmindex++
グラフの類似検索 gwt

データが加わった場合どうなるか？
ウェーブレット木の場合、末尾に追加された場合は簡単。
現実的に完備辞書の動的更新も可能になってきている。ただ遅くなる。

バイオの方ではBWTはアライメントの標準ツールになっている。

google 日本語入力は簡潔データ構造を作っている。
LOUS

「ディスクに置かなければならない場合は、できるだけアクセスしない方がいいので、
分岐数を増やして深さを減らしてアクセスを減らせばできると思う。」

NII定兼先生がこの分野の研究をしている。東工大田部井さん、産総研津田さん。

2012-12-31 高速文字列解析の世界 1，2章

p.4 「演算速度は速くなる一方で記憶装置へのアクセス速度は一定のまま」

0次 H_0(T) = - Sigma_{c \in Σ} n_c / n * log ( n_c / n )
n次 H_k(T) = - Sigma_{W \in Σ^k} n_w / n * H_0(T_w)
T は文字列、
Σは文字集合、
T_w は T 中に出現する部分文字列Wの直前に出現する1文字をすべてつなげて構成された文字列

  • 計算モデル

- Cell Probe モデル:
メモリ参照のみにコストがかかると仮定
- Transdichotomous RAM モデル:
モデルのパラメータが log n として問題サイズに応じて計算モデルが変化する。
- Word RAM モデル
上＋データに対する任意の操作もコストとしてカウントする

  • 符号

- 接頭辞符号: 瞬時に復号可能な符号の一つ。ある文字列の符号が他の文字列の接頭辞になっていないこと。
- 単進符号: 整数xは x-1個の0の後に1をつなげたもの。
- 二進符号: 普通の二進数
- γ符号: 二進表現の符号長を単身符号で表しそれに二進表現をつけたもの
- δ符号: γ符号の中で単身符号で長さを表している部分をもう一度γ符号で表現したもの
- ゴロム符号、ライス符号
- ハフマン符号

2012-12-27 I/O バッファリングについて

buffering in standard streams
http://www.pixelbeat.org/programming/stdio_buffering/

why IO::Pty and Expect modules can help to solute open2 's block?
http://stackoverflow.com/questions/12705460/why-iopty-and-expect-modules-can-help-to-solute-open2-s-block

2012-12-13 「eXtreme Programmingテスト技法」 3，4，6章

pp.47-81( Chap3,4 ), pp.114-131( Chap6 )

テストすべき項目
1. コントラクトテスト = 外部に公開されているインターフェースのテスト
2. 入力値範囲テスト
3. path テスト = if 分岐による実行パスのテスト
4. 外部状態テスト = ファイルがあるか、読み込み可かなど。
5. 例外テスト

HttpUnit とは
JUnit を利用したテストツールで、ブラウザをエミュレートして Web にアクセスしてテストする。

リンク、テーブル、フォームなどについてしかできないようだ。
Google Map 表示や JQuesy のグラフィック表示についてはどうテストしたらいいか？