Navigatie

Bedoelde u Groningen? Suggesties bij het zoeken

Wanneer een zoekopdracht geen resultaten terug geeft, kun je de gebruiker een melding voorschotelen om aan te geven dat er niets gevonden is, wellicht gevolgd door een uitgebreid zoekformulier indien aanwezig. Gebruiksvriendelijker is natuurlijk om achter de schermen op zoek te gaan naar suggesties, ofwel resultaten welke lijken op de zoekopdracht, een situatie waar ik tegen aan liep.

In mijn situatie ging het slechts om naamgevingen, laten we zeggen, plaatsnamen. In de naam van een woonplaats is al snel een typefout gemaakt, bijvoorbeeld door te snel typen, onduidelijkheid over het gebruik van een koppelteken, het gebruik van Y of IJ of, in het geval van Friesche plaatsnamen, alternatieve schrijfwijzen wanneer je een uniforme naamgeving wilt hanteren.

Leestekens en reguliere expressies

Het probleem van leestekens in plaatsnamen is eenvoudig te tackelen door gebruik te maken van reguliere expressies binnen SQL-statements. De zoekopdracht van een gebruiker kan door de php functie preg_replace gehaald worden om alle leestekens in de string om te zetten naar een reguliere expressie klasse. Vervolgens kun je de uitkomst meegeven in de WHERE-clausule van de SQL-statement, waarbij je gebruik maakt van een reguliere expressie in SQL (REGEXP), bijvoorbeeld:

$mysqlRegexp = preg_replace( '/[^[:alnum:]]/', '[^[:alnum:]]', "'s-Hertogenbosch" );
$select = "SELECT plaats FROM tabel WHERE LCASE(plaats) REGEXP '^" . strtolower($mysqlRegexp) . "$'";

De plaatsnaam 's Hertogenbosch zal nu zowel gevonden worden bij gebruik van een koppelteken als het gebruik van een spatie. De statement kan naar wens versoepeld worden, bijvoorbeeld om ook gewenste resultaten terug te geven wanneer in bovenstaand voorbeeld de quote niet getypt wordt door de gebruiker.

Gelijkenissen op basis van overeenkomst en klank

PHP heeft verschillende functies om de mate van overeenkomst en verschil te bepalen tussen twee zogenaamde strings (teksten), bijvoorbeeld similar_text() en levenshtein(). Als effici├źntie belangrijk is, kun je voor een oplossing in de SQL-statement kiezen. In dat geval kom je al snel uit bij SOUNDEX, een functie welke ook in php aanwezig is (soundex()) en een klankwaarde terug geeft. Voor engelstalige woorden kan de php functie metaphone() gebruikt worden om de klank zelf te verkrijgen.

De soundex functie

De Soundex functie is vaak standaard ook aanwezig binnen MySQL. Door de soundex van een zoek-string op te halen en deze te vergelijken met de soundex van bijvoorbeeld de plaatsnamen in je tabel, kun je resultaten terughalen die lijken op een zoekopdracht. De soundex-waarde van bijvoorbeeld de strings Amsterdam, Amstrdam en Amstrdm zijn allen gelijk aan elkaar, namelijk A523635.

Dit gegeven kan gebruikt worden om de soundex-waarde van een zoek-string te vergelijken met de soundex-waarde van aanwezige plaatsnamen in een tabel. Helaas zullen de soundex-waarden verschillen wanneer een klinker in een woord weg valt of wanneer klinkers verwisseld worden. De SQL soundex-waarde van Amstedram is bijvoorbeeld A52365, de 6 en 3 staan dus andersom. De string Asterdam levert zelfs een sound-waarde op die korter is, namelijk A23635, Amstedam levert A5235 op. Een daadwerkelijke vergelijking van soundex-waarden zal dus niet praktisch zijn. Sterker nog, wanneer de eerste letter afwijkt van het bedoelde, zal het eerste karakter van de soundex-waarde geheel verschillend zijn.

Puntensysteem in SQL

Alle plaatsnamen en zijn bijbehorende soundex-waarde uit een tabel halen, om vervolgens middels de eerder genoemde php-functies te gaan vergelijken, zou een oplossing kunnen zijn. Aan de hand van de vergelijkingen, kan een overeenkomst-percentage berekend worden, waarop de resultaten geordend kunnen worden.

Een SQL alternatief, is controleren in hoeverre een soundex van de zoekstring overeenkomt met de soundex van de plaatsnamen in een tabel. Indien een plaats geheel gelijk is aan elkaar, geef je het bijvoorbeeld 10 punten. Amsterdam zal bijvoorbeeld gelijk zijn aan Amstrdm, en dus kun je Amsterdam als gevonden waarde teruggeven.
Vervolgens controleer je in hoeverre een deel van de soundex-waarde van de zoekopdracht voorkomt in de soundex-waarden van de plaatsnamen in de tabel. Ook hiervoor geef je weer punten. Daarna controleer je enkel de overeenkomst in de numerieke waarde van de soundex-waarde,hetzelfde kun je doen voor subsets, et cetera.
Om te voorkomen dat plaatsnamen die beduidend langer zijn dan de zoekopdracht te hoog in de resultaten verschijnt, kun je minpunten uitdelen per karakter dat een gevonden plaats langer of korter is dan de zoekopdracht.

Uiteindelijk zou je, met enkele eigen aanvullingen, een volgende query gemaakt kunnen hebben:

SELECTDISTINCT(plaats)AS distinctplaats,SOUNDEX(plaats)AS soundexplaats,
ROUND((-- exact similarity or similarity of first 4 chars
IF(SOUNDEX(plaats)=SOUNDEX('Groningen'),4,
IF(SOUNDEX(plaats)LIKECONCAT(LEFT(SOUNDEX('Groningen'),4),'%'),2,0))+-- numeric similarity
(
SUBSTRING(SOUNDEX(plaats),2)=SUBSTRING(SOUNDEX('Groningen'),2))*3+-- left similarity
IF(SOUNDEX(plaats)LIKECONCAT('_',SUBSTRING(SOUNDEX('Groningen'),2,4),'%'),2,
IF(SOUNDEX(plaats)LIKECONCAT('_',SUBSTRING(SOUNDEX('Groningen'),2,3),'%'),1,0))+-- right similarity
IF
(SOUNDEX(plaats)LIKECONCAT('%',RIGHT(SOUNDEX('Groningen'),4)),2,
IF(SOUNDEX(plaats)LIKECONCAT('%',RIGHT(SOUNDEX('Groningen'),3)),1,0))+-- first pronounce similarity
(
SUBSTRING(SOUNDEX(LEFT(plaats,5)),2,3)=SUBSTRING(SOUNDEX(LEFT('Groningen',5)),2,3))*2+ -- last pronounce similarity
(
SUBSTRING(SOUNDEX(RIGHT(plaats,5)),2,3)=SUBSTRING(SOUNDEX(RIGHT('Groningen',5)),2,3))*4+-- similarity of first subsets
(SOUNDEX(plaats)LIKECONCAT(LEFT(SOUNDEX('Groningen'),4),'%'))*3+
(SOUNDEX(plaats)LIKECONCAT(LEFT(SOUNDEX('Groningen'),3),'%'))*2+
(SOUNDEX(plaats)LIKECONCAT(LEFT(SOUNDEX('Groningen'),2),'%'))+ -- similarity of last subsets
(
SOUNDEX(plaats)LIKECONCAT('%',RIGHT(SOUNDEX('Groningen'),(LENGTH(SOUNDEX('Groningen'))-1))))*3+
(SOUNDEX(plaats)LIKECONCAT('%',RIGHT(SOUNDEX('Groningen'),(LENGTH(SOUNDEX('Groningen'))-2))))*2+
(SOUNDEX(plaats)LIKECONCAT('%',RIGHT(SOUNDEX('Groningen'),(LENGTH(SOUNDEX('Groningen'))-3))))*1+ -- check difference in length, this will resolve in a negative number
IF
(LENGTH(plaats)>LENGTH('Groningen'),
LENGTH('Groningen')-LENGTH(plaats),
LENGTH(plaats)-LENGTH('Groningen'))*0.3
AS points FROM plaatsnaam
ORDERBY points DESC

Voor de personen die direct aan de slag willen met bovenstaande query om de suggesties te bekijken, hier een tabel-dump (sql) van 1595 willekeurige plaatsnamen.

Heb je zelf ooit eerder een vergelijkbare query of functie geprogrammeerd, of heb je aanvullingen / verbeteringen? Laat het me weten!

5 reacties

donderdag 18 februari 2010 om 10:36
door Frank

Dank voor deze post! Interessante functie die Soundex.

Ik heb hem zelf even uitgeprobeerd op een eigen locatiedatabase, er missen nog 2 afsluitende )) van de ROUND( ( op regel 2, maar daarna deed hij het prima.

Erg bruikbaar voor een 404 pagina die met plaatsnamen te maken krijgt.

zondag 13 juni 2010 om 19:32
door Pieter

superhandige tip! Gaan we gebruiken voor de woningverhuur website. Afgekeken van de koning Google?

maandag 25 oktober 2010 om 22:50
door Huurda

Handige topic! Ga er gelijk mee bezig, bedankt!

maandag 5 september 2011 om 19:48
door Eric

Zeker handig. En praktisch gebracht zo!

maandag 26 december 2016 om 15:09
door Reynaert Makelaardij

Prima tip!
Hier kan ik wat mee.
Ga hiermee aan de slag.