Intelligente suggesties, deel 1: Introductie en 'StartsWith' nl

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

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')

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.

C#:
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:

C#:
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.

code:
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.

Volgende: Intelligente suggesties, deel 2: Volledige matching en typfouten 12-'10 Intelligente suggesties, deel 2: Volledige matching en typfouten
Volgende: Video! On-the-fly zoeksuggesties: Levenshtein en Soundex in de praktijk 12-'10 Video! On-the-fly zoeksuggesties: Levenshtein en Soundex in de praktijk

Reacties


Door Tweakers user jbdeiman, maandag 27 december 2010 15:30

Kan je hier niet iets van sql voor gebruiken met een SOUNDAS functionaliteit?

Door Tweakers user Snikker, maandag 27 december 2010 15:33

Super dat je dit deelt, heel leerzaam!

Door Tweakers user kipusoep, maandag 27 december 2010 15:42

Iehl, methoden en variabelen met Nederlandse namen :X

Door Tweakers user creator1988, maandag 27 december 2010 15:48

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

Door Tweakers user YopY, maandag 27 december 2010 15:52

Taalkundige zooi is nu niet heel erg domeinspecifiek, ;).

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?

Door Tweakers user creator1988, maandag 27 december 2010 16:05

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?
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:

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]


Door Tweakers user flowerp, maandag 27 december 2010 20:13

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 :9
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...

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 :P Geloof 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.

Door Tweakers user Bramģ, maandag 27 december 2010 23:31

kipusoep schreef op maandag 27 december 2010 @ 15:42:
Iehl, methoden en variabelen met Nederlandse namen :X
Inderdaad, leest zo lekker weg:
private static Regex _alleenWordChar
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.

Door Tweakers user creator1988, dinsdag 28 december 2010 10:42

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

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
    }

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 :P Geloof 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.
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.
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.
Ik vind absoluut dat je gewoon in het Engels moet schrijven, maar niet geforceerd.

Door Tweakers user beeman, woensdag 29 december 2010 17:20

@creator1988 Goeie serie, en hij komt precies op het juiste moment voor mij :)

Voor de mensen die op zoek zijn naar lijsten met plaatsnamen en dergelijke:

Reageren is niet meer mogelijk