This post was originally published on Coding Glamour.

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. 

        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: 

    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. 

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.