[PHP/Alg] naam-match vraagstuk

[sjoerdb2]

Wie kan mij helpen met het volgende vraagstuk:

Ik moet een stukje programma schrijven dat namen kan 'matchen'. De situatie is als volgt:
Aan de ene kant heb ik een lijst met bedrijven in een database. Aan de andere kant een CSV file.

Het eindresultaat na het uitvoeren van het stukje programma is dat ik een CSV bestand wil hebben met alle bedrijven die voorkomen in zowel de CSV als de MySQL database, met daarbij de door de gebruiker geselecteerde gegevens uit de CSV en/of de Database. De selectie van kolommen is op dit moment geen probleem.

• In de mysql database heb ik 20.000 bedrijven staan, met NAW gegevens en nog een aantal intern gebruikte codes. Dit aantal, 20.000, kan nog behoorlijk groeien.

• In het CSV bestand staat minimaal een bedrijfsnaam, en optioneel nog meer kolommen die niet in de mysql database voorkomen. In het csv bestand staan gemiddeld 1500 records

Wat er nu moet gebeuren is het matchen van deze twee gegevensbronnen. Ik kan dus alleen matchen op bedrijfsnaam. Het probleem is echter dat er niet 1 op 1 te matchen valt, omdat de schrijfwijze van de bedrijfsnamen nogal verschillend kan zijn.

Wat ik heb verzonnen is een functie die gebruikmaakt van de levenshtein functie in PHP. Een SELECT-query haalt alle records uit de database, en terwijl door het result wordt gelopen, wordt elk record tegen elk record in de csv gematcht. De functie wordt dus 20.000 x 1.500 = 30.000.000 keren aangeroepen. Deze methode werkt (bij kleinere aantallen), maar et zal jullie niet verbazen dat deze methode veel en veel te lang duurt.

De functie die ik heb gemaakt:

PHP:

<?
function nameScore($input1,$input2) {

  $input1 = str_replace(array("bv","b.v.","nv","n.v."),"",strtolower($input1));
  $input2 = str_replace(array("bv","b.v.","nv","n.v."),"",strtolower($input2));
  $score = levenshtein($input1,$input2);
  $num_chars = round(strlen($input1) + strlen($input2) /2);
 
  return round(pow(((1-($score/$num_chars))*100),2)*0.05);

}
?>

Pseudo-code die door de gegevens heenloopt:

code:

$data = array, 1 regel CSV per arrayelement 
while ($get = mysql_Fetch_object($query)) {
  for ($i=0;$i<sizeof($data);$i++) {
    $score = nameScore($data[$i]['naam'],$get->naam);
      als score > 185 registreer dat de match correct is    
  }
}

Ik weet niet of het zin heeft om de genoemge functies te optimaliseren, ik denk dat er een andere insteek voor de oplossing van het probleem moet komen.

Wat ik verder nog geprobeerd heb is in de database de eerste 2 en de laatste 2 tekens van een bedrijfsnaam op te slaan en daarmee een soort voorselectie creeeren. Door de verschillende schrijfwijzen is dit niet mogelijk.

Een aantal voorbeelden van gematchte bedrijfsnamen die in het doelbestand moeten komen:

code:

DUIJVELAAR POMPEN BV - DP Pumps/Duijvelaar Pompen
GERARD VINK STANDBOUW - Vink Standbouw b.v.
DONNER BOEKEN BV - PS Games Donner Boeken

Ik ben benieuwd of er iets te bedenken valt voor dit probleem, of dat men de gegevens maar moet gaan nettoyeren.

[Gonadan]

Ik vraag me af of hier een 100% sluitende methode voor te schrijven is.
Maar je kan altijd een poging wagen.

Misschien is het handig om eens naar regular expressions te kijken, die lijken me hier wel geschikt

[sjoerdb2]

Gonadan schreef op donderdag 23 maart 2006 @ 10:39:

Misschien is het handig om eens naar regular expressions te kijken, die lijken me hier wel geschikt

Op zich ben ik redelijk bekend met het schrijven van reguliere expressies, maar ik zie niet helemaal hoe ik ze hier kan toepassen. Ben erg benieuwd hoe wel.

Jouw opmerking triggerde bij mij de volgende mogelijkheid: Ik zou de middelste 3 a 4 letters van de bedrijfsnaam uit de CSV kunnen pakken en dan met een LIKE %$stukjebedrijfsnaam% in mysql aan de slag kunnen gaan, om daarmee een voorselectie te creëren.

Wat denken jullie hiervan?

[Gonadan]

sjoerdb schreef op donderdag 23 maart 2006 @ 10:44:
[...]


Op zich ben ik redelijk bekend met het schrijven van reguliere expressies, maar ik zie niet helemaal hoe ik ze hier kan toepassen. Ben erg benieuwd hoe wel.

Jouw opmerking triggerde bij mij de volgende mogelijkheid: Ik zou de middelste 3 a 4 letters van de bedrijfsnaam uit de CSV kunnen pakken en dan met een LIKE %$stukjebedrijfsnaam% in mysql aan de slag kunnen gaan, om daarmee een voorselectie te creëren.

Wat denken jullie hiervan?

Dat zal de performance in iedergeval een stuk verbeteren

Het risico is alleen dat als je nou net het verkeerde stukje kiest hij het goede bedrijf niet vindt

[Gonadan]

En nog even over die regex. Daarin kan je aangeven dat de punten in B.V. optioneel zijn, en dat de letters kapitaal of normaal mogen zijn. Met preg_match zoek je dan een stuk sneller denk ik

[Anoniem: 26421]

Wat is momenteel de parsetime, bij de huidige aantallen (20k, 1500)?
Wat noem je onacceptabel? Ik vindt namelijk, als gebruik van dit proces door een gebruiker aangegaan wordt, dat hij/zij best kan accepteren dat dit enkele minuten duurt. Ook als het proces bijvoorbeeld 15 minuten duurt, waarna er natuurlijk wel een gegarandeerde goede uitkomst moet zijn.

Dus, wat is je huidige parsetime?
En zijn de resultaten dan perfect?
En hoe vaak gaat deze batch gedraaid worden? Eenmalig? Of elke week 5 keer door een andere gebruiker met diverse bestanden?

Afhankelijk van de antwoorden heb ik er vervolgens wel een mening over

[ Voor 20% gewijzigd door Anoniem: 26421 op 23-03-2006 11:34 ]

[vinnux]

Misschien kun je voor de gein eens de functies soundex gebruiken en kijken wat er gebeurd.
Ben erg benieuwd. http://nl2.php.net/soundex

De functie similar-text kan ook helpen denk ik zo
http://nl2.php.net/manual/en/function.similar-text.php

[ Voor 30% gewijzigd door vinnux op 23-03-2006 11:43 ]

[DPLuS]

En het zal ook wel schelen als je eens begint met het inladen van het csv-bestand naar een tijdelijke tabel in de MySQL-database...

[BestTested!]

Anoniem: 26421 schreef op donderdag 23 maart 2006 @ 11:33:
Wat is momenteel de parsetime, bij de huidige aantallen (20k, 1500)?
Wat noem je onacceptabel? Ik vindt namelijk, als gebruik van dit proces door een gebruiker aangegaan wordt, dat hij/zij best kan accepteren dat dit enkele minuten duurt. Ook als het proces bijvoorbeeld 15 minuten duurt, waarna er natuurlijk wel een gegarandeerde goede uitkomst moet zijn.

Dus, wat is je huidige parsetime?
En zijn de resultaten dan perfect?
En hoe vaak gaat deze batch gedraaid worden? Eenmalig? Of elke week 5 keer door een andere gebruiker met diverse bestanden?

Afhankelijk van de antwoorden heb ik er vervolgens wel een mening over

Kan je niet in de MySQL database een extra veld creeeren 'CVS Name' of iets dergelijkse. Dan laat je je algoritme 1 nachtje draaien en update je steeds die veld bij een gevonden match.
De volgende keer dat je weer zo'n bestand moet matchen, kan je de oude matchings gebruiken, en dus alleen de nieuwe entries aan het algoritme voeren.
Dit werkt natuurlijk alleen als die namen in het CVS bestand elke keer hetzelfde zijn

[Anoniem: 26421]

Een oplossing kan de volgende zijn;

Je begint vanuit je verzameling namen in je database.
Pér naam uit je database doe je het volgende, je explode je naam op spaties. Op die manier krijg je een verzameling van alle woorden uit één database-naam. Bijvoorbeeld, "KEES JANSEN B.V." wordt als drie woorden gezien. Vervolgens ga je kijken, per woord, of dat woord voorkomt in een naam uit je CSV-bestand. Dus er wordt gekeken of KEES voorkomt in een naam uit je CSV-bestand, of JANSEN voorkomt, etc. Áls er een match is, dan sla je dit op. Op het einde kijk je welke naam uit je CSV de meeste matches heeft bij de naam uit je DB.

Voorbeeld.

Je hebt een naam in je database:
db1) KEES JANSEN BV (drie woorden dus).
Je hebt twee namen in je CSV-bestand:
csv1) HENK JANSEN NV
csv2) SLOOPWERKEN JANSEN KEES BV

Als je nu het algoritme draait zoals ik het hierboven probeerde te omschrijven, dan zul je een resultaat krijgen dat aangeeft dat er voor db1 twéé matches zijn gevonden: namelijk woord 1 én 2 uit je CSV bestand. Om onderscheid te maken zijn de woord-matches geteld en is het resultaat dat er bij csv1 één woord is gevonden dat matcht, en in csv2 dríe woorden (JANSEN, KEES en BV).
Uiteraard doe je de matchcontrole case-insensitive.

Je kunt vervolgens, in het voorbeeld, concluderen dat csv2 de beste match is.
Toch moet je daarmee oppassen. Er kunnen meerdere matches zijn waarbij evenveel woorden gevonden zijn. Dat is simpelweg een probleem dat handmatig bekeken moet worden.
Oftewel: als er meerdere namen uit je CSV-bestand overeenkomen met de naam in je DB, dan moet dit handmatig bekeken worden. In je CSV-bestand kunnen namelijk kopieën van namen staan.
Aan de andere kant, als er slechts één match gevonden wordt dan kun je er vanuit gaan dat dit de goede is, vindt ik. Je kunt deze stelling ook (kwaliteitief) opschroeven door te stellen dat er minimaal twee woorden overeen moeten komen in een naam, voordat deze als match gezien wordt. Dit is aan jou achteraf om te bepalen doormiddel van handmatige controles.

Een script wat bewerkstelligd wat ik allemaal verkondig, is het volgende.

PHP:

$array['db'] = array('DUIJVELAAR POMPEN BV','GERARD VINK STANDBOUW','DONNER BOEKEN BV');
$array['csv'] = array('DP Pumps/Duijvelaar Pompen','PS Games Donner Boeken','Vink Standbouw b.v.', 'Minister Donner');

foreach($array['db'] AS $dbKey => $dbString) {

    if(!isset($result)) $result = array();  
    $dbString = strtolower($dbString);
    $dbWords = explode(" ", $dbString);

    foreach($array['csv'] AS $csvKey => $csvString) {

        $csvString = strtolower($csvString);        
        $csvWords = explode(" ", $csvString);

        foreach($dbWords AS $dbWord) {

            if(in_array($dbWord, $csvWords)) {

                if(isset($result[$dbKey][$csvKey]))
                    $result[$dbKey][$csvKey]++;
                else
                    $result[$dbKey][$csvKey] = 1;

            }

        }

    }

}

Met als resultaat:

code:

Array
(
    [0] => Array
        (
            [0] => 1
        )

    [1] => Array
        (
            [2] => 2
        )

    [2] => Array
        (
            [1] => 2
            [3] => 1
        )

)

Een uitleg over deze resultaat-array.
De indexes van de eerste dimensie representeren de indexes van $array['db'].
De eerste dimentie-nodes hebben een waarde die wederom een array is.
De indexes van deze tweede dimentie representeren de indexes van $array['csv'].
De tweede dimentie-nodes hebben een waarde die aangeeft hoeveel woorden matchen als de namen vergeleken worden.

Zo zie je dat de derde node van de eerste dimentie aangeeft dat er twee namen in je CSV array overeenkomen met "DONNER BOEKEN BV", te weten de nodes van de csv array namen met de indexes 1 en 3, waarbij deze respectievelijk 2 woorden matchen en 1.

Het ís een oplossing, maar zeker geen waterdichte. Ik krijg een klein beetje het gevoel dat je situatie altijd (gedeeltelijk?) mensenwerk blijft. Ik zou dat kunnen aantonen met wederom een voorbeeld maar ik vindt deze mega-reply wel mooi zo eigenlijk. Succes, je kunt een stuk automatiseren (waarbij jij bepaald welke kwaliteitseisen hieraan gesteld worden - moet een csv naam minimaal 2 woorden van de naam bevatten voordat deze als match gezien wordt, of slechts één? Of zelfs drie?) maar een gedeelte blijft mensenwerk - helaas.

Daarbij is het jammer dat je nog geen antwoord hebt gegeven op mijn eerdere vragen. Maakt verder niet heel veel uit want ik blijf bij mijn standpunt dat batches als deze best tijdrovend mogen zijn (wat heet; een mens zou er dagen/weken/maanden mee bezig zijn).

[ Voor 9% gewijzigd door Anoniem: 26421 op 23-03-2006 12:54 ]

[sjoerdb2]

Anoniem: 26421 schreef op donderdag 23 maart 2006 @ 12:50:
Een geweldige reply!

Supergeweldig bedankt voor de moeite. Ik ga meteen aan de slag met deze oplossing en laat weten hoe dit match mechanisme voldoet. Het klinkt als een waterdichtere oplossing dan die ik hiervoor had verzonnen.

Nogmaals, Super!