Intelligente suggesties, deel 2: Volledige matching en typfouten 
Dit is deel 2 in een serie over de techniek uit een 'intelligente' zoekbox.
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:

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#
Gebruik
Morgen...
Gaan we in op hierarchie, en het gebruik van SoundEx om op basis van uitspraak alternatieven te vinden. Stay tuned!
- 1. Introductie en 'StartsWith'
- 2. Volledige matching en typfouten
- 3. Uitspraak en hierarchie
- 4. Aantallen, caching en Protocol Buffers
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

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#
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!
12-'10 Intelligente suggesties, deel 3: Uitspraak en hierarchie
12-'10 Intelligente suggesties, deel 1: Introductie en 'StartsWith'
Reacties
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
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
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!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?
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?
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.-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?
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-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)?

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:
werkt nog prima met 1400 gemeentes
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