This post was originally published on Coding Glamour.

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. In een boom opslaan van de Soundex waardes
Voor het opslaan van de Soundex waarde doe ik hetzelfde als gisteren voor de normale waardes; we gebruiken dus weer Levenshtein om de distance op te slaan. We kunnen dan gelijkklinkende woorden vinden door een query uit te voeren op de tree: 

var list = SoundexRootNode.Query("wiboudstraat", 0); // Wibautstraat, Amsterdam gevonden

Nu kunnen we meerdere dingen doen om fouten in zowel spelling als uitspraak te vinden:
  • Alleen zoeken op soundex van de invoer van de gebruiker
  • Alle woorden vinden met een distance van 1; en hier soundex op toepassen (als je 'Driese Wetering' intikt, krijg je bijv. 'Drielse Wetering'; op elk van deze resultaten doe je een query in de Soundex Tree)
  • Alle resultaten in de soundex vinden met een distance van 1 ('Wiboukstraat' resulteert in 'Wibautstraat')
Het resultaat van elk van deze benaderingen varieert nogal per dataset, maar voor onze implementatie hebben we voorlopig gekozen voor 1., maar 2. staat nog ter discussie. De implementatie is immers verborgen in de BK-tree, en we kunnen dus makkelijk schakelen.

Hierarchisch zoeken
Gebruikers kunnen met komma's zoeken op hierarchie: 

Pijp, Noord-Holland 
// vindt alleen alle entiteiten met naam 'Pijp' in de provincie NH
// dus niet 'Pijpenring' in 'Delft'

Hierbij zijn twee problemen:
  • Hoe vinden we hierarchie als de gebruiker geen komma's gebruikt; maar bijv. Pijp Amsterdam intikt?
  • Hoe vinden we snel en vooral efficiënt de hierarchische parents?
Geen komma's?
Wanneer een gebruiker geen komma's gebruikt, zoeken we eerst naar resultaten die precies matchen ('Pijp Amsterdam'), als deze geen resultaten geeft, dan berekenen we alle mogelijke queries die we kunnen maken als we de spaties vervangen door komma's (in dit geval 'Pijp Amsterdam' en 'Pijp,Amsterdam') met de volgende code: 

public List<string> GetAllPossibleQueries(string query)
{
    string normalisedQuery = query.Replace(",", " ");
    string[] queryParts = normalisedQuery.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
    normalisedQuery = string.Join(" ", queryParts); // 1 spatie is goed
    List<string> queries = new List<string>();
    int[] spacePositions = new int[queryParts.Length - 1];
    int lixSpace = -1;
    for(int ix = 0; ix < spacePositions.Length; ix++)
    {
        lixSpace = normalisedQuery.IndexOf(' ', lixSpace + 1);
        spacePositions[ix] = lixSpace;
    }
    var powerSet = GetPowerSet(spacePositions.ToList());
    // order de powerset zo dat eerst de minste queries van achter naar voor
    // dus Drielse Wetering, Zaandam komt voor Drielse, Wetering, Zaandam
    powerSet = powerSet.OrderBy(i => i.Count()).ThenByDescending(i => i.Sum());
    foreach(var set in powerSet)
    {
        char[] newQuery = normalisedQuery.ToCharArray();
        foreach(var space in set)
        {
            newQuery[space] = ',';
        }
        queries.Add(new string(newQuery));
    }
    return queries.Where(q=>!q.Equals(normalisedQuery, StringComparison.Ordinal)).ToList();
}
// http://social.msdn.microsoft.com/Forums/en-CA/netfxbcl/thread/42375146-eade-43ae-9550-1dfdd7c8aa18
private IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
           select
               from i in Enumerable.Range(0, list.Count)
               where (m & (1 << i)) != 0
               select list[i];
}

Hierna voeren we alle mogelijke queries nog een keer uit.

Wel komma's
Na de eerste keer geen komma's gehad te hebben, parsen we de query ('Pijp, Amsterdam') van de gebruiker naar dit model: 

    public class Zoekhierarchisch
    {
        public string Term { get;set;}
        public Zoekhierarchisch Parent { get;set;}
    }
    
    // hier komt uit
    { Term: "Pijp", Parent: { Term: "Amsterdam", Parent: null } }

En we zoeken nu met de standaard-zoekcode naar alles waar 'Pijp' in voorkomt. Hieruit komt bijvoorbeeld 'Oude Pijp', 'Nieuwe Pijp' en 'Pijperring'. Omdat elk gebied een 'Parent' property heeft, kunnen we dit gebruiken om te controleren of er ooit een parent is van het huidige gebied die matcht tegen de invoer van de gebruiker: 

public List<GeoGebied> FilterHierarchic(IEnumerable<GeoGebied> gebieden, Zoekhierarchisch criterium, int fuziness, bool useSoundex)
{
    // als de zoekopdracht geen parent heeft, dan matcht alles
    if (criterium.Parent == null)
        return gebieden.ToList();
    // maak een lijst met alle parents
    List<string> terms = new List<string>();
    var cp = criterium.Parent;
    while(true)
    {
        if (cp == null) break;
        terms.Add(cp.Term);
        cp = cp.Parent;
    }
    // als query was 'Drostendiep, Kalf, Zaandam' dan terms is
    // [ Kalf, Zaandam ]
    // we gaan nu van elk gebied in de set controleren of deze ooit matcht
    return gebieden.Where(g => EverMatchesHierarchic(g, terms, fuziness, useSoundex, 0)).ToList();
}
public bool EverMatchesHierarchic(GeoGebied gebied, List<string> terms, int fuziness, bool useSoundex, int level)
{
    var soundex = new Soundex();
    // dit slaan we de eerste keer over want anders werkt utrecht, utrecht, utrecht niet meer correct
    // we moeten namelijk minimaal 1 niveau omhoog zijn gegaan
    if (++level > 1)
    {
        // als het gebied NULL is, dan matcht dit natuurlijk niet
        if (gebied == null) return false;
        bool success = false;
        string terms0Soundex = useSoundex ? soundex.Calculate(terms[0]) : null;
        // een gebied kan meerdere keys hebben; want varianten enzo
        foreach(var gebiedVariant in LongCache.IxGebiedId[gebied.Id])
        {
            // een gebied matcht als:
            // 1. zijn keys overeenkomt met terms[0]
            if (gebiedVariant.Keys.Any(key=>key.Equals(terms[0], StringComparison.Ordinal))) success = true;
            // 2. zijn keys starts with terms[0]
            else if (gebiedVariant.Keys.Any(key=>key.StartsWith(terms[0]))) success = true;
            // 3. zijn soundexkeys overeenkomen met soundex van terms[0]
            else if (useSoundex && gebiedVariant.Keys.Any(key=>soundex.Calculate(key) == terms0Soundex)) success = true;
            // 4. fuziness goed is
            else if (fuziness > 0 && gebiedVariant.Keys.Any(key => EditDistance.YetiLevenshtein(key, terms[0]) <= fuziness)) success = true;
        }
        if (success)
        {
            // als dit de laatste term was dan true
            if (terms.Count == 1) return true;
            // anders halen we de huidige term eraf en zoeken we verder
            terms = terms.Skip(1).ToList();
        }
    }
    // zoek in onze cache of we het parent-element van het huidige geoGebied wel kennen
    if (!LongCache.IxGebiedId.ContainsKey(gebied.Parent)) return false;
    return EverMatchesHierarchic(LongCache.IxGebiedId.ContainsKey(gebied.Parent) ? LongCache.IxGebiedId[gebied.Parent].FirstOrDefault() : null, terms, fuziness, useSoundex, level);
}

De lijst is nu gefilterd, en 'Pijperring' is verwijderd; daar deze in Delft ligt!

Morgen
Het laatste deel in deze serie: aantallen woningen, caching en Protocol Buffers.