バイト・データのハミング距離を算出するため、データのビットが 1 の数を数えたい。

int(123) = (0b00000001) ---> 1 個 // ハミング距離 = 1
int(123) = (0b10000000) ---> 1 個 // ハミング距離 = 1
int(240) = (0b11110000) ---> 4 個 // ハミング距離 = 4
int(255) = (0b11111111) ---> 8 個 // ハミング距離 = 8

TL; DR _{^{（今北産業）}}

math/bits パッケージの OnesCount 系の関数で取得できる。
型ごとに関数が用意されている。

使い方：

import "math/bits"

func Example() {
	for _, data := range []uint{
		0b10000000,
		0b11110000,
		0b11111111,
	} {
		fmt.Printf(
			"0b%08b=0d%03d --> OnesCount(%d) = %d\n",
			data, data, data, bits.OnesCount(data),
		)
	}
	// Output:
	// 0b10000000=0d128 --> OnesCount(128) = 1
	// 0b11110000=0d240 --> OnesCount(240) = 4
	// 0b11111111=0d255 --> OnesCount(255) = 8
}

オンラインで動作を見る @ GoPlayground

TS; DR _{^{（用途を kwsk）}}

他言語から Golang に引っ越してきて、一番「良いな」と思ったところはバイトやバイナリ・データが鬼のように扱いやすいことです（他にも良いところがたくさんあるのですが）。

フラグのカウント

やはり、一番の王道はビットによるフラグ管理でしょう。フラグが何本立っているかをカウントすることで、何かを判断する場合です。

例えばゲームで n 個のアイテムがあった場合、n ビットのデータを用意します。そして、各ビットを各アイテムと見立て、アイテムを取得したらフラグを立てます。つまり、アイテム 1 を取得したら、1 ビット目を 1 にするみたいな処理です。

uint64 の場合、1 つで最大 64 アイテムまで管理できることになります。これを複数セット用意して総和（合計）を出せば 64 アイテム以上も扱えます。

func Example() {
	data := []uint64{
		0b1111011111001111111111000111111111110111111110011111110111001101, // 51 個
		0b1111111111111111111111111111111111111111111111111111111111111111, // 64 個
	}

	total := 0
	for _, val64 := range data {
		total += bits.OnesCount64(val64)
	}

	fmt.Println("アイテム取得数:", total)
	// Output: アイテム取得数: 115
}

オンラインで動作を見る @ GoPlayground

「そんなん DB や配列で管理すればいいじゃん」と思うなかれ。ビットを使った考え方は後々、色々と役に立ってきます（ました）。

ちなみに Golang の場合、32bit OS でも uint64 は扱えます。OS の 32/64 bit に注意しなければいけないのは int や uint の方です。

データの類似度

「Golang を、ふいんきで触っている」という文字入力に対して、「もしかして、『ふんいき』？」といった、単語辞書にはないものの、近い単語が見つかった場合にオススメしたい場合があります。

「ふんいき」と「ふいんき」以外にも、「備忘録」と「忘備録」や、length と lenght といった typo 的な指摘です。

このような場合、よく使われるのが「レーベンシュタイン距離」と「ハミング距離」です。

どちらも、2 つのデータの「違いの度合いを表す数値」の 1 種です。

値が大きい（距離が離れる）ほど異なるデータになり、値が 0（距離がゼロ）の場合は同じデータということになります。そのため、逆に言えば「データの類似度」を知りたい場合にも使えるということです。

レーベンシュタイン距離

「レーベンシュタイン距離」は、片方のデータを 1 つずつ入れ替えて、もう片方と同じになるまでの回数を距離とします。ハノイの塔的なイメージが近いでしょう。

例えば、neko と nuko を比較した場合、neko の e を u に入れ替えると nuko となり、1 回の置き換えで済むため、レーベンシュタイン距離は 1 となります。

ハミング距離

対して「ハミング距離」は、2 つのデータ差（違いの数）を距離としたものです。

例えば、neko と nuko を比較した場合、neko の e と nuko の u の 2 文字目の 1 箇所が違うので、ハミング距離は 1 となります。

そう。耳慣れない用語で小難しく聞こえますが、「レーベンシュタイン距離」と「ハミング距離」は親戚のようなものです。

主な違いは、レーベンシュタイン距離の場合は、データの長さが異なっても距離が出せ、ハミング距離は、同じ長さのデータでないと距離が出せないことです。

ハミング氏の、排他おじさんったら排他おじさん

この記事は、筆者が Golang で「ハミング距離」を算出したくて探した結果の備忘録であるため、もう少しハミング距離を掘り下げたいと思います。

先の neko と nuko の違いですが、バイトデータ（のビット並び）の場合でも例えると、色々と応用が見えてきます。

例えば、11110001 と 10110000 を比較した場合は、7 桁目と 1 桁目（11110001 と 10110000）の 2 箇所が異なるため、ハミング距離は 2 となります。

では、この 2 をどうやってプログラムで（外部ライブラリを使わず）算出するかと言うと、幸いなことにコンピューター（バイナリの世界）では、2 つの値を xor することで異なる箇所だけ抜き出せます。そうです、排他的論理和です。

     0b11110001
xor  0b10110000
----------------
     0b01000001 ---> Dist: 2

上記は以下と同文です。

func Example() {
	p1 := uint(0b11110001)
	p2 := uint(0b10110000)

	diff := p1 ^ p2 // xor p1 and p2

	fmt.Printf("%08b xor %08b = %08b\n", p1, p2, diff)
	fmt.Printf("Dist: %d\n", bits.OnesCount(diff))
	// Output:
	// 11110001 xor 10110000 = 01000001
	// Dist: 2
}

オンラインで動作を見る @ GoPlayground

画像の類似度

先述しましたが、ハミング距離のデメリットは、同じデータサイズでないといけないことです。しかし、同じサイズに出来るなら高速に距離が算出できるということでもあります。

ハミング距離の面白い使い方として、画像の類似度の算出があります。つまり、2 つの画像が類似しているかを数値にできるのです（厳密には、比較可能なデータの、差分測定にハミング距離を使っています）。

画像やドキュメントの類似性を測定する方法は色々あります。

ここでは画像の類似性を数値化する pHash（知覚ハッシュ）と呼ばれるハッシュ関数のアルゴリズムで、どのようにハミング距離が使われているか簡単な概要を説明します。より具体的な情報へのリンクは以下の Qiita 記事を参照してください。

暗号学的ではないアルゴリズム（破損と類似の検知）| hashアルゴリズムとハッシュ値の長さ一覧（＋ハッシュ関数の基本と応用）より @ Qiita

さて、画像の場合は、縮小しても元画像と類似していることが感覚的に（目視で）確認できます。また、カラー画像をモノクロ（グレースケール）に変換しても、元画像と類似していることが感覚的に確認できます。

ということは、異なるサイズの画像であっても、モノクロ変換して、同じサイズに縮小 or 拡大することで、比較可能な同じデータサイズに出来るということです。

しかし感覚的に類似していると「人間が」認識できても、ピクセル毎のデータ値（グレースケールの 0 〜 255 の値）は異なるため、単純なハミング距離では算出できません。全体の濃度が異なるかもしれないからです。

そこで、各々の画像の濃度の最小値を 0、最大値を 1 として、各ピクセルを uint8 から float 値に置き換えます。これにより、絶対的な濃度が、相対的な濃度に変換されることになります。

次に、並んだピクセルの変化量（変化の差）を測定します。

よほどランダムなノイズでない限り、画像の場合、一般的に隣あうデータはスムーズに変化していきます。スムーズな変化があるということは、波がある（「〜」のような波）ということです。そして、波があるということは、周波数を持っているということでもあります。

一見、綺麗な波（「〜」のようなサイン波）に見えなくても、実は複数の周波数の波を合成したものだったりします。逆に言うと、複数の周波数の波を合成すると、任意の波を作れるということでもあります。音の場合、ピアノやトランペットといった音色が作れるということで、これがいわゆるシンセサイザーというヤツです。

この理屈を画像にも当てはめます。

つまり、ピクセルの変化を測定していき、その複雑な変化を「シンプルな変化の組み合わせ」に分解していくのです。

このように、データの複雑な変化も、複数の単純な変化の組み合わせにできるということは、パターン化できるということです。そして、パターン化できるということは、データを小さくすることができます。

これを画像圧縮に活用したものが JPEG で、動画圧縮の場合は MPEG です。

ちなみに「データの複雑な変化を、複数の単純な変化に分解する」もしくは、その逆である「複数の単純な変化を合成して、任意の複雑な変化にする」ことを「フーリエ変換」「逆フーリエ変換」と言います。

余談ですが、「複雑な波を、単純な波に分解する」ことを「波の成分分析」とも言います。例えば、地震などの揺れが、揺れの成分を解析することで、核実験による揺れなのか／地殻の岩盤が割れたことによる揺れなのか／火山による揺れなのか、といった判断にも使われます。

さて、話しを戻すと、ここまでで、画像のピクセルの変化をパターン化できました（理論的に）。そして、そのパターンを固定長の配列にマッピングするのです。つまり、左上のピクセルの変化パターンは x、その隣の変化パターンは y ... と配列データに並べていきます。

そして、最後に 2 つの画像を比べるときに、ハミング距離を使い「パターンが違う箇所の数」を測定して、値が小さいほど類似している（似たパターンのブロックが多い）ということで判断します。

最後に

わかってる風に偉そうに説明しましたが、筆者がハミング距離を使いたかったのは、なんてことない「ループ処理を抜ける際の判断として」でした。

つまり、すべての条件のフラグが立ったらループを抜けるという処理です。Golang の sync.WaitGroup にインデックスを付けたような処理です。

問題は、具体的な条件数（フラグ数）が実行時まで不定なことと、単純なカウントアップ（done++）ではループ内で、どのフラグが立っているかの判断を配列（map）で行うにはいささか煩雑だったからです。

とは言え、素直に配列を使った方が実装は早かった気がします。実行速度を早めることに先走ってしまいました。未来の自分への戒めとして記事に残します。あっちょんぶりけ。