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をつなげたもの。
- 二進符号: 普通の二進数
- γ符号: 二進表現の符号長を単身符号で表しそれに二進表現をつけたもの
- δ符号: γ符号の中で単身符号で長さを表している部分をもう一度γ符号で表現したもの
- ゴロム符号、ライス符号
- ハフマン符号