Ben grup benzer adreslere daha iyi bir yol olacağını düşünüyorum:

1. adresi için bir (ve id), (adresler tablonun yabancı anahtar) adresinde kelimelerin veya değişmez sayı soundexes için bir - iki tablo ile bir veritabanı oluşturmak

2. adresini harfe, bir boşluk [AZ] başka bir şey veya [0-9] değiştirin

3. , boşluk adresi bölünmüş, her bir 'Kelime' soundex hesaplamak, olduğu gibi sadece rakam ile bir şey bırakmak ve ile başlayan adresi yabancı anahtar ile soundexes tabloda depolamak

4. (id $ hedef) her adres için en benzer adreslerini bulabilirsiniz:

   SELECT similar.id, similar.address, count(*) 
   FROM adress similar, word cmp, word src
   WHERE src.address_id=$target
   AND src.soundex=cmp.soundex
   AND cmp.address_id=similar.id
   ORDER BY count(*)
   LIMIT $some_value;
   

5. kaynak adresi ve sorgu tarafından döndürülen üst birkaç değerleri arasındaki Levenstein farkı hesaplamak.

(Büyük diziler üzerinde operasyon herhangi bir sıralama yaparak veritabanları genellikle daha hızlıdır)

Sen hızlandırmak için arama / karşılaştırma a bk-tree kullanabilirsiniz.

http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees diyor ki:

Now we can make a particularly useful observation about the Levenshtein Distance: It forms a Metric Space.
[...]
Assume for a moment we have two parameters, query, the string we are using in our search, and n the maximum distance a string can be from query and still be returned. Say we take an arbitary string, test and compare it to query. Call the resultant distance d. Because we know the triangle inequality holds, all our results must have at most distance d+n and at least distance d-n from test.
[...]
Tests show that searching with a distance of 1 queries no more than 5-8% of the tree, and searching with two errors queries no more than 17-25% of the tree - a substantial improvement over checking every node!

edit: (". 12. Bird Rd # 6" "12 Kuş Yolu, Apt 6" ve) Ama bu size yardımcı olmuyor sorun. Yalnızca kaba kuvvet m * n karşılaştırma ile.

Ben () fonksiyonu giriş olarak sadece dizeleri değil, bir dizi alır Levenstein olarak dizi döngü kaçınamaz düşünüyorum.

Sen gibi bir şey yapabilirsiniz:

for($i=0;$i<count($array)-1;$i++)
{
    for($j=$i+1;$j<count($array);$j++)
    {
    	$lev = levenshtein($array[$i],$array[$j]);
    	if($lev == 0)
    	{
    		// exact match
    	}
    	else if($lev <= THRESHOLD)
    	{
    		// similar
    	}
    }
}

Nedeniyle Levenshtein algoritması (iki dizeleri arasında bir karşılaştırma olduğunu özellikle gerçeği) doğası gereği, bu nasıl mümkün olduğunu göremiyorum.

Siz tabii ki ilk olarak bazı temel gereksinimleri eşleşen yaparak karşılaştırmaların sayısını azaltabilir, ancak bu soruyorsun ne kapsamı dışındadır.

Bir (büyük olasılıkla ilgisiz) bir seçenek olarak, her zaman dize değerlerini önceden hesaplamak izin istiyorum soundex gibi bir şey kullanabilirsiniz. (Ayrıca ben inanıyorum MySQL doğrudan kullanabilirsiniz.)

Sen grubu onları soundexes dayalı ardından en yakın N durumlarda karşılaştırmalar sınırı olabilir ...

 $mashed=array();
 foreach ($address as $key=>$val) {
      $mashed[$key]=soundex($val);
 }
 sort($mashed);

Sonra $ püre anahtarları yineleyemezsiniz.

C.

Eğer kullanmak istiyorsanız, size sorunu göz önüne alındığında, ben her adresi ile her adresini karşılaştırmak için başka bir yol göremiyorum Lehvenstein distance.

Her şeyden önce, siz adresleriyle normalleştirmek gerektiğini, kısaltmalar vb kurtulmak

• Ave -> Caddesi
• Rd. -> Yol

Eğer benzer adresleri için bazı sabit max Lehvenstein mesafe (N) olabilir.

Öyleyse şimdiki adresi çifti için düzenleme mesafe size Lehvenstein algoritmasının özel bir sürümünü yazmak gerekiyor Bunun için N'ye daha büyük olduğundan emin olduğunuzda, size Lehvenstein algoritma iptal olabilir olabilir. Bu biraz daha hızlı algoritması yapacaktır.

Ilgili bazı önemsiz optimizasyonlar da vardır. Örneğin: adresi A 10 karakter uzunluğunda olduğunu ve adresi B 20 karakter uzunluğunda olduğunu ve daha az 8 Lehvenstein mesafe var Adreslerin benzer olarak düşünün. Sen adresleri uzunlukları bakmak ve hemen onlar benzer olmadığını karar verebilirsiniz.

Diyorsunuz ...

Genel amacı kullanıcı gönderilen sokak adreslerine göre benzer girdileri bulmak (ve çiftleri ortadan kaldırmak) için.

Diyorum ... at teknikleri kullanmak http://semaphorecorp.com/mpdd/mpdd.html

Eğer all benzer değerleri bulmak istiyorsanız, diğerleri için tüm öğeleri karşılaştırmak gerekir. Ama doğru dizi fonksiyonları seçerek anlamlı şeyler hızlandırır. İşte (results dizisi daha iyi olabilirdi) hızlı bir örnek:

$results = array();
$count = count($entries);
while ($count != 0) {
    # The entry to process
    $entry = array_shift($entries);
    # Get levenshtein distances to all others
    $result = array_map(
        'levenshtein',
        # array_map() needs two arrays, this one is an array consisting of
        # multiple entries of the value that we are processing
        array_fill($entry, 0, $count),
        $toCompare
    );
    $results[] = array($entry => $result);
    $count--;
}