Intelligente suggesties, deel 3: Uitspraak en hierarchie
This post was originally published on Coding Glamour.
Dit is deel 3 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
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:
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:
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:
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:
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:
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.
There are 8 comments on this article, read them on Coding Glamour.