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

本記事の内容

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

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

↓グラフの記事

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

...

for-spring.com

2022.09.20

↓距離関数の記事

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

...

for-spring.com

2022.09.21

ちょっとだけイントロ

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

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

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

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

ハミング距離

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

アルファベット、符号

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

上のように\(V\)を定めているので、\(\left|V\right|=\left|W\right|^n\)です。
現実に即した形で述べれば、\(W\)が英語のアルファベットの集合だとすると\(\left|W\right|=25\)です(現実のアルファベットは25個なので)。
しかし、今回はそれは仮定せずに、\(W\)は単に有限集合とします(\(W\)は日本語の平仮名の集合でも良いし、ギリシャ語のアルファベットでも良いし、ロシア語のアルファベットでも良いからです)。

文字列の遠近

\(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\)は距離関数です。
距離関数とは以下でした。

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

1. \(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}\)です。
2. \(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})\)です。
3. \(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\)をハミング距離といいます。

ハミンググラフ

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

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

ハミンググラフの性質

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

命題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.の証明

\(\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を数の16進数表記だとして、DEADを10進数表記にすると57005だからです。

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

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

結

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

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

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

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