hkucuk

Levenshtein Mesafesi Nedir, Nasıl Hesaplanır?

2 Eylül 2023 • ☕️ 5 dk okuma • 🏷 bilgisayar, yazılım, algoritma

Yazar tarafından şu dillere çevrildi: English


Levenshtein Mesafesi, metin veya dizgeler arasındaki benzerliği veya farklılığı ölçmenin temel bir yöntemidir ve genellikle bilgisayar bilimleri, doğal dil işleme ve genetik analiz gibi birçok farklı alanın yanı sıra günlük hayatta da yaygın olarak kullanılır. Bu metrik, iki dizge arasındaki karakterlerin kaç kez değiştirilmesi, eklenmesi veya çıkarılması gerektiğini belirleyerek bu dizgelerin ne kadar benzer veya farklı olduğunu nicel olarak ifade eder. Bu nedenle Levenshtein Mesafesi, veri madenciliği, otomatik düzeltme sistemleri, yazılı metin karşılaştırmaları ve hatta genetik dizilim analizinde önemli bir rol oynamaktadır. İlerleyen bölümlerde, Levenshtein Mesafesi’nin nasıl hesaplandığını ayrıntılı bir şekilde inceleyeceğiz ve bu metriği anlamanıza yardımcı olacak örnekler sunacağız.

Levenshtein Mesafesi Nedir?

Levenshtein Mesafesi, metin veya dizgeler arasındaki benzerlik veya farklılık ölçümünü belirlemek amacıyla kullanılan bir metrik veya algoritmadır. Bu metrik, iki dizge arasındaki karakterlerin nasıl değiştirildiğini, eklenip çıkarıldığını belirleyerek bu iki dizgenin birbirine ne kadar benzediğini nicel olarak ifade eder. İki dizge arasındaki farkın veya benzerliğin ölçülmesinde oldukça kullanışlıdır ve birçok uygulama alanında kendini gösterir.

Levenshtein Mesafesi, ilk olarak 1965 yılında Sovyet bilgisayar bilimcisi Vladimir Levenshtein tarafından tanıtılmıştır. Bu nedenle bu metrik, onun adını taşır. Levenshtein, bu metriği yazım hatalarını düzeltme işlemlerini analiz etmek amacıyla geliştirdi, ancak daha sonra birçok farklı alanda kullanım potansiyeli keşfedildi.

Bu mesafe hesaplanırken, iki dizge arasındaki karakter diziliminin nasıl değiştirildiğini, eklendiğini veya çıkarıldığını gözlemlemek esastır. Her bir karakter dizgesi birbirine dönüştürülmeye çalışıldığında ne kadar çok düzenleme işlemi gerekiyorsa, Levenshtein Mesafesi de o kadar büyük olur. Yani, iki dizge arasındaki mesafe, bu düzenleme işlemlerinin sayısını temsil eder.

Levenshtein Mesafesi’nin temel amacı, iki dizge arasındaki farklılığı nicel olarak ifade ederek metin benzerliği analizi, yazım denetimi, veri eşleme, genetik dizilim karşılaştırmaları ve daha birçok alanda kullanım olanağı sunmaktır. Özellikle doğal dil işleme uygulamalarında ve veri analizi projelerinde sıkça kullanılır. Bu algoritma, metin madenciliği ve veri işleme alanlarında önemli bir araçtır ve çok sayıda kullanım senaryosu sunar. İlerleyen bölümlerde, Levenshtein Mesafesi’nin nasıl hesaplandığını ve uygulama örneklerini daha ayrıntılı bir şekilde inceleyeceğiz.

Levenshtein Mesafesi Nasıl Hesaplanır?

Levenshtein Mesafesi, dinamik programlama yöntemiyle hesaplanır. Temel fikir, iki dizgeyi karşılaştırarak ve her bir karakterin eşleşme durumunu izleyerek bir matris oluşturmaktır.

Hesaplama adımları şunlardır:

Adım 1: İlk Matrisi Oluşturma

İlk olarak, iki dizgeyi karşılaştırmak için bir matris oluşturuyoruz. Matrisin satırları birinci dizgeyi, sütunları ise ikinci dizgeyi temsil eder. Matrisin boyutları, her iki dizgenin uzunluğuna göre belirlenir. Matrisin ilk satırı ve ilk sütunu sıfır değerleri ile başlar. Bu matris, Levenshtein Mesafesi hesaplamasının temelini oluşturur.

Örnek:

  |   | M | I | N | E
-----------------------
  | 0 | 1 | 2 | 3 | 4
-----------------------
H | 1 |   |   |   |  
-----------------------
O | 2 |   |   |   |  
-----------------------
U | 3 |   |   |   |  
-----------------------
S | 4 |   |   |   |

Adım 2: Matrisi Doldurma

Matrisin oluşturulmasının ardından, her bir hücrenin değerini hesaplamaya başlarız. Her hücre, iki karşılaştırılan karakterin eşleşme durumuna göre değer alır. İki karakter aynı ise, o hücrenin değeri sol üst köşedeki hücrenin değeridir. Eğer karakterler eşleşmiyorsa, o hücrenin değeri sol, üst ve sol üst köşedeki hücrelerin en küçüğüne bir eklemesi yapılmasıyla belirlenir.

Matematiksel olarak, iki karakter arasındaki mesafe (D) şu şekilde hesaplanır:

D(i, j) = 0, eğer string1[i] = string2[j]
D(i, j) = min(D(i-1, j), D(i, j-1), D(i-1, j-1)) + 1, eğer string1[i] ≠ string2[j]

Burada, i ve j, iki dizgeyi karşılaştırmada kullanılan indeksleri temsil eder.

Örnek:

  |   | M | I | N | E
-----------------------
  | 0 | 1 | 2 | 3 | 4
-----------------------
H | 1 | 1 | 2 | 3 | 4
-----------------------
O | 2 | 2 | 2 | 3 | 4
-----------------------
U | 3 | 3 | 3 | 3 | 4
-----------------------
S | 4 | 4 | 4 | 4 | 4

Adım 3: Levenshtein Mesafesini Bulma

Matrisin sağ alt köşesindeki değer, Levenshtein Mesafesi’ni temsil eder. Bu değer, iki dizge arasındaki minimum düzenleme işlemi sayısını ifade eder. İki dizge arasındaki benzerlik veya farklılığı ölçmek istediğinizde, bu değeri kullanabilirsiniz.

Matematiksel olarak, Levenshtein Mesafesi (L) şu şekilde hesaplanır:

L = D(m, n)

Burada, m ve n, sırasıyla birinci ve ikinci dizgenin uzunluğunu temsil eder.r

Örnek:

Levenshtein Mesafesi = 4

Levenshtein Mesafesi’nin hesaplanma süreci bu adımları izler ve sonuç olarak iki dizge arasındaki benzerlik veya farklılığı nicel olarak ifade eder.

Levenshtein Mesafesi hesaplama işlemi, karakter dizgelerini karşılaştırmanın ve düzenleme işlemlerini belirlemenin güçlü bir yolunu sunar. Bu nedenle yazım denetimi, metin benzerliği analizi, veri eşleme ve genetik dizilim karşılaştırmaları gibi birçok farklı uygulama alanında yaygın olarak kullanılır.

GoLang’de Levenshtein Mesafesi uygulaması:

package main

import (
	"fmt"
)

func Min(a, b, c int) int {
	if a <= b && a <= c {
		return a
	} else if b <= a && b <= c {
		return b
	} else {
		return c
	}
}

func LevenshteinDistance(str1, str2 string) int {
	m := len(str1)
	n := len(str2)

	matrix := make([][]int, m+1)
	for i := range matrix {
		matrix[i] = make([]int, n+1)
	}

	for i := 0; i <= m; i++ {
		matrix[i][0] = i
	}
	for j := 0; j <= n; j++ {
		matrix[0][j] = j
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			cost := 0
			if str1[i-1] != str2[j-1] {
				cost = 1
			}
			matrix[i][j] = Min(
				matrix[i-1][j]+1,
				matrix[i][j-1]+1,
				matrix[i-1][j-1]+cost,
			)
		}
	}

	return matrix[m][n]
}

func main() {
	str1 := "hors"
	str2 := "rose"

	distance := LevenshteinDistance(str1, str2)

	fmt.Printf("Levenshtein Distance between '%s' and '%s': %d\n", str1, str2, distance)
}

Program çalıştırıldığında çıktısı aşağıdaki gibi olacaktır.

Levenshtein Distance between 'hors' and 'rose': 3

Çıktı, “hors” ve “rose” dizgeleri arasındaki Levenshtein Mesafesi’ni (Levenshtein Distance) gösterir ve sonucun 2 olduğunu belirtir. Bu, iki dizge arasında en az 2 düzenleme işlemi gerektiği anlamına gelir.

Programın çalışır haline şuradan erişilebilir.

Kaynaklar