bi-gram頻度からの論理配列評価

## 目的

キーボードの論理配列について、入力文書の各bi-gramの頻度と各打鍵パターンのコストから、その総打鍵コストを算出する。
ただし、ここでのコストとは、打鍵にかかる時間や指の移動量などを想定する。

## 定義
### 文字とキー

$n$種の文字を各々$c_i$とする。  
ただし、$0 \leqq i < n, i \in \mathbb{N}$とする。

```math
\{c_0, \cdots,c_{n-1}\} \\
```

同様にキーを各々$k_i$とする。

```math
\{k_0, \cdots, k_{n-1}\} \\
```

### 論理配列

文字$c_i$とキー$k_i$の対応が以下の例ように与えられたとする。  
($\circ$が対応する箇所, $\times$が対応しない箇所)

|           | $c_0$    | $c_1$    | $\cdots$ | $c_{n-1}$ |
| --------- | -------- | -------- | -------- | --------- |
| $k_0$     | $\times$ | $\circ$  | $\cdots$ | $\times$  |
| $k_1$     | $\circ$  | $\times$ | $\cdots$ | $\times$  |
| $\vdots$  | $\vdots$ | $\vdots$ |          | $\vdots$  |
| $k_{n-1}$ | $\times$ | $\times$ | $\cdots$ | $\circ$   |


これを論理配列$\boldsymbol{A}$とする。

```math
\begin{aligned}
    \boldsymbol{A} &= \begin{pmatrix}
        a_{0\ 0} &  \cdots & a_{0\ n-1} \\
        \vdots &         & \vdots \\
        a_{n-1\ 0} &  \cdots & a_{n-1\ n-1} \\
    \end{pmatrix} \qquad where \quad a_{ij} \in \{0, 1\} \\
    &\ni \begin{pmatrix}
        0 & 1 & \cdots & 0 \\
        1 & 0 & \cdots & 0 \\
        \vdots & \vdots && \vdots \\
        0 & 0 & \cdots & 1 \\
    \end{pmatrix} \qquad\cdots\ [例]\ 上記の表の場合
\end{aligned}
```

論理配列$\boldsymbol{A}$は置換行列である。

### bi-gramの出現頻度

各bi-gramの出現頻度が以下ように与えられたとする。

|          | $c_0$    | $\cdots$ | $c_{n-1}$    |
| -------- | -------- | -------- | -------- |
| $c_0$    | $b_{0\ 0}$ | $\cdots$ | $b_{0\ n-1}$ |
| $\vdots$ | $\vdots$ |          | $\vdots$ |
| $c_{n-1}$    | $b_{n-1\ 0}$ | $\cdots$ | $b_{n-1\ n-1}$ |

これをbi-gram頻度行列$\boldsymbol{B}$とする。

```math
\boldsymbol{B} = \begin{pmatrix}
    b_{0\ 0} & \cdots & b_{0\ n-1} \\
    \vdots &        & \vdots \\
    b_{n-1\ 0} & \cdots & b_{n-1\ n-1} \\
\end{pmatrix}
```

### 打鍵パターンのコスト

各キーの打鍵パターンにかかるコストが以下のように与えられたとする。  

|          | $k_0$    | $\cdots$ | $k_{n-1}$    |
| -------- | -------- | -------- | -------- |
| $k_0$    | $t_{0\ 0}$ | $\cdots$ | $t_{0\ n-1}$ |
| $\vdots$ | $\vdots$ |          | $\vdots$ |
| $k_{n-1}$    | $t_{n-1\ 0}$ | $\cdots$ | $t_{n-1\ n-1}$ |

これを打鍵コスト行列 $\boldsymbol{T}$ とする。

```math
\boldsymbol{T} = \begin{pmatrix}
    t_{0\ 0} & \cdots & t_{0\ n-1} \\
    \vdots &        & \vdots \\
    t_{n-1\ 0} & \cdots & t_{n-1\ n-1} \\
\end{pmatrix}
```

## モデル化
### 打鍵パターンの頻度

論理配列$\boldsymbol{A}$とbi-gram頻度行列$\boldsymbol{B}$から、キー打鍵のパターン頻度行列$\boldsymbol{P}$が以下で求まる。

```math
\boldsymbol{P} = \boldsymbol{A}\boldsymbol{B}\boldsymbol{A}^T \qquad \cdots 式(1) \\
```

#### [例]

論理配列$\boldsymbol{A}$とbi-gram頻度行列$\boldsymbol{B}$を以下と仮定する。

```math
\boldsymbol{A} = \begin{pmatrix}
    0 & 0 & 1 \\
    1 & 0 & 0 \\
    0 & 1 & 0 \\
\end{pmatrix},\qquad
\boldsymbol{B} = \begin{pmatrix}
    b_{00} & b_{01} & b_{02} \\
    b_{10} & b_{11} & b_{12} \\
    b_{20} & b_{21} & b_{22} \\
\end{pmatrix}\\
```

この時のパターン頻度行列$\boldsymbol{P}$は以下となる。

```math
\begin{aligned}
    \boldsymbol{P} &= \boldsymbol{A}\boldsymbol{B}\boldsymbol{A}^T \qquad \cdots 式(1) 再掲 \\
    &= \begin{pmatrix}
        0 & 0 & 1 \\
        1 & 0 & 0 \\
        0 & 1 & 0 \\
    \end{pmatrix}\begin{pmatrix}
        b_{00} & b_{01} & b_{02} \\
        b_{10} & b_{11} & b_{12} \\
        b_{20} & b_{21} & b_{22} \\
    \end{pmatrix}\begin{pmatrix}
        0 & 0 & 1 \\
        1 & 0 & 0 \\
        0 & 1 & 0 \\
    \end{pmatrix}^T \\
    &= \begin{pmatrix}
        b_{20} & b_{21} & b_{22} \\
        b_{00} & b_{01} & b_{02} \\
        b_{10} & b_{11} & b_{12} \\
    \end{pmatrix}\begin{pmatrix}
        0 & 1 & 0 \\
        0 & 0 & 1 \\
        1 & 0 & 0 \\
    \end{pmatrix} \\
    &= \begin{pmatrix}
        b_{22} & b_{20} & b_{21} \\
        b_{02} & b_{00} & b_{01} \\
        b_{12} & b_{10} & b_{11} \\
    \end{pmatrix}
\end{aligned}
```

以下の手順でも求めてみる。

|       | $c_0$    | $c_1$    | $c_2$    |
| ----- | -------- | -------- | -------- |
| $c_0$ | $b_{00}$ | $b_{01}$ | $b_{02}$ |
| $c_1$ | $b_{10}$ | $b_{11}$ | $b_{12}$ |
| $c_2$ | $b_{20}$ | $b_{21}$ | $b_{22}$ |

$\boldsymbol{M}$に従い$c_i$を$k_i$置換

|       | $k_1$    | $k_2$    | $k_0$    |
| ----- | -------- | -------- | -------- |
| $k_1$ | $b_{00}$ | $b_{01}$ | $b_{02}$ |
| $k_2$ | $b_{10}$ | $b_{11}$ | $b_{12}$ |
| $k_0$ | $b_{20}$ | $b_{21}$ | $b_{22}$ |

並び替え

|       | $k_0$    | $k_1$    | $k_2$    |
| ----- | -------- | -------- | -------- |
| $k_0$ | $b_{22}$ | $b_{20}$ | $b_{21}$ |
| $k_1$ | $b_{02}$ | $b_{00}$ | $b_{01}$ |
| $k_2$ | $b_{12}$ | $b_{10}$ | $b_{11}$ |

```math
\therefore \quad \boldsymbol{P} = \begin{pmatrix}
    b_{22} & b_{20} & b_{21} \\
    b_{02} & b_{00} & b_{01} \\
    b_{12} & b_{10} & b_{11} \\
\end{pmatrix}
```

式(1)で求めた結果と一致する。

### 総打鍵コスト

論理配列$\boldsymbol{A}$の総打鍵コスト$E$を以下の数式でモデル化できる。

```math
\begin{aligned}
    E &= \boldsymbol{T} \cdot \boldsymbol{P} \\
    &= \boldsymbol{T} \cdot (\boldsymbol{A}\boldsymbol{B}\boldsymbol{A}^T) \\
    &= \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} t_{ij}(\boldsymbol{A}\boldsymbol{B}\boldsymbol{A}^T)_{ij}\\
    &= \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} t_{ij} \lbrace \sum_{k=0}^{n-1} (\boldsymbol{A}\boldsymbol{B})_{ik}(\boldsymbol{A}^T)_{kj}  \rbrace \\
    &= \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} t_{ij} \lbrace \sum_{k=0}^{n-1} a_{jk} (\sum_{l=0}^{n-1} a_{il}b_{lk}) \rbrace \qquad // \\
\end{aligned} 
```

## TODO: 

* [ ] 式(1)の証明