First, take a look at the Levenshtein algorithm on wikipedia. Then go on and look at the examples and the resulting matrix d on the article page:

                *k* 	*i* 	*t* 	*t* 	*e* 	*n*
        >0    1  	 2  	 3  	 4  	 5  	 6 
*s*      1      >1  	 2  	 3  	 4  	 5  	 6 
*i*      2       2  	>1  	 2  	 3  	 4  	 5 
*t*      3       3  	 2  	>1  	 2  	 3  	 4 
*t*      4       4  	 3  	 2  	>1  	 2  	 3 
*i*      5       5  	 4  	 3  	 2  	>2  	 3 
*n*      6       6  	 5  	 4  	 3  	 3  	>2 
*g*      7       7  	 6  	 5  	 4  	 4  	>3 

The distance is found on lower right corner of the matrix, d[m, n]. But from there it is now possible to follow backtrack the minimum steps to the upper left of of the matrix, d[1, 1]. You just go left, up-left, or up at each step whichever minimizes the path. In the example above, you'd find the path marked by the '>' signs:

  s i t t i n g      k i t t e n
0 1 1 1 1 2 2 3    0 1 1 1 1 2 2 3
  ^       ^   ^      ^       ^   ^
  changes in the distance, replace by dots

Şimdi konumları d hangi asgari yolunda bulabilirsiniz [i, j] (Yukarıdaki örnekte ^ ile işaretlenmiş) mesafesi değişiklikleri, ve i (pozisyonunda birinci (ya da ikinci) kelime bir nokta koymak bu mektuplar için ya da j) bulundu.

Sonuç:

  s i t t i n g      k i t t e n
  ^       ^   ^      ^       ^   ^
  . i t t . n .      . i t t . n . 

Aradığınız terminoloji "edit mesafe" denir. Gibi bir şey kullanarak Levenshtein distance size diğer (eklemeler, silme, yer değiştirmelerin, vb) içine bir dize dönüştürmek için gerekli operasyonların sayısını söyleyecektir.

Here is a list of other "editing distance" algorithms.

Eğer bir kelime (yani gerekli düzenlemeleri bazı eşiği aşmadığı) "yeterince yakın" olduğuna karar sonra düzenlemelerin ortaya gereken yere, sen (noktalar göstererek) gösterebilir.

So how do you know where to put the dots?

"Levenshtein mesafe" ile ilgili ilginç şey, her eksen üzerinde tek kelime ile bir M x N matrisini kullanır (örnek matrisi görüyoruz Levenshtein article). Eğer matris oluşturduktan sonra, harfleri doğru olması için "ek düzenlemeler" gerektiren belirleyebilirsiniz. Eğer nokta koymak orası. Harf gerektiriyorsa "ek düzenlemeleri," sadece mektup yazdırmak. Pretty cool.

Ben sadece Levenshtein değil bir çok adım süreci yapmak gerek. Giriş kelimesi, hedef kelimenin bir şekli ise ilk kontrol ederim. Bu sizin 3 örnek ve aynı zamanda noktalar eklenmesi konusunda hiçbir endişe yakalamak istiyorsunuz. Ayrıca eş yakalamak için bu adımı kullanabilirsiniz. Bir sonraki adım, iki dizeleri uzunluğu farkını kontrol etmektir.

Farkı 0 ise, nokta yerleştirmek için mektup karşılaştırma için bir mektup yapabilirsiniz. Eğer tüm noktalar göstermek istemiyorsanız, o zaman yerleştirilmiş noktaların sayısını tutmalı ve bir kez sınır ekran üzerinde bazı hata iletisi. (Maalesef bu yanlış oldu)

Farkı gösteren ise giriş artık size sorunu çözmek istiyorsunuz silmek üzere bir mektup kontrol etmek için ihtiyaç vardır. İşte onlar çok uzak bu aralıkta ise size ters Levenshtein adımlarını yapmak gerekir ve bir şekilde değişiklikleri işaretlemek olacaktır hata mesajı göstermek eğer onlar ne kadar yakın olduğunu görmek için Levenshtein kullanabilirsiniz. Değil bir mektup ihtiyacı silinmiş olduğunu göstermek istiyorum nasıl emin.

Fark gösteriyorsa iki kelime kadar yakın olan ya da hatayı göstermek durumunda giriş görmek Levenshtein mesafe kullanımını yapabilirsiniz kısadır. Sonra ters adımlar tekrar değiştirmeler için eklemeler ve noktaları noktalar eklenmesi yok.

Aslında son iki adım algoritması ile çalışır ve ekleme silme veya ikamesi hatırlar ve buna göre çıkışı değiştiren bir fonksiyon haline de getirilebiliyor.