Confronta 5000 stringhe con PHP Levenshtein

Question

Ho 5000, a volte più, stringhe di indirizzo in una matrice. Mi piacerebbe confrontarli tutti con levenshtein per trovare corrispondenze simili. Come posso fare questo senza eseguire il ciclo di tutti i 5000 e confrontarli direttamente con ogni altro 4999?

Modifica: Sono anche interessato a metodi alternativi se qualcuno ha suggerimenti. L'obiettivo generale è quello di trovare voci simili (ed eliminare i duplicati) in base agli indirizzi stradali inviati dagli utenti.

Answer 1

Penso che un modo migliore per gruppo indirizzi simili sarebbe quello di:

1. creare un database con due tabelle - uno per l'indirizzo (e un ID), uno per le soundexes di parole o numeri letterali l'indirizzo (con la chiave esterna della tabella indirizzi)

2. maiuscolo l'indirizzo, sostituire un elemento diverso [AZ] o [0-9], con uno spazio

3. dividere l'indirizzo dallo spazio, calcolare il soundex di ogni 'parola', lasciare nulla con solo cifre come è e memorizzarlo nella tabella soundexes con la chiave esterna di indirizzo si è iniziato con

4. per ogni indirizzo (con id $ target) trovare gli indirizzi più simili:

   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. calcola la differenza levenstein tra il tuo indirizzo di origine e i primi valori restituiti dalla query.

(fare qualsiasi tipo di operazione su array di grandi dimensioni è spesso più veloce in database)

Answer 2

Penso che non si possa evitare di eseguire il ciclo attraverso la matrice poiché la funzione levenstein() accetta solo stringhe e non una matrice come input.

Si può fare qualcosa di simile:

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 
     } 
    } 
} 

Answer 3

A causa della natura dell'algoritmo Levenshtein (in particolare il fatto che si tratta di un confronto tra due stringhe), non riesco a vedere come questo sia possibile.

Si potrebbe ovviamente ridurre il numero di confronti eseguendo prima alcuni requisiti di corrispondenza di base, ma ciò non rientra nell'ambito di ciò che si sta chiedendo.

Come opzione (molto probabilmente irrilevante), è possibile utilizzare sempre qualcosa come soundex che consente di calcolare preventivamente i valori di stringa. (È inoltre possibile utilizzare direttamente in MySQL credo.)

Answer 4

Si potrebbe raggrupparli in base a soundexes quindi limitare i confronti con l'approssimazione di casi N ...

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

Poi scorrere le chiavi di $ purè.

C.

Answer 5

dato problema, non vedo altra via che per confrontare ogni indirizzo con ogni altro indirizzo, se si desidera utilizzare Lehvenstein distance.

Prima di tutto, si dovrebbe normalizzare gestire indirizzi, sbarazzarsi di abbreviazioni ecc

• Ave -> Viale
• Rd. -> Strada

Si potrebbe avere una certa distanza fissa max Lehvenstein (N) per gli indirizzi simili.

In tal caso, è possibile interrompere l'algoritmo di Lehvenstein quando si è certi che la distanza di modifica per la coppia di indirizzi corrente è maggiore di N. Per questo è necessario scrivere una versione personalizzata dell'algoritmo di Lehvenstein. Questo renderà l'algoritmo un po 'più veloce.

Esistono anche alcune ottimizzazioni futili correlate. Ad esempio: se l'indirizzo A è lungo 10 caratteri e l'indirizzo B è lungo 20 caratteri, si considerano indirizzi che hanno una distanza inferiore a 8 rispetto a Lehvenstein. Puoi guardare lunghezze di indirizzi e decidere immediatamente che non sono simili.

Answer 6

Se si desidera trovare tutti i valori simili, sarà necessario confrontare tutti gli articoli con tutti gli altri. Ma scegliere le giuste funzioni di array velocizzerà notevolmente le cose.Ecco un esempio veloce (la matrice risultati avrebbe potuto essere migliore):

$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--; 
} 

Answer 7

È possibile utilizzare un bk-tree per accelerare la ricerca/confronto.

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

Ora possiamo fare un particolarmente utile osservazione circa la Levenshtein Distanza: Esso costituisce uno spazio metrico.
[...]
Supponiamo per un momento di avere due parametri, una query, la stringa che stiamo utilizzando nella nostra ricerca e n la distanza massima che una stringa può derivare da una query e che deve ancora essere restituita. Diciamo che prendiamo una stringa arbitaria, testiamo e confrontiamo con la query. Chiama la distanza risultante d. Poiché sappiamo che la disuguaglianza del triangolo vale, tutti i nostri risultati devono avere al massimo la distanza d + n e almeno la distanza d-n dal test.
[...]
I test mostrano che la ricerca con una distanza di 1 query non supera il 5-8% dell'albero e la ricerca con due errori non supera il 17-25% dell'albero - un sostanziale miglioramento rispetto a controllando ogni nodo!

modifica: Ma questo non ti aiuta con il problema ("12 Bird Road, Apt 6" e "12 Bird Rd. # 6"). Solo con il tuo confronto forza-forza m * n.

Answer 8

Tu dici ...

L'obiettivo generale è quello di trovare voci simili (ed eliminare i duplicati) in base agli indirizzi stradali inviati dall'utente.

dico ... utilizzare le tecniche a http://semaphorecorp.com/mpdd/mpdd.html

Answer 9

$stringA = "this is php programming language"; 
$stringB = "this is complete programming script in which java php and all other minor languages include"; 

echo "string 1---->".$stringA."<br />"; 
echo "string 2---->".$stringB."<br />"; 
// changing string to arrays 
$array1 = explode(' ', $stringA); 
$array2 = explode(' ', $stringB); 

// getting same element from two strings 
$c = array_intersect($array1, $array2); 
// changing array to the string 
$d=implode(' ',$c); 

echo "string same elements---> ".$d."<br />"; 


// getting difrent element from two arrays 
$result = array_diff($array2, $array1); 
// changing array to the string 
$zem = implode(' ',$result); 

if (!empty($zem)) { 
    echo "string diffrence---> ".$zem."<br />"; 
} else { 
    echo "string diffrence--->both strings are same <br />"; 
} 

similar_text($stringA, $d, $p); 
echo " similarity between the string is ".$p."% <br />";