Doldurulan hücreler
Düzenleme mesafesi
Korunan harfler

  • Dolduruluyor
  • Okunan
  • Cevap

Düzenleme mesafesi hakkında daha fazla

Düzenleme mesafesi (Levenshtein mesafesi)

Kaç tane tek harflik değişiklik kitten kelimesini sitting kelimesine dönüştürür? Üç: k yerine s, e yerine i koyun ve bir g ekleyin. Bu sayı düzenleme mesafesidir; yazım denetleyicileri önerileri bununla sıralar, biyologlar genleri bununla karşılaştırır. İki kelime yazın ve bir tablonun bu sayıyı nasıl bulduğunu izleyin. Tablonun dolmasını izlemek için Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. İki kelime yazın: birincisi tablonun kenarında yukarıdan aşağıya, ikincisi üst kenarında soldan sağa dizilir. Her hücre, satırına kadar olan harfleri sütununa kadar olan harflere dönüştüren en az düzenleme sayısını tutar. Sonunda düzenlemeler sağ alt hücreden geriye doğru okunur. Yeni örnek başka bir kelime çifti seçer. Pano seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.

Nasıl çalışır

  1. İki kelime yazın: birincisi tablonun kenarında yukarıdan aşağıya, ikincisi üst kenarında soldan sağa dizilir.
  2. Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin.
  3. Her hücrenin üç komşusundan en ucuzunu almasını izleyin, ardından düzenlemelerin turuncuyla geriye doğru okunmasını görün.

Tablo nasıl çalışır

Bir hücre, birinci kelimenin satırına kadar olan harflerini ikinci kelimenin sütununa kadar olan harflerine dönüştüren en az düzenleme sayısını tutar. İlk satır eklemeleri sayar ve ikinci kelimeyi sıfırdan oluşturur; ilk sütun ise silmeleri sayar. Bir hücrenin iki harfi aynıysa hücre, sol üst çaprazdaki hücreyi kopyalar: düzenleme gerekmez. Aksi hâlde üç komşunun en küçüğünden bir fazladır: değiştirme için sol üst çapraz, silme için üstteki ve ekleme için soldaki hücre.

Düzenlemeleri geriye doğru okumak

Sağ alt hücre düzenleme mesafesidir. Uygulama oradan başlayarak hücrenin değerinin hangi komşudan geldiğini bulur ve ona geçer: korunan ya da değiştirilen harf için çapraz, silinen harf için yukarı, eklenen harf için sola. Sol üstten okunduğunda bu adımlar, tablonun altında gösterilen en kısa düzenleme listesini verir: düz bir harf korunmuştur, k→s bir değiştirme, −e bir silme ve +g bir eklemedir.

Sık sorulan sorular

Levenshtein mesafesi nedir?

Bu düzenleme mesafesinin diğer adıdır: bir dizeyi başka bir dizeye dönüştüren en az tek harflik ekleme, silme ve değiştirme sayısı. Adını, onu 1965'te tanımlayan Vladimir Levenshtein'dan alır.

kitten ile sitting arasındaki düzenleme mesafesi nedir?

3: k yerine s, e yerine i koyun ve sona g ekleyin. Tablo, daha kısa bir düzenleme listesi olmadığını gösterir.

Düzenleme mesafesi algoritması ne kadar hızlıdır?

Uzunlukları m ve n olan kelimeler için tabloda (m + 1)·(n + 1) hücre vardır ve her biri tek adımda doldurulur; bu yüzden O(m·n) zaman alır. Yalnızca mesafe gerekiyorsa tablonun iki satırı yeterlidir.

Başka hangi düzenleme mesafeleri vardır?

Damerau–Levenshtein mesafesi, komşu iki harfin yer değiştirmesini de tek düzenleme sayar; bu da yazım hatalarına uygundur. Hamming mesafesi yalnızca değiştirmeye izin verir ve eşit uzunluktaki dizelerde çalışır. LCS mesafesi yalnızca ekleme ve silmeye izin verir.

Herhangi bir yere veri gönderiliyor mu?

Hayır. Her şey tarayıcınızda hesaplanır ve son ayarlarınız bu tarayıcının yerel depolamasında kalır.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Editöre Git