Wie mache ich ein fuzzy-match von Unternehmens-Namen in MYSQL mit PHP für auto-complete?

Meine Benutzer importieren werden durch Ausschneiden und einfügen eine große Zeichenfolge, enthalten Sie die Namen der Unternehmen.

Ich habe eine bestehende und weiter wachsende MYSQL-Datenbank mit Firmen-Namen, die jeweils mit einer einzigartigen company_id.

Ich möchte in der Lage sein zu analysieren, die durch den string und weisen Sie jedem der vom Benutzer eingegebene Firmennamen ein fuzzy-match.

Recht jetzt, nur tun, eine straight-up-string-match, ist auch langsam. * * * Soundex-Indexierung schneller sein? Wie kann ich dem Benutzer einige Optionen, wie Sie Tippen? **

Zum Beispiel, jemand schreibt:

Microsoft -> Microsoft 
Bare Essentials -> Bare Escentuals 
Polycom, Inc. -> Polycom

Habe ich die folgenden threads, die ähnlich zu sein scheinen, auf diese Frage, aber das Plakat nicht genehmigt hat und ich bin mir nicht sicher, ob Ihre Verwendung-Fall anwendbar ist:

So finden Sie die beste fuzzy-match für einen string in einen großen string-Datenbank

Passende ungenau Unternehmens-Namen in Java

Sorry für mis-Bearbeitung, übersah ich den zweiten link.
Unten meine Antwort eliminiert die Notwendigkeit für eine fuzzy-Suche und werden indiziert, Suche nach einem beliebigen Teil des namens - check it out!

InformationsquelleAutor AFG | 2008-12-15

50

Können Sie beginnen, mit SOUNDEX(), dies wird wahrscheinlich nicht für, was Sie brauchen (Bild ich mir ein auto-suggestion-box der bereits bestehenden alternativen für das, was der Benutzer eingibt).

Nachteile SOUNDEX() sind:
- seine Unfähigkeit zu differenzieren, die mehr Saiten. Nur die ersten Zeichen berücksichtigt werden, längere Zeichenfolgen, die abweichen, am Ende generieren, die den gleichen SOUNDEX-Wert
- die Tatsache, das der erste Buchstabe muss gleich sein oder Sie wird nicht finden ein Spiel leicht. SQL Server hat den UNTERSCHIED () - Funktion, um Ihnen zu sagen, wie viel zwei SOUNDEX-Werte auseinander liegen, aber ich glaube, MySQL hat nichts von dieser Art gebaut.
- für MySQL, zumindest nach die docs, SOUNDEX ist gebrochen für die unicode-Eingabe
Beispiel:
```
SELECT SOUNDEX('Microsoft')
SELECT SOUNDEX('Microsift')
SELECT SOUNDEX('Microsift Corporation')
SELECT SOUNDEX('Microsift Subsidary')

/* all of these return 'M262' */
```
Für weitere Anforderungen, ich denke, Sie müssen sich auf die Die Levenshtein-Distanz (auch als "edit-distance") von zwei strings und arbeiten mit einem Schwellenwert. Dies ist die komplexere (=langsamer) Lösung, aber es ermöglicht eine größere Flexibilität.

Größte Nachteil ist, dass Sie brauchen beide strings zur Berechnung der Entfernung zwischen Ihnen. Mit SOUNDEX können Sie speichern eine vor-berechnete SOUNDEX-in Ihre Tabelle und vergleichen/Sortieren/gruppieren/filtern. Mit der Levenshtein-Distanz, könnten Sie feststellen, dass der Unterschied zwischen "Microsoft" und "Nzcrosoft" ist nur 2, aber es wird viel mehr Zeit, um kommen zu diesem Ergebnis.

In jedem Fall, ein Beispiel für die Levenshtein-Distanz-Funktion für MySQL finden Sie unter codejanitor.com: die Levenshtein-Distanz als MySQL Gespeicherten Funktion (Feb. 10th, 2007).

Beide verwenden; wählen Sie einen ersten Satz von Ergebnissen, die mit soundex, dann Sortieren und filtern die Ergebnisse durch die Levenshtein-Distanz.
Immer noch der "erste Brief-problem" muss sich gekümmert werden. Wenn Sie mit der Eingabe beginnen mit dem falschen Buchstaben, die die SOUNDEX-Ergebnisse wird Weg sein.
Ich erwarte nicht, dass die Filterung benötigt werden - ich erwarte nicht, gibt es zu viele mögliche Treffer, eher nicht genug (oder nicht die richtigen). Dann ist es nicht helfen, zu beseitigen einige von Ihnen.
Vielleicht. Wenn die Anzahl der Optionen begrenzt ist, und ein Benutzer eine Reine drop-down-box, SOUNDEX ohne weitere Komplikationen ausreichen.
Die Levenshtein-Distanz ist eine feine Algorithmus. Aber es ist nicht anfällig zu sein, optimiert durch jede Art von index, wie SOUNDEX oder (double) Metaphone sein könnte. Also, wenn Ihr Unternehmen die Datenbank groß ist Ihr Zeichen-für-Zeichen-match-Vorschlagswesen kann sehr teuer werden.

InformationsquelleAutor Tomalak
22

SOUNDEX ist ein OK-Algorithmus für diese, aber es gab in letzter Zeit Fortschritte auf diesem Thema. Ein anderer Algorithmus erstellt wurde namens Metaphone, und es wurde später überarbeitet, um eine Double-Metaphone-Algorithmus. Ich habe persönlich verwendet das java-apache-commons-Umsetzung von double metaphone und es ist anpassbar und präzise.

Haben Sie Implementierungen in viele andere Sprachen auf der wikipedia-Seite für Sie zu. Diese Frage beantwortet worden ist, aber sollten Sie irgendwelche der festgestellten Probleme mit der SOUNDEX-erscheint in Ihre Anwendung, es ist schön zu wissen, gibt es Möglichkeiten. Manchmal kann es erzeugen den gleichen code für zwei wirklich unterschiedliche Wörter. Double metaphone wurde geschaffen, um zu helfen, kümmern sich um das problem.

Geklaut aus der wikipedia: http://en.wikipedia.org/wiki/Soundex

Als Reaktion auf Mängel in der
Soundex-Algorithmus, Lawrence Philips
entwickelt der Metaphone-Algorithmus für
den gleichen Zweck. Philips später
entwickelt für eine Verbesserung Metaphone,
die er als Double-Metaphone.
Double-Metaphone-enthält eine viel
größere Codierung Regelwerk als seine
Vorgänger, Griffe eine Teilmenge von
nicht-lateinische Zeichen, und gibt ein
primäre und sekundäre Kodierung
Konto für die unterschiedliche Aussprache
ein einziges Wort in Englisch.

An der Unterseite des double-metaphone-Seite haben Sie die Implementierungen der es für alle Arten von Programmiersprachen: http://en.wikipedia.org/wiki/Double-Metaphone

Python & MySQL-Implementierung: https://github.com/AtomBoy/double-metaphone

Die MySQL-Double-Metaphone-Umsetzung bewegt: atomodo.com/code/double-metaphone
bitte beachten Sie, dass die levenshtein-ist sehr sehr schwer auf eine Datenbank, es sei denn, Sie sind in der Lage, um die Daten zu normieren, es ist nicht eine gute option für ein medium-heavy Website verwendet.
dm-Funktion liefert genaue Ergebnisse, als Beispiel schauen Sie sich die Ausgabe von unter zwei WHER, WO dm(Vorname) = dm('Jakobus') WHERE SOUNDEX(first_name) = SOUNDEX('Jakobus')

InformationsquelleAutor Cheese Daneish
9

Erstens, ich möchte hinzufügen, dass Sie sollten sehr vorsichtig sein, wenn Sie irgendeine form von Phonetischen/Fuzzy-Matching-Algorithmus, der diese Art von Logik ist genau das, Fuzzy-oder, um es deutlicher zu sagen einfach; möglicherweise ungenau. Vor allem, wenn Sie für die passenden Firmennamen.

Ist ein guter Ansatz ist die Suche nach Bestätigung von anderen Daten, wie Adressdaten, Postleitzahlen, Telefon-Nummern, Geo-Koordinaten usw.. Dies wird helfen, bestätigen die Wahrscheinlichkeit, dass Ihre Daten genau abgestimmt.

Gibt es eine ganze Reihe von Fragen im Zusammenhang mit B2B-Daten-Matching-zu viele, um Sie hier angesprochen werden, die ich geschrieben habe, mehr über Name Des Unternehmens Zusammenbringen in meinem blog, aber in der Zusammenfassung die wichtigsten Punkte sind:
- Dass der gesamte string ist wenig hilfreich, da der wichtigste Teil
  der Name des Unternehmens ist nicht notwendigerweise an den Beginn des Unternehmens
  Name. D. H. 'Der Proctor-und-Gamble-Unternehmen "oder" United States Federal
  Naturschutzgebiet"
- Abkürzungen sind gemeinsame Stelle im Firmennamen d.h. HP, GM, GE, P&G,
  D&B etc..
- Einige Firmen, die absichtlich Zauber Ihre Namen fälschlicherweise als Teil der
  Ihr branding und heben sich von anderen Unternehmen.
Passenden genauen Daten ist easy, aber passende nicht-die genauen Daten kann sehr viel mehr Zeit in Anspruch und ich würde vorschlagen, dass Sie sollten betrachten, wie Sie wird die Validierung des nicht-exakten übereinstimmungen, um sicherzustellen, diese sind von akzeptabler Qualität.

Bevor wir gebaut Match2Lists.com wir verbrachten eine ungesunde Menge an Zeit, die Validierung von fuzzy-matches. In Match2Lists wir integriert ein leistungsstarkes Visualisierungs-tool ermöglicht es uns, zu überprüfen, nicht genau übereinstimmt, wird diese erwies sich als ein echter Spiel-wechsler in Bezug auf die übereinstimmung der Validierung, senken unsere Kosten und ermöglichen es uns, Ergebnisse zu erzielen, viel schneller.

Viel Glück!!

InformationsquelleAutor Derren
4

Hier ist ein link auf die php-Diskussion der soundex-Funktionen in mysql und php. Ich würde von dort aus starten, erweitern Sie dann in Ihre anderen nicht-so-gut-definierten Anforderungen.

Ihre Referenz Referenzen die Levenshtein-Methodik für das matching. Zwei Probleme. 1. Es ist besser geeignet für die Messung des Abstands zwischen zwei bekannten Wörter, nicht für die Suche. 2. Es beschreibt eine Lösung entwickelt, mehr zu erkennen, Dinge wie die proofing-Fehler (mit "Levenshtien" für "Levenshtein"), anstatt den Rechtschreibfehler (wobei die Benutzer nicht wissen, wie zu buchstabieren, sagen, "Levenshtein" und Typen in "Levinstein". Ich in der Regel assoziieren es mit der Suche nach einem Satz in einem Buch als ein Schlüssel-Wert in einer Datenbank.

EDIT: In Antwort auf Kommentar--
1. Kann man zumindest bekommen die Benutzer den Namen des Unternehmens in mehrere Textfelder; 2. oder verwenden Sie eine unambigous name Trennzeichen (z.B. backslash); 3. weglassen von Artikeln ("Der") und generischen Abkürzungen (oder können Sie die filter für diese); 4. Squoosh die Räume aus und passen für diesen auch (also Micro Weich => microsoft, Bare Essentials => bareessentials); 5. Filter aus Satzzeichen; 6. Tun "ODER" sucht auf Worte ("bare" ODER "essentials") - Menschen zwangsläufig verlassen die eine oder die andere manchmal aus.
Testen wie verrückt, und verwenden Sie die feedback-Schleife vom Benutzer.

Welche zusätzlichen Anforderungen wären hilfreich?
Hinzugefügt änderungen zu der Antwort oben.
+1 für "die Levenshtein-ist entworfen, um zu erkennen proofing Fehler und nicht als Rechtschreibfehler"

InformationsquelleAutor dkretz
0

die beste Funktion für die fuzzy-matching ist die levenshtein. es ist traditionell verwendet von Rechtschreibkorrektur, so dass möglicherweise der Weg zu gehen. es gibt eine UDF für Sie finden Sie hier: http://joshdrew.com/

den Nachteil levenshtein ist, dass es nicht sehr gut skalieren. eine bessere Idee sein könnte, um einen dump der gesamten Tabelle in eine Rechtschreibprüfung, Benutzerwörterbuch-Datei und führen Sie dem Vorschlag von Ihrem Anwendungsebene statt die Datenbank-Ebene.

InformationsquelleAutor
0

Dieser Antwort ergibt sich in indizierte Suche fast jedem Unternehmen mit Eingabe von 2 oder 3 Zeichen oder mehr.

Im Grunde erstellen Sie eine neue Tabelle mit 2 Spalten, word und Schlüssel. Ausführen eines Prozesses auf der ursprünglichen Tabelle, die die Spalte enthält, werden unscharf gesucht. Dieser Prozess extrahiert jedes einzelne Wort aus der ursprünglichen Spalte und schreiben Sie diese Wörter, um die word-Tabelle zusammen mit den original-Schlüssel. Während dieses Prozesses, der Häufig vorkommende Wörter wie "der", " und " usw. verworfen werden sollte.

Dann erstellen Sie mehrere Indizes auf die word-Tabelle wie folgt...
- Eine normale, klein-index für Wort + - Taste
- Einen index auf die 2. durch 5. Zeichen " + " - Taste
- Einen index auf der 3. durch 6. Buchstabe + Schlüssel
  
  Alternativ erstellen Sie eine SOUNDEX () - index auf die Wort-Spalte.
Einmal in diesem Ort, wir nehmen jede Eingabe und Suche mit normalen word = Eingang oder WIE input -%. Wir machen nie einen WIE eine % - Eingabe, wie wir sind immer auf der Suche, für ein Spiel auf einem der ersten 3 Charaktere, die sind alle indiziert.

Wenn Ihr original-Tabelle ist riesig, Sie könnte die Partitionierung der word-Tabelle von Blöcken von das alphabet, um sicherzustellen, die Eingabe des Benutzers wird eingegrenzt Kandidat Zeilen sofort.

InformationsquelleAutor Rodney P. Barbati

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.