Jarak Hamming

Jarak Hamming adalah ukuran yang digunakan untuk menghitung berapa banyak posisi karakter yang berbeda antara dua string yang memiliki panjang sama.

Secara intuitif, jarak Hamming menunjukkan jumlah minimum perubahan karakter yang diperlukan untuk mengubah satu string menjadi string lainnya.

Jika diberikan dua string \( s \) dan \( t \) dengan panjang \( n \), maka jarak Hamming \( D_H(s,t) \) didefinisikan sebagai:

$$ D_H(s, t) = \sum_{i=1}^{n} \delta(s_i, t_i) $$

Di sini, \( s_i \) dan \( t_i \) adalah karakter pada posisi ke-\( i \) dalam string \( s \) dan \( t \). Fungsi \( \delta(s_i,t_i) \) bernilai 1 jika kedua karakter berbeda, dan 0 jika keduanya sama.

Karena perbandingan dilakukan posisi demi posisi, jarak Hamming hanya dapat diterapkan pada string yang memiliki panjang yang sama.

Contoh Praktis

Misalkan kita membandingkan dua string berikut:

$$ s = \text{"karbon"} $$

$$ t = \text{"carbon"} $$

Kedua string tersebut hanya berbeda pada karakter pertama, yaitu k dan c. Oleh karena itu:

$$ D_H(s,t) = 1 $$

Contoh 2

Sekarang perhatikan dua kata bahasa Inggris berikut:

$$ s = \text{"thing"} $$

$$ t = \text{"thank"} $$

Kedua kata tersebut berbeda pada dua posisi:

• Huruf ketiga: i pada thing dan a pada thank.
• Huruf kelima: g pada thing dan k pada thank.

Karena terdapat dua perbedaan posisi, maka:

$$ D_H(s,t) = 2 $$

Topologi Metrik Berdasarkan Jarak Hamming

Jarak Hamming tidak hanya digunakan dalam teori informasi dan ilmu komputer. Jarak ini juga dapat digunakan untuk membangun sebuah ruang metrik.

Suatu fungsi jarak dapat disebut metrik jika memenuhi tiga sifat dasar berikut.

1. Ketaknegatifan

   $$ D_H(x, y) \geq 0 \quad \text{dan} \quad D_H(x, y)=0 \text{ jika dan hanya jika } x=y $$

   Karena jarak Hamming menghitung jumlah perbedaan, nilainya tidak mungkin negatif. Nilai 0 hanya terjadi jika kedua string identik.

2. Simetri

   $$ D_H(x, y)=D_H(y,x) $$

   Jumlah perbedaan antara \( x \) dan \( y \) akan selalu sama dengan jumlah perbedaan antara \( y \) dan \( x \).

3. Ketaksamaan Segitiga

   $$ D_H(x,z) \leq D_H(x,y)+D_H(y,z) $$

   Untuk tiga string apa pun, jarak langsung dari \( x \) ke \( z \) tidak dapat melebihi jumlah jarak yang ditempuh melalui string perantara \( y \).

Karena memenuhi ketiga sifat tersebut, jarak Hamming mendefinisikan sebuah ruang metrik pada himpunan string-string dengan panjang tertentu.

Setelah memiliki ruang metrik, kita dapat membangun sebuah topologi metrik berdasarkan konsep kedekatan yang ditentukan oleh jarak tersebut.

Untuk setiap string \( x \) dan radius \( r \), didefinisikan sebuah bola terbuka (open ball) sebagai:

$$ B(x,r)=\{y \mid D_H(x,y)

Artinya, himpunan tersebut berisi semua string yang jaraknya terhadap \( x \) lebih kecil daripada \( r \).

Bola-bola terbuka inilah yang menjadi dasar pembentukan himpunan-himpunan terbuka dalam topologi metrik.

Catatan. Jika himpunan yang digunakan terdiri atas semua string biner atau string simbol dengan panjang tetap \( n \), maka himpunan tersebut bersifat hingga. Dalam situasi ini, topologi yang diinduksi oleh jarak Hamming adalah topologi diskret. Setiap string menjadi himpunan terbuka sekaligus himpunan tertutup karena kita dapat memilih radius yang sangat kecil, misalnya \( r=1 \), sehingga setiap bola terbuka hanya memuat satu string.

Dengan demikian, pada himpunan hingga yang terdiri atas string-string dengan panjang sama, jarak Hamming menghasilkan topologi diskret.

Contoh

Pertimbangkan himpunan string biner berikut:

$$ X = \{000,001,011,110,111\} $$

Kita akan membangun topologi yang diinduksi oleh jarak Hamming dengan radius \( r=2 \).

$$ B(x,r)=\{y \mid D_H(x,y)<2\} $$

Karena syaratnya adalah jarak harus kurang dari 2, maka setiap bola terbuka memuat string-string yang berbeda dari pusatnya pada paling banyak satu posisi.

• Bola terbuka berpusat di \( 000 \) $$ B(000,2)=\{000,001\} $$ Hanya \( 001 \) yang berbeda satu posisi dari \( 000 \).
• Bola terbuka berpusat di \( 001 \) $$ B(001,2)=\{001,000,011\} $$ String \( 000 \) dan \( 011 \) masing-masing berbeda satu posisi dari \( 001 \).
• Bola terbuka berpusat di \( 011 \) $$ B(011,2)=\{011,001,111\} $$ String \( 001 \) dan \( 111 \) berbeda satu posisi dari \( 011 \).
• Bola terbuka berpusat di \( 110 \) $$ B(110,2)=\{110,111\} $$ Hanya \( 111 \) yang berbeda satu posisi dari \( 110 \).
• Bola terbuka berpusat di \( 111 \) $$ B(111,2)=\{111,011,110\} $$ String \( 011 \) dan \( 110 \) berbeda satu posisi dari \( 111 \).

Bola-bola terbuka tersebut membentuk basis topologi yang diinduksi oleh jarak Hamming untuk radius \( r=2 \). Dari basis ini, kita dapat membangun himpunan-himpunan terbuka lain melalui operasi gabungan.

Catatan. Radius \( r=2 \) tidak berarti string dapat berbeda hingga dua posisi. Karena yang digunakan adalah bola terbuka, syaratnya adalah \( D_H(x,y)<2 \). Dengan kata lain, string hanya boleh berbeda pada nol atau satu posisi. Jika ingin menyertakan titik batas, maka digunakan bola tertutup: $$ C(x,r)=\{y \mid D_H(x,y)\leq 2\} $$

Sebagai contoh, gabungan antara \( B(000,2) \) dan \( B(110,2) \) adalah:

$$ B(000,2)\cup B(110,2) $$

Karena:

$$ B(000,2)=\{000,001\} $$

dan

$$ B(110,2)=\{110,111\} $$

maka diperoleh:

$$ B(000,2)\cup B(110,2)=\{000,001\}\cup\{110,111\} $$

$$ B(000,2)\cup B(110,2)=\{000,001,110,111\} $$

Jadi, himpunan \( \{000,001,110,111\} \) juga merupakan himpunan terbuka dalam topologi ini.

Singkatnya, jarak Hamming tidak hanya berfungsi sebagai ukuran perbedaan antara string, tetapi juga dapat digunakan untuk membangun sebuah topologi metrik. Dalam contoh ini, setiap himpunan terbuka diperoleh sebagai gabungan dari bola-bola terbuka yang ditentukan oleh jarak Hamming.

Dan seterusnya.