Önekler/ekler için Levenshtein mesafesi için alternatif

Question

Birçok farklı kaynaktan derlenmiş büyük bir şehir veritabanına sahibim. Şehir adına göre çiftleri kolayca tespit etmenin bir yolunu bulmaya çalışıyorum. Naif cevap levenshtein mesafesini kullanmak olacaktır. . Ancak, şehirler ile sorun genellikle onlar Örneğin

Bulunduğunuz ülke ortak olan önek ve sonek olması: Bu neredeyse kesin farklı şehirler Boulleville Boscherville

vs

. Ancak, her ikisi de "ville" (ve her ikisi de "Bo" ile başlar) ile bittikleri için, oldukça küçük bir Levenstein mesafesine sahiptirler.

* Sözcüğün sonundaki harflerden yüksek sözcüğün ortasındaki harfleri ağırlıklandırma yoluyla öneklerin ve soneklerin etkisini en aza indirmek için karakterin konumunu dikkate alan bir dize mesafe algoritması arıyorum. *

Muhtemelen kendim bir şeyler yazabilirim ama hiç kimsenin henüz uygun bir algoritma yayınlamadığına inanmak zor.

Answer 1

Bunu yapmanın oldukça basit bir yolu, mesafe hesaplamasını yapmadan önce ortak öneki ve soneki kaldırmak olacaktır. Sonuç dizeleri arasındaki mutlak mesafe, tam dizelerle aynı olacaktır, ancak daha kısa uzunluk dikkate alındığında mesafe çok daha fazla görünür. Genel olarak 'un numaralı numaranın bile imkansız yazım hatalarının ilk harfi doğru aldığını aklınızda bulundurun. Bu durumda, büyük olasılıkla, Cowville ve Bowville, L. mesafeleri 1 olsa da, farklı şehirlerdir.

İki kişiyse, en azından ilk önce mesafe hesaplamasını yapmadan işinizi çok daha kolay yapabilirsiniz. kelimeler farklı harflerle başlar. Farklı olmaları muhtemeldir. Önce aynı harflerle başlayan sözcüklerin kopyalarını kaldırmaya konsantre olun. Bundan sonra, hala çok sayıda potansiyel kopyası varsa, farklı harflerle başlayan kelimeleri daha yakından incelemek için mesafe eşiğinizi hassaslaştırabilirsiniz.

Answer 2

Bu, Doğal Dil Programlama'da stemming'a benzer. Bu alanda, bir sözcüğün sapı, daha ileri analizler gerçekleştirmeden önce bulunur, örn.

run => run 
running => run 
runs => run 

(... o biri lemmatizer kullanabilirsiniz İçin ran gibi tabii şeyler. run için kök yoktur. Ama konuyu dağıtmak). Her ne kadar NLP'de mükemmel olmaktan uzak olsa da, son derece iyi çalışır. Sizin durumunuzda, Levenstein'ı uygulamadan önce şehir adlarına özgü kuralları kullanarak kenti kökten çıkarmak iyi olabilir. Şehirler için daha köklü bir uygulama olduğunun farkında değilim, ancak kuralların yüzeyde oldukça basit görünmesi.

Öneklerin bir listesiyle ve soneklerin bir listesiyle başlayabilirsiniz (ortak değişken/yazım hataları dahil) ve sadece Levenstein mesafesini kontrol etmeden önce böyle bir önek/sonek kaldırabilirsiniz.

Bir yan notda, ek adres bilgileriniz varsa (sokak adresi veya posta kodu/posta kodu gibi), adrese özgü algoritmalara göre en iyi eşleşmeyi bulabilecek birçok ülke için normalleştirme yazılımının adresi vardır.