「ハミンググラフとハミング距離」【幾何学の基礎シリーズ】グラフ理論編その10

本記事の内容
ちょっとだけイントロ
ハミング距離
ハミンググラフ
ハミンググラフの性質
ハミンググラフの例
皆様のコメントを下さい！
結

本記事の内容

本記事はハミンググラフとハミング距離について解説する記事です。

本記事を読むにあたり、距離関数とグラフについて知っている必要があるため、以下の記事も合わせてご覧ください。

↓グラフの記事

「グラフって何？〜クイズからイメージしよう〜(応用例も紹介！)」【幾何学の基礎シリーズ】グラフ理論編その1

...

↓距離関数の記事

「連結、グラフ距離、組み合わせグラフ、同型なグラフ」【幾何学の基礎シリーズ】グラフ理論編その3

...

ちょっとだけイントロ

ハミンググラフとハミング距離は情報理論に登場します。
今回はグラフ理論の応用例を紹介、解説する記事ということです。

我々はアルファベットや平仮名や漢字を適当な長さで組み合わせることで単語を作り、それを助詞(英語にはありませんが)や接続詞を使って単語をつなげて文章にし、意思疎通をします。

とはいえ、たとえ日本人だったとしても「すうがく」を「すうらく」と噛んでしまったり、文章を書いているときに「です。」を「だす。」のように書き間違えたり、タイプミスで「箸」を「橋」としたりすることがあります。
英語なら尚の事です。

この「単語と単語との距離」がハミング距離です。

ハミング距離

では、早速内容に入ります。

アルファベット、符号

ここでは、「アルファベット(文字)」と「文字列(符号)」というものを以下で定まるモノとします。

文字、文字列

$W$を有限集合とし、$V=W\times\cdots\times W$ ($n$個の直積)とする。$W$の要素を文字(letter)あるいはアルファベット(alphabet)という。$V$の要素は長さ$n$の文字列あるいは符号(code)と呼ぶ。

文字列の遠近

$V$の2つの要素
\begin{eqnarray}
\boldsymbol{a}&=&\left(a_1,\dots,a_n \right)\quad \left(a_i\in W \right),
\boldsymbol{b}&=&\left(b_1,\dots,b_n \right)\quad \left(b_i\in W \right)
\end{eqnarray}
に対して、
$$
d(\boldsymbol{a},\boldsymbol{b})=\left|\left\{i\in\{1,\dots,n\}\middle|\ a_i\neq b_i\right\}\right|
$$
とします。
要するに、長さが同じ文字列$\boldsymbol{a}$と$\boldsymbol{b}$が何文字異なるか、ということを表しているのが関数$d$です。

例えば、$n=12$として、$W$を英語のアルファベットとします。
つまり、
$$
W=\left\{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z\right\}
$$
として、
$$
V=W^{12}
$$
とします。
ここで、
\begin{eqnarray}
\boldsymbol{a}&=&\left(c,o,n,f,i,r,m,a,t,i,o,n \right),\\
\boldsymbol{b}&=&\left(c,o,n,f,o,r,m,a,t,i,o,n \right),\\
\boldsymbol{c}&=&\left(c,o,n,g,r,e,g,a,t,i,o,n \right),\\
\end{eqnarray}
とすると、
$$
d(\boldsymbol{a},\boldsymbol{b})=1,\quad d(\boldsymbol{a},\boldsymbol{c})=4
$$
です。

余談(confirmation, conformation, congregation)

ちなみに、confirmationは「確認」、conformationは「整合」あるいは「形態」、congregationは「集まり」です。

このことから、$d$は2つの文字列の「遠近」を測るのに適しているだろう、ということが分かります。

$d$は距離関数です。(ハミング距離)

先の$d$は距離関数です。
距離関数とは以下でした。

距離関数、距離空間

集合$V$において、次の性質を満たす$d:V\times V\to\mathbb{R}$を$V$上の距離関数(distance function, metric)という。

任意の$x,y,z\in V$に対して

$d(x,y)\geq0$であり、$d(x,y)=0\Leftrightarrow x=y$
$d(x,y)=d(y,x)$
$d(x,y)+d(y,z)\geq d(x,z)$(三角不等式)

である。

距離関数の与えられた集合を距離空間(metric space)という。

つまり、$d$を
$$
d(\boldsymbol{a},\boldsymbol{b})=\left|\left\{i\in\{1,\dots,n\}\middle|\ a_i\neq b_i\right\}\right|
$$
とするとき、以下の3つが成り立ちます。

$d(\boldsymbol{a},\boldsymbol{b})\geq0$であり、$d(\boldsymbol{a},\boldsymbol{b})=0\Leftrightarrow \boldsymbol{a}=\boldsymbol{b}$
$d$は集合の要素の個数なので、任意の$\boldsymbol{a},\boldsymbol{b}\in V$に対して$d(\boldsymbol{a},\boldsymbol{b})\geq0$です。
また、任意の$\boldsymbol{a},\boldsymbol{b}\in V$に対して、$\boldsymbol{a}=\boldsymbol{b}$であれば、$\boldsymbol{a}$と$\boldsymbol{b}$は同じ文字列ということですので、$d(\boldsymbol{a},\boldsymbol{b})=0$です。
逆に、$d(\boldsymbol{a},\boldsymbol{b})=0$であれば、文字列$\boldsymbol{a}$と文字列$\boldsymbol{b}$には異なる文字が存在しないので、$\boldsymbol{a}=\boldsymbol{b}$です。
$d(\boldsymbol{a},\boldsymbol{b})=d(\boldsymbol{b},\boldsymbol{a})$
文字列$\boldsymbol{a}$と文字列$\boldsymbol{b}$の異なる文字の個数と文字列$\boldsymbol{b}$と文字列$\boldsymbol{a}$の異なる文字の個数は一致しているため、$d(\boldsymbol{a},\boldsymbol{b})=d(\boldsymbol{b},\boldsymbol{a})$です。
$d(\boldsymbol{a},\boldsymbol{b})+d(\boldsymbol{b},\boldsymbol{c})\geq d(\boldsymbol{a},\boldsymbol{c})$(三角不等式)
任意の$V$の要素
\begin{eqnarray}
\boldsymbol{a}&=&\left( a_1,\dots,a_n\right),\\
\boldsymbol{b}&=&\left( b_1,\dots,b_n\right),\\
\boldsymbol{c}&=&\left( c_1,\dots,c_n\right)
\end{eqnarray}
に対して
\begin{eqnarray}
A=\left\{i\middle|\ a_i=b_i\right\},\quad B=\left\{j\middle|\ b_j=c_j\right\},\quad C=\left\{k\middle|\ c_k=a_k\right\}
\end{eqnarray}
とおくと、$A\cap B\subset C$が成り立ちます。
補集合を考えることにより、$A^c\cup B^c\supset C^c$(ただし、$A^c$は$\left\{1,\dots,n\right\}$における$A$の補集合を指します)。
$d$の定め方から、
\begin{eqnarray}
d(\boldsymbol{a},\boldsymbol{b})=\left|A^c\right|,\quad d(\boldsymbol{b},\boldsymbol{c})=\left|B^c\right|,\quad d(\boldsymbol{a},\boldsymbol{c})=\left|C^c\right|
\end{eqnarray}
だから、
\begin{eqnarray}
d(\boldsymbol{a},\mathbb{C})&=&\left|C^c\right|\\
&\leq&\left|A^c\cup B^c\right|\\
&\leq&\left|A^c\right|+\left|B^c\right|\\
&=&d(\boldsymbol{a},\boldsymbol{b})+d(\boldsymbol{b},\boldsymbol{c})
\end{eqnarray}

従って、$d$は距離関数です。
個の$d$をハミング距離といいます。

ハミング距離

長さ$n$の文字列$\boldsymbol{a},\boldsymbol{b}\in V$に対して、 $$ d(\boldsymbol{a},\boldsymbol{b})=\left|\left\{i\in\{1,\dots,n\}\middle|\ a_i\neq b_i\right\}\right| $$ とし、この距離$d$をハミング距離(Hamming distance)という。

ハミンググラフ

先程定めた文字列の集合$V=W^n$($W$は有限集合)を頂点の集合とするグラフ$X$を考えます。
辺の繋がり方については

$\boldsymbol{a},\boldsymbol{b}$が辺で結ばれる$\Longleftrightarrow\ d(\boldsymbol{a},\boldsymbol{b})=1$

で定めます。
つまり、2つの文字列$\boldsymbol{a},\boldsymbol{b}$が辺で結ばれるのは、文字列の中の1箇所だけが異なり、他では一致するときです。
この操作で出来るグラフ$X$をハミンググラフといいます。

ハミンググラフ

文字列の集合$V=W^n$($W$は有限集合)を頂点の集合とし、

$\boldsymbol{a},\boldsymbol{b}$が辺で結ばれる$\Longleftrightarrow\ d(\boldsymbol{a},\boldsymbol{b})=1$

とすることで得られるグラフをハミンググラフ(Hamming graph)という。

ハミンググラフの性質

ハミンググラフの性質について解説します。

命題1.

ハミンググラフは連結である。

命題1.の証明

$\boldsymbol{a},\boldsymbol{b}\in V$を任意の取って、$d(\boldsymbol{a},\boldsymbol{b})=s$とします。
このとき、次を満たす$V$の要素$\boldsymbol{c}_0,\boldsymbol{c}_1,\dots,\boldsymbol{c}_s$が存在することを示せばOKです。
\begin{eqnarray}
&&\boldsymbol{c}_0=\boldsymbol{a},\quad \boldsymbol{c}_s=\boldsymbol{b},\\
&&d(\boldsymbol{c}_{i-1},\boldsymbol{c}_i)=1\ (i=1,2,\dots,s)
\end{eqnarray}

$\boldsymbol{a}=(a_1,\dots,a_n)$と$\boldsymbol{b}=(b_1,\dots,b_n)$が異なる成分を持つ番号を$k_1<\cdots<k_s$とするとき、$\boldsymbol{c}_1$は$\boldsymbol{c}_0=\boldsymbol{a}$の$k_1$番目の成分を$\boldsymbol{b}$の対応する成分で置き換えたものとして、機能的に$\boldsymbol{c}_{i-1}$まで定まったときに、$\boldsymbol{c}_i$は$\boldsymbol{c}_{i-1}$の$k_i$番目の成分を$\boldsymbol{b}$の対応する成分で置き換えたものとします。

例えば、先程の例の
\begin{eqnarray}
\boldsymbol{a}&=&\left(c,o,n,f,i,r,m,a,t,i,o,n \right),\\
\boldsymbol{b}&=&\left(c,o,n,f,o,r,m,a,t,i,o,n \right)
\end{eqnarray}
のとき、
\begin{eqnarray}
\boldsymbol{c}_1&=&(c,o,n,g,i,r,m,a,t,i,o,n),\\
\boldsymbol{c}_1&=&(c,o,n,g,r,r,m,a,t,i,o,n),\\
\boldsymbol{c}_1&=&(c,o,n,g,r,e,m,a,t,i,o,n),\\
\boldsymbol{c}_1&=&(c,o,n,g,r,e,g,a,t,i,o,n)
\end{eqnarray}
です。

従って、連結です。

命題1.の証明終わり

以下、文字の数は$q$とします。
すなわち、$q=\left|W\right|$とします。

命題2.

ハミンググラフ$X=(V,E)$は正則グラフであり、その次数は$n(q-1)$である。

命題2.の証明

$\boldsymbol{a}=(a_1,\dots,a_n)\in V$に対して、$\boldsymbol{b}=(b_1,\dots,b_n)$で$d(\boldsymbol{a},\boldsymbol{b})=1$となるのは、文字列$\boldsymbol{b}$の1箇所のみが$\boldsymbol{a}$と異なるときです。
異なる場所を$i$番目とすると、$i$番目のところで$a_i$と異なる文字の個数は$\left|W\right|-1=q-1$です。
また、ことなる場所の数は$n$個なのだから、次数は$n(q-1)$となって、$X$は正則グラフです。

命題2.の証明終わり

ハミンググラフの例

情報理論で使われる文字の集合は$W=\left\{0,1\right\}$です。
この場合のハミンググラフは$n-$正則グラフです($n(q-1)=n(2-1)=n$)。

長さ$n$の文字列を$\mathbb{R}^m$の座標と考えることにより、$V$は$\mathbb{R}^n$の部分集合と同一視出来ます。

$n=1$のとき、$V=\left\{0,1\right\}$、
$n=2$のとき、$V=\left\{(0,0),(0,1),(1,0),(1,1)\right\}$、
$n=3$のとき、$V=\left\{(0,0,0),(1,0,0),(0,1,0),(0,0,1),(1,1,0),(1,0,1),(0,1,1),(1,1,1)\right\}$

次の図は$n=1,2,3$のハミンググラフです。

これらのグラフの頂点の集合は、それぞれ、線分$[0,1]$、正方形$\left\{(x,y)\middle|0\leq x,y\leq 1\right\}$、立方体$\left\{(x,y,z)\middle|0\leq x,y,z\leq 1\right\}$の頂点の集合に対応しています。

ちなみに、$n=4$の場合、４次元立方体$\left\{(x,y,z,w)\middle|0\leq x,y,z,w\leq 1\right\}$を図に描くことはできませんが、その頂点と辺からなるハミンググラフは以下のように描くことが出来ます。

皆様のコメントを下さい！

前回の記事で紹介したジョーク

数学ジョーク
ある人「もし死人(DEAD people)のみが16進数を理解できるなら、16進数を理解できるのは何人でしょうか？」
数学者「…人だね。」

の答えは

答え
数学者「57005人だね。」

です。
DEADを数の16進数表記だとして、DEADを10進数表記にすると57005だからです。

今回はクイズではなく、紹介だけにします。

数学ジョーク
この世の中には10種類の人間しかいない。2進数を理解する人間と理解しない人間だ。

このようなジョークをご存じの方はぜひコメントで教えて下さい！

結

今回は、ハミング距離とハミンググラフについて解説しました。
それぞれ情報理論で出現するものです。

ハミンググラフは正則行列であるとともに、実数の直積と同一視出来るため、4次元など図形として描けないものもハミンググラフとして表現することが出来ます。

次回は誤り訂正可能符号について解説します。

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければ全てお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ３日以内にお答えします。
もし直ちに回答が欲しければその旨もコメントでお知らせください。直ちに対応いたします。