Intelligente suggesties, deel 1: Introductie en 'StartsWith' 
- 1. Introductie en 'StartsWith'
- 2. Volledige matching en typfouten
- 3. Uitspraak en hierarchie
- 4. Aantallen, caching en Protocol Buffers
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)
- 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')
Normaliseren van namen en zoekacties
Voor we data uit de database gaan halen, is het van belang om alle namen te normaliseren. Denk hierbij aan het strippen van spaties en diakrieten, en het gebruik van synoniemen.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| private static Regex _alleenWordChars = new Regex(@"[^a-z0-9]+", RegexOptions.Compiled); public string NormaliseerNaam(string q) { q = q.Trim(); q = NormaliseerHoofdlettergebruik(q); q = NormaliseerDiakritisch(q); q = NormaliseerSynoniemen(q); // alles wat nu nog geen a-z0-9 eruit strippen q = _alleenWordChars.Replace(q, String.Empty); return q; } private string NormaliseerHoofdlettergebruik (string q) { return q.ToLowerInvariant(); } private static Encoding removal = Encoding.GetEncoding(Encoding.ASCII.CodePage, new EncoderReplacementFallback(""), new DecoderReplacementFallback("")); public string NormaliseerDiakritisch(string q) { string normalized = q.Normalize(NormalizationForm.FormD); byte[] bytes = removal.GetBytes(normalized); return Encoding.ASCII.GetString(bytes); } private static Dictionary<string, string> _synoniemen; private string NormaliseerSynoniemen(string q) { if (_synoniemen == null) { _synoniemen = new Dictionary<string, string> { { "ad", "aan de" }, { "a/d", "aan de" }, { "aan den", "aan de" }, { "1e", "eerste" }, { "2e", "tweede" }, { "3e", "derde" }, }; } // special cases ; regex is te langzaam if (q.StartsWith("de ")) q = q.Substring(3); if (q.StartsWith("het ")) q = q.Substring(4); if (q.Contains(" in ")) q = q.Replace(" in ", " "); if (q.EndsWith(" in")) q = q.Substring(0, q.Length - 3); foreach(var syn in _synoniemen) { q = q.Replace(syn.Key, syn.Value); } return q; } |
Model
Voor het opslaan van de verschillende gebieden maken we gebruik van GIS-data die we aankopen. Tijdens de eerste run trekken we dit uit de database en slaan we dit op in een in-memory lijst. Van elk gebied hebben we nodig:
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class GeoGebied { // Straat, Buurt, Regio etc. (gebruik hier een 'byte' voor, lekker efficient) public Niveau Niveau { get; set; } // Naam van het gebied (officiële schrijfwijze) public string Naam { get; set; } // Uniek ID public int Id { get; set; } // Het ID van de parent (bv. Zaandam heeft 'Gemeente Zaanstad') public int Parent { get; set; } public string[] Keys { get; set; } } |
Speciaal geval hierboven is de array van 'Keys'. Dit zijn alle zoektermen waarop gezocht kan worden en waarin dit gebied terug moet komen. Denk hierbij bij 'Den Haag' aan 'denhaag' en 'haag'. De reden dat we dit doen is omdat je altijd een StartsWith wil doen en geen Substring, omdat dat niet te indexen valt.
Gebieden vinden (StartsWith)!
Gebieden vinden we op basis van hun Keys. Wanneer een bezoeker 'Amste' intypt willen we alle gebieden vinden die een key hebben die begint met 'amste'. Voor dit doel hebben we een index nodig; maar die is niet zo makkelijk te leggen. Daarom kies ik er hier voor om de index op de eerste twee karakters te leggen. Dit doen we voor elk element in de 'Keys' array.
1
2
| IxTwoChar['am'] -> 'amsterdam', 'amstelveen', 'amsterdamsestraatweg' etc. IxTwoChar['ha'] -> 'den haag', 'hattemerbroek', etc. |
We kunnen hierdoor al snel 99,8% van alle mogelijkheden schrappen door alleen te kijken naar de eerste twee karakters. Er zitten per key zo'n 600 entiteiten onder en die zijn in een duizendste van een seconde te doorzoeken.
Morgen dieper de algoritmes in om efficiënt gebieden te vinden waarbij de input volledig matcht, en op typfouten.
12-'10 Intelligente suggesties, deel 2: Volledige matching en typfouten
12-'10 Video! On-the-fly zoeksuggesties: Levenshtein en Soundex in de praktijk
Reacties

Ja, alleen is die Engels en te traag om te gebruiken in deze situatie.jbdeiman schreef op maandag 27 december 2010 @ 15:30:
Kan je hier niet iets van sql voor gebruiken met een SOUNDAS functionaliteit?
Iehl, mensen die geforceerd Engelse termen gaan gebruiken voor domeinspecifieke entiteitenkipusoep schreef op maandag 27 december 2010 @ 15:42:
Iehl, methoden en variabelen met Nederlandse namen


Overigens hoop ik - voor je eigen mentale gezondheid - dat die normalisatie en die index van eerste twee karakters niet allemaal hardcoded is.
Hoe staan die gegevens overigens in de database, en hoe wordt daarin met diakrieten omgegaan? bijvoorbeeld je hebt een dorpje "dûrp", je script normaliseert een invoer "dûrp" naar "durp" zonder dakje. Wordt het dan nog gevonden?
Nee, bij een application startup trek ik alles uit de database, en sla het dan genormaliseerd op in memory. De database wordt niet meer geraakt na de eerste start. Bij het zoeken wordt dus alleen van de genormaliseerd index gebruik gemaakt. Zoiets:YopY schreef op maandag 27 december 2010 @ 15:52:
Overigens hoop ik - voor je eigen mentale gezondheid - dat die normalisatie en die index van eerste twee karakters niet allemaal hardcoded is.
Hoe staan die gegevens overigens in de database, en hoe wordt daarin met diakrieten omgegaan? bijvoorbeeld je hebt een dorpje "dûrp", je script normaliseert een invoer "dûrp" naar "durp" zonder dakje. Wordt het dan nog gevonden?
C#:
1
2
| IxTwoChar["wu"].Where(x=>x.Keys.Any(y=>y.StartsWith("wunsera"))); // Bij Wûnseradiel staat in de keys de key 'wunseradiel'. |
[Reactie gewijzigd op maandag 27 december 2010 16:06]
En toen ging je internationaal met je software, werd je software gekocht door een derde partij of kreeg je een sloot medewerkers van buiten Nederland...creator1988 schreef op maandag 27 december 2010 @ 15:48:
[...]
Ja, alleen is die Engels en te traag om te gebruiken in deze situatie.
[...]
Iehl, mensen die geforceerd Engelse termen gaan gebruiken voor domeinspecifieke entiteiten
In de 20+ jaar dat ik nu als developer bezig ben heb ik echt *zelden* de noodzaak gezien om een nationale taal te gebruiken in source code, zelfs voor entities (models). Er zijn heel af en toe uitzonderingen voor een begrip wat echt alleen voor een bepaald gebied bestaat en waar vertaling naar Engels zinloos zou zijn, maar dit zijn echt de uitzonderingen.
Ik hoop niet voor je dat je ooit nog eens in een team van een Japans bedrijf komt te werken dat dezelfde mentaliteit heeft als jij

Inderdaad, leest zo lekker weg:kipusoep schreef op maandag 27 december 2010 @ 15:42:
Iehl, methoden en variabelen met Nederlandse namen
Maar het kan altijd nog een stapje erger. Een ex-werkgever (met de nadruk op exprivate static Regex _alleenWordChar

Ook heel praktisch als je dan Engelse documentatie moet lezen (en 99%+ van de documentatie waar het programmeertalen betreft is dat wel) en je bent gewend in het 'Nederlands' te programmeren.
Nou lijkt me niet. Ik kan wel alles gaan zitten vertalen, maar bijvoorbeeld de 'niveau's' die we voor geografische entiteiten hebben zijn gewoon domeinspecifiek:flowerp schreef op maandag 27 december 2010 @ 20:13:
In de 20+ jaar dat ik nu als developer bezig ben heb ik echt *zelden* de noodzaak gezien om een nationale taal te gebruiken in source code, zelfs voor entities (models). Er zijn heel af en toe uitzonderingen voor een begrip wat echt alleen voor een bepaald gebied bestaat en waar vertaling naar Engels zinloos zou zijn, maar dit zijn echt de uitzonderingen.
C#:
1
2
3
4
5
6
7
8
9
10
| public enum Niveau : byte { Buurt = 2, Gemeente = 1, Plaats = 0, Provincie = 5, Regio = 3, Straat = 4, Land = 6 } |
Nee, niet alle entities moeten in dezelfde taal; maar de domeinspecifieke wel. Ik schrijf mijn code over het algemeen gewoon in het Engels; zeker generieke stukken. Geo is een domeinspecifiek onderdeel. Hoe ga je de VS geografisch weergeven in deze entities. Niet; want compleet anders.Ik hoop niet voor je dat je ooit nog eens in een team van een Japans bedrijf komt te werken dat dezelfde mentaliteit heeft als jijGeloof me, dan stap je HEEL snel van je opvatting af dat entities in de taal moeten van het bedrijf dat begonnen is met de code.
Ik vind absoluut dat je gewoon in het Engels moet schrijven, maar niet geforceerd.Maar het kan altijd nog een stapje erger. Een ex-werkgever (met de nadruk op ex ) deed ook het e.e.a. in het Nederlands: krijgVariabeleNaam() en zetVariabeleNaam().
Ook heel praktisch als je dan Engelse documentatie moet lezen (en 99%+ van de documentatie waar het programmeertalen betreft is dat wel) en je bent gewend in het 'Nederlands' te programmeren.

Voor de mensen die op zoek zijn naar lijsten met plaatsnamen en dergelijke:
- http://kvdb.net/projects/6pp/ Nederland
- http://www.geonames.org/ Wereldwijd
Reageren is niet meer mogelijk