📂レンマ

ハミング距離

定義

自然数 $n \in \mathbb{N}$ に対して、長さが $n$ のコードポイント^{code point}の集合 $\left\{ 0, 1 \right\}^{n}$ から、次のように定義された距離関数 $H$ をハミング距離^{Hamming distance}という¹。

$$ H \left( \mathbf{x} , \mathbf{y} \right) = \operatorname{card} \left\{ k : x_{k} \ne y_{k} \right\} $$ ここでコードポイントは $\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$ と $\mathbf{y} = \left( y_{1} , \cdots , y_{n} \right)$ で表され、$\operatorname{card}$ は集合の濃度である。簡単に言うと、2つのコードポイントを座標ごとに比較した時に異なる座標の数である。

説明

ハミング距離は離散距離を除けば最もシンプルな距離関数として、ある意味で異常な距離で行われる比較演算を各座標にブロードキャストすると見ることができる。当然ながら、同じか異なるかだけで使用できるため、「差異」や「乖離」を比較する全ての分野で最初の候補として検討する価値がある。

一般化

2進数 $\left\{ 0, 1 \right\}$ ではなく、アルファベットのような有限集合に一般化できない理由は全くない。また、順序を正確に守ることができ、その順序で比較することができれば、行列やさらに進んでテンソルなど、様々なデータ型にも直接適用可能である。