[php/mysql/alg] woorden met typefouten matchen

[marty]

als je bijvoorbeeld bij de kaart van amsterdam op straatnaam gaat zoeken en je maakt een typefout dan geeft ie een aantal mogelijke matches weer.
mijn vraag: hoe doen ze dat
bestaan daar in php of mysql bepaalde functies voor of zul je daar zelf iets voor moeten scripten. En als je zelf aan de slag moet, hoe kan ik dat dan het beste aanpakken? Ik kon er met de search niets over vinden.

[Verwijderd]

wat je bijvoorbeeld zou kunnen doen in SQL is met LIKE werken en tussen elke letter een wildcard zetten

maar ik weet niet of dit efficient is ...

[ Voor 18% gewijzigd door Verwijderd op 15-09-2003 02:09 ]

[Verwijderd]

Ik zou beginnen te kijken in de richting van LIKE in MySQL. Bijv. als je zoekt naar "kade": SELECT naam FROM straten WHERE naam LIKE '%kade%'. Dan zal MySQL alle straatnamen die het woord "kade" bevatten returnen. Ook zitten er in PHP 2 functies die een waarde berekenen van hoe het woord klinkt: metaphone() en soundex().

Het ligt er natuurlijk ook maar aan hoe geavanceerd je het wil maken. Bijv. de spellingcorrecties die www.google.com en www.allmusic.com suggereren zijn best wel knap IMO, maar dat is voor de meeste huis tuin en keuken websites niet nodig.

edit: Nog 2 van die functies gevonden .
levenshtein() en similar_text().

[ Voor 20% gewijzigd door Verwijderd op 15-09-2003 02:16 ]

[marty]

Verwijderd schreef op 15 september 2003 @ 02:08:
wat je bijvoorbeeld zou kunnen doen in SQL is met LIKE werken en tussen elke letter een wildcard zetten

maar ik weet niet of dit efficient is ...

dat gaat niet werken. het gaat me er om dat als je bijvoorbeeld philips per ongeluk als filips of phillips schrijft, dat ie dan toch nog philips als mogelijkheid geeft. dat lukt met jouw oplossing niet.

Verwijderd schreef op 15 september 2003 @ 02:10:
Ik zou beginnen te kijken in de richting van LIKE in MySQL. Bijv. als je zoekt naar "kade": SELECT naam FROM straten WHERE naam LIKE '%kade%'. Dan zal MySQL alle straatnamen die het woord "kade" bevatten returnen. Ook zitten er in PHP 2 functies die een waarde berekenen van hoe het woord klinkt: metaphone() en soundex().

hmm...dan zou ik die waarde ook moeten opslaan....kan ik wel eens mee gaan experimenteren. vraag me alleen af of dit ook goed voor nederlandse woorden gaat lukken

Het ligt er natuurlijk ook maar aan hoe geavanceerd je het wil maken. Bijv. de spellingcorrecties die www.google.com en www.allmusic.com suggereren zijn best wel knap IMO, maar dat is voor de meeste huis tuin en keuken websites niet nodig.

waar doel je precies op, want dat is me even niet duidelijk. Het is overigens niet voor een huis tuin en keuken website Het is voor een redelijk serieuze intranet applicatie.

edit: Nog 2 van die functies gevonden .
levenshtein() en similar_text().

daar schiet ik denk ik ook niet veel mee op, want ik moet wel in een database zoeken. kan moelijk alle 10.000+ records er uit trekken en dan een vergelijking gaan doen.

[marty]

Ik heb even zitten klooien met soundex (de minst specifieke van de twee - daarbij metaphone() is gebasseerd op de engelse uitspraak). Heb een aparte kolom aangemaakt en daar alle soundex() waardes in opgeslagen, waar ik dan vervolgens een match op doe. Dat werkt wel aardig...maar niet goed genoeg

Die soundex-functie vind de beginletter nogal belangrijk. Als je iets met een k schrijft zul je bijvoorbeeld alleen maar woorden met een k terugkrijgen. Helaas geen woorden met een c. Nou zou ik daar een uitzondering voor kunnen schrijven, maar dat woorden er onnoemelijk veel. denk bijvoorbeeld ook aan het wel of niet gebruiken van een lidwoord, etc. Dat is dus niet te doen.

zo'n soundex() geeft een string van 4 karakters terug. wat ik ook nog geprobeerd heb is om een query te doen waarbij ik match op de vier mogelijkheden waarbij ik telkens 1 karakter uit die string voor een jokerteken (_) vervang. Maar dan krijg ik gelijk tegen de 300 matches terug, dus dat gaat ook niet werken.

Kortom: ik heb nog steeds geen goede oplossing

Heeft iemand anders misschien nog suggesties?

[slm]

de soundex functie in MySQL werkt in principe prima. Het klopt dat er grote waarde wordt gehecht aan de beginletter, je ziet dat terug in de soundex string die MySQL van de betreffende string maakt.

Je kan dat omzeilen door met substring of replace de beginletter te wijzigen, zodat je bv het volgende resultaat krijgt:
where soundex(naam)="C000" or soundex(naam)="K000"

Er zijn slechts een aantal beginletters die hetzelfde (kunnen!) klinken in het NL dus dat moet geen groot probleem zijn. Let er wel op dat Carel hetzelfde klinkt als Karel, maar dat Cher weer anders klinkt dan Kher.

[marty]

slm schreef op 15 September 2003 @ 12:59:
Je kan dat omzeilen door met substring of replace de beginletter te wijzigen, zodat je bv het volgende resultaat krijgt:
where soundex(naam)="C000" or soundex(naam)="K000"

marty schreef op 15 September 2003 @ 11:42:
Nou zou ik daar een uitzondering voor kunnen schrijven, maar dat worden er onnoemelijk veel. denk bijvoorbeeld ook aan het wel of niet gebruiken van een lidwoord, etc. Dat is dus niet te doen.

Het gaat in mijn geval om bedrijfsnamen in een bestand van ruim 10.000 namen. Soms wordt er een lidwoord toegevoegd, soms wordt er BV voor gezet, soms zelfs een plaatsnaam. Ik schiet met die optie dus niets op.

Bovendien ben ik bang dat die soundex toch te aspecifiek (is dat een goed woord?) wordt als ik 'm 'in het begin van het woord' nog meer ruimte ga gegven. Ik krijg nu namelijk telkens al zo'n 15 resultaten terug (waarvan er echt veel totaal niet lijken)

[MSalters]

Als soundex je niet bevalt kun je hetzelde principe met een eigen algoritme proberen. Lidwoorden of BV/NV/VoF kun je er beter met de hand uitfilteren, net zoals leestekens.

[OkkE]

En als je een extra tabel maakt met de bedrijfsnaam + alle mogelijke opties.

Een idee is dan de tabel in het begin leeg te laten, en wel met die soundex te werken, en op het moment dat een gebruiker het goede bedrijf heeft gevonden zijn zoekterm in die extra database op te slaan zodat je daar de volgende keer op kunt zoeken. Event. ook bij houden hoevaak een bepaald woord is gebruikt.
Dit is in het begin erg veel werk lijkt me, maar ik denk dat je - als je eenmaal die extra tabel hebt - een redelijk goed zoek-systeem hebt.

Zelf nooit echt over zo'n zoekfunctie nagedacht, werd mij te ingewikkeld.

[slm]

marty schreef op 15 September 2003 @ 14:25:
[...]
[...]
Het gaat in mijn geval om bedrijfsnamen in een bestand van ruim 10.000 namen. Soms wordt er een lidwoord toegevoegd, soms wordt er BV voor gezet, soms zelfs een plaatsnaam. Ik schiet met die optie dus niets op.

Bovendien ben ik bang dat die soundex toch te aspecifiek (is dat een goed woord?) wordt als ik 'm 'in het begin van het woord' nog meer ruimte ga gegven. Ik krijg nu namelijk telkens al zo'n 15 resultaten terug (waarvan er echt veel totaal niet lijken)

Ja, als de database niet goed op orde is dan kan soundex daar weinig aan doen... Dit is eerder een invoer/beheer probleem of zelfs een ontwerp foutje in tegenstelling tot een scripting of query probleem.

Je had er voor moeten zorgen dat lidwoorden, toevoegingen als BV/NV/CV e.d. gescheiden worden van de werkelijke naam van het bedrijf, zodat je met een query steeds gelijkwaardige data aan het vergelijken bent.

[marty]

allerst even wat ik zelf nog geprobreerd heb ondertussen:

nog een extra veld aangemaakt en daar de soundex van de bedrijfsnaam-in-omgekeerde-volgorde in opgeslagen - in de hoop het 'begin-van-het-woord-probleem' op te lossen. Dat werd er niet echt heel veel beter op, want leverde veel te veel resultaten op in totaal.
Daarop heb ik het wat specifiekere metaphone() geprobeerd (met beide velden), maar dat werd weer veel te specifiek en er werden eigenlijk exacte matches gevonden

slm schreef op 15 september 2003 @ 20:16:
Ja, als de database niet goed op orde is dan kan soundex daar weinig aan doen... Dit is eerder een invoer/beheer probleem of zelfs een ontwerp foutje in tegenstelling tot een scripting of query probleem.

Je had er voor moeten zorgen dat lidwoorden, toevoegingen als BV/NV/CV e.d. gescheiden worden van de werkelijke naam van het bedrijf, zodat je met een query steeds gelijkwaardige data aan het vergelijken bent.

Ik ben de puinhoop van een paar jaar op amateuristische wijze met access klooien aan het oplossen. Toen ik er bij kwam bestonden al die tabellen en de content al, ik kan daar dus niet zoveel aan doen.
Maar ik had bedrijfsnamen denk ik toch niet zo opgeslagen als jij voorstelt. Er zit een zoeksysteem bij waarbij ze zelf jokers op kunnen geven e.d. Het probleem is dat als ze iets zoeken ze er wel moeite voor doen om het goede bedrijf te vinden (ze weten waar ze naar zoeken immers), maar op het moment dat er iets ingevoerd moet worden springen ze daar nogal laks mee om. vandaar dat ik dit wilde

@MSalters
hmmmm...ik klink nu heeeel lui, maar dat wordt me een beetje teveel werk

ik hoopte eigenlijk op een functie of suggestie waar mee ik wat makkelijker zo'n string kon vergelijken. Ik gebruik het hiervoor dat ik niet wil dat ze bedrijven gaan toevoegen die al bestaan. Dus wil ik gewoon een tussenschermpje maken waarin wordt aangegeven dat de bedrijfsnaam erg veel lijkt op een paar andere namen. Het is dus meer een stukje gemak dan noodzaak. Misschien als ik nog eens heel veel tijd over heb dat ik me in zo'n algoritme ga verdiepen (heb nog nooit zoiets gemaakt namelijk)

@Okke
zie antwoord hierboven...da's dus niet echt van toepassing..

[ Voor 34% gewijzigd door marty op 15-09-2003 21:03 ]