Bir dize ve bir bilgi tabanı verildiğinden, dize benzerliği sorunu için k-en yakın komşulardan yararlanmaya çalışıyorum, verilen dizgime benzer olan k dizelerini vermek istiyorum. Bu k-en yakın komşu araması için dizeleri verimli bir şekilde yapmak için kd ağaçlarının nasıl kullanılacağını açıklayan herhangi bir eğitim var mı? Dize uzunluğu 20 karakterden fazla olmayacaktır.Dize benzerliğini belirlemek için kd ağaçlarını nasıl kullanırım?
Muhtemelen bir yıl kadar önce okuduğum en sıcak blog gönderilerinden biri: Levenstein Automata. Bu makaleye bir bakın. Sadece algoritmanın bir tanımını değil, aynı zamanda takip edecek kodu da sağlar. Teknik olarak, bir kd ağacı değildir, ancak gerçek dünyada karşılaşabileceğiniz/kullanabileceğiniz dizgi eşleme ve sözlük düzeltme algoritmalarıyla oldukça ilgilidir.
Ayrıca, başka bir blog yazısı da var. BK-trees, dizeleri ve dizgilerle ilgili yanlış eşleşmelerde bulanık eşlemede çok daha iyi. İşte bir kaynak kodu BK-tree için bir kaynak kodudır burada (bu doğruluğu doğru uygulayamıyor veya doğru uygulamam.)
+ 1. –
Levenshtein Automata etkileyici olsa da, bunu uyguladıktan sonra, sadece önceden hesaplanan sürümün, mesafe büyüdüğünde (düğümler açısından) hızlı bir şekilde patladığını söyleyebilirim. Pratikte, bir Trie'de arama yapmak hızlıdır, fakat otomatikman 4 ve yukarı bir mesafe için gerçekten büyük olmaya başlar. –
@Matthieu M. bunun yerine ne önerirsiniz? – wheaties
2 karakter arasında benzerlik metriğiniz nedir? [scipy.spatial.cKDtree] (http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.cKDTree.html) hızlı ve sağlam, 20d için iyi, ancak yalnızca Lp metrikleri var. Levenshtein dönüştürücüleri için – denis