İki dizginin ne kadar olduğunu bulma

Question

2 dizeyi alan bir algoritma arıyorum ve bana "benzerlik katsayısı" vereceğim.

Temel olarak, yazım yanlış yazılmış, harflerle çevrilmiş vb. Olabilecek bir girdim olacak ve sahip olduğum olası değerler listesinde en yakın eşleşmeleri bulmam gerekiyor.

Veritabanında arama yapmak için değil. Karşılaşmak için 500 veya daha fazla dizenin bir bellek içi listesi olacak, 30 karakterin altında, bu yüzden nispeten yavaş olabilir.

Bunu biliyorum, daha önce görmüştüm ama adını hatırlayamıyorum.

---

Düzenleme: Levenshtein ve Hamming'i işaretlediğiniz için teşekkür ederiz. Şimdi hangisini uygulamalıyım? Temel olarak farklı şeyler ölçüyorlar, her ikisi de istediklerim için kullanılabilir, ancak hangisinin daha uygun olduğundan emin değilim.

Algoritmalarımı okudum Hamming daha hızlı görünüyor. Ne tür bir yanlışlık olacağına inandığım iki karakterin (yani, Jordan ve Jodran) ne olduğunu tespit edemediğimden, ne istediğim için daha doğru olacak? Birisi bana takaslardan biraz bahsedebilir mi?

Answer 1

Tamam

, bu nedenle standart algoritmaları şunlardır:

1) aynı uzunlukta dizeler için sadece iyi, ama çok etkili Hamming distance . Temel olarak sadece farklı karakterlerin sayısını sayar. Doğal dil metninin bulanık arama için yararlı değil.

2) . Levenstein uzaklığı, bir dizgiyi diğerine dönüştürmek için gereken "işlemler" sayısı bakımından mesafeyi ölçer. Bu işlemler ekleme, silme ve alt katmanları içerir. Levenstein mesafesini hesaplamanın standart yaklaşımı, dinamik programlamayı kullanmaktır.

3) Generalized Levenstein/(Damerau–Levenshtein distance) Bu mesafe, bir kelimenin karakterlerinin transpozisyonlarını da dikkate alır ve muhtemelen elle girilen metnin bulanık eşleşmesi için en uygun düzenleme mesafesidir. Mesafeyi hesaplamaya yarayan algoritma Levenstein mesafesinden biraz daha fazla etkilenir (transpozisyonları tespit etmek kolay değildir). En yaygın uygulamalar, bitap algoritmasının (grep gibi) bir değişikliğidir. Genelde

muhtemelen, Hamming ve Levenshtein mesafesi hem her 2 bir maliyet atama, transpozisyonlar tespit

Answer 2

Sen Levenshtein distance

Answer 3

• Levenstein mesafe için aradığınız
• Hamming uzaklığı
• soundex
• metafon

Answer 4

Damerau-Levenshtein distance Levenshtein mesafeye benzer, ama aynı zamanda içerir iki karakterli transpozisyon. wikipedia sayfası (bağlantılı), uygulamak için oldukça önemsiz olması gereken sözde kodu içerir.