Bilişim dünyasına kaliteli, özgün ve Türkçe içerikler kazandırmayı hedefleyen bir platform..

Denetimli veya denetimsiz birçok algoritma, mesafe ölçümlerinden yararlanır. Öklid mesafesi veya kosinüs benzerliği gibi bu ölçümler, k-NN, UMAP, HDBSCAN vb. algoritmalarda sıklıkla bulunur.

Doğal dil işleme (NLP) ve metin analizinde, iki dizenin ne kadar farklı olduğunu nicel olarak belirlememiz sıklıkla gerekir. Bu farkları ölçebilmek için 2(iki) klasik düzenleme mesafesi ölçütü Hamming mesafesi ve Levenshtein mesafesidir. Eşit uzunluktaki iki dize arasındaki Hamming mesafesi, karşılık gelen sembollerin farklı olduğu pozisyon sayısıdır. Buna karşılık, Levenshtein mesafesi (bir düzenleme mesafesi biçimi), bir dizeyi diğerine dönüştürmek için gereken minimum tek karakterlik düzenleme sayısıdır – eklemeler, silmeler veya değiştirmeler.

Hamming Mesafesi

Hamming mesafesini hesaplamak için basit bir fonksiyon verebiliriz. Eğer dizelerin uzunlukları eşit değilse hata verir. Ardından "mahmut" ve "mehmet" arasındaki mesafeyi hesaplıyoruz ve sonuç 2 çıkıyor.

def hamming_distance(s1, s2):
    if len(s1) != len(s2):
        raise ValueError("Hamming distance eşit uzunlukta ifade ister")
    # Count positions with differing characters
    return sum (ch1!=ch2 for ch1, ch2 in zip (s1, s2))

# Example usage:
print (hamming_distance("mahmut", "mehmet")) # Output: 2

Levenshtein Distance

Levenshtein mesafesi (genellikle sadece düzenleme mesafesi olarak adlandırılır), karakter ekleme, silme veya değiştirme işlemlerine izin vererek Hamming yöntemini genelleştirir. Bir dizeyi başka bir dizeye dönüştürmek için gereken minimum tek karakterlik düzenleme sayısını bulur. Ekleme/silme işlemlerini dikkate aldığı için Levenshtein mesafesi farklı uzunluktaki dizeleri karşılaştırabilir.

def levenshtein_distance(s1, s2):
    m, n = len(s1), len(s2)
    # Initialize a (m+1)x(n+1) matrix
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(m+1):
        dp[i][0] = i
    for j in range(n+1):
        dp[0][j] = j
    # Compute distances
    for i in range(1, m+1):
        for j in range(1, n+1):
            cost = 0 if s1[i-1] == s2[j-1] else 1
            dp[i][j] = min (
                dp[i-1][j] + 1,      # deletion
                dp[i][j-1] + 1,      # insertion
                dp[i-1][j-1] + cost  # substitution
            )
    return dp[m][n]

# Example usage:
print (levenshtein_distance("mahmut", "muhammet")) # Output: 4

Temel Farklılıklar

Hamming ve Levenshtein mesafeleri arasındaki temel farklar aşağıda özetlenmiştir:

String Uzunluğu:

Hamming mesafesi yalnızca eşit uzunluktaki dizgiler için tanımlıdır. Buna karşılık Levenshtein mesafesi farklı uzunluktaki dizgilerle de çalışabilir (ekleme veya silme işlemleriyle hizalama yapabilir).

Düzenleme İşlemleri (Edit Operations):

Hamming mesafesi yalnızca karakter değişimlerini (uyuşmayan karakterleri) sayar. Levenshtein mesafesi ise değişimlere ek olarak ekleme ve silme işlemlerini de içerir. Örneğin, "rain" kelimesini "shine" kelimesine dönüştürmek Levenshtein mesafesinde 3 işlem gerektirir (iki değişim, bir ekleme). Ancak bu iki kelimenin uzunlukları farklı olduğu için Hamming mesafesi tanımsızdır.

Zaman Karmaşıklığı (Complexity):

Hamming mesafesi, uzunluğu n olan dizgiler için O(n) zamanda hesaplanır çünkü tek geçişlidir. Levenshtein mesafesi ise (dinamik programlama ile) uzunlukları m ve n olan dizgiler için O(mn) zaman alır ve uzun dizgilerde daha maliyetli olabilir.

Yorumlama (Interpretation):

Hamming mesafesi, kaydırma olmadan doğrudan hizalanmış karakterler arasındaki farkları sayar. Levenshtein mesafesi ise ekleme ve silme işlemlerine izin vererek en iyi hizalamayı bulur, bu yüzden daha esnek ve gerçekçi bir benzerlik ölçüsüdür. Hatta, dizgiler uygun şekilde doldurulursa (padding), Hamming mesafesi Levenshtein mesafesi için bir üst sınır olabilir. Ancak Levenshtein genellikle daha küçük ve daha doğru bir fark değeri verir.

Kullanım Alanı (Scope):

Hamming mesafesi genellikle kodlama teorisi, hata tespiti ve sabit uzunluklu veri yapılarında kullanılır. Levenshtein mesafesi ise daha genel amaçlıdır ve doğal dil işleme (NLP) ile biyoinformatik alanlarında yaygın olarak kullanılır (çoğu zaman "edit distance" olarak adlandırılır).