Intelligente suggesties, deel 4: Aantallen, caching en Protocol Buffers

Door creator1988 op donderdag 30 december 2010 15:57 - Reacties (2)
Categorie: Algoritmes, Views: 2.148

Dit is deel 4 in een serie over de techniek uit een 'intelligente' zoekbox.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 »

Intelligente suggesties, deel 3: Uitspraak en hierarchie

Door creator1988 op woensdag 29 december 2010 15:05 - Reacties (8)
Categorie: Algoritmes, Views: 3.122

Dit is deel 3 in een serie over de techniek uit een 'intelligente' zoekbox.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 »

Intelligente suggesties, deel 2: Volledige matching en typfouten

Door creator1988 op dinsdag 28 december 2010 14:23 - Reacties (7)
Categorie: Algoritmes, Views: 3.085

Dit is deel 2 in een serie over de techniek uit een 'intelligente' zoekbox.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 »

Intelligente suggesties, deel 1: Introductie en 'StartsWith'

Door creator1988 op maandag 27 december 2010 14:23 - Reacties (10)
Categorie: Algoritmes, Views: 3.194

Dit is deel 1 in een serie over de techniek uit een 'intelligente' zoekbox.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 »

Video! On-the-fly zoeksuggesties: Levenshtein en Soundex in de praktijk

Door creator1988 op vrijdag 24 december 2010 10:59 - Reacties (14)
Categorie: -, Views: 2.865

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.