Vergleichen Sie 5000 Strings mit PHP Levenshtein

Question

Ich habe 5000, manchmal mehr, street address strings in einem Array. Ich möchte sie alle mit Levenshtein vergleichen, um ähnliche Übereinstimmungen zu finden. Wie kann ich dies tun, ohne alle 5000 zu durchlaufen und sie direkt mit jedem anderen 4999 zu vergleichen?

Bearbeiten: Ich bin auch an alternativen Methoden interessiert, wenn jemand Vorschläge hat. Das allgemeine Ziel besteht darin, ähnliche Einträge zu finden (und Dubletten zu eliminieren), basierend auf von Benutzern eingegebenen Straßenadressen.

Answer 1

denke ich, ein besserer Weg zu einer Gruppe ähnliche Adressen wären:

1. eine Datenbank mit zwei Tabellen erstellen - einem für die Adresse (und id), eine für die soundexes von Worten oder wörtlicher Zahlen in der Adresse (mit dem Fremdschlüssel der Tabelle Adressen)

2. Groß die Adresse, ersetzen, etwas anderes als [AZ] oder [0-9] mit einem Raum

3. die Adresse durch den Raum geteilt, berechnen der Soundex jedes "Wortes", läßt alles mit nur Ziffern wie und speichern sie in der soundexes Tabelle mit dem Fremdschlüssel der Adresse, die Sie mit gestartet

4. für jede Adresse (mit ID $ target) finden, die am ähnlichsten Adressen:

   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. berechnen Sie den Unterschied levenstein zwischen Ihrer Quelladresse und den ersten paar von der Abfrage zurückgegebenen Werte.

(tut jede Art von Betrieb auf großen Feldern ist oft schneller in Datenbanken)

Answer 2

Ich denke, Sie können nicht vermeiden, das Array durchlaufen, da die Funktion levenstein() nur Zeichenfolgen und nicht ein Array als Eingabe verwendet.

Sie können wie etwas tun:

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

Aufgrund der Natur des Levenshtein-Algorithmus (insbesondere die Tatsache, dass es ein Vergleich zwischen zwei Strings ist), kann ich nicht sehen, wie dies möglich ist.

Sie könnten natürlich die Anzahl der Vergleiche reduzieren, indem Sie zunächst einige grundlegende Übereinstimmungsanforderungen erfüllen, aber dies gehört nicht zum Umfang dessen, was Sie fragen.

Als eine (möglicherweise irrelevante) Option könnten Sie immer etwas wie soundex verwenden, mit dem Sie die Zeichenfolgenwerte vorberechnen könnten. (Sie können auch direkt in MySQL verwenden, glaube ich.)

Answer 4

Sie könnten Gruppe sie basierend auf soundexes begrenzen dann die Vergleiche auf die nächsten N Fälle ...

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

Dann durchlaufen die Schlüssel von $ püriert.

C.

Answer 5

Angenommen, Sie Problem, sehe ich keine andere Möglichkeit, als jede Adresse mit jeder anderen Adresse zu vergleichen, wenn Sie Lehvenstein distance verwenden möchten.

Zunächst einmal sollten Sie addressess normalisieren usw. Abkürzungs

• Ave loszuwerden -> Avenue
• Rd. -> Road

Sie könnten einigen festen max Lehvenstein Abstand haben (N) für ähnliche Adressen.

Wenn ja, könnten Sie den Lehvenstein-Algorithmus abbrechen, wenn Sie sicher sind, dass die Bearbeitungsentfernung für das aktuelle Adresspaar größer als N ist. Dazu müssen Sie eine benutzerdefinierte Version des Lehvenstein-Algorithmus schreiben. Dies wird den Algorithmus ein wenig schneller machen.

Es gibt auch einige verwandte triviale Optimierungen. Zum Beispiel: wenn Adresse A 10 Zeichen lang ist und Adresse B 20 Zeichen lang ist und Sie Adressen mit Lehvenstein Abstand von weniger als 8 als ähnlich betrachten. Sie können Längen von Adressen suchen und sofort entscheiden, dass sie nicht ähnlich sind.

Answer 6

Wenn Sie alle ähnliche Werte finden möchten, müssen Sie alle Elemente mit allen anderen vergleichen. Aber die Auswahl der richtigen Array-Funktionen wird die Dinge erheblich beschleunigen.Hier ist ein kurzes Beispiel (die Ergebnisse Array hätte besser sein können):

$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

Sie können eine bk-tree verwenden zu beschleunigen, um die Suche/Vergleich.

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

Jetzt haben wir eine besonders nützliche Beobachtung über die Levenshtein Entfernung machen: Es bildet einen metrischen Raum.
[...]
Nehmen wir an, wir haben zwei Parameter, Abfrage, die Zeichenfolge, die wir in unserer Suche verwenden, und n die maximale Entfernung eine Zeichenfolge kann aus Abfrage und noch zurückgegeben werden. Nehmen wir an, wir nehmen eine willkürliche Zeichenkette, testen und vergleichen sie mit der Abfrage. Nennen Sie die resultierende Entfernung d. Da wir wissen, dass die Dreiecksungleichung gilt, müssen alle unsere Ergebnisse höchstens den Abstand d + n und mindestens den Abstand d-n vom Test haben.

Tests zeigen, dass die Suche mit einer Entfernung von 1 Abfragen nicht mehr als 5-8% des Baumes, und die Suche mit zwei Fehler Abfragen nicht mehr als 17-25% des Baumes - eine erhebliche Verbesserung gegenüber jeden Knoten überprüfen!

edit: Aber das hilft Ihnen nicht mit Ihrem ("12 Bird Road, Apt 6" und "12 Bird Rd. # 6") Problem. Nur mit deinem Brute-Force-m * n-Vergleich.

Answer 8

Sie sagen ...

Das Ziel ähnliches zu finden ist (und zu beseitigen Duplikate) basierend auf vom Benutzer eingegebenen Straßenadressen.

ich sagen ... nutzen die Techniken bei 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 />";