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

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

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.125

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.089

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.198

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 »

Typfouten, Levenshtein en Burkhard-Keller trees

Door creator1988 op maandag 20 december 2010 15:25 - Reacties (11)
Categorie: Algoritmes, Views: 3.085

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 »