登場人物紹介
僕:数学が好きな高校生。
テトラちゃん:僕の後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。
ミルカさん:数学が好きな高校生。 僕のクラスメート。長い黒髪の《饒舌才媛》。
僕とテトラちゃんとミルカさんの三人は、 放課後の図書室で数学トークを続けている。
いまは、 四つの条件を一つ一つ確かめて、 テトラちゃんが距離空間の定義を終えたところだ(第419回参照)。
僕「……これで距離空間が定義できたんだね、テトラ先生!」
距離空間 $(S,d)$ の定義(まとめ)
$S$ を集合とします。
$d$ を $S\times S$ から実数全体の集合 $\REAL$ への関数とします。
以下の(1)〜(4)が成り立つとき、 $S$ と $d$ の組 $(S,d)$ を距離空間といい、関数 $d$ を距離関数といいます。 また、 $d(x,y)$ を $x$ と $y$ の距離といいます。
(1)集合 $S$ に属している任意の要素 $x,y$ に対して、 $$ d(x,y) \GEQ 0 $$ です。
(2)集合 $S$ に属している任意の要素 $x,y$ に対して、 $$ d(x,y) = 0 \quad\Longleftrightarrow\quad x = y $$ です。
(3)集合 $S$ に属している任意の要素 $x,y$ に対して、 $$ d(x,y) = d(y,x) $$ です。
(4)集合 $S$ に属している任意の要素 $x,y,y$ に対して、 $$ d(x,y) + d(y,z) \GEQ d(x,z) $$ です。
テトラ「はい……ここであたしの疑問をスタックから$\textrm{POP}$させてください」
僕「ああ、そうだったね。条件(2)?」
テトラ「そうです。あたし、この条件(2)がどうも納得いかないんです……」
距離空間 $(S,d)$ の定義(2)
関数 $d$ は、集合 $S$ に属している任意の要素 $x,y$ に対して、 $$ d(x,y) = 0 \quad\Longleftrightarrow\quad x = y $$ が成り立つものとします(第419回参照)。
僕「たとえば、イメージ図にすればこういうことだよね」
ミルカ「テトラは『納得いかない』を言語化する」
ミルカさんは淡々と言葉を放つ。
彼女の一言で、僕たちの頭は急回転を始める。
テトラ「はい……あのですね。 $S$ に属している二つの点 $x,y$ が等しいとき、つまり $x = y$ のときに距離が $0$ というのは、 特に疑問に思いません。 だって、一つの点なんですから。それはいいんです。 でも……その逆が引っかかるんです」
僕「逆は『$d(x,y) = 0$ ならば $x = y$』だね?」
ミルカ「いまはテトラが説明中」
僕「おっと、ごめん」
テトラ「はい。 $d(x,y) = 0$ のとき——この《お気持ち》は $x$ と $y$ の距離が $0$ ということですが——そのとき、 $x$ と $y$ が等しいというところが引っかかります」
ミルカ「その理由」
テトラ「引っかかる理由は、 二点 $x,y$ の距離が $0$ であっても $x \NEQ y$ で構わないのではないかしらん……と思うからです」
ミルカ「さらにその理由」
テトラ「さらにその理由……は、はい。 あたしは、距離空間を考えるとき、空中を飛び回るボールのようなものをイメージしていました。 $S$ の要素を《空中を飛び回っているボール》のように考えて、 $d(x,y)$ を《二つのボール $x$ と $y$ の距離》のように考えて、 それで、 $d(x,y) = 0$ ならば、その二つのボールが衝突するイメージで考えました」
僕「なるほど」
ミルカ「ふうん……」
テトラ「でも、二つのボールが衝突したとしても、 二つのボールは違うボールです。 違うボールが、たまたま同じ位置にあるだけです。 それなのに $d(x,y) = 0$ のとき $x = y$ としていいものかどうか……そこが引っかかっていたんです」
ミルカ「君が答える」
ミルカさんは僕を指さした。
僕「距離空間は四つの条件で規定されていて、 その条件の一つに『$d(x,y) = 0$ は $x = y$ と同値』がある。 関数 $d$ はその条件を満たすときに距離関数になるとしたんだから、 そこで引っかかるのは不適切じゃないのかな……違う? つまり $(S,d)$ を距離空間と呼ぶならば、 $x,y$ が $S$ の要素で、 $d(x,y) = 0$ のとき $x = y$ にならざるを得ないよね」
テトラ「……」
ミルカ「君の答えは正しいが、テトラの疑問解決にはなっていない」
僕「うーん……そうなのかな」
ミルカ「テトラは、 $d(x,y) = 0$ のとき $x = y$ になることそのものに疑問を抱いているのではない。 テトラは、自分のイメージしている距離というものとの解釈のズレに疑問を抱いているのだ」
テトラ「……はい。ミルカさんがおっしゃる通りです。解釈のズレ、 まさにそうです。 日常生活に対応付けること自体がまちがっているのかもしれませんけれど……」
ミルカ「テトラは $S$ の要素を動き回るボールに見立てた。その見立て——すなわち解釈——にズレがある。 空中を飛び回るボールを考えたいのなら、 $S$ の要素はボールではなく空中の位置を表すと考えた方がいいだろうな」
テトラ「位置……?」
ミルカ「そう」
ミルカさんの言葉に、テトラちゃんは視線を上げて空中をぐるっと見回した。
テトラ「ははあ……理解しました。 $S$ の要素をボールだと考えるのではなく、ボールの位置だと考える。 二つのボールの距離が $0$ になるというのは、 二つのボールが同じ位置に来るということになって、 $x = y$ です。 ボールは違うけれど、ボールの位置が同じ。 なるほど!」
僕「なるほどね。解釈ってそういうことか」
ミルカ「時間に応じて移動する特定のボールを考えるときには、 時刻 $t$ から $S$ の要素——つまり位置——を得る関数を考えればいい。 ボール $A$ の運動は $a(t)$ で表し、ボール $B$ の運動は $b(t)$ で表し、 $a(t)$ と $b(t)$ はどちらも $S$ の要素とすると、 $a(t) = b(t)$ が成り立つ $t$ は、二つのボール $A,B$ が衝突する時刻ということになる」
テトラ「確かに!」
僕「その場合の $S$ は三次元空間 $\REAL^3$ ということになるね」
ミルカ「そう考えてもいいけれど、そう考えなければならない理由はない。 たとえば $S$ を座標平面の格子点全体の集合と考えることも可能だ。 せっかく距離空間として抽象化したのだから、自由に考えられるということを意識した方が楽しい」
僕「そうか! 《格子点の世界》で移動する《ボール》 を考えてもいいわけだね! そうすれば《ボールの衝突》という概念も別世界に移すことができる!」
ミルカ「そういうこと」
テトラ「なるほどです……」
ミルカ「せっかく距離空間が定義できたのだから、 日常生活では《距離》と思えない距離を考えることにしよう」
テトラ「?」
ミルカ「たとえば、ビットパターン間の距離。ハミング距離を考えよう」
テトラ「ハミング距離……何だか歌が出てきそうです」
ミルカ「鼻歌のハミング(humming)ではない。数学者のハミング(Hamming)に由来する距離だ」
テトラ「ああ、ハミングさんなのですね」
ミルカ「一般の文字列で定義できるが、簡単のために $7$ ビットからなるビットパターンで説明する。 $7$ ビットからなるビットパターン全体の集合を $S$ とする。 そして $S$ の二つの要素 $x,y$ ——つまり二つのビットパターン $x,y$ を比べて《異なるビットの個数》を $d(x,y)$ とする。 すると、 $(S,d)$ は距離空間の条件を満たす」
僕「たとえば、 $0000111$ と $0010110$ の距離は $2$ ということ?」
テトラ「えっえっ?」
僕「こんなふうにビットパターンを比較するという意味だよね? 《異なるビットの個数》が $2$ 個だから」
$0000111$ と $0010110$ のハミング距離は $2$
$$ \begin{array}{ccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ \hline & &\uparrow & & & & \uparrow \end{array} $$
$2$ 箇所異なっているので、 《異なるビットの個数》は $2$ となり、 $0000111$ と $0010110$ のハミング距離は $2$ となります。
$$ d(0000111,0010110) = 2 $$
テトラ「意味はわかりましたが……確かにこれはあまり《距離》という感じはしませんね」
僕「でも、距離空間の四つの条件は満たすよね」
僕たちは、 ハミング距離が距離空間の定義を満たすことを確認した。
ハミング距離が距離空間の定義を満たすことの確認($7$ ビットの例)
$7$ ビットパターン全体の集合を $S$ とします。 $$ S = \SET{00000000,0000001,0000010,\ldots,1111111} $$ $x,y$ を $S$ の要素としたとき、 $S\times S$ から $\REAL$ への関数 $d$ を $$ d(x,y) = \text{《$x$と$y$で異なるビットの個数》} $$ で定義すると、 $(S,d)$ は距離空間になります。
(1)集合 $S$ に属している任意の要素 $x,y$ に対して、 $$ d(x,y) \GEQ 0 $$ です。なぜなら、 $d(x,y)$ の値は《$x$ と $y$ で異なるビットの個数》なので、 $0,1,2,3,4,5,6,7$ のいずれかだからです。
(2)集合 $S$ に属している任意の要素 $x,y$ に対して、 $$ d(x,y) = 0 \quad\Longleftrightarrow\quad x = y $$ です。なぜなら、 $d(x,y) = 0$ とは《$x$ と $y$ で異なるビットの個数》が $0$ 個ということなので、 $x = y$ に他ならないからです。
(3)集合 $S$ に属している任意の要素 $x,y$ に対して、 $$ d(x,y) = d(y,x) $$ です。なぜなら、 《$x$ と $y$ で異なるビットの個数》は《$y$ と $x$ で異なるビットの個数》に等しいからです。
(4)集合 $S$ に属している任意の要素 $x,y,y$ に対して、 $$ d(x,y) + d(y,z) \GEQ d(x,z) $$ です。なぜなら……(これは読者の演習問題とします)
テトラ「確かに、ハミング距離は距離空間の条件を満たしますが……でも、 So what?(だから、何?)という感じがします」
ミルカ「そう?」
僕「いや、でも、実際的な意味を持たないこういうものも、 定義の理解には大事なんじゃないのかな」
ミルカ「ハミング距離は実際的な応用もある」
僕「そうなんだ」
ミルカ「ちょうどいいところに」
ちょうどいいところに、とミルカさんが指さした先を見ると、 赤い髪をしたリサが図書室の入り口に立っていた。
今日も真っ赤なコンピュータを持っている。
ミルカさんは手を挙げて彼女を呼ぶ。
リサ「話題?」
ミルカ「ハミング距離の応用」
リサ「ハミング符号」
ミルカ「$7$ ビットで」
リサ「データ $4$ ビットに、パリティ $3$ ビット(咳)」
ミルカ「エラーコレクション」
リサ「$1$ ビット」
ミルカさんとリサが早口で短いやりとりをした後、 リサはコンピュータを開いて僕たちにハミング符号の解説文を見せてくれた。
リサ「概要」
$(7,4)$ ハミング符号
$(7,4)$ ハミング符号とは、 $7$ ビットのうち $4$ ビットをデータに用い、 残りの $3$ ビットをパリティとして用いる誤り訂正符号である。
$7$ ビットを用いて $4$ ビットのデータを相手に伝える際に、 ビット反転するエラーが起きたとしても、 $1$ ビットまでなら訂正することができる。
テトラ「通信エラーを訂正できる……間違っても正しくもとに戻せるということでしょうか?」
僕「そうみたいだね」
無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。
ひと月500円で「読み放題プラン」へご参加いただきますと、 435本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。
参加済みの方/すぐに参加したい方はこちら
結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加(2024年3月15日)