こんにちは、キャベツです。
検索の高速化をする際に組み合わせを数字に変換したくなったので、まとめます。
似たような条件での検索を高速化したい
例えば、こんなテーブルを考える(縦H行, 横W列)
| sex | bloodtype | birthplace | x |
|---|---|---|---|
| M | A | Hokkaido | 1 |
| M | B | Hokkaido | 1.2 |
| M | A | Aomori | 1.5 |
| ... | ... | ... | ... |
| F | A | Hokkaido | 1.1 |
| ... | ... | ... | ... |
| F | AB | Okinawa | 1.4 |
これに対して、$Q$個のクエリが与えられる。
$i$番目のクエリ$q_i$では、生物学的性別$S_i$、血液型$BL_i$、出身$BP_i$が与えられる。
与えられた条件に対応した$x$を出力したい。
愚直に毎回検索をかけると、1クエリにつきテーブルの列数分計算が必要なため、かなり遅い($O(QHW)$)。
そのため、クエリの条件を数字に変換して、愚直な検索を行わないようにする。
やることは3つ
- 条件→数字の対応式を作る。
- テーブルの条件に番号をふり、ソートする。
- クエリを処理する。
条件→数字の対応式を作る。
今回の条件では、sexが2種類、blood typeが4種類、birthplaceが47種類存在するため
都合$2\times4\times47 = 376$行存在する。
まず、それぞれのカテゴリを数値に変換する。
| sex | number |
|---|---|
| M | 0 |
| F | 1 |
| bloodtype | number |
|---|---|
| A | 0 |
| B | 1 |
| O | 2 |
| AB | 3 |
| birthplace | number |
|---|---|
| Aichi | 0 |
| Akita | 1 |
| ... | ... |
| Yamanashi | 46 |
次に、条件の組を数字に変換する。
ここがポイント。
一旦2進数$\rightarrow $10進数に思いを馳せる。
例えば、$1001_{(2)}$は、10進数で$9$である。
これを表にすると、
| 桁数 | number | かける数 | 10進数 |
|---|---|---|---|
| $1$ | $1$ | $1$ | $1\times 2^0$ |
| $2$ | $0$ | $2^1$ | $0\times 2^1$ |
| $3$ | $0$ | $2^2$ | $0\times 2^2$ |
| $4$ | $1$ | $2^3$ | $1\times 2^3$ |
ここで、かける数が2に増えていくことに着目してほしい。
一方で、今回の条件の組を同じようにまとめると、
| カテゴリ | 条件 | number | かける数 | 10進数 |
|---|---|---|---|---|
| sex | F | $1$ | $1$ | $1\times 1$ |
| bloodtype | B | $1$ | 2 | $1\times 2$ |
| birthplace | Akita | $1$ | $2\times 4$ | $1\times 2\times 4$ |
となり、(F, B, Akita) $=(1\times 1) + (1\times 2) + (1\times 2\times 4) =11$と変換される。
重要なのはかける数の変遷であり、
直前のカテゴリ数だけ倍増していくことだけ覚えてほしい。
すなわち、
sexのカテゴリ数は2、bloodtypeのカテゴリ数は4、birthplaceのカテゴリ数は47。
なので、
sexの桁にかける数は$1$
bloodtypeの桁にかける数は$2$(sexのカテゴリ数)
birthplaceの桁にかける数は$2\times 4$(sexのカテゴリ数$\times$bloodtypeのカテゴリ数)
となる。
テーブルの条件に番号をふり、ソートする
全通り番号をふる。
| ID | sex | bloodtype | birthplace | x |
|---|---|---|---|---|
| 0 | M | A | Aichi | 1 |
| 1 | F | A | Aichi | 1.1 |
| ... | ... | ... | ... | ... |
| 375 | F | AB | Yamanashi | 1.4 |
こうすれば、条件から検索抜きで位置を指定できる。
あとはクエリを数字に変換して、その行のxを出力すればよい
k-merを数字に変換する
k-mer とは、長さ$k$の塩基配列のことである。
ここまで読んだら、k-merを数字に変換することなどいとも容易いだろう。
説明のため、$6$-merである、を例にする。
まずは、数字に対応付ける。
| Base | number |
|---|---|
| A | 0 |
| T | 1 |
| C | 2 |
| G | 3 |
変換する（例えば、ATCGAT）
| Base | number | かける数 | 10進数 |
|---|---|---|---|
| A | $0$ | $1$ | $0\times 1$ |
| T | $1$ | $4$ | $1\times 4$ |
| C | $2$ | $4^2$ | $2\times 4^2$ |
| G | $3$ | $4^3$ | $3\times 4^3$ |
| A | $0$ | $4^4$ | $0\times 4^4$ |
| T | $1$ | $4^5$ | $1\times 4^5$ |
よって、ATCGAT $= 1252$。
次回は、この逆
数字を組み合わせに変換する
を書きます。