Coding Glamour

Dit is deel 4 in een serie over de techniek uit een 'intelligente' zoekbox.

• 1. Introductie en 'StartsWith'
• 2. Volledige matching en typfouten
• 3. Uitspraak en hierarchie
• 4. Aantallen, caching en Protocol Buffers

We kunnen hierarchisch zoeken, spel- en typfouten verhelpen en zelfs vrij goed gokken wat een gebruiker bedoelt als we de zoekterm niet helemaal begrijpen; waardoor alleen nog de grijze getallen met aantallen openstaan.

Lees verder »

Dit is deel 3 in een serie over de techniek uit een 'intelligente' zoekbox.

• 1. Introductie en 'StartsWith'
• 2. Volledige matching en typfouten
• 3. Uitspraak en hierarchie
• 4. Aantallen, caching en Protocol Buffers

Na gisteren een BK-tree gemaakt te hebben waarmee we kunnen zoeken op woorden, en daarbij ook typfouten kunnen ondervangen, verbeteren we dit vandaag door middel van een combinatie van het fonetisch algoritme Soundex en de Burkhard-Keller tree.

Lees verder »

Dit is deel 2 in een serie over de techniek uit een 'intelligente' zoekbox.

• 1. Introductie en 'StartsWith'
• 2. Volledige matching en typfouten
• 3. Uitspraak en hierarchie
• 4. Aantallen, caching en Protocol Buffers

Na gisteren in te zijn gegaan op de basis van de applicatie, vandaag gaan we dieper in op Burkhard-Keller trees voor efficiënte volledige matching, en het ondervangen van typfouten.

Burkhard-Keller tree
Een BK-tree is een tree-based datastructuur om snel en efficiënt woorden te vinden die op elkaar lijken. We moeten dus eerst een algoritme hebben dat woorden kan vergelijken, en een getal kan geven aan het verschil. Hiervoor heb ik eerder al de Levenshtein-distance voor gekozen, en als implementatie de 'YetiLevenshtein' methode uit het Tenka.Text project.

De 400.000 verschillende 'keys' die we in deel 1 hebben bepaald gaan we nu rangschikken in deze boom. Als voorbeeld de volgende set:

Lees verder »

Dit is deel 1 in een serie over de techniek uit een 'intelligente' zoekbox.

• 1. Introductie en 'StartsWith'
• 2. Volledige matching en typfouten
• 3. Uitspraak en hierarchie
• 4. Aantallen, caching en Protocol Buffers

Enkele weken geleden werd mij een functioneel ontwerp in de handen gedrukt met als enige opmerking: 'kijk eens of we dit kunnen maken'. In twee weken bouwtijd was dit het resultaat. Vandaag deel 1 in een serie over de techniek die het mogelijk maakt om in fracties van een seconde intelligente suggesties te geven.

Doelen

• Tonen van suggesties op basis van de input van de gebruiker
• Suggesties kunnen zowel geheel matchen ('Amsterdam'), of gedeeltelijk ('Amste')
• Hierarchie moet ondersteunt worden ('Amsterdam, Noord-Holland'; 'Wibautstraat, Amsterdam')
• Het aantal woningen dient naast de suggestie getoond te worden
• Tolerant in invoer ('Köog a/d Zaan' moet 'Koog aan de Zaan' als suggestie geven)

Wanneer er geen suggesties te geven zijn, moeten er alternatieven worden voorgesteld:

• Op basis van uitspraak gebieden vinden die hetzelfde klinken ('Wiboudstraat' en 'Wibautstraat')
• Tolerantie voor typfouten ('Utrect')
• Omdraaien van de opdracht ('Amsterdam, Pijp' wordt 'Pijp, Amsterdam')

Lees verder »

Momenteel nog aan het werk aan een project waar ik al eerder helemaal los op ging, alwaar ik vandaag aankwam op de mogelijkheid van typfouten.

Levenshtein distance
De levenshtein distance is het minimale aantal bewerkingen dat nodig is om van het ene woord naar het andere woord te komen.

code:

1 2 3 4 5 6

1: Amsterdam 2: Amsteldam A m s t e r d a m ^ A m s t e d a m

In bovenstaand geval dus één mutatie. Netjes van wikipedia gejat is dit voorbeeld, van kitten -> sitting:

code:

1 2 3

1. kitten -> sitten (substitution of 'k' with 's') 2. sitten -> sittin (substitution of 'e' with 'i') 3. sittin -> sitting (insert 'g' at the end).

Waar is het goed voor?
We kunnen veel met Soundex en alternatieve woorden, maar fuzzy matching is daarmee niet mogelijk. Door alle plaatsen / straten / etc. te vinden die een afstand van één hebben tot de zoekterm kan je vrij eenvoudig een lijst met alternatieven geven (natuurlijk samen met Soundex).

Lees verder »