Intelligente suggesties, deel 3: Uitspraak en hierarchie 
- 1. Introductie en 'StartsWith'
- 2. Volledige matching en typfouten
- 3. Uitspraak en hierarchie
- 4. Aantallen, caching en Protocol Buffers
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:
1
| 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')
Hierarchisch zoeken
Gebruikers kunnen met komma's zoeken op hierarchie:
1
2
3
| 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?
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:
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
| 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:
1
2
3
4
5
6
7
8
| 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:
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
| 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.
12-'10 Intelligente suggesties, deel 4: Aantallen, caching en Protocol Buffers
12-'10 Intelligente suggesties, deel 2: Volledige matching en typfouten
Reacties
Ik heb meteen even die link gelezen over Power Sets, en ondanks dat het erg krachtig lijkt, vind ik dit:
echt walgelijk om te lezen. Nu ben ik natuurlijk een VB.Net monkey en heb ik nog steeds een beetje moeite met C en C# syntax, maar dit slaat allesprivate IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)

Grazie!Battle Bunny schreef op woensdag 29 december 2010 @ 15:19:
Erg leuke en boeiende serie so far, bedankt!
Beter zo?echt walgelijk om te lezen. Nu ben ik natuurlijk een VB.Net monkey en heb ik nog steeds een beetje moeite met C en C# syntax, maar dit slaat alles
Visual Basic .NET:
1
| Private Function GetPowerSet(Of T)(list As List(Of T)) As IEnumerable(Of IEnumerable(Of T)) |
Enige punt is nu dat mijn vingers jeuken om dit ergens in onze software te implementeren... Kan alleen nog geen geschikte plek vindenGrazie!

Leest voor mij iets beter, maar nog steeds een erg ... euhm ... leuke oplossingBeter zo?
Visual Basic .NET:
1 Private Function GetPowerSet(Of T)(list As List(Of T)) As IEnumerable(Of IEnumerable(Of T))

Ik neem trouwens aan dat deze blog entries ook wel op een grote programmeer-kennis-dump-site komen? Zou zonde zijn als dit niet meer te vinden is of niet meer gelezen wordt puur omdat te weinig mensen op de tweakblogs komen!
nvm. Hier stond (dikke) onzin

[Reactie gewijzigd op donderdag 30 december 2010 03:02]
Het lijkt mij een stuk optimalisatie om het juist niet te doen: op het moment dat de gebruiker komma's gebruikt hoef je niet 'slimmer' te gaan doen dan de gebruiker en ook niet onnodig hierarchisch te zoeken. Verder zullen komma's ook problemen geven bij het zoeken naar "den haag" of "krimpen aan de ijssel".


Kerstdufheid zullen we maar zeggen

[Reactie gewijzigd op donderdag 30 december 2010 02:46]
"De Groningerstraatweg Groningen (Groningen)" [deze straat ligt in Leeuwarden maar zo is het voorbeeld leuker ;) ]
Niet helemaal onzin; het ligt eraan hoe je verwacht dat je gebruikers gaan invoeren. Wij nemen aan dat de gebruiker het in de meeste gevallen correct invoert, en dus houden we de zoekterm eerst intact. Verwacht je dat je veel 1-woords termen hebt waarbij de gebruiker altijd spaties i.p.v. komma's gebruikt kan je de set andersom evalueren.RobIII schreef op donderdag 30 december 2010 @ 01:19:
Ja dat bedacht ik later ookSowieso een duf moment gehad; want dan waren die komma's helemaal overbodig geweest en had je net zo goed kunnen splitten op spaties
Kerstdufheid zullen we maar zeggen
Hoe meer termen hoe minder efficiënt; of de termen hetzelfde zijn maakt hiervoor niet uit. Ter info: de term 'utrecht utrecht utrecht utrecht utrecht' (de langste die we hebben: Utrechtseweg in de plaats Utrecht, in de gemeente Utrecht, in de regio Utrecht, in de provincie Utrecht) wordt uitgevoerd (zonder komma's) in 10 ms. Met komma's in 4 ms. Dus ja wordt wel trager maar niet schokkend.-RetroX- schreef op donderdag 30 december 2010 @ 08:59:
Hoe is de efficiency als een term in meerdere levels voorkomt?
"De Groningerstraatweg Groningen (Groningen)" [deze straat ligt in Leeuwarden maar zo is het voorbeeld leuker ;) ]
Google waardeert over het algemeen mijn stukjes wel; dus vooralsnog vind ik dat wel genoeg. Zoek maar op 'bk tree c#'; sta op plek 3 en plek 4 als je vanuit Nederland zoektBattle Bunny schreef op woensdag 29 december 2010 @ 21:23:
Ik neem trouwens aan dat deze blog entries ook wel op een grote programmeer-kennis-dump-site komen? Zou zonde zijn als dit niet meer te vinden is of niet meer gelezen wordt puur omdat te weinig mensen op de tweakblogs komen!

[Reactie gewijzigd op donderdag 30 december 2010 10:17]
Reageren is niet meer mogelijk