Intelligente suggesties, deel 2: Volledige matching en typfouten

Dit is deel 2 in een serie over de techniek uit een 'intelligente' zoekbox.

• 1. Introductie en 'StartsWith'
• 2. Volledige matching en typfouten
• 3. Uitspraak en hierarchie
• 4. Aantallen, caching en Protocol Buffers

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:

• Jan
• Jas
• Jaap
• Jak
• Aap

Intern doet een BK-tree het volgende: begin bovenaan (bij 'Jan' bv.), en kijk naar het verschil tussen het bovenste element en je volgende element ('Jas'). Het verschil is '1'; dus we tekenen van boven een tak naar beneden met waarde '1'.

We doen nu hetzelfde voor het volgende element. Het verschil tussen 'Jan' en 'Jaap' is '2'.

Bij 'Jak' doen we dit weer. Het verschil tussen 'Jan' en 'Jak' is '1'. Er loopt al een tak met waarde '1' dus die lopen we af, en we vergelijken nu 'Jak' met 'Jas'. Verschil is '1', dus we tekenen hier de nieuwe tak.

Same, same voor 'Aap'. Verschil tussen 'Jan' en 'Aap' is '2', verschil tussen 'Aap' en 'Jaap' is '1'.


The beauty of it is dat we met deze boom snel kunnen bepalen of een item in de boom voorkomt. Willen we weten of 'Jak' in de boom staat, beginnen we bovenaan: verschil tussen 'Jan' en 'Jak' is 1, verschil tussen 'Jas' en 'Jak' is 1, verschil tussen 'Jak' en 'Jak' is 0: gevonden!

We hebben nu dus maar 3 vergelijkingen hoeven doen, terwijl er 4 waardes zijn die dezelfde beginkarakters hebben. Dit loopt nog veel meer op wanneer je een gigantische set hebt, want je kunt met slechts 9 vergelijkingen alle 400.000 waardes afzoeken!

Fuzzy matching
Een BK-tree is ook goed in 'fuzzy' matching, waarin er tussen de woorden een verschil mag zitten; ideaal om typfouten af te vangen. Bijvoorbeeld: we willen alle woorden in de boom vinden waarin het verschil met 'Aak' maximaal 1 is. We beginnen bovenaan: verschil tussen 'Aak' en 'Jan' is 2, we gaan nu alle bomen af waarvoor geldt: waardeVanTak BETWEEN verschil - maximaalVerschil AND verschil + maximaalVerschil. In dit geval dus: 1, 2, 3.

We doen nu weer hetzelfde: Verschil tussen 'Jas' en 'Aak' is 2, dus we gaan weer bomen 1, 2 en 3 af. Het verschil tussen 'Jak' en 'Aak' is 1, dit valt binnen de grens: 'Jak' is dus een match. Er zijn geen takken hieronder; maar anders zouden we 0, 1 en 2 aflopen.
Aan de andere kant is het verschil tussen 'Jaap' en 'Aak' ook 2, en tussen 'Aap' en 'Aak' 1. Ook hier geldt hetzelfde: 'Aap' is een match.

Zoals je ziet scheelt het in een kleine set niets, maar bij grote sets met veel verschil tussen de data heb je maar zo'n 900 vergelijkingen nodig om alle 400.000 keys te evalueren! Typfouten worden hiermee makkelijk verholpen, aangezien 'Amstredam' en 'Amsterda' allebei 'Amsterdam' als suggestie gaan vinden.

BK-tree in C#

    public class BkTreeNode<T>
        where T : class
    {
        public string Key { get; set; }
        
        public Dictionary<int, BkTreeNode<T>> Nodes { get; set; }
        private List<T> Items { get; set; }
        public BkTreeNode(string identifier, T item)
        {
            Key = identifier;
            Nodes = new Dictionary<int, BkTreeNode<T>>();
            Items = new List<T>();
            if(item != null)
            {
                Items.Add(item);
            }
        }
        public void Add(string identifier, T item)
        {
            // bereken de afstand
            int ix = EditDistance.YetiLevenshtein(identifier, Key);
            // als de afstand 0 is dan kennen we dit item al, we voegen het gebied toe aan de lijst
            if (ix == 0)
            {
                Items.Add(item);
                return;
            }
            // als de afstand nog niet bestaat
            if (!Nodes.ContainsKey(ix))
            {
                // voeg een nieuwe node toe
                Nodes.Add(ix, new BkTreeNode<T>(identifier, item));
            }
            else
            {
                // anders ga naar de node met dezelfde afstand
                Nodes[ix].Add(identifier, item);
            }
        }
        public List<T> Query(string searchTerm, int maxDistance)
        {
            List<T> nodes = new List<T>();
            // verschil tussen zoektermen
            int levenshteinDiff = EditDistance.YetiLevenshtein(searchTerm, this.Key);
            if (levenshteinDiff <= maxDistance) nodes.AddRange(this.Items);
            // alle bomen die qua distance
            // dist BETWEEN verschil - maxDistance AND verschil + maxDistance
            foreach (var distance in Enumerable.Range(levenshteinDiff - maxDistance, (maxDistance * 2) + 1))
            {
                if (Nodes.ContainsKey(distance))
                {
                    nodes.AddRange(Nodes[distance].Query(searchTerm, maxDistance));
                }
            }
            return nodes.ToList();
        }
        public override string ToString()
        {
            return Key + " (" + Nodes.Count + ")";
        }
    }

Gebruik

BkTreeNode<GeoGebied> root = new BkTreeNode<GeoGebied>("amsterdam", null); // kies een triviale waarde
// doe dit voor al je items in de lijst
root.Add("rotterdam", geoGebiedRotterdam); 
List<GeoGebied> queryResult = root.Query("amsteldam", 1);
Assert.That(queryResult.Count(), Is.EqualTo(1)); // yay!

Morgen...
Gaan we in op hierarchie, en het gebruik van SoundEx om op basis van uitspraak alternatieven te vinden. Stay tuned!