Intelligente suggesties, deel 3: Uitspraak en hierarchie nl

Door creator1988 op woensdag 29 december 2010 15:05 - Reacties (8)
Categorie: Algoritmes, Views: 4.066

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:

C#:
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')
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:

code:
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?
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:

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
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:

C#:
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:

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
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.

Volgende: Intelligente suggesties, deel 4: Aantallen, caching en Protocol Buffers 12-'10 Intelligente suggesties, deel 4: Aantallen, caching en Protocol Buffers
Volgende: Intelligente suggesties, deel 2: Volledige matching en typfouten 12-'10 Intelligente suggesties, deel 2: Volledige matching en typfouten

Reacties


Door Tweakers user Battle Bunny, woensdag 29 december 2010 15:19

Erg leuke en boeiende serie so far, bedankt!

Ik heb meteen even die link gelezen over Power Sets, en ondanks dat het erg krachtig lijkt, vind ik dit:
private IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
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 ;)

Door Tweakers user creator1988, woensdag 29 december 2010 15:27

Battle Bunny schreef op woensdag 29 december 2010 @ 15:19:
Erg leuke en boeiende serie so far, bedankt!
Grazie!
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 ;)
Beter zo?

Visual Basic .NET:
1
Private Function GetPowerSet(Of T)(list As List(Of T)) As IEnumerable(Of IEnumerable(Of T))


Door Tweakers user Battle Bunny, woensdag 29 december 2010 21:23

Grazie!
Enige punt is nu dat mijn vingers jeuken om dit ergens in onze software te implementeren... Kan alleen nog geen geschikte plek vinden :p
Beter zo?

Visual Basic .NET:
1
Private Function GetPowerSet(Of T)(list As List(Of T)) As IEnumerable(Of IEnumerable(Of T))

Leest voor mij iets beter, maar nog steeds een erg ... euhm ... leuke oplossing ;)

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!

Door Tweakers user RobIII, woensdag 29 december 2010 21:36

edit:
nvm. Hier stond (dikke) onzin :X

[Reactie gewijzigd op donderdag 30 december 2010 03:02]


Door Tweakers user FlowinG, woensdag 29 december 2010 23:34

@RobIII

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".

Door Tweakers user RobIII, donderdag 30 december 2010 01:19

Ja dat bedacht ik later ook :P Sowieso een duf moment gehad; want dan waren die komma's helemaal overbodig geweest en had je net zo goed kunnen splitten op spaties :X
Kerstdufheid zullen we maar zeggen :P

[Reactie gewijzigd op donderdag 30 december 2010 02:46]


Door Tweakers user -RetroX-, 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 ;) ]

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

RobIII schreef op donderdag 30 december 2010 @ 01:19:
Ja dat bedacht ik later ook :P Sowieso een duf moment gehad; want dan waren die komma's helemaal overbodig geweest en had je net zo goed kunnen splitten op spaties :X
Kerstdufheid zullen we maar zeggen :P
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.
-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 ;) ]
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.
Battle 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!
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 zoekt :) .

[Reactie gewijzigd op donderdag 30 december 2010 10:17]


Reageren is niet meer mogelijk