Hamming mesafesi - Hamming distance

çekiç mesafesi

Hamming mesafesini bulmak için 4 bitlik ikili tesseract . İki örnek mesafe: 0100→1001 , mesafe 3'e sahiptir; 0110→1110 mesafe 1'e sahip
Sınıf	dize benzerliği
Veri yapısı	sicim
En kötü durum performansı	${\görüntüleme stili O(n)}$
En iyi durum performansı	${\görüntüleme stili O(1)}$
Ortalama performans	${\görüntüleme stili O(n)}$
En kötü durum alanı karmaşıklığı	${\görüntüleme stili O(n)}$

Hamming mesafesini bulmak için 3 bitlik ikili küp

İki örnek mesafe: 100→011 , mesafe 3'e sahiptir; 010→111 mesafesi 2'ye sahip

Herhangi iki köşe arasındaki minimum mesafe, iki ikili dizi arasındaki Hamming mesafesidir.

Olarak bilgi teorisi , Hamming mesafesi iki arasında dizeleri eşit uzunlukta gelen pozisyonların sayısı semboller farklıdır. Başka bir deyişle, bir diziyi diğerine dönüştürmek için gereken minimum ikame sayısını veya bir diziyi diğerine dönüştürebilecek minimum hata sayısını ölçer . Daha genel bir bağlamda, Hamming mesafesi, iki dizi arasındaki düzenleme mesafesini ölçmek için çeşitli dizi ölçümlerinden biridir . Adını Amerikalı matematikçi Richard Hamming'den almıştır .

Önemli bir uygulama, kodlama teorisinde , daha özel olarak , eşit uzunluktaki dizilerin sonlu bir alan üzerinde vektörler olduğu blok kodlarıdır .

Tanım

Eşit uzunluktaki iki sembol dizisi arasındaki Hamming mesafesi, karşılık gelen sembollerin farklı olduğu konumların sayısıdır.

Örnekler

Semboller, diğer olasılıkların yanı sıra harfler, bitler veya ondalık rakamlar olabilir. Örneğin, aşağıdakiler arasındaki Hamming mesafesi:

• " ka rol in " ve " ka thr in " 3'tür.
• " K bir r ol içinde " ve " k e r st içinde " 3'tür.
• " K ATHR içinde " ve " k erst de " 4'tür.
• 0000 ve 1111 4'tür.
• 2 17 3 8 96 ve 2 23 3 7 96 , 3'tür.

Özellikler

Sabit bir uzunluk n için , Hamming mesafesi, n uzunluğundaki kelimelerin ( Hamming uzayı olarak da bilinir) kümesindeki bir metriktir , çünkü negatif olmama, simetri koşullarını yerine getirir, iki kelimenin Hamming mesafesi 0'dır. ve eğer iki kelime aynıdır ve tatmin sadece üçgen eşitsizliği de: üç kelime düzeltmek Gerçekten de, bir , B ve c , o zaman bir fark arasındadır her i inci yazmak bir ve i 'ya işaret ve c , daha sonra arasında bir fark olması gerekir i inci harf , bir ve i inci harf b arasında veya i inci harfi b ve i inci harfi c . Dolayısıyla a ve c arasındaki Hamming uzaklığı, a ve b ile b ve c arasındaki Hamming uzaklıklarının toplamından daha büyük değildir . İki kelime arasında Hamming uzaklığı bir ve b aynı zamanda şu şekilde görülebilir Hamming ağırlığı arasında bir - b iki tamsayı arasındaki fark numarası hattında sıfırdan bir mesafede olarak görülebilir kadar, operatör - uygun bir seçimi için.

a ve b ikili dizeleri için Hamming mesafesi, bir XOR b'deki birlerin sayısına ( popülasyon sayısı ) eşittir . Uzunluk- n ikili dizilerin metrik uzayı , Hamming mesafesi ile Hamming küpü olarak bilinir ; bir hiperküp grafiğindeki köşeler arasındaki mesafeler kümesine bir metrik uzay olarak eşdeğerdir . Ayrıca , dizideki her bir sembolü gerçek bir koordinat olarak ele alarak, n uzunluğundaki ikili bir diziyi bir vektör olarak görüntüleyebilirsiniz; bu yerleştirmeyle, diziler n boyutlu bir hiperküpün köşelerini oluşturur ve dizilerin Hamming mesafesi köşeler arasındaki Manhattan mesafesine eşittir . ${\displaystyle \mathbb {R} ^{n}}$

Hata algılama ve hata düzeltme

En az Hamming uzaklığı bazı temel kavramları tanımlamak için kullanılır kodlama teorisi gibi hata tespit ve hata düzeltme kodları . Özellikle, bir C kodunun , yalnızca ve ancak, kod sözcüklerinden herhangi ikisi arasındaki minimum Hamming mesafesinin en az k +1 olması durumunda, k hata algılaması olduğu söylenir .

Örneğin, "000" ve "111" kod sözcüklerinden oluşan kodu ele alalım. Bu iki kelime arasındaki hamming mesafesi 3'tür ve bu nedenle k =2 hata algılamadır. Bu, eğer bir bit çevrilirse veya iki bit çevrilirse, hatanın tespit edilebileceği anlamına gelir. Üç bit çevrilirse, "000" "111" olur ve hata algılanamaz.

Temeldeki Hamming uzayı H içindeki her w sözcüğü için , w ve c arasındaki Hamming mesafesi en fazla k olacak şekilde ( C'den ) en fazla bir c kod sözcüğü varsa, bir C kodunun k-hatalarını düzelttiği söylenir . Başka bir deyişle, bir kod, yalnızca ve ancak, herhangi iki kod sözcüğü arasındaki minimum Hamming mesafesi en az 2 k +1 ise, k -hatalarını düzeltir . Herhangi biri gibi bu daha kolay geometrik anlaşılmaktadır kapalı toplar yarıçapı k ayrı kod sözcükleri olan ayrık üzerine odaklandı. Bu toplara bu bağlamda Hamming küreleri de denir .

Örneğin, "000" ve "111" kod sözcüklerinden oluşan aynı 3 bitlik kodu düşünün. Hamming uzayı 8 kelime 000, 001, 010, 011, 100, 101, 110 ve 111'den oluşur. "000" kod kelimesi ve "001","010","100" tek bitlik hata kelimelerinin tümü veya daha küçüktür. 1 ila "000" arasındaki Hamming mesafesine eşittir. Benzer şekilde, "111" kod sözcüğü ve onun tek bitlik hata sözcükleri "110", "101" ve "011", orijinal "111"in 1 Hamming mesafesi içindedir. Bu kodda, tek bitlik bir hata her zaman orijinal kodların 1 Hamming mesafesi içindedir ve kod 1-hata düzeltme , yani k=1 olabilir . "000" ve "111" arasındaki minimum Hamming mesafesi 3'tür, bu da 2k+1 = 3'ü sağlar .

Böylece, kod sözcükleri arasında minimum Hamming mesafesi d olan bir kod, en fazla d -1 hata tespit edebilir ve ⌊ ( d -1)/2⌋ hatalarını düzeltebilir. İkinci sayı ayrıca paketleme yarıçapı veya kodun hata düzeltme yeteneği olarak da adlandırılır .

Tarih ve uygulamalar

Hamming mesafesi adını , 1950'de Hamming kodları , Hata bulma ve hata düzeltme kodları hakkındaki temel makalesinde tanıtan Richard Hamming'den almıştır . Bitlerin Hamming ağırlık analizi, bilgi teorisi , kodlama teorisi ve kriptografi dahil olmak üzere çeşitli disiplinlerde kullanılmaktadır. .

Telekomünikasyonda , sabit uzunluktaki bir ikili sözcükteki çevrilmiş bitlerin sayısını bir hata tahmini olarak saymak için kullanılır ve bu nedenle bazen sinyal mesafesi olarak adlandırılır . İçin q, aşırı -ary dizeleri alfabe boyutu q  2 ≥ Hamming uzaklığı halinde uygulanır q-li simetrik kanalı ise, Lee, mesafe için kullanılan faz kayması anahtarlama daha genel olarak kanal hassas veya eşzamanlama hata Lee nedeniyle mesafe, ±1'lik hataları hesaba katar. Herhangi bir öğe çifti 1'den veya 1'den farklı olduğu için veya her iki mesafe çakışıyorsa , ancak daha büyük için mesafeler farklıdır . ${\görüntüleme stili q=2}$${\görüntüleme stili q=3}$${\textstyle \mathbb {Z} /2\mathbb {Z} }$${\textstyle \mathbb {Z} /3\mathbb {Z} }$${\görüntüleme stili q}$

Hamming mesafesi, sistematikte genetik mesafenin bir ölçüsü olarak da kullanılır .

Bununla birlikte, farklı uzunluktaki dizileri veya sadece ikamelerin değil, aynı zamanda eklemelerin veya silmelerin de beklendiği dizileri karşılaştırmak için, Levenshtein mesafesi gibi daha karmaşık bir metrik daha uygundur.

algoritma örneği

Python 3'te yazılan aşağıdaki işlev, iki dize arasındaki Hamming mesafesini döndürür:

def hamming_distance(string1, string2):
	dist_counter = 0
	for n in range(len(string1)):
		if string1[n] != string2[n]:
			dist_counter += 1
	return dist_counter

Veya daha kısa bir ifadeyle:

sum(xi != yi for xi, yi in zip(x, y))

Python 2.3+ sürümündehamming_distance() uygulanan işlev , iki girdideki karşılık gelen konumlar arasındaki uyumsuzlukları ve eşleşmeleri gösteren bir Boole değerleri dizisi oluşturarak ve ardından diziyi False ile toplayarak eşit uzunluktaki iki dize (veya diğer yinelenebilir nesneler) arasındaki Hamming mesafesini hesaplar. ve True değerlerinin sıfır ve bir olarak yorumlanması.

def hamming_distance(s1, s2) -> int:
    """Return the Hamming distance between equal-length sequences."""
    if len(s1) != len(s2):
        raise ValueError("Undefined for sequences of unequal length.")
    return sum(el1 != el2 for el1, el2 in zip(s1, s2))

burada fermuar () işlevi, çiftler halinde, iki eşit uzunlukta koleksiyonları birleştirir.

Aşağıdaki C işlevi, iki tamsayının Hamming mesafesini hesaplayacaktır (ikili değerler olarak, yani bit dizileri olarak kabul edilir). Bu prosedürün çalışma süresi, girişlerdeki bit sayısından ziyade Hamming mesafesi ile orantılıdır. Bit düzeyinde dışlamayı veya iki girdiyi hesaplar ve ardından en düşük sıralı sıfır olmayan biti tekrar tekrar bulan ve temizleyen Wegner'in (1960) bir algoritmasını kullanarak sonucun Hamming ağırlığını (sıfır olmayan bitlerin sayısı ) bulur. Bazı derleyiciler, mümkün olduğunda özel işlemci donanımını kullanarak bunu hesaplayabilen __builtin_popcount işlevini destekler .

int hamming_distance(unsigned x, unsigned y)
{
    int dist = 0;

    // The ^ operators sets to 1 only the bits that are different
    for (unsigned val = x ^ y; val > 0; ++dist)
    {
        // We then count the bit set to 1 using the Peter Wegner way
        val = val & (val - 1); // Set to zero val's lowest-order 1
    }

    // Return the number of differing bits
    return dist;
}

Daha hızlı bir alternatif, nüfus sayımı ( popcount ) derleme talimatını kullanmaktır. GCC ve Clang gibi belirli derleyiciler, onu içsel bir işlev aracılığıyla kullanılabilir hale getirir:

// Hamming distance for 32-bit integers
int hamming_distance32(unsigned int x, unsigned int y)
{
    return __builtin_popcount(x ^ y);
}

// Hamming distance for 64-bit integers
int hamming_distance64(unsigned long long x, unsigned long long y)
{
    return __builtin_popcountll(x ^ y);
}

Ayrıca bakınız

• En yakın dize
• Damerau-Levenshtein mesafesi
• Öklid mesafesi
• Gap-Hamming sorunu
• gri kod
• jakar indeksi
• Levenştein mesafesi
• Mahalanobis mesafesi
• Mannheim mesafesi
• Sørensen benzerlik indeksi
• Seyrek dağıtılmış bellek
• kelime merdiveni

Referanslar

daha fazla okuma

•  Bu makale , Genel Hizmetler İdaresi belgesindeki kamuya açık materyalleri içermektedir  : "Federal Standart 1037C" .
• Wegner, Peter (1960). "İkili bir bilgisayarda olanları saymak için bir teknik". ACM'nin İletişimi . 3 (5): 322. doi : 10.1145/367236.367286 . S2CID  31683715 .
• MacKay, David JC (2003). Bilgi Teorisi, Çıkarım ve Öğrenme Algoritmaları . Cambridge: Cambridge Üniversitesi Yayınları . ISBN'si 0-521-64298-1.