Come faccio a fare un fuzzy match di nomi di società in MYSQL con PHP per il completamento automatico?

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

Domanda

Ai miei utenti di importare tramite tagliare e incollare una stringa che conterrà i nomi di società.

Ho esistente e crescente MYSQL database di nomi di aziende, ciascuna con un unico company_id.

Voglio essere in grado di analizzare attraverso la stringa e di assegnare a ciascun utente attribuirsi nomi di società una corrispondenza fuzzy.

Adesso, solo facendo una normale stringa di corrispondenza, è anche lento.** Si Soundex di indicizzazione per essere più veloce?Come posso dare all'utente alcune opzioni di battitura?**

Per esempio, qualcuno scrive:

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

Ho trovato il seguente thread che sembrano simili a questa domanda, ma il poster non ha approvato e non sono sicuro se il loro caso è applicabile:

Come trovare la migliore corrispondenza fuzzy per una stringa in una stringa di grandi dimensioni database

Corrispondenza esatta nomi di società in Java

È stato utile?

Soluzione

Si può iniziare con l'utilizzo di SOUNDEX() , questo sarà probabilmente fare per quello che vi serve ( mi immagino una scatola di auto-suggestione di alternative già esistenti per ciò che l'utente sta scrivendo).

Gli inconvenienti di <=> sono:

  • la sua incapacità di distinguere le stringhe più lunghe. Solo i primi caratteri sono presi in considerazione, stringhe più lunghe che divergono alla fine generano lo stesso valore SOUNDEX
  • il fatto che la prima lettera deve essere la stessa o non sarà trovare una corrispondenza con facilità. SQL Server ha funzione DIFFERENZA () per dirvi quanto due valori SOUNDEX sono a parte, ma credo che MySQL non ha nulla del genere costruito in.
  • per MySQL, almeno secondo la documentazione , SOUNDEX è rotto per l'input Unicode

Esempio: 

SELECT SOUNDEX('Microsoft')
SELECT SOUNDEX('Microsift')
SELECT SOUNDEX('Microsift Corporation')
SELECT SOUNDEX('Microsift Subsidary')

/* all of these return 'M262' */

Per esigenze più avanzate, penso che hai bisogno di guardare il Levenshtein distanza (chiamato anche "edit distance") di due stringhe e lavorare con una soglia. Questo è il (= lento) soluzione più complessa, ma consente una maggiore flessibilità.

svantaggio principale è che è necessario entrambe le stringhe per calcolare la distanza tra loro. Con SOUNDEX è possibile memorizzare un SOUNDEX pre-calcolata nella tabella e confrontare / tipo / group / filtro su questo. Con la distanza Levenshtein, si potrebbe scoprire che la differenza tra "Microsoft" e "Nzcrosoft" è solo 2, ma ci vorrà molto più tempo per arrivare a questo risultato.

In ogni caso, una funzione di distanza Levenshtein esempio per MySQL può essere trovato a codejanitor.com :. Levenshtein distanza come MySQL Stored Function (10 feb 2007)

Altri suggerimenti

SOUNDEX è un algoritmo OK per questo, ma ci sono stati recenti progressi su questo argomento. Un altro algoritmo è stato creato chiamato il Metaphone, ed è stato successivamente rivisto per un algoritmo Doppio Metaphone. Personalmente ho usato il Java comuni apache realizzazione del doppio metaphone ed è personalizzabile e preciso.

Hanno implementazioni in un sacco di altre lingue sulla pagina di Wikipedia per esso, anche. Questa domanda è stato risposto, ma si dovrebbe trovare nessuno dei problemi individuati con il SOUNDEX che appaiono nella vostra applicazione, è bello sapere che ci sono opzioni. A volte può generare lo stesso codice per due parole molto diverse. Doppia metaphone è stato creato per aiutare a prendersi cura di questo problema.

Stolen da wikipedia: http://en.wikipedia.org/wiki/Soundex

  

In risposta alle carenze del   algoritmo Soundex, Lawrence Philips   sviluppato l'algoritmo Metaphone per   lo stesso scopo. Philips tardi   sviluppato un miglioramento Metaphone,   che chiamò doppio Metaphone.   Fare doppio Metaphone include una più   regola di codifica maggiore impostato rispetto al suo   predecessore, gestisce un sottoinsieme di   caratteri non latini, e restituisce un   primaria e secondaria per una codifica   conto per le diverse pronunce   di una sola parola in inglese.

Nella parte inferiore della pagina doppia metaphone, hanno le implementazioni di esso per tutti i tipi di linguaggi di programmazione: http://en.wikipedia.org/wiki/Double-Metaphone

Python e MySQL applicazione: https://github.com/AtomBoy/double-metaphone

In primo luogo, vorrei aggiungere che si dovrebbe essere molto attenti quando si utilizza qualsiasi forma di algoritmo fonetico / Fuzzy Matching, in quanto questo tipo di logica è esattamente questo, Fuzzy o per dirla più semplicemente; potenzialmente impreciso. Particolarmente vero quando viene utilizzato per la corrispondenza nomi di società.

Un buon approccio è quello di cercare conferme da altri dati, ad esempio informazioni sugli indirizzi, codici postali, numeri di tel, Geo Coordinate ecc Ciò contribuirà a confermare la probabilità dei dati in fase di precisione abbinate.

Ci sono tutta una serie di questioni relative alla dati B2B paritarie troppi per essere affrontati qui, ho scritto più su Nome Azienda matching nel mio blog, ma in sintesi i punti chiave sono:

  • Guardando l'intera stringa è inutile come la parte più importante di un nome di società non è necessariamente all'inizio della Società Nome. vale a dire ‘The Procter & Gamble Company’ o ‘federale degli Stati Uniti Riserva ‘
  • abbreviazioni sono comuni in Società Nomi cioè HP, GM, GE, P & G, D & B ecc ..
  • Alcune aziende deliberatamente scrivere i loro nomi in modo non corretto come parte di il loro marchio e di differenziarsi da altre aziende.

corrispondenza dati esatti è facile, ma corrispondenti dati non esatti può essere molto più tempo e vorrei suggerire che si dovrebbe considerare come sarà convalidando le partite non esatte per accertarsi che siano di qualità accettabile.

Prima abbiamo costruito Match2Lists.com, abbiamo usato per spendere una quantità malsana di tempo convalidare fuzzy match. In Match2Lists abbiamo incorporato un potente strumento di visualizzazione che ci permette di rivedere le partite non esatte, questo si è rivelato un punto di svolta vero e proprio gioco in termini di validazione partita, riducendo i costi e che ci permette di fornire risultati molto più rapidamente.

Buona fortuna !!

Ecco un link alla discussione php delle funzioni soundex in MySQL e PHP. Mi piacerebbe iniziare da lì, poi espandersi in altri tuoi requisiti non-così-ben definite.

I suoi riferimenti di riferimento della metodologia Levenshtein per la corrispondenza. Due problemi. 1. E 'più appropriato per misurare la differenza tra due parole conosciute, non per la ricerca. 2. Si discute una soluzione progettata più per rilevare le cose come impermeabilizzazione errori (utilizzando "Levenshtien" per "Levenshtein") piuttosto che gli errori di ortografia (in cui l'utente non sa come si scrive, dire "Levenshtein" e tipi di "Levinstein" . io di solito associo con ricerca di una frase in un libro piuttosto che un valore chiave in un database.

EDIT: In risposta al commento -

  1. Si può ottenere almeno gli utenti di mettere i nomi di società in più caselle di testo; 2. o utilizzare un delimitatore nome unambigous (diciamo backslash); 3. lasciare fuori gli articoli ( "I") e abbreviazioni generiche (o è possibile filtrare per questi); 4. Squoosh gli spazi fuori e incontro anche per questo (così Micro soft => Microsoft, Introduzione Informazioni => bareessentials); 5. Filtra la punteggiatura; 6. Do "OR" Ricerche di parole ( "nude" OR "essenziali") - le persone lasceranno inevitabilmente uno o l'altro fuori a volte
    2. .

Prova come un matto e utilizzare l'anello di retroazione da parte degli utenti.

la funzione migliore per corrispondenza fuzzy è Levenshtein. è tradizionalmente usato dai correttori ortografici, in modo che potrebbe essere la strada da percorrere. c'è un'UDF per esso disponibili qui: http://joshdrew.com/

Lo svantaggio di utilizzare levenshtein è che non scala molto bene. una migliore idea potrebbe essere quella di scaricare l'intera tabella in un file dizionario personalizzato correttore ortografico e fare il suggerimento dalla vostra applicazione livello invece del livello di database.

Questa risposta risultati di ricerca indicizzata di quasi qualsiasi entità che utilizza l'ingresso di 2 o 3 o più caratteri.

In sostanza, creare una nuova tabella con 2 colonne, parola chiave.Eseguire un processo sulla tabella originale contenente la colonna fuzzy cercato.Questo processo consentirà di estrarre ogni singola parola dalla colonna originale e scrivo queste parole la tabella di word con la chiave originale.Durante questo processo, che si verificano comunemente parole come 'la','e', ecc dovrebbe essere scartato.

Abbiamo quindi creare diversi indici sulla tabella di word, come segue...

  • Un normale, minuscolo indice in parola + chiave
  • Un indice sul 2 al 5 ° carattere + chiave

  • Un indice su 3 al 6 caratteri + chiave

    In alternativa, creare un SOUNDEX() indice sulla parola di colonna.

Una volta che questo è a posto, qualsiasi input dell'utente e di ricerca utilizzando la parola normale = input o COME input%.Non facciamo mai una COME %di input come noi sono sempre alla ricerca per una partita su uno dei primi 3 caratteri, che sono tutti indicizzati.

Se la tabella originale è enorme, si potrebbe partizione della tabella di word da blocchi di alfabeto per garantire l'input dell'utente viene ridotto a candidato righe immediatamente.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top