Cum pot face o potrivire neclară a numelor de companii în MYSQL cu PHP pentru autocompletare? (Programare, Mysql, String, Potrivire, Căutare Fuzzy)

AFG a intrebat.

Utilizatorii mei vor importa prin tăiere și lipire un șir mare care va conține nume de companii.

Am o bază de date MYSQL existentă și în creștere cu nume de companii, fiecare cu un company_id unic.

Vreau să pot analiza șirul și să atribui fiecăruia dintre numele de companii introduse de utilizator o potrivire neclară.

În momentul de față, efectuarea unei potriviri directe a șirului este, de asemenea, lentă. ** Va fi mai rapidă indexarea Soundex? Cum pot oferi utilizatorului câteva opțiuni în timp ce tastează? **

De exemplu, cineva scrie:

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

Am găsit următoarele discuții care par similare cu această întrebare, dar posterul nu a aprobat și nu sunt sigur dacă cazul lor de utilizare este aplicabil:

Cum să găsiți cea mai bună potrivire fuzzy pentru un șir de caractere într-o bază de date mare de șiruri de caractere

Potrivirea numelor de companii inexacte în Java

Comentarii

  • Scuze pentru editarea greșită, am trecut cu vederea al doilea link. –  > Por Tomalak.
  • Răspunsul meu de mai jos va elimina necesitatea unei căutări fuzzy și va oferi o căutare indexată pentru orice nume parțial – verificați-l! –  > Por Rodney P. Barbati.
  • Este o enigmă pentru mine cum de unele funcționalități de bază nu sunt încorporate într-un proiect open source, și chiar produse/companii născute din această cauză (cum ar fi căutarea elastică). –  > Por JorgeGarza.
7 răspunsuri
Tomalak

Puteți începe cu utilizarea SOUNDEX(), , acest lucru va fi probabil suficient pentru ceea ce aveți nevoie (îmi imaginez o casetă de auto-sugestie a alternativelor deja existente pentru ceea ce tastează utilizatorul).

Dezavantajele lui SOUNDEX() sunt:

  • incapacitatea sa de a diferenția șirurile mai lungi. Sunt luate în considerare doar primele câteva caractere, șirurile mai lungi care diferă la sfârșit generează aceeași valoare SOUNDEX
  • faptul că prima literă trebuie să fie aceeași, altfel nu veți găsi cu ușurință o potrivire. SQL Server are funcția DIFFERENCE() care vă spune cât de mult se deosebesc două valori SOUNDEX, dar cred că MySQL nu are nimic de acest gen încorporat.
  • Pentru MySQL, cel puțin conform documentația, , SOUNDEX nu funcționează pentru intrările Unicode.

Exemplu:

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

/* all of these return 'M262' */

Pentru nevoi mai avansate, cred că trebuie să vă uitați la distanța Levenshtein (numită și „distanța de editare”) a două șiruri de caractere și să lucrați cu un prag. Aceasta este o soluție mai complexă (=mai lentă), dar permite o mai mare flexibilitate.

Principalul dezavantaj este că aveți nevoie de ambele șiruri pentru a calcula distanța dintre ele. Cu SOUNDEX puteți stoca un SOUNDEX precalculat în tabelul dvs. și puteți compara/sorta/grupa/filtra pe baza acestuia. Cu distanța Levenshtein, s-ar putea să constatați că diferența dintre „Microsoft” și „Nzcrosoft” este de numai 2, dar va fi nevoie de mult mai mult timp pentru a ajunge la acest rezultat.

În orice caz, un exemplu de funcție de distanță Levenshtein pentru MySQL poate fi găsit la adresa codejanitor.com: Levenshtein Distance as a MySQL Stored Function (10 februarie 2007).

Comentarii

  • Folosiți ambele; selectați un set inițial de rezultate folosind soundex, apoi sortați și, opțional, filtrați rezultatele după distanța Levenshtein. –  > Por Daniel Cassidy.
  • Tot trebuie rezolvată „problema primei litere”. Dacă începeți să tastați cu o literă greșită, rezultatele SOUNDEX vor fi mult greșite. –  > Por Tomalak.
  • Nu mă aștept să fie nevoie de filtrare – nu mă aștept să existe prea multe potriviri potențiale, ci mai degrabă prea puține (sau nu cele potrivite). Atunci nu ajută la nimic eliminarea unora dintre ele. –  > Por dkretz.
  • Linkul de mai sus către Distanța Levenshtein MySQL este rupt acum. Iată un link actual: artfulsoftware.com/infotree/queries.php#552 –  > Por Mike Gorski.
  • Distanța Levenshtein este un algoritm bun. Dar nu este susceptibil de a fi optimizat de niciun fel de index, așa cum ar putea fi SOUNDEX sau (dublu) Metaphone. Deci, dacă baza de date a companiei dumneavoastră este mare, schema de sugestii de potrivire caracter cu caracter ar putea deveni foarte costisitoare. –  > Por O. Jones.
Brânză Daneză

SOUNDEX este un algoritm OK pentru acest lucru, dar au existat progrese recente pe această temă. A fost creat un alt algoritm numit Metaphone, care a fost revizuit ulterior în algoritmul Double Metaphone. Personal, am folosit implementarea Java apache commons a metafonului dublu și este personalizabilă și precisă.

Au implementări în o mulțime de alte limbi pe pagina wikipedia pentru el, de asemenea. La această întrebare s-a răspuns, dar dacă găsiți oricare dintre problemele identificate cu SOUNDEX care apar în aplicația dumneavoastră, este bine de știut că există opțiuni. Uneori poate genera același cod pentru două cuvinte foarte diferite. Metafonul dublu a fost creat pentru a ajuta la rezolvarea acestei probleme.

Furat de pe wikipedia: http://en.wikipedia.org/wiki/Soundex

Ca răspuns la deficiențele algoritmului Soundex, Lawrence Philips a dezvoltat algoritmul Metaphone în același scop. Ulterior, Philips a dezvoltat o îmbunătățire a Metaphone, pe care a numit-o Double-Metaphone. Double-Metaphone include un set de reguli de codificare mult mai mare decât predecesorul său, gestionează un subset de caractere nelatine și returnează o codificare primară și una secundară pentru a ține cont de diferitele pronunții ale unui singur cuvânt în limba engleză.

În partea de jos a paginii cu metafonul dublu, se găsesc implementările acestuia pentru toate tipurile de limbaje de programare: http://en.wikipedia.org/wiki/Double-Metaphone

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

Comentarii

  • Implementarea Metafonului dublu MySQL se mută la: atomodo.com/code/double-metaphone –  > Por Andrew.
  • vă rugăm să rețineți că levenshtein este foarte, foarte greu pentru o bază de date, dacă nu sunteți capabil să normalizați datele, nu este o opțiune bună pentru un site cu utilizare medie. –  > Por renevdkooi.
  • Funcția dm oferă rezultate precise, ca exemplu, vă rugăm să vedeți rezultatul celor două WHER-uri de mai jos WHERE dm(first_name) = dm(‘james’) WHERE SOUNDEX(first_name) = SOUNDEX(‘james’) –  > Por Umair.
Derren

În primul rând, aș dori să adaug că ar trebui să fiți foarte atenți atunci când folosiți orice formă de algoritm de potrivire fonetică/fuzzy, deoarece acest tip de logică este exact asta, fuzzy sau, mai simplu spus, potențial inexactă. Acest lucru este valabil mai ales atunci când este folosit pentru a potrivi numele companiilor.

O abordare bună este să căutați o coroborare a altor date, cum ar fi adresele, codurile poștale, numerele de telefon, coordonatele geografice etc. Acest lucru va ajuta la confirmarea probabilității ca datele dvs. să corespundă cu exactitate.

Există o gamă întreagă de aspecte legate de corelarea datelor B2B, prea multe pentru a fi abordate aici; am scris mai multe despre Potrivirea numelui companiei pe blogul meu (de asemenea, un articol actualizat), dar, în rezumat, principalele aspecte sunt:

  • Nu este util să se analizeze întregul șir de caractere, deoarece cea mai importantă parte a denumirii unei companii nu se află neapărat la începutul acesteia, de exemplu, „The Proctor and Gamble Company” sau „United States FederalReserve”.
  • Abrevierile sunt frecvente în denumirile societăților, de exemplu HP, GM, GE, P&G, D&B etc..
  • Unele companii își scriu în mod deliberat numele în mod incorect ca parte a brandingului lor și pentru a se diferenția de alte companii.

Potrivirea datelor exacte este ușoară, dar potrivirea datelor neexacte poate necesita mult mai mult timp și v-aș sugera să luați în considerare modul în care veți valida potrivirile neexacte pentru a vă asigura că acestea sunt de o calitate acceptabilă.

Înainte de a construi Match2Lists.com, obișnuiam să petrecem o cantitate nesănătoasă de timp validând potrivirile neclare. În Match2Lists am încorporat un instrument puternic de vizualizare care ne permite să revizuim corespondențele neexacte, ceea ce s-a dovedit a fi o adevărată schimbare în ceea ce privește validarea corespondențelor, reducându-ne costurile și permițându-ne să furnizăm rezultate mult mai rapid.

Mult succes!!!

dkretz

Iată un link către discuția din php despre funcțiile soundex în mysql și php. Aș începe de acolo, apoi aș extinde în alte cerințe nu atât de bine definite ale tale.

Referința ta face referire la metodologia Levenshtein pentru potrivire. Două probleme. 1. Este mai potrivită pentru măsurarea diferenței dintre două cuvinte cunoscute, nu pentru căutare. 2. Se discută despre o soluție concepută mai degrabă pentru a detecta lucruri precum erorile de corectură (folosind „Levenshtien” pentru „Levenshtein”) decât erorile de ortografie (în cazul în care utilizatorul nu știe cum se scrie, să zicem „Levenshtein” și tastează „Levinstein”. De obicei, asociez acest lucru cu căutarea unei fraze într-o carte mai degrabă decât a unei valori cheie într-o bază de date.

EDIT: Ca răspuns la comentariul…

  1. 1. Poți cel puțin să-i faci pe utilizatori să pună numele companiilor în mai multe căsuțe de text; 2. sau să folosești un delimitator de nume lipsit de ambiguitate (să zicem backslash); 3. să lași la o parte articolele („The”) și abrevierile generice (sau poți filtra pentru acestea); 4. să folosești un nume care să nu fie ambiguu. Scoateți spațiile și potriviți și pentru asta (deci Micro Soft => microsoft, Bare Essentials => bareessentials); 5. Filtrați punctuația; 6. Faceți căutări „OR” pe cuvinte („bare” OR „essentials”) – oamenii vor omite inevitabil unul sau altul uneori.

Testați ca nebunii și folosiți bucla de feedback de la utilizatori.

Comentarii

  • Ce cerințe suplimentare ar fi utile? –  > Por AFG.
  • +1 pentru „Levenshtein este conceput pentru a detecta erorile de corectare mai degrabă decât cele de ortografie” – –  > Por jrharshath.
Rodney P. Barbati

Acest răspuns are ca rezultat căutarea indexată a aproape oricărei entități care utilizează o intrare de 2 sau 3 caractere sau mai multe.

Practic, creați un tabel nou cu 2 coloane, cuvânt și cheie. Executați un proces pe tabelul original care conține coloana în care se va face o căutare fuzzy. Acest proces va extrage fiecare cuvânt individual din coloana originală și va scrie aceste cuvinte în tabelul de cuvinte împreună cu cheia originală. În timpul acestui proces, cuvintele care apar frecvent, cum ar fi „the”, „and”, etc., trebuie eliminate.

Apoi creăm mai mulți indici în tabelul de cuvinte, după cum urmează…

  • Un index normal, minuscul, pentru cuvântul + cheie
  • Un index pentru al doilea până la al cincilea caracter + cheie
  • Un index pentru al treilea până la al șaselea caracter + cheie

    Alternativ, creați un index SOUNDEX() pe coloana word.

Odată ce acest lucru este pus în aplicare, luăm orice intrare a utilizatorului și căutăm folosind cuvântul normal = intrare sau LIKE intrare%. Nu facem niciodată un LIKE %input, deoarece căutăm întotdeauna o potrivire pentru oricare dintre primele 3 caractere, care sunt toate indexate.

În cazul în care tabelul original este masiv, ați putea împărți tabelul de cuvinte pe bucăți de alfabet pentru a vă asigura că datele introduse de utilizator sunt restrânse imediat la rândurile candidate.

longneck

cea mai bună funcție pentru potrivirea fuzzy este levenshtein. este folosită în mod tradițional de verificatoarele ortografice, așa că ar putea fi calea de urmat. există un UDF pentru aceasta disponibil aici: http://joshdrew.com/

Un dezavantaj al utilizării levenshtein este că nu se va scala foarte bine. o idee mai bună ar fi să aruncați întregul tabel într-un fișier dicționar personalizat de verificare ortografică și să faceți sugestia de la nivelul aplicației în loc de nivelul bazei de date.

ErJab

Deși întrebarea se referă la modul de a face căutări fuzzy în MySQL, aș recomanda să luați în considerare utilizarea unui motor de căutare fuzzy separat (aka toleranță la greșeli de scriere) pentru a realiza acest lucru. Iată câteva motoare de căutare de luat în considerare:

  • ElasticSearch (sursă deschisă, are o tonă de caracteristici și, prin urmare, este, de asemenea, complex de operat)
  • Algolia (Proprietar, dar are o documentație excelentă și este foarte ușor de pus în funcțiune)
  • Typesense (sursă deschisă, oferă aceeași funcție de căutare neclară ca Algolia)