Ich denke, Sie können nicht vermeiden, das Array durchzulaufen, da die Funktion levenstein () nur Strings und kein Array als Eingabe akzeptiert.
Sie können etwas tun wie:
%Vor%Ich habe 5000, manchmal mehr, Straßenadressstrings 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 übergeordnete Ziel besteht darin, ähnliche Einträge zu finden (und Dubletten zu eliminieren), basierend auf von Benutzern eingegebenen Straßenadressen.
Ich denke, eine bessere Möglichkeit, ähnliche Adressen zu gruppieren, wäre:
Erstellen Sie eine Datenbank mit zwei Tabellen - eine für die Adresse (und eine ID), eine für die Soundexte von Wörtern oder Literalzahlen in der Adresse (mit dem Fremdschlüssel der Adressentabelle)
Geben Sie in Großbuchstaben die Adresse ein, ersetzen Sie alles andere als [A-Z] oder [0-9] durch ein Leerzeichen
Teilen Sie die Adresse nach dem Leerzeichen, berechnen Sie den soundex jedes 'Wortes', lassen Sie alles mit nur Ziffern unverändert und speichern Sie es in der Soundexes-Tabelle mit dem Fremdschlüssel der Adresse, mit der Sie begonnen haben
finde für jede Adresse (mit id $ target) die ähnlichsten Adressen:
%Vor%Berechnen Sie den Unterschied zwischen Ihrer Quelladresse und den letzten wenigen Werten, die von der Abfrage zurückgegeben werden.
(das Ausführen von Operationen auf großen Arrays ist in Datenbanken oft schneller)
Sie könnten sie basierend auf Soundexten gruppieren und dann die Vergleiche auf die nächsten N Fälle beschränken ...
%Vor%Dann iteriere durch die Schlüssel von $ pashed.
C.
Aufgrund der Natur des Levenshtein-Algorithmus (insbesondere die Tatsache, dass es ein Vergleich zwischen zwei Strings ist), kann ich nicht sehen, wie das möglich ist.
Sie könnten natürlich die Anzahl der Vergleiche reduzieren, indem Sie zuerst einige grundlegende Anforderungen erfüllen, aber dies gehört nicht zu dem, was Sie fragen.
Als (möglicherweise irrelevante) Option könnten Sie immer etwas wie %code% verwenden, mit dem Sie die Zeichenfolgenwerte vorberechnen könnten. (Sie können es auch direkt in MySQL verwenden, glaube ich.)
Wenn Sie alle ähnlichen 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 (das Ergebnis-Array könnte besser gewesen sein):
%Vor%Wenn Sie ein Problem haben, sehe ich keinen anderen Weg, als jede Adresse mit jeder anderen Adresse zu vergleichen, wenn Sie Lehvenstein distance .
Zuallererst sollten Sie die Adressaten normalisieren, Abkürzungen loswerden.
Sie könnten eine feste maximale Lehvenstein-Distanz ( N ) für ähnliche Adressen haben.
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 sehen und sofort entscheiden, dass sie nicht ähnlich sind.
Sie können einen bk-tree verwenden, um die Suche / den Vergleich zu beschleunigen.
Ссылка sagt:
Nun können wir eine besonders nützliche Beobachtung über die Levenshtein-Distanz machen: Sie bildet einen metrischen Raum.
[...]
Nehmen wir für einen Moment, wo wir zwei Parameter, Abfrage der Zeichenfolge wir bei unserer Suche verwenden, und n der maximale Abstand kann eine Zeichenfolge 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. Weil wir die Dreiecksungleichung hält wissen, sind alle unsere Ergebnisse müssen höchstens Abstand d haben + n und mindestens Abstand d-n-Test.
[...]
Tests zeigen, dass die Suche mit einem Abstand von 1 Abfragen nicht mehr als 5-8% des Baums und die Suche mit zwei Fehler Abfragen nicht mehr als 17-25% des Baumes - eine erhebliche Verbesserung gegenüber der Überprüfung jedes Knotens!
edit: Aber das hilft dir nicht mit deinem ("12 Bird Road, Apt 6" und "12 Bird Rd. # 6") Problem. Nur mit deinem Brute-Force-m * n-Vergleich.