Intelligente suggesties, deel 2: Volledige matching en typfouten nl

Door creator1988 op dinsdag 28 december 2010 14:23 - Reacties (7)
Categorie: Algoritmes, Views: 4.000

Dit is deel 2 in een serie over de techniek uit een 'intelligente' zoekbox.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'.
http://www.100procentjan.nl/tweakers/bk.png
We doen nu hetzelfde voor het volgende element. Het verschil tussen 'Jan' en 'Jaap' is '2'.
http://www.100procentjan.nl/tweakers/bk(2).png
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.
http://www.100procentjan.nl/tweakers/bk(3).png
Same, same voor 'Aap'. Verschil tussen 'Jan' en 'Aap' is '2', verschil tussen 'Aap' en 'Jaap' is '1'.
http://www.100procentjan.nl/tweakers/bk(4).png

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!
http://www.100procentjan.nl/tweakers/bk(5).png
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.
http://www.100procentjan.nl/tweakers/bk(6).png
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.
http://www.100procentjan.nl/tweakers/bk(7).png
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#

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
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

C#:
1
2
3
4
5
6
7
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!

Volgende: Intelligente suggesties, deel 3: Uitspraak en hierarchie 12-'10 Intelligente suggesties, deel 3: Uitspraak en hierarchie
Volgende: Intelligente suggesties, deel 1: Introductie en 'StartsWith' 12-'10 Intelligente suggesties, deel 1: Introductie en 'StartsWith'

Reacties


Door Tweakers user Sjakskus, woensdag 29 december 2010 00:20

Ik heb me 2 jaar bezig gehouden met datamatching (vooral adressen en namen)
Wel grappig om iemand anders zijn aanpak te zien.

heb je ook de longest common sequence methode al eens bekeken?

deze kan voor jouw doel ook nuttig zijn.

Soundex was voor mijn doelen wat minder nuttig

Door Tweakers user creator1988, woensdag 29 december 2010 10:52

Sjakskus schreef op woensdag 29 december 2010 @ 00:20:
Ik heb me 2 jaar bezig gehouden met datamatching (vooral adressen en namen)
Wel grappig om iemand anders zijn aanpak te zien.

heb je ook de longest common sequence methode al eens bekeken?
Nee, kende deze niet. Maar an sich ziet de suffix tree er sowieso best handig uit; ook om het StartsWith probleem efficiŽnter op te lossen. Zal er eens in detail naar gaan kijken. Danke!

Door Tweakers user -RetroX-, donderdag 30 december 2010 11:18

Zeg ik het goed als elke term in je dictionary een bk-tree krijgt?

Hoeveel tijd kost dan het genereren van alle trees voor je volledige dictionary?

Door Tweakers user creator1988, donderdag 30 december 2010 12:39

-RetroX- schreef op donderdag 30 december 2010 @ 11:18:
Zeg ik het goed als elke term in je dictionary een bk-tree krijgt?

Hoeveel tijd kost dan het genereren van alle trees voor je volledige dictionary?
Ongeveer 15 secondes op 1 core van een consumenten E6600 (2.4 GHz). Dit is alleen het bouwen van de dictionary van woorddelen, geen soundex etc.

Door Tweakers user -RetroX-, donderdag 30 december 2010 12:46

heb je een willekeurig woord genomen als root van je tree of heb je nog gelet op het bevatten van veel voorkomende (s,t,e,r,n,a,d) letters of juist medeklinkers of juist minder voorkomende tekens (x, c, q, y)?

Door Tweakers user creator1988, donderdag 30 december 2010 13:52

-RetroX- schreef op donderdag 30 december 2010 @ 12:46:
heb je een willekeurig woord genomen als root van je tree of heb je nog gelet op het bevatten van veel voorkomende (s,t,e,r,n,a,d) letters of juist medeklinkers of juist minder voorkomende tekens (x, c, q, y)?
Amsterdam is mijn root (en daar komen geheel toevallig s, t, e, r, a en d in voor :) )

Door Tweakers user dragontje124, dinsdag 4 januari 2011 22:39

ik heb geprobeerd een eigen implementatie te schrijven in php+mysql
ik heb daarvoor 2 tabellen in mysql aangemaakt:
(met in de woorden tabel een hoop gemeentes)
woorden:
-id
-woord

bktree:
-id
-parentid
-nodeid
-distance

het volgende stukje code is mijn php implementatie

PHP:
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
<?php
mysql_connect('127.0.0.1','root','');
mysql_select_db('fuzzy');
$lijst = array();
$zoeken = "Amsteldam";
$maxverschil = 3;
function findNodes($nodeId,$searchTerm,$maxdifference)  {
    global $lijst;
    $select = mysql_query("SELECT woord FROM woorden WHERE id = ".$nodeId);
    $word = mysql_fetch_array($select);
    $distance = levenshtein($word['woord'],$searchTerm);
    $min = $distance-$maxdifference;
    $max = $distance+$maxdifference;
    if($min <0 ) $min = 0;
    $select_nodes = mysql_query("SELECT nodeid FROM bktree WHERE parentid = ".$nodeId." AND distance BETWEEN ".$min." AND ".$max) OR die(mysql_error());
    $count = mysql_num_rows($select_nodes);
    if($distance <=$maxdistance)    {
        $lijst[] = $word['woord'];
    }
    while($node = mysql_fetch_array($select_nodes)) {
            findNodes($node['nodeid'],$searchTerm,$maxdistance);
    }
    return true;
        
}
$select = mysql_query("SELECT parentid FROM bktree WHERE id=1");
$root = mysql_fetch_assoc($select);
findNodes($root['parentid'],$zoeken,$maxverschil);
print_r($lijst);
?>


werkt nog prima met 1400 gemeentes

[Reactie gewijzigd op dinsdag 4 januari 2011 23:06]


Reageren is niet meer mogelijk