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 »

Naar aanleiding van mijn eerdere post over Levenshtein, Soundex en Burkhard-Keller trees, én omdat een video meer zegt dan duizend woorden: een korte impressie van het resultaat. Volgende week ga ik wat dieper in op de onderliggende algorithmes, met voorbeeldcode etc.