Vergleichen Sie 5000 Saiten mit PHP Levenshtein

StackOverflow https://stackoverflow.com/questions/1957989

Frage

Ich habe 5000, manchmal mehr Straßenadressen in einem Array. Ich möchte sie alle mit Levenshtein vergleichen, um ähnliche Übereinstimmungen zu finden. Wie kann ich das tun, ohne alle 5000 zu durchlaufen und sie direkt mit allen anderen 4999 zu vergleichen?

Bearbeiten: Ich interessiere mich auch für alternative Methoden, wenn jemand Vorschläge hat. Das Gesamtziel ist es, ähnliche Einträge zu finden (und Duplikate zu beseitigen), die auf vom Benutzer eingereichten Straßenadressen basieren.

War es hilfreich?

Lösung

Ich denke, ein besserer Weg, ähnliche Adressen zu gruppieren, wäre:

  1. Erstellen Sie eine Datenbank mit zwei Tabellen - eine für die Adresse (und eine ID), eine für die Soundxes von Wörtern oder Literalnummern in der Adresse (mit dem Fremdschlüssel der Adresstabelle)

  2. Großbuchstaben der Adresse, ersetzen Sie etwas anderes als [AZ] oder [0-9] durch einen Raum

  3. Teilen Sie die Adresse durch den Raum auf, berechnen Sie den Soundex jedes "Wortes", lassen Sie alles mit nur Ziffern wie es sind und speichern

  4. Für jede Adresse (mit ID $ Ziel) finden Sie die ä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 Levenstein -Differenz zwischen Ihrer Quelladresse und den besten Werten, die von der Abfrage zurückgegeben wurden.

(In Datenbanken ist in Datenbanken oft schneller ein Betrieb in großen Arrays)

Andere Tipps

Ich denke, Sie können es nicht vermeiden, das Array durch das Array zu schieben, da die Funktion Levenstein () nur Strings und kein Array als Eingabe nimmt.

Sie können so etwas wie:

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

Sie können a verwenden Bk-Baum um die Suche/den Vergleich zu beschleunigen.

http://blog.notdot.net/2007/4/damn-cool-algorithms-part-1-bk-bäume sagt:

Jetzt können wir eine besonders nützliche Beobachtung über die Levenshtein -Entfernung machen: Es bildet einen metrischen Raum.
[...]
Angenommen, wir haben für einen Moment zwei Parameter: Abfrage, die Zeichenfolge, die wir in unserer Suche verwenden, und n Die maximale Entfernung kann eine Zeichenfolge aus der Abfrage stammen und trotzdem zurückgegeben werden. Sagen Sie, wir nehmen eine willkürliche Zeichenfolge, testen und vergleichen sie mit Abfrage. Nennen Sie die resultierende Entfernung d. Da wir die Dreiecksungleichheit kennen, müssen alle unsere Ergebnisse höchstens D+n und zumindest DN DN vom Test aufweisen.
[...]
Tests zeigen, dass die Suche mit einem Abstand von 1 Abfragen nicht mehr als 5-8% des Baumes und die Suche mit zwei Fehlern nicht mehr als 17 bis 25% des Baumes-eine erhebliche Verbesserung gegenüber der Überprüfung jedes Knotens!

Bearbeiten: Aber das hilft Ihnen nicht bei Ihrem Problem mit Ihrem ("12 Bird Road, APT 6" und "12 Bird Rd. #6"). Nur mit Ihrem Brute-Force-Vergleich.

Aufgrund der Art des Levenshtein -Algorithmus (insbesondere der Tatsache, dass es sich um einen Vergleich zwischen zwei Zeichenfolgen handelt) kann ich nicht sehen, wie dies möglich ist.

Sie können natürlich die Anzahl der Vergleiche reduzieren, indem Sie zuerst einige grundlegende Anpassungsanforderungen durchführen, aber dies ist nicht der Umfang dessen, was Sie verlangen.

Als (möglicherweise möglicherweise irrelevante) Option könnten Sie immer so etwas verwenden soundex Dadurch werden Sie die Stringwerte vorab vorarbeiten. (Ich glaube, Sie können es auch direkt in MySQL verwenden.)

Sie können sie basierend auf SoundExes gruppieren und dann die Vergleiche auf die nächsten N -Fälle beschränken ...

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

Dann durch die Schlüssel von $ Mashed iterieren.

C.

Wenn Sie finden möchten alle Ähnliche Werte müssen alle Elemente mit allen anderen vergleichen. Die Auswahl der richtigen Array -Funktionen wird jedoch erheblich beschleunigt. Hier ist ein kurzes Beispiel (das Ergebnisarray 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--;
}

In Anbetracht des Problems sehe ich keinen anderen Weg, als jede Adresse mit jeder anderen Adresse zu vergleichen, wenn Sie verwenden möchten Lehvenstein -Entfernung.

Zunächst sollten Sie die Adresse normalisieren, Abkürzungen beseitigen usw.

  • Ave -> Avenue
  • Rd. -> Straße

Sie könnten eine feste Entfernung von Max Lehvenstein haben ( N ) für ähnliche Adressen.

In diesem Fall könnten Sie den Lehvenstein -Algorithmus abbrechen, wenn Sie sicher sind, dass die Bearbeitungsentfernung für aktuelles Adresspaar größer ist als N. Dafür müssen Sie eine benutzerdefinierte Version des Lehvenstein -Algorithmus schreiben. Dies macht den Algorithmus etwas schneller.

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

$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 />";
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top