[.NET] locaties in tekst zoeken

[NLAnaconda]

Hey Tweakers.

Ik heb een volgende situatie waarbij ik niet weet hoe ik dit het beste aan kan pakken.

Situatie:
Ik heb een MySQL database met 250.000+ locaties
Ik heb een stuk tekst van variabele lengte, een verhaal.

Wat ik wil realiseren
Ik wil bij het submitten van het verhaal controleren of een of meerdere locaties voorkomen in het verhaal.

Probleem:
Ik heb geen idee hoe ik dit het beste kan doen wat performance betreft.
Het is natuurlijk mogelijk om elke entry in de database door te loopen om te kijken of deze in het verhaal staat. Maar dat lijkt me niet echt heel snel werken.

Hoe zouden jullie dit aanpakken?

[RobIII]

Makkelijk en snel is van je lijst van woorden een array met unieke waardes maken, die tegen je DB houden in een in-clause en vervolgens iets met die resultaten doen.

C#:

using System;
using System.Linq;
using System.Text.RegularExpressions;

class Program
{
    static void Main(string[] args)
    {
        var text = @"Far out in the uncharted backwaters of the unfashionable end of the western spiral arm of the Galaxy 
                    lies a small unregarded yellow sun. 
                    Orbiting this at a distance of roughly ninety-two million miles is an utterly insignificant little blue green 
                    planet whose ape-descended life forms are so amazingly primitive that they still think digital watches are a 
                    pretty neat idea. 
                    This planet has - or rather had - a problem, which was this: most of the people on it were unhappy for 
                    pretty much of the time. Many solutions were suggested for this problem, but most of these were largely 
                    concerned with the movements of small green pieces of paper, which is odd because on the whole it wasn't 
                    the small green pieces of paper that were unhappy.";

        //Build list of (unique) words
        var words = new Regex(@"((?:\w+[-'])*\w+)(?=\s)")
            .Matches(text)
            .Cast<Match>()
            .Select(m => m.Value)
            .Where(w => w.Length > 0)
            .Distinct(StringComparer.OrdinalIgnoreCase)
            .OrderBy(w => w);

        //Build query
        var query = string.Concat(
            "select `locationname` from `mytable` where `locationname` in ('", 
            string.Join("','", words.Select(w=>w.Replace("'", "''"))),
            "');"
        );

        //Get matching locations
        using (var conn = new MySqlConnection("foo.bar"))
        {
            conn.Open();
            var result = conn.ExecuteQuery(query);
            foreach (var m in result)
            {
                //Doe iets met de match(es)
            }
        }
    }
}

Een aantal dingen: er moet een index staan op, in mijn voorbeeld, locationname wil dit een beetje performen. Daarbij zul je, bij "lange verhalen", deze query batch-gewijs met batches van, zeg, 500 of 1000 woorden willen uitvoeren (en dus geen in-clause van een shitload aan woorden bouwen!). Daarbij is bovenstaande code enkel bedoeld als 'proof-of-concept' of 'pseudo-code'; iets om mee van start te kunnen. Er schort nog wel wat aan en vooral 't opbouwen van je query (en escaping!) zul je zeker even nader willen bekijken/bijschaven.

[NLAnaconda]

Bedankt voor de tijd die je in je post hebt gestoken! hier kan ik wel wat mee.

[ Voor 48% gewijzigd door NLAnaconda op 23-04-2014 02:29 ]

[Gomez12]

Zet naast je 250.000 locaties een 2e tabel neer met veel gebruikte tekstgedeeltes binnen een locatie (bijv dam / straat / laan ) en een 3e tabel met bijv alles wat niet matched met tabel 2 en daarvan dan de 1e 5 letters oid. (of bijv een soundex of ... het doel is gewoon om niet direct op die 250.000+ te matchen)

Dan kan je elk woord eerst vergelijken met tabel 2 (200 entries) en alles wat niet matched daarna met tabel 3 (1.000 entries) en het eindresultaat daarvan kan je dan gaan matchen met de 250.000+ tabel.
In principe wil je gewoon een early exit hebben, daarvoor kan ook een stopwoorden lijst nog wel nuttig zijn. Of bijv een minimale plaatslengte

Dat was het makkelijke gedeelte (1-woord locaties), hierna gaat het al snel complex worden. Want nu heb je bijv Bosch gevonden, maar wordt dat voorafgegaan door den of niet?

[NLAnaconda]

Ja precies. Ik denk dat ik het aantal records ga verminderen door te zoeken binnen een straal van X km binnen latitude en longitude.
Zoals je voorstelt: er moeten zo veel mogelijk records weggefilterd worden.

Voor het meerdere woorden probleem denk ik dat ik de situatie om moet draaien.
Niet de woorden van de tekst zoeken in de database, maar de database woorden in de tekst zoeken.

[BikkelZ]

Het zou sneller zijn als je je data permanent laadt in een tree in je geheugen. Dus cities[a][m][s][t][e][r][d][a][m] geeft je dan Amsterdam, andere woorden komen op niks uit. Dat is altijd sneller dan een database en het is met een seconde weer opgebouwd. Woorden zijn achteraf ook nog eenvoudig toe te voegen of je bouwt de hele tree gewoon weer opnieuw op (er van uit gaande dat er niet zo veel plaatsen bij komen).

Hou de tree in je geheugen klein maar slim en ga dan de grotere data gewoon ophalen achteraf als je alle id's van plaatsnamen verzameld hebt. Je wil in principe je zoekproces in een zo klein mogelijk stukje geheugen (cache) in een zo snel mogelijke manier op een zo lineair mogelijke manier doorlopen, dus zo weinig mogelijk code zo veel mogelijk herhalen waardoor branch prediction makkelijker wordt en er meer in de cache gedaan wordt in plaats van steeds opnieuw geheugen te moeten lezen.

Dus eerst heel simpel alles doorlopen en detecteren en alleen wat id's opslaan van plaatsnamen en woordarray indexnummers en pas daarna alles gaan doen wat je wil doen

[ Voor 13% gewijzigd door BikkelZ op 24-04-2014 12:39 ]