Algoritme voor uitzoeken van een adres

[tom_swinkels]

Dag allen,

Aangezien ik niet veel kon vinden op internet en personen die het wel voor elkaar hebben gekregen mij verder niet willen helpen, heb ik besloten om hier een topic te openen om te kijken of hier personen zijn die er meer ervaring mee hebben.

Via het p2000 netwerk komen een tal van meldingen binnen van de hulpdiensten. De meldingen zijn echter per regio anders opgebouwd en wat ik nu wil doen is uit een melding halen welke locatie het is.

Zo zijn er aan tal van websites die dit voor elkaar hebben, bijvoorbeeld www.alarmeringen.nl.

Hier een aantal voorbeelden van meldingen:

PRIO 1 : Rookmelder OMS Zorgcentrum Sonnehove SONNEHOVE 1 SOM : 4241 4242 3251 OVD-B
PRIO 1 : BRAND WONING (Onderdeel gebouw: schoorsteen) ROERDOMPWEG 9 HEU : 2041 3251
PRIO 1 : Handmelder OMS Savant De Lisse DEKEN MEIJERSTRAAT 1 AST : 1041 1042 3251 OVD-B

Hoe denk ik een melding uit te kunnen rekenen:

- Ik heb al een database met alle adressen, plaatsen, provincies van Nederland
- Adressen zijn niet altijd met hoofdletters dit is per regio anders
- Ook de opbouw van een melding is niet altijd het zelfde

Als eerste alle woorden van een melding in een array zetten.

Volgens ga ik kijken of een van de woorden een staat is. Als hij een straat vindt dan krijg ik ook de resultaten terug in welke plaatsen dit een straat naam is. Dan kijk ik welke woorden in de melding het meeste matchen met de plaatsnaam en dat zou dan de goede straat en plaats moeten zijn.

Een aantal problemen, wat doe ik met de straat naam die niet uit een woord bestaat? Bijvoorbeeld "DEKEN MEIJERSTRAAT"? Wat ik kan doen is een LIKE op DEKEN en kijken of het geen dat er achter of ervoor staat ook in de melding zo is?

Het is een redelijk ingewikkeld proces, ook omdat ik later ook nog snelwegen en n-wegen uit wil rekenen. Dit zou dan eventueel via de API van www.hmpaal.nl moeten gaan.

Bij de websites die het wel voor elkaar hebben gaan er zelfs soms nog een aantal meldingen mis. Zie -> http://112meldingen.nl/me...3&d=05-01-14&attr=E221AA1 je ziet daar dat ze bij deze melding niet op BOSCHDIJK 771 gezocht hebben maar op GGZE DE GROTE BEEK. Dit is wat mij betreft dus niet juist.

Wat informatie van internet

- http://bojhan.com/peter/s...les/Processing-log-v9.pdf.
"Hiermee kon ik heel makkelijk een verkenbare map tonen in processing, maar had geen
mogelijkheid om aan de hand van een adres een locatie te vinden.
Door middel van een stukje code wat de auteur van de volgende blog post had geschreven heb ik
volgens mij een manier om de latitude en longitude op te halen."

- http://forum.livep2000.nl...5002620764a2609fc662f0aea
"Toen we gingen onderzoeken hoe we het beste straatnamen konden herkennen is er een algoritme bedacht die voorvoegsels (dr. laan. van) en achtervoegsels (straat, weg, park, laan) en veelvoorkomende tussenvoegsels omvormt tot een waarschijnlijkheid in procenten.

De uitkomst was dat we de term 'zeer waarschijnlijk' wel kunnen benaderen, maar dat dit niet voldoende is.

De namen zouden herkent kunnen worden, zonder dat ze bestaan. Bedenk je hoe irritant dat zou zijn."


Hoe denken jullie hierover, zijn er soms manieren om een berekening te kunnen maken?

[Snikker]

Als je wat rommel eruit filtert en het naar Google stuurt: https://developers.google...entation/geocoding/?hl=nl

Zou je dan bruikbare data krijgen? De responses lijken netjes een string voor je te parsen + je krijgt de coordinaten.

[Gomez12]

Bedenk je heel erg goed of je dit wel echt wilt.
Adres herkenning geautomatiseerd is moeilijk, heel erg moeilijk...

En je houdt altijd false positives.

[tom_swinkels]

@snikker : Dit is iets wat ik eigenlijk juist niet wilde. Omdat het dan nog wel eens voorkomt dat hij op iets anders aan match heeft dan op een adres. Ook wil Google graag de plaatsnaam hebben.

@gomez12 : Ja eigenlijk wel. Andere p2000 monitors kunnen het ook. Het is moeilijk, maar dat wil niet zeggen dat er geen oplossing voor is. Met de oplossing die ik geef is wel wat te bedenken, bijvoorbeeld bestaat de straat naam niet, probeer dan het woord ervoor en er achter e.t.c op deze manier moet er wel een match komen.

Daarom de vraag hoe jullie er over denken en wat jullie zouden doen. Antwoorden met dat het moeilijk is kan ik verder niet veel mee, als het niet moeilijk was had ik ook geen topic geplaatst

[MSalters]

Het is makkelijker om je database voor te bewerken. "Deken Meijerstraat"? Voeg dan verwijzingen "Meijerstraat", "Deken Meijersstraat", "Meijerstr", "Deken Meijer Straat" etc toe.

Wat betreft hoofdletters/kleine letters, dat maakt niet uit voor een case-insensitive search.

Verder kun je nog wel wat winst bereiken door bekende woorden eerst te herkennen. "Brand", "Inbraak", "OMS" hoef je niet op te zoeken.

TS zal er nites aan hebben (gezien de verwarring over hoofd/kleine letetrs) maar voor anderen die dit topic vinden: SOUNDEX is voor Engels, niet Nederlands. Het idee is redelijk correct, maar de letterkeuze niet.

[storeman]

Inderdaad lastig. Ik heb zelf soortgelijke problemen met hotels van verschillende leveranciers. Die schrijven dit allemaal op hun eigen wijze en dit geeft dan ook dergelijke problemen.

Ik zit zelf aan iets als dit te denken:
1. Schrijf alles voluit (St. => Sint, str. => straat...), dit moet bij de referenctiedata natuurlijk ook zo zijn
2. Bereken de levenshtein distance tussen de input en elk adres in je database
3. Als er geen distance van 0 is gevonden, druk deze distance uit als percentage de straat in je database
(stringlengte db - levdist) / stringlengte db
4. Het hoogste percentage is een match

Ik doe dit voor een 4 tal velden, hotelnaam, straat, plaats en postcode, elk met een bepaald minimum percentage.

Het werkt redelijk goed, maar zeker niet feilloos.

In die voorbeelden, voor de laatste dubbelepunt, staan 3 letterige codes. Zijn dit plaatscodes? Als je hierop kan matchen ben je al een heel eind.

[cannibal]

Die plaatscodes wilde ik eigenlijk net noemen.
Als je van achter zoekt bij de 3 voorbeelden, komt na de numerieke waarden een plaats code.

Zoek deze op en kijk dan of 1 van de bekende straatnamen voorkomt in de melding-text.
Of eventueel een deel van de straatnaam om wat verschillende schrijfwijzen af te vangen.

Alleen goede snelheid in ophalen van je straatnamen per plaats mogelijk maken.

[P.O. Box]

tom_swinkels schreef op maandag 06 januari 2014 @ 11:30:
De meldingen zijn echter per regio anders opgebouwd en wat ik nu wil doen is uit een melding halen welke locatie het is.

Kun je dan niet het makkelijkst per regio een aparte functie maken... desnoods een alert mailtje naar jezelf als de regio ineens zijn berichtlayout wijzigt? zodat je het snel kunt aanpassen...
ik vermoed dat je conculega's dat ook zo doen...

[creator1988]

MSalters schreef op maandag 06 januari 2014 @ 14:50:
TS zal er nites aan hebben (gezien de verwarring over hoofd/kleine letetrs) maar voor anderen die dit topic vinden: SOUNDEX is voor Engels, niet Nederlands. Het idee is redelijk correct, maar de letterkeuze niet.

Tah dah. Coding Glamour: Diakritische tekens en Soundex in .NET

In principe is dit probleem wel redelijk te bruteforcen denk ik. Maak een in-memory index aan van alle straatnamen, split alle woorden in een melding en kijk welke losse of combinatie van woorden in de index voorkomt. Soundex heb je niet nodig zolang de officiele straatnamen maar worden gebruikt (zal wel niet ).

[tom_swinkels]

@msalters : Het voorprogrammeren van die straatnamen vind ik beetje onnodig. Ik kan dat beter dan bij elke straat doen bij het zoeken, en dat hoef pas wanneer er geen straat gevonden is. In de meeste gevallen hoef dit dus niet.
Verder heb je dat leuk bedacht met de woorden die er standaard uitgefilterd kunnen worden, alleen "Brand" mag er niet uit gefilterd worden in sommige gemeente is dit namelijk een straatnaam Je ziet ook dat bij veel websites deze locatie dus niet gevonden kan worden.

@storeman : Precies, dat is dus een probleem wat ook erg in de richting van mijn probleem komt.
1. In mijn regio "Brabant zuid-oost" komt het al bijna niet door dat er een afkorting gebruikt wordt maar ik kan hier natuurlijk wel een check op zetten, in het geval dat het bij andere regio's wel voorkomt.
2. Wat bedoel je precies met de input? Ik heb alle straatnamen in mijn tabel staan, en in een melding staan verschillende woorden ik moet de woorden dus niet meer in een array gooien maar de hele sting vergelijken met de straatnamen in de database? Ik heb een klein stukje code geprobeerd, alleen een goede match heb je niet 1 2 3.

code:

<?
$message = 'PRIO 1 : BRAND GEZONDHEIDSZORG (Onderdeel gebouw: dak) (NB BRAND: middel) Savant De Lisse DEKEN MEIJERSTRAAT 1 AST :';
$message = str_replace( array('$', '.', ':', '(', ')', 'prio 2', 'inzet brw', 'reinigen wegdek', 'vervuild wegdek', 'prio 1', 'nb brand'), array('', '', '', '', '', '', '', '', '', '', ''), strtolower( $message ) );

// input misspelled word
$input = $message;

// array of words to check against
$words = $streetMapper->getStreets();

// no shortest distance found, yet
$shortest = -1;

// loop through words to find the closest
foreach ($words as $word) {

    // calculate the distance between the input word,
    // and the current word
    $lev = levenshtein($input, $word->getName());

    // check for an exact match
    if ($lev == 0) {

        // closest word is this one (exact match)
        $closest = $word->getName();
        $shortest = 0;

        // break out of the loop; we've found an exact match
        break;
    }

    // if this distance is less than the next found shortest
    // distance, OR if a next shortest word has not yet been found
    if ($lev <= $shortest || $shortest < 0) {
        // set the closest match, and shortest distance
        $closest  = $word->getName();
        $shortest = $lev;
    }
}

echo 'Input word: ' . $input . '<br /><br />';
if ($shortest == 0) {
    echo "Exact match found: " . $closest . "<br />";
} else {
    echo "Did you mean: " . $closest . "?<br />"; 
}
?>

P.O. Box : Dat doe ik liever niet. Er zijn 25 regio's..

creator1988 : Dat zou inderdaad de oplossing zijn, maar dan heb ik nog eerst de straatnaam nodig

[creator1988]

tom_swinkels schreef op maandag 06 januari 2014 @ 16:46:
Ik heb een klein stukje code geprobeerd, alleen een goede match heb je niet 1 2 3.

Kijk eens naar mijn serie artikelen over BK-trees en Levenshtein. Coding Glamour: Intelligente suggesties, deel 2: Volledige matching en typfouten

Je moet niet 400000 entry's gaan levenshteinen, want dat gaat erg traag.

creator1988 : Dat zou inderdaad de oplossing zijn, maar dan heb ik nog eerst de straatnaam nodig

Nee, stel je hebt deze inkomende string:

BLA DEZE STRAAT

Je gooit
BLA
DEZE
STRAAT
BLA DEZE
DEZE STRAAT
BLA DEZE STRAAT

door je algoritme (kan prima met een goeie index). Kijkt welke er voorkomt (DEZE STRAAT), en maakt dan een keuze (langste match gok ik).

[ Voor 26% gewijzigd door creator1988 op 06-01-2014 16:50 ]

[tom_swinkels]

@creator1988 : Thanks, daar ga ik eens even na kijken. Valt mee het zijn 126715 straten. Het berekenen van een locatie wordt natuurlijk door een service op de achtergrond van de applicatie gedaan.

Dat is denk ik precies wat ik moet doen. Heb je dan niet heel veel combinaties, en is er een algoritme voor de verschillende combinaties makkelijk te maken?

[ Voor 28% gewijzigd door tom_swinkels op 06-01-2014 17:28 ]

[Gomez12]

Waarom wil je direct op straat matchen?

Dat lijkt mij onbegonnen werk (geen idee hoeveel "hoofdstraat"en er in NL zijn, maar volgens mij veel)
En helemaal als je ook nog eens fuzzy gaat zoeken heb je kans op heel veel resultaten.

En ik vermoed dat je straten db niet klopt, ik heb in het verleden ook wel iets met adressen gedaan en dan zag ik rustig 250.000 straten voorbij komen.

[tom_swinkels]

@gomez12 : Waar wil je dan op gaan zoeken? De database moet volgens mij wel kloppen, data komt van http://www.d-centralize.nl. Het zijn natuurlijk wel de unieke straatnamen, de straatnamen zijn daarna weer gekoppeld aan een plaats

Ondertussen dacht ik ook een andere oplossing te hebben. Je kunt namelijk met array_intersect kijken welke woorden in beide arrays voorkomen. Maar omdat hij dan niet kijkt naar de volgorde van de woorden gaat dit fout.

De manier van @creator1988 lijkt mij nog steeds de beste manier, morgen ik dus even bekijken hoe ik deze manier toe zou kunnen passen op mijn applicatie.

[ Voor 44% gewijzigd door tom_swinkels op 07-01-2014 01:32 ]

[Snikker]

tom_swinkels schreef op dinsdag 07 januari 2014 @ 00:41:
De manier van @creator1988 lijkt mij nog steeds de beste manier, morgen ik dus even bekijken hoe ik deze manier toe zou kunnen passen op mijn applicatie.

Creator is denk ik ook wel een goede referentie, als ik het goed heb, heeft hij bij Funda gewerkt

[Hydra]

MSalters schreef op maandag 06 januari 2014 @ 14:50:
Het is makkelijker om je database voor te bewerken. "Deken Meijerstraat"? Voeg dan verwijzingen "Meijerstraat", "Deken Meijersstraat", "Meijerstr", "Deken Meijer Straat" etc toe.

Nogal veel werk denk je niet?

[creator1988]

Snikker schreef op vrijdag 10 januari 2014 @ 11:37:
[...]


Creator is denk ik ook wel een goede referentie, als ik het goed heb, heeft hij bij Funda gewerkt

Yep, ik heb de zoekbox op de homepage geschreven.

[DeoDupke]

Ik zou denk ik wat experimenteren met n-grams en een lucene index.

Je gegevens stop je dan in verschillende n-grams (Wikipedia: n-gram) in je index, en wanneer je gaat zoeken split je je input ook op in n-grams. Dan laat je lucene (http://lucene.apache.org/) daar een result op teruggeven. Dan kun je in elk geval wat variaties van input/stored documents opvangen.

Je zou ook eens naar http://www.elasticsearch.org/ kunnen kijken (ipv zelf op lucene te bouwen).

Ik heb niet echt een gevoel voor je gegevens dus vind het lastig om te voorspellen of dit werkt. Je moet wat experimenteren denk ik.

@Hydra, met bovenstestaande kun je dat dus 'automatisch' doen.