[.NET] Input filteren op een lijst van 564 woorden

[Blue-eagle]

Ik heb een lijst met 564 woorden ontvangen, dit zijn zogenaamde UPC-waarden die veel gebruikte afkortingen zijn voor Engelstalige straten en dergelijke. Een klein voorbeeld:

ALLEE, ALLEY, ALLY, ALY, ANEX, ANNEX, ANNX, ANX, ARC, ARCADE, AV, AVE, AVEN, AVENU, AVENUE, AVN, AVNUE, BAYOO, BAYOU, BCH, BEACH, BEND, BG, BGS, BLF, BLFS, BLUF, BLUFF, BLUFFS, BLVD, BND, BOT, etc.

Deze woorden heb ik inmiddels in een database tabel staan (1 record per woord, niet alle woorden in 1 record ofzo ) en nu moet er het volgende mee gebeuren..

Een gebruiker van het systeem voert zijn adres gegevens in, ik transformeer de waarden naar lowercase (of uppercase, maakt niet uit) en strip alle mogelijk "matches" in de UPC-lijst eruit. Vervolgens strip ik alle spaties en dergelijke weg zodat ik een zo kaal mogelijk adres opsla in de database.

Voorbeeld:
Ik voer in: "Flat 5 115 Roe Lane", wat er over moet blijven is dit: "flat5115roe".
Ik voer in: "115 Robertson Avenue", wat er over moet blijven is dit: "115robertson".
Etc.

Nu wil ik best uitleggen waarom dat zo moet maar da's niet belangrijk voor de vraag

De vraag is dan ook: hoe filter ik de invoer (een string) op al deze 564 woorden zonder veel performance van de server te vragen?

Oplossing #1: Loop door de gehele recordset en replace het woord met niks, repeat tot 564 en klaar ben je. Probleem hiermee is uiteraard dat het niet erg netjes over komt, het vreet performance (het gebeurt nogal vaak in het systeem) en... ik ben benieuwd wat jullie Tweakers mij nog meer kunnen leren

[Woy]

waarom niet gewoon

C#:

public string StripWords( string val ){
    StringBuilder input = new StringBuilder( value.ToLowerCase() );
    string[] filterWords = { "allee", .... };
    foreach( string word in filterWords ){
        input.Replace( word, "" );
    }
    return input.ToString();
}

Je zult zowiezo alle woorden langs moeten lopen om ze te veranderen. Het belangrijkste is denk dat je gebruik maat van een StringBuilder omdat er anders voor elke replace een nieuwe string aangemaakt moet worden. Door gebruik te maken van een StringBuilder hoeft dit niet meer.

[ Voor 107% gewijzigd door Woy op 23-01-2006 14:31 ]

[Verwijderd]

@rwb: Dit gaf de TS al aan, maar is performancetechnisch wat bruteforce. Ik weet ook niet hoe het anders zou moeten... Ik denk eigenlijk dat dit de enige oplossing is.

564 valt op zich ook nog wel mee...

Het kan ook anders:

Explode het adres op de spatie en doe voor elk 'element' een query op de database / check of het in de lijst met filter-woorden staat. Zo ja -> replace met niks.

[ Voor 32% gewijzigd door Verwijderd op 23-01-2006 14:32 ]

[Woy]

Ja dat las ik later inderdaad ook. Aangezien het altijd om adressen gaat is de oplossing die Boland aandraagt nog wel redelijk. Aangezien een adress meestal niet extreem lang is kan je waarschijnlijk beter de woorden in je adres controleren tegen je lijst met niet toegestane woorden. ( Als je zorgt dat deze gesorteerd is kun je dit met een binary search doen bijvoorbeeld ).

Dus dan zou ik het zoiets doen.

C#:

public string StripWords( string val ){ 
    StringBuilder output = new StringBuilder();
    string[] filterWords = { "allee", .... };
    val = val.ToLowerCase();
    string[] input = val.Split();
    foreach( string word in input ){ 
        if( Array.BinarySearch( filterWords, word ) >= 0 )
            output.Append( word );
    } 
    return output.ToString(); 
}

[ Voor 37% gewijzigd door Woy op 23-01-2006 14:39 ]

[Janoz]

Wat je zou kunnen doen is een boom bouwen van de filterwoorden. Elke node heeft max 26 childs (voor elke letter 1). Wanneer een compleet woord in de boom opgeslagen is sluit je deze af met een leaf. Dit kun je gewoon in het laatste node opgeven. Je wandeld dan door je woord en je boom en wanneer je in een leaf terecht komt weet je dat je een filterwoord te pakken hebt. Is een node geen leaf en heeft hij geen kinderen bij de volgende letter in je search string, dan heb je geen filterwoord en begin je bij het volgende teken (Het volgende teken na het teken waarmee je begonnen bent om door de boom te wandelen).


@Hieronder: Ik ging er vanuit dat deelwoorden ook verwijderd moesten worden. In principe kwam dit ook voor in het orgineel voorgestelde algoritme (met replace). Als het gehele woorden moeten zijn dan maakt het de boel wel een stuk makkelijker. Je hoeft dan immers niet per karakter, maar per woord te controleren. Je begint altijd bij de eerste letter van een woord in de orginele string en je moet bij het einde van een woord zijn als je in een leaf komt. In dat geval haal je het weg, in het andere geval ga je door met het volgende woord.

[ Voor 31% gewijzigd door Janoz op 23-01-2006 15:18 ]

[Twilight Burn]

Je moet er ook even rekening mee houden dat de woorden in "aflopende grootte" gereplaced moeten worden. Anders krijg je dat maar een deel "weggefilterd" wordt:
Avenue -> enue (omdat AV als eerste in je lijstje staat)
Ook als zo'n filterwoord als deel van de "echte" straatnaam voorkomt zou het weggehaald worden. Lavenstraat -> lenstraat (kon ff geen beter voorbeeld bedenken )

De boom-oplossing van Janoz lijkt me wel wat, maar dan met de restrictie dat je met "whitespace" (inclusief leestekens, begin van de regel en eind van de regel) moet beginnen en eindigen.

[marrik]

Gooi alle woorden in een (gecachte) Array. Split je invoer op spaties en gebruik Array.IndexOf(string) om te bepalen of het stukje invoer voorkomt in je woordenlijst.
Een array heeft weinig overhead en is dus lekker snel. Bovendien hoef je niet steeds door alle woorden heen te loopen, slechts door het aantal woorden van de invoer.

Wat ik me wel afvraag is hoe je omgaat met woorden die je niet kunt vinden.
In je voorbeeld het je namelijk "Robertson Avenue" en dit wordt "robertson". Betekent dit dat je "Robertson" niet in je woordenlijst hebt staan en dus moet het blijven en "Avenue" heb je wel dus dat verdwijnt?

[Woy]

Ik denk dat het toch het beste blijft om iets te doen met de input die krijgt en die tegen je verboden woorden lijst te houden. In je voorbeeld "Flat 5 115 Roe Lane" heb je 5 char sequences die je dan moet controleren. 5 keer een BinarySearch doen is echt niet zo zwaar. Het lijkt me ook dat een adres nooit uit extreem veel sequences zal bestaan.

Het is dan overigens wel van belang dat dingen als "blalbadfAvenue" niet verwijderd hoeven te worden want die vindt je dan natuurlijk nooit op deze manier. Als hier ook avenue weg gefilterd moet worden zul je toch iets moeten doen met de oplossing van Janoz denk

[ Voor 3% gewijzigd door Woy op 23-01-2006 14:57 ]

[MetalfanBlackness]

Kun je dan niet beter per woord (van de ingevoerde gegevens) een query uitvoeren op de database en als hij in de db voorkomt hem er dan uit halen?

[Blue-eagle]

Hmm.. zonder echt moeilijke (en interessante) dingen te gaan doen ontkom ik eigenlijk niet aan een loop, lijkt het. Zelfs een array zou gevuld moeten worden met values, er zal vast een Array.Fill(DataStream) zijn of iets dergelijks maar het achterliggende idee lijkt me toch terug vallen op hetzelfde: loop door 564 records en [doe iets]

Wat betreft Twilight Burn's opmerking; dat klopt helemaal! Alleen is het in deze opzet (voor mijn specifieke wens) niet van toepassing, het gaat erom dat adres en postcode gegevens (UK-only) worden opgeslagen in een database op een zo uitgekleed mogelijke manier zodat de beheerder van de site in zijn "back office" makkelijk kan zien wie zich meerdere malen registreerd voor een bepaalde dienst.

Als "flat5115roe" (uit mijn eerste voorbeeld) 20 keer voorkomt dan kan je dat makkelijk filteren in de database, als ik het niet had gefilterd dan had deze persoon zich dus 20 keer kunnen registreren onder:

• Flat 5 115 Roe Lane
• Flat 5 115 Roe Lanes
• Flat 5 115 Roe Lan
• Flat 5 115 Roe L.
• Etc.

Of in het geval van "junction" heb je al 8 mogelijke manieren om het op een geldige manier op te schrijven.

rwb: Heel erg bedankt voor je voorbeelden! En de rest ook natuurlijk Als ik hier meer tijd voor had dan was ik me zeker gaan verdiepen in andere oplossingen.. maarja.. tijd, geld, deadline, klant, boos, the usual

offtopic:
Er zijn ongetwijfeld betere oplossingen maar op deze manier moet het maar, mocht iemand toch nog een idee hebben wat me nog meer tijd gaat schelen: bring it!

[ACM]

rwb schreef op maandag 23 januari 2006 @ 14:35:
Aangezien een adress meestal niet extreem lang is kan je waarschijnlijk beter de woorden in je adres controleren tegen je lijst met niet toegestane woorden. ( Als je zorgt dat deze gesorteerd is kun je dit met een binary search doen bijvoorbeeld ).

Is een (Hash)Set niet nog weer wat sneller te doorzoeken dan een array? Althans, in Java is ie dat vziw wel.

[ Voor 5% gewijzigd door ACM op 23-01-2006 15:19 ]

[Janoz]

marrik schreef op maandag 23 januari 2006 @ 14:45:
Gooi alle woorden in een (gecachte) Array. Split je invoer op spaties en gebruik Array.IndexOf(string) om te bepalen of het stukje invoer voorkomt in je woordenlijst.
Een array heeft weinig overhead en is dus lekker snel. Bovendien hoef je niet steeds door alle woorden heen te loopen, slechts door het aantal woorden van de invoer.

En wat denk je dat Array.IndexOf() doet? Juist, die loopt (afhankelijk van de implementatie) door de complete lijst met woorden heen. Waar komt toch altijd het idee vandaan dat een API operatie vast altijd wel O(1) is?

[Janoz]

Blue-eagle schreef op maandag 23 januari 2006 @ 15:13:
Als "flat5115roe" (uit mijn eerste voorbeeld) 20 keer voorkomt dan kan je dat makkelijk filteren in de database, als ik het niet had gefilterd dan had deze persoon zich dus 20 keer kunnen registreren onder

Ik zou iig de spaties erin laten, of mag degene in flat 5 115 roe lane niet meer registreren wanneer zijn straatgenoot wonende te flat 51 15 roe lane al geregistreerd heeft.

[Woy]

ACM schreef op maandag 23 januari 2006 @ 15:19:
[...]

Is een (Hash)Set niet nog weer wat sneller te doorzoeken dan een array? Althans, in Java is ie dat vziw wel.

Het zou kunnen dat het nog sneller is ja. Het ligt er een beetje aan hoe zwaar het is om een hash te maken van een woord om de juiste index te berekenen en of de woorden netjes verspreid over de gebruikte array daarvoor komen.

Om het precies te weten te komen zou je het eigenlijk even moeten benchmarken maar ik denk dat het elkaar niet heel veel zal ontopen. Met een BinarySearch door een array van 564 woorden hoef je ook niet al te veel stappen te maken dus dat zou ook redelijk snel moeten zijn.

[Nvidiot]

Blue-eagle schreef op maandag 23 januari 2006 @ 14:20:
...
Voorbeeld:
Ik voer in: "Flat 5 115 Roe Lane", wat er over moet blijven is dit: "flat5115roe".
...

En nou woon ik op Flat 51 15 Roe Lane. Dan kan ik me dus niet meer registreren omdat iemand op Flat 5 115 Roe Lane zich al geregistreerd heeft. Handig...

[whoami]

rwb schreef op maandag 23 januari 2006 @ 15:24:
[...]

Het zou kunnen dat het nog sneller is ja. Het ligt er een beetje aan hoe zwaar het is om een hash te maken van een woord om de juiste index te berekenen en of de woorden netjes verspreid over de gebruikte array daarvoor komen.

Om het precies te weten te komen zou je het eigenlijk even moeten benchmarken maar ik denk dat het elkaar niet heel veel zal ontopen. Met een BinarySearch door een array van 564 woorden hoef je ook niet al te veel stappen te maken dus dat zou ook redelijk snel moeten zijn.

Een hashtable is sneller.
Je kan een O(1) zoek-operatie doen. (Je key moet dan wel uniek zijn natuurlijk).
Het maken van de hash is zo geen dure operatie vermoed ik. Daarbij komt nog eens dat je die hash voor ieder woord slechts 1x moet maken; je kan je hashtable daarna cachen.

(Om een BinarySearch te doen, moet je natuurlijk wel eerst je lijst sorteren).

[Woy]

whoami schreef op maandag 23 januari 2006 @ 15:58:
[...]

Een hashtable is sneller.
Je kan een O(1) zoek-operatie doen. (Je key moet dan wel uniek zijn natuurlijk).
Het maken van de hash is zo geen dure operatie vermoed ik. Daarbij komt nog eens dat je die hash voor ieder woord slechts 1x moet maken; je kan je hashtable daarna cachen.

Ja je kan je hashtable daarna cachen. Maar voor elk woord wat je wilt checken zul je weer moeten hashen. Dat het zoeken sneller gaat ben ik zowiezo met je eens. Maar er zijn natuurlijk nog meer dingen die mee tellen. Voor een HashTable heb je wel iets meer geheugen ruimte nodig aangezien een hashtable nooit een fillrate van 100% zal hebben en het kan ook nog voorkomen dat er op 1 index meerdere elementen komen omdat hun hash dezelfde index opleveren. Dan heb je op die positie nog steeds iets van een lijst waar je doorheen moet lopen voordat je het goede element hebt.

(Om een BinarySearch te doen, moet je natuurlijk wel eerst je lijst sorteren).

Ja dat klopt ( Had ik ook al vermeld in mijn post ) maar dat hoef je natuurlijk ook maar 1 maal te doen.

Al met al denk ik ook wel dat een HashTable wat sneller zal zijn maar er zijn nogal wat punten waar dat van afhankelijk is om het precies te kunnen voorspellen.

[whoami]

rwb schreef op maandag 23 januari 2006 @ 16:06:
[...]

Ja je kan je hashtable daarna cachen. Maar voor elk woord wat je wilt checken zul je weer moeten hashen. Dat het zoeken sneller gaat ben ik zowiezo met je eens. Maar er zijn natuurlijk nog meer dingen die mee tellen.

Het creeëren van een hash voor een string, zal wel sneller gaan dan iedere keer een array van 500 elementen doorlopen.

Dan heb je op die positie nog steeds iets van een lijst waar je doorheen moet lopen voordat je het goede element hebt.

Maar, een beperkte lijst.

[Woy]

whoami schreef op maandag 23 januari 2006 @ 16:08:
[...]
Het creeëren van een hash voor een string, zal wel sneller gaan dan iedere keer een array van 500 elementen doorlopen.

Met een BinarySearch loop je bij lange na niet door 500 elementen heen. Het is net zo zwaar als in een gebalanceerde boom zoeken ( Een boom met 2 children per node ).

Maar, een beperkte lijst.

True, maar het zorgt er wel voor dat het niet helemaal O( 1 ) is.

[whoami]

rwb schreef op maandag 23 januari 2006 @ 16:31:
[...]

Met een BinarySearch loop je bij lange na niet door 500 elementen heen. Het is net zo zwaar als in een gebalanceerde boom zoeken ( Een boom met 2 children per node ).

Ik had het niet over een binary-search; ik vergeleek het met sequentieel de lijst te doorlopen.

True, maar het zorgt er wel voor dat het niet helemaal O( 1 ) is.

Als je 2 items hebt die dezelfde hash opleveren idd.... Maar een binarysearch is ook niet o(1).

[ACM]

whoami schreef op maandag 23 januari 2006 @ 15:58:
Daarbij komt nog eens dat je die hash voor ieder woord slechts 1x moet maken; je kan je hashtable daarna cachen.

Als je zoektocht begint met een adres dat op te splitsen is in vijf termen, moet je vijf hashes aanmaken. En dat voor ieder adres opnieuw

Een dure operatie zal het nog steeds niet zijn, maar het is natuurlijk wel mogelijk dat het met zo weinig woorden dan niet meer opweegt tegen andere zoekoplossingen. Het is natuurlijk de vraag of de hashing+hashlook-up sneller is dan 564/2 (of log 564, afhankelijk van hoe je zoekt) gewone stringcompares.
Als je je paar termen uit het adres sorteert kan je met één enkele sweep door je gesorteerde woordarray al bepalen welke delen wel en niet eruit moeten.

In theorie kan je natuurlijk ook een eigen hashing maken, door bijvoorbeeld domweg een switch-case te bouwen op de eerste letter, daarbinnen op de tweede, etc of een op alle woorden in je lijst. Nadeel is dat zoiets hardcoded is, maar het kan de performance natuurlijk ten goede komen.

[Gé Brander]

Maar als "Flat 5 115 Roe Lane", "flat5115roe" wordt, en er is iemand met "Flat 51 15 Roe Lane", wordt dat dan niet ook "flat5115roe"? Of snap ik het niet helemaal?

[Woy]

whoami schreef op maandag 23 januari 2006 @ 16:40:
Ik had het niet over een binary-search; ik vergeleek het met sequentieel de lijst te doorlopen.

Ok. Maar sequentieel je lijst doorlopen is zowiezo niet slim.
[quote
Als je 2 items hebt die dezelfde hash opleveren idd.... Maar een binarysearch is ook niet o(1).[/quote]
Dat is waar. Als de gebruikte array voor de HashTable groot genoeg is zal een dubbel hash niet al te vaak voor moeten komen.

Maar zoals ik al eerder zei ben ik het er wel mee eens dat een HashTable waarschijnlijk wel sneller is. Probeerde alleen mijn aanpak nog een beetje te verdedigen

[Woy]

ACM schreef op maandag 23 januari 2006 @ 16:40:
[...]
In theorie kan je natuurlijk ook een eigen hashing maken, door bijvoorbeeld domweg een switch-case te bouwen op de eerste letter, daarbinnen op de tweede, etc of een op alle woorden in je lijst. Nadeel is dat zoiets hardcoded is, maar het kan de performance natuurlijk ten goede komen.

Mjah ik kan me bijna niet voorstellen dat dat nog loont om dat te maken. Het is echt geen super zware taak om 5 checks te doen tegen een HashTable/Array van minder als 600 elementen.

Als de performance voor dit stukje dan zo belangrijk is kan je die controle waarschijnlijk beter in een taal als c/c++ maken waar je veel meer controle over je geheugenbeheer hebt. Daar valt waarschijnlijk meer resultaat te behalen dan door zulke kleine optimalisaties.

[EfBe]

hashtable is niet echt te verslaan met je eigen sortspul, omdat hij intern al allerlei methoden gebruikt om snel keys e.d. terug te vinden in de hashbuckets. (key -> hashvalue -> bucketselect -> search voor key in bucket -> value retrieval).

[Woy]

EfBe schreef op maandag 23 januari 2006 @ 19:16:
hashtable is niet echt te verslaan met je eigen sortspul, omdat hij intern al allerlei methoden gebruikt om snel keys e.d. terug te vinden in de hashbuckets. (key -> hashvalue -> bucketselect -> search voor key in bucket -> value retrieval).

Dat klopt, ik had het ook niet over eigen sortspul maar over een standaard BinarySearch. Het enige wat ik me af vroeg was hoe snel het genereren van een hash was. Aangezien je door een relatief klein aantal elementen moet zoeken is een BinarySearch ook vrij snel. Ik ben het er ook wel mee eens dat een HashTable waarschijnlijk de snelste oplossing is hoor daar niet van.

[H!GHGuY]

ik denk dat als je het adres opsplits in meerdere velden, je het probleem voor jezelf gemakkelijker maakt.
bovendien kan ik zowiezo toch zoveel keer registreren als ik wil?
H!GHGuY - belgenland 15
H!GHGuY - belgenland 16 (als ik lieve buren hebben die post doorgeven aan mij)
H!GHGuY - onbestaand_adres 31 (als ik niet geinteresseerd ben in je post)

het doet me denken aan het creeren van unieke keys op basis van de familienaam
(van de ketel -> vdketel)
daarenboven is de methode die hierboven aangegeven wordt (de woorden uit je invoer vergelijken met een gesorteerde lijst van foute woorden (dmv binary search) het performantst is:
O(n*l*lg(m)) met n het aantal woorden te controleren en m het aantal "foute" woorden en l de totale lengte van je invoerstring
tegenover O(m*n*l) bij het vergelijken van enkel fout woord tov de invoer.

kijk voor snelle string-search algoritmen hier:
http://en.wikipedia.org/wiki/String_searching_algorithm

als geen van je "foute" strings langer is dan 32 karakters kun je't wel eens proberen met de bitap (shift-and) methode, dan kun je gelijk ook fuzzy compare doen.