ハミング距離
同じ長さをもつ2つの文字列のハミング距離とは、対応する位置にある文字を比較したとき、異なっている位置の数を表す。
言い換えれば、ハミング距離は、一方の文字列を他方の文字列へ変換するために必要な文字の置換回数の最小値を表す尺度である。
長さ \( n \) の2つの文字列 \( s \) と \( t \) に対し、ハミング距離 \( D_H(s, t) \) は次のように定義される。
$$ D_H(s, t) = \sum_{i=1}^{n} \delta(s_i, t_i) $$
ここで、\( s_i \) と \( t_i \) は、それぞれ文字列 \( s \) および \( t \) の \( i \) 番目の文字を表す。また、\( \delta(s_i, t_i) \) は、\( s_i \neq t_i \) の場合に 1、それ以外の場合に 0 を返す関数である。
なお、ハミング距離は長さが等しい文字列同士に対してのみ定義される。
具体例
次の2つの文字列を考えてみよう。
$$ s = \text{"karbon"} $$
$$ t = \text{"carbon"} $$
この場合、\( s \) と \( t \) のハミング距離は 1 である。異なっているのは先頭の文字（k と c）だけであり、それ以外の文字はすべて一致しているためである。
例2
次は、ハミング距離が 2 となる英単語の例である。
$$ s = \text{"thing"} $$
$$ t = \text{"thank"} $$
この2つの単語は2か所で異なっている。
具体的には、3文字目は「thing」の「i」と「thank」の「a」、5文字目は「thing」の「g」と「thank」の「k」である。
ハミング距離に基づく距離位相
ハミング距離は、同じ長さをもつ任意の文字列 \( x \)、\( y \)、\( z \) に対して、次の3つの性質を満たす。そのため、ハミング距離は距離空間を定める。
- 非負性
$$ D_H(x, y) \geq 0 \quad \text{and} \quad D_H(x, y) = 0 \ \text{if and only if} \ x = y $$
ハミング距離は文字列間の相違箇所を数えるため、値が負になることはない。また、2つの文字列が完全に一致するとき、かつその場合に限り、距離は 0 となる。 - 対称性
$$ D_H(x, y) = D_H(y, x) $$
対応する位置の違いだけを数えるため、\( x \) から \( y \) への距離と \( y \) から \( x \) への距離は常に等しい。 - 三角不等式
$$ D_H(x, z) \leq D_H(x, y) + D_H(y, z) $$
任意の3つの文字列 \( x \)、\( y \)、\( z \) に対し、直接の距離 \( D_H(x, z) \) は、途中で \( y \) を経由した距離の和を超えることはない。これは、\( x \) と \( z \) の相違箇所は、少なくとも \( x \) と \( y \)、または \( y \) と \( z \) のどちらかに必ず現れるためである。
これらの性質を満たすことから、ハミング距離は一定の長さをもつすべての文字列の集合上に距離空間を定義する。
距離空間では、距離によって定まる「近さ」の概念を基に位相を導入できる。
したがって、ハミング距離は距離位相を定義することもできる。
長さ \( n \) の文字列 \( x \) と半径 \( r \) に対して、中心を \( x \) とする開球（近傍） \( B \) は、\( x \) からのハミング距離が \( r \) 未満であるすべての文字列からなる集合として定義される。
$$ B(x, r) = \{y \mid D_H(x, y) < r\}. $$
このような開球の集合は距離位相の基底を構成する。距離位相における開集合は、これらの開球の任意の和集合として表すことができるからである。
注．長さ \( n \) のすべての2進文字列（あるいは一般の記号列）の集合は有限集合である。そのため、この集合上でハミング距離から誘導される位相は離散位相となる。つまり、それぞれの文字列は、それ自体で開集合であると同時に閉集合でもある。これは、十分に小さい半径（たとえば \( r = 1 \)）を選ぶことで、各文字列だけを含む開球を作ることができるためである。
したがって、同じ長さをもつ有限個の文字列からなる集合では、ハミング距離が誘導する距離位相は離散位相となる。
例
長さ3の2進文字列からなる次の集合を考える。
$$ X = \{000, 001, 011, 110, 111 \} $$
半径 \( r = 2 \) の場合、各文字列を中心とする開球を調べることで、ハミング距離から誘導される位相を構成できる。
$$ B(x, r) = \{y \mid D_H(x, y) < 2 \} $$
つまり、それぞれの開球には、中心となる文字列と高々1か所だけ異なる文字列が含まれる。
- \( 000 \) を中心とする開球：$$ B(000, 2) = \{000, 001\} $$ 中心は \( 000 \) であり、\( 001 \) だけが1か所異なる。
- \( 001 \) を中心とする開球：$$ B(001, 2) = \{001, 000, 011 \} $$ 中心は \( 001 \) であり、\( 000 \) と \( 011 \) がそれぞれ1か所だけ異なる。
- \( 011 \) を中心とする開球：$$ B(011, 2) = \{011, 001, 111\} $$ 中心は \( 011 \) であり、\( 001 \) と \( 111 \) がそれぞれ1か所だけ異なる。
- \( 110 \) を中心とする開球：$$ B(110, 2) = \{110, 111\} $$ 中心は \( 110 \) であり、\( 111 \) だけが1か所異なる。
- \( 111 \) を中心とする開球：$$ B(111, 2) = \{111, 011, 110\} $$ 中心は \( 111 \) であり、\( 011 \) と \( 110 \) がそれぞれ1か所だけ異なる。
これらの開球は、半径 \( r = 2 \) に対する誘導位相の基底を構成する。これらを自由に和集合として組み合わせることで、この位相のあらゆる開集合を作ることができる。
注．半径 \( r = 2 \) の開球では境界点を含まないため、条件は「2以下」ではなく「2未満」となる。したがって、含まれるのはハミング距離が 0 または 1 の文字列だけである。すなわち、$$ B(x, r) = \{ y \mid D_H(x, y) < 2 \} $$ となる。一方、閉球を定義する場合には「2以下」の条件を用い、$$ C(x, r) = \{ y \mid D_H(x, y) \le 2 \} $$ と表される。
たとえば、集合 \( B(000, 2) \) と \( B(110, 2) \) の和集合を考える。
$$ B(000, 2) \cup B(110, 2) $$
\( B(000, 2)=\{000,001\} \)、\( B(110,2)=\{110,111\} \) であるから、その和集合は次のようになる。
$$ B(000, 2) \cup B(110, 2) = \{000,001\} \cup \{110, 111 \} $$
$$ B(000, 2) \cup B(110, 2) = \{000, 001, 110, 111\} $$
したがって、この位相では、集合 \( \{000,001,110,111\} \) も開集合となる。
以上より、半径 \( r = 2 \) のハミング距離から誘導される距離位相では、すべての開集合が半径2の開球の和集合として表される。
以下も同様である。
