Dublettensuche

elTorito · 26.09.2008, 14:13

Hallo,

nach 5 Jahre regelmässiger PHP Programmierung mit einer anschliessender Pause von 4 Jahren Pause, versuch ich mich gerade wieder in die Materie einzuarbeiten.

Ich habe eine *.csv Datei, und eine MySql Tabelle , ich möchte die Datensätze der CSV Datei in die Tabelle importieren, vorher aber eine Dublettensuche starten um aus der CSV Datei ggf. Daten zu entfernen die womöglich schon in der MySql Tabelle vorhanden sind.

Mit der levenshtein Funktion ermittle ich eine Dubletten Wahrscheinlichkeit in %.

Ich nehme einen Datensatz aus der CSV Tabelle und vergleiche ihn mit jedem Eintrag in der MySql Tabelle und prüfe derzeit wie folgt:

PHP-Code:


			
if (_vergleich(FeldA_csv,FeldA_mysql) >80) { //Wenn Abweichung größer als 80% dann
  if (_vergleich(FeldB_csv,FeldB_mysql) >80) {
    if (_vergleich(FeldC_csv,FeldC_mysql) >80) {
      if (_vergleich(FeldD_csv,FeldD_mysql) >80) {
           echo "Der CSV Datensatz ist zu ".$summe_alle_vergleiche/4 ." % eine Doublette verglichen mit dem Datenbank Eintrag.";
      }
    }
  } 
}

Die Problematik ist klar, das funktioniert halt solange wie alles schön der Reihe nach abgearbeitet wird

Was aber wenn Feld A unter 80% faellt und B,C,D > 80% , dann würde hier keine Dublette erkannt.

Bevor ich da jetzt für jeden Fall eine Schleife erstelle wollte ich mal fragen wie man das elegant lösen könnte.

Vielen Dank schonmal.

EDIT:
Habe nun folgendes probiert:

PHP-Code:


			
$row = 1;                                                  // Anzahl der Arrays 
$handle = fopen ("datei.csv","r");                  // CSV Datei zum Lesen �ffnen
while ( ($data = fgetcsv ($handle, 1000, ";")) !== FALSE ) {     // Daten werden aus der Datei in ein Array $data gelesen
                                                                   
    $num = count ($data);                      // Anzahl Felder im Array $data werden gez�hlt
    $row++;                                    // Anzahl der Arrays wird inkrementiert
    
         
    $newData = array($data);
            
    $arr_company = check_FeldA($newData);
    $arr_street = check_FeldB($newData);
    $arr_zip = check_FeldC($newData);
    $arr_city = check_FeldD($newData);
    
    $result = array($arr_company,$arr_street,$arr_zip,$arr_city);
    print_r($result);
fclose ($handle);
}

Die Funktionen zum checken der Felder sehen so aus:

PHP-Code:


			
function check_FeldA($csvdata) {
    $sql = new mySQL(datenbank); // Verbindung zur Datenbank aufbauen.
    $daten = $sql->select("SELECT FeldA FROM Tabelle"); // Datenbank Abfrage
   
        for ($i = 0; $i < count($daten); $i++) { // Für jeden Datensatz in der Tabelle folgendes machen
        if (_vergleich($csvdata[0][0], utf8_decode($daten[$i]->FeldA)) > 80 ) {
          return $csvdata[0];
        }
    }
}

Was ich mir dabei gedacht habe .... die CSV Zeile geht als Array in die Funktion reingeht, dort vergleiche ich mit dem Datenbank Feld, und möchte alle in frage kommenden Datensaetze als Array wieder rausgeben, das gleiche mit den anderen Feldern, so das ich am Ende ein Array habe wo alle in Frage kommenden Datensaetze drin stehen sollten, wie ich den auseinander nehme weiß ich noch nicht.

Danke

EDIT2:

Zitat:

wie ich den auseinander nehme weiß ich noch nicht

so vielleicht:

PHP-Code:


			
    foreach ($result as $treffer) 
      if ($treffer != '') 
        echo print_r($treffer)."<hr>";

Meine Dummies werden bisher identifiziert.....

Was meint Ihr zu dem ganzen ?
Danke

Robsen · 17.10.2008, 23:32

Hallo,

zunächst ein Hinweis - ich empfinde es nicht als sehr klug, die Daten zunächst in einem Array zu halten und dann anschließend wegzuschreiben. Ok sagen wir es mal so - es ist abhängig von der Datenmenge. Bei sehr großen CSV Dateien kann es dann aber schnell ans Memory Limit gehen und dann ist aus die Maus. Bei kleinen CSV Dateien ist das jedoch kein Problem.

ok nun mal zu deiner Lösung:

PHP-Code:


			
$bufferRows = array ();

$handle = fopen ("datei.csv","r");
if ($handle)
{
    while ( ($row = fgetcsv ($handle, 1000, ";")) !== FALSE )
    {
        if (isDuplicate ($row, $bufferRows))
            continue;
        
        // wenn du sammeln möchtest 
        $bufferRows [] = $row;
    }
    fclose ($handle);
    
    // und ab in die DB
    // Fetchen von $bufferRows ... mysql_query
}

/**
 * findet Dupletten
 *
 * @param array $row ([])
 * @param array $rowsBuffered ([][])
 * @return boolean
 */
function isDuplicate ($row, $rowsBuffered)
{
    list ($fieldA, $fieldB, $fieldC, $fieldD) = $row;
    
    // hier dann dein Vergleichsalgo
    // z.B. sinngemäß! mußte natürlich anpassen
    foreach ($rowsBuffered as $bufferRow)
    {
        list ($fieldA_x, $fieldB_x, $fieldC_x, $fieldD_x) = $bufferRow;
        if ($fieldA==$fieldA_x) return true;
        if ($fieldB==$fieldB_x) return true;
        if ($fieldC==$fieldC_x) return true;
        if ($fieldD==$fieldD_x) return true;
    }
    
    return false;
}

Habe für mich unwesentliche DInge (Wie den Increment) mal raus gehauen....

Ich würde die Daten jedoch direkt in die DB schreiben und innerhalb der Funktion mit einer DB Abfrage arbeiten.

Grüße Robsen

elTorito · 20.10.2008, 08:51

Hallo Robsen,

die Sache mit dem Memory Limit habe ich schnell erfahren, leider ist es mir nicht erlaubt Daten direkt in die Datenbank zu schreiben, das Script laeuft Lokal und liest die Daten aus einer Online DB, meine Abhilfe bisher war einfach die CSV Datein zu verkleinern und das Memory Limit zu erhöhen.

Mein Skript sah letzendlich wie folgt aus, versuche aber das aber jetzt nochmal an hand von deinen Tipps zu optimieren

PHP-Code:


			
echo "<h1>Dublettensuche mit Levenshtein</h1><hr>";

include("timer.class.php");
$Timer = new Timer();
$Timer->start();
include("mysql.class.php");
include("levenshtein.class.php");


// Dubletten Wahrscheinlichkeiten bestimmen, ab wie viel % /durch fnc _similar ermittelt 
$per_csfd_company = 80;
$per_csfd_street = 80;
$per_csfd_streetnumber = 85;
$per_csfd_zip = 80;
$per_csfd_city = 80; 

$StrNr_are_one = 1;


$row = 0;                                                  // Anzahl der Arrays 
//$handle = fopen ("EST_20080730.csv","r");                  // CSV Datei zum Lesen �ffnen
$handle = fopen ("data016-gartenarbeiten.de.csv","r");                  // CSV Datei zum Lesen �ffnen
while ( ($data = fgetcsv ($handle, 1000, ";")) !== FALSE ) {     // Daten werden aus der Datei in ein Array $data gelesen
                                                                   
    $num = count ($data);                      // Anzahl Felder im Array $data werden gez�hlt
    $row++;                                    // Anzahl der Arrays wird inkrementiert
    
    #    for ($c=0; $c < $num; $c++) {              // FOR-Schleife zur Behandlung des Array $data[$c] 
        // Die For Schleife wird nicht benötigt weil die CSV folgendes Format aufweisen sollte 
        // $c ==   0= csfd_company // 1 = csfd_street // 2 = csfd_streetnumber // 3 = csfd_zip // 4 = csfd_city
            
    array_push($data,'Row'.$row);

    $newData = array($data);
            
    $arr_company = check_company($newData);
    $arr_adress = check_adress($newData);
    #$arr_street = check_street($newData);
    #$arr_zip = check_zip($newData);
    #$arr_city = check_city($newData);
    
    $result = array();
    $result[0] = $arr_company;
    $result[1] = $arr_adress;
    
    /*
    $result[1] = $arr_street;
    $result[2] = $arr_zip;
    $result[3] = $arr_city;
    */
    
    
    foreach ($result as $key => $value) {
       
        $newResult = $result[$key];
        
        if (!empty($newResult)) {
          foreach ($newResult as $key1 => $value2){
            echo "csv-Zeile ".$value2[0][12].":".$value2[0][0].", ".$value2[0][1].", ".$value2[0][2].", ".$value2[0][3].", ".$value2[0][4]."<br>";
            echo $value2[2]." % Wahrscheinlichkeit beim ".$value2[3]." verglichen mit<br>";
            echo "Db-csfd_id ". $value2[1]->csfd_id.": ".$value2[1]->csfd_company.", ".$value2[1]->csfd_street.", ".$value2[1]->csfd_streetnumber.", ".$value2[1]->csfd_zip.", ". $value2[1]->csfd_city."<hr>";
          }
        }
    }    
    
#   } FOR-Schleife zur Behandlung des Array $data[$c] 

}
fclose ($handle);

echo "<hr>";
$Timer->finish();
echo "Dauer Skriptausfuehrung: " . $Timer->getTime()."<br>";

PHP-Code:


			
function check_company($csvdata) {
    $sql = new mySQL(online); // Verbindung zur online Datenbank aufbauen.
    $daten = $sql->select("SELECT csfd_id,csfd_company,csfd_street,csfd_streetnumber,csfd_zip, csfd_city FROM classifieds"); // Datenbank Abfrage
    
    $arr_res = array ();
        
    for ($i = 0; $i < count($daten); $i++) { // Für jeden Datensatz in der Tabelle classifieds folgendes machen
      if (_similar($csvdata[0][0], utf8_decode($daten[$i]->csfd_company)) > 85 ) {
          $arr_res[$i][0] = $csvdata[0];
          $arr_res[$i][1] = $daten[$i];
          $arr_res[$i][2] = _similar($csvdata[0][0], utf8_decode($daten[$i]->csfd_company));
          $arr_res[$i][3] = 'company_check';
        }
    }
    return $arr_res;
}


function check_adress($csvdata) {
    $sql = new mySQL(online); // Verbindung zur online Datenbank aufbauen.
    $daten = $sql->select("SELECT csfd_id,csfd_company,csfd_street,csfd_streetnumber,csfd_zip, csfd_city  FROM classifieds"); // Datenbank Abfrage
   
        $ary_res = array ();
    for ($i = 0; $i < count($daten); $i++) { // Für jeden Datensatz in der Tabelle classifieds folgendes machen
        if (_similar($csvdata[0][4], utf8_decode($daten[$i]->csfd_city)) > 80 ) {
          if (_similar($csvdata[0][3], utf8_decode($daten[$i]->csfd_zip)) > 40 ) {
            if (_similar($csvdata[0][1], utf8_decode($daten[$i]->csfd_street)) > 80 ) {
              if (_similar($csvdata[0][2], utf8_decode($daten[$i]->csfd_streetnumber)) > 80 ) {
                $arr_res[$i][0] = $csvdata[0];
                $arr_res[$i][1] = $daten[$i];
                $arr_res[$i][2] = ((
                                  (_similar($csvdata[0][4], utf8_decode($daten[$i]->csfd_city)))
                                  +(_similar($csvdata[0][3], utf8_decode($daten[$i]->csfd_zip)))
                                  +(_similar($csvdata[0][2], utf8_decode($daten[$i]->csfd_streetnumber)))
                                  +(_similar($csvdata[0][1], utf8_decode($daten[$i]->csfd_street)))
                                  )/4)
                                  ;
                $arr_res[$i][3] = 'adress_check';
              }
            }
          }
        }
    }
    return  $arr_res;
}

Chriz · 20.10.2008, 09:15

Gehts dir also jetzt nurnoch um die Performance oder klappt das ganze Skript nicht?

CSV in die MySQL druecken:
MySQL :: MySQL 5.0 Reference Manual :: 12.2.6 LOAD DATA INFILE Syntax

Levenshtein als STORED PROCEDURE:
codejanitor Levenshtein Distance as a MySQL Stored Function

elTorito · 20.10.2008, 09:42

Geht mir nur noch um die Performance, mit den Ergebnissen des Skripts bin ich sehr zufrieden, meine Vorgehensweise ist das ich mir alle möglichen Dubletten auflisten lasse, um dann anschliessend Manuell zu entscheiden was eine Dublette ist. Schaue mir das mit dem MySql auch nochmal an, theoritisch waere möglich das ich die CSV in eine Temporaere Tabelle einlese um dann von dort aus weiter zu arbeiten, muss ich mal mit dem Admin klaeren. Danke.

17.10.2008, 23:32	#2 (permalink)
Robsen Neuer Benutzer Registriert seit: 17.10.2008 Beiträge: 20	Hallo, zunächst ein Hinweis - ich empfinde es nicht als sehr klug, die Daten zunächst in einem Array zu halten und dann anschließend wegzuschreiben. Ok sagen wir es mal so - es ist abhängig von der Datenmenge. Bei sehr großen CSV Dateien kann es dann aber schnell ans Memory Limit gehen und dann ist aus die Maus. Bei kleinen CSV Dateien ist das jedoch kein Problem. ok nun mal zu deiner Lösung: PHP-Code: $bufferRows = array (); $handle = fopen ("datei.csv","r"); if ($handle) { while ( ($row = fgetcsv ($handle, 1000, ";")) !== FALSE ) { if (isDuplicate ($row, $bufferRows)) continue; // wenn du sammeln möchtest $bufferRows [] = $row; } fclose ($handle); // und ab in die DB // Fetchen von $bufferRows ... mysql_query } /** * findet Dupletten * * @param array $row ([]) * @param array $rowsBuffered ([][]) * @return boolean / function isDuplicate ($row, $rowsBuffered) { list ($fieldA, $fieldB, $fieldC, $fieldD) = $row; // hier dann dein Vergleichsalgo // z.B. sinngemäß! mußte natürlich anpassen foreach ($rowsBuffered as $bufferRow) { list ($fieldA_x, $fieldB_x, $fieldC_x, $fieldD_x) = $bufferRow; if ($fieldA==$fieldA_x) return true; if ($fieldB==$fieldB_x) return true; if ($fieldC==$fieldC_x) return true; if ($fieldD==$fieldD_x) return true; } return false; } Habe für mich unwesentliche DInge (Wie den Increment) mal raus gehauen.... Ich würde die Daten jedoch direkt in die DB schreiben und innerhalb der Funktion mit einer DB Abfrage arbeiten. Grüße Robsen Geändert von Robsen (17.10.2008 um 23:44 Uhr).*

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Thema bewerten
Thema bewerten:


Mister Ad PHP Code Flüsterer Registriert seit: 21.08.2005 Beiträge: 4682 PHP-Kenntnisse: Fortgeschritten

20.10.2008, 08:51	#3 (permalink)
elTorito Neuer Benutzer Registriert seit: 26.09.2008 Beiträge: 3	Hallo Robsen, die Sache mit dem Memory Limit habe ich schnell erfahren, leider ist es mir nicht erlaubt Daten direkt in die Datenbank zu schreiben, das Script laeuft Lokal und liest die Daten aus einer Online DB, meine Abhilfe bisher war einfach die CSV Datein zu verkleinern und das Memory Limit zu erhöhen. Mein Skript sah letzendlich wie folgt aus, versuche aber das aber jetzt nochmal an hand von deinen Tipps zu optimieren PHP-Code: echo "<h1>Dublettensuche mit Levenshtein</h1><hr>"; include("timer.class.php"); $Timer = new Timer(); $Timer->start(); include("mysql.class.php"); include("levenshtein.class.php"); // Dubletten Wahrscheinlichkeiten bestimmen, ab wie viel % /durch fnc _similar ermittelt $per_csfd_company = 80; $per_csfd_street = 80; $per_csfd_streetnumber = 85; $per_csfd_zip = 80; $per_csfd_city = 80; $StrNr_are_one = 1; $row = 0; // Anzahl der Arrays //$handle = fopen ("EST_20080730.csv","r"); // CSV Datei zum Lesen �ffnen $handle = fopen ("data016-gartenarbeiten.de.csv","r"); // CSV Datei zum Lesen �ffnen while ( ($data = fgetcsv ($handle, 1000, ";")) !== FALSE ) { // Daten werden aus der Datei in ein Array $data gelesen $num = count ($data); // Anzahl Felder im Array $data werden gez�hlt $row++; // Anzahl der Arrays wird inkrementiert # for ($c=0; $c < $num; $c++) { // FOR-Schleife zur Behandlung des Array $data[$c] // Die For Schleife wird nicht benötigt weil die CSV folgendes Format aufweisen sollte // $c == 0= csfd_company // 1 = csfd_street // 2 = csfd_streetnumber // 3 = csfd_zip // 4 = csfd_city array_push($data,'Row'.$row); $newData = array($data); $arr_company = check_company($newData); $arr_adress = check_adress($newData); #$arr_street = check_street($newData); #$arr_zip = check_zip($newData); #$arr_city = check_city($newData); $result = array(); $result[0] = $arr_company; $result[1] = $arr_adress; /* $result[1] = $arr_street; $result[2] = $arr_zip; $result[3] = $arr_city; */ foreach ($result as $key => $value) { $newResult = $result[$key]; if (!empty($newResult)) { foreach ($newResult as $key1 => $value2){ echo "csv-Zeile ".$value2[0][12].":".$value2[0][0].", ".$value2[0][1].", ".$value2[0][2].", ".$value2[0][3].", ".$value2[0][4]."<br>"; echo $value2[2]." % Wahrscheinlichkeit beim ".$value2[3]." verglichen mit<br>"; echo "Db-csfd_id ". $value2[1]->csfd_id.": ".$value2[1]->csfd_company.", ".$value2[1]->csfd_street.", ".$value2[1]->csfd_streetnumber.", ".$value2[1]->csfd_zip.", ". $value2[1]->csfd_city."<hr>"; } } } # } FOR-Schleife zur Behandlung des Array $data[$c] } fclose ($handle); echo "<hr>"; $Timer->finish(); echo "Dauer Skriptausfuehrung: " . $Timer->getTime()."<br>"; PHP-Code: function check_company($csvdata) { $sql = new mySQL(online); // Verbindung zur online Datenbank aufbauen. $daten = $sql->select("SELECT csfd_id,csfd_company,csfd_street,csfd_streetnumber,csfd_zip, csfd_city FROM classifieds"); // Datenbank Abfrage $arr_res = array (); for ($i = 0; $i < count($daten); $i++) { // Für jeden Datensatz in der Tabelle classifieds folgendes machen if (_similar($csvdata[0][0], utf8_decode($daten[$i]->csfd_company)) > 85 ) { $arr_res[$i][0] = $csvdata[0]; $arr_res[$i][1] = $daten[$i]; $arr_res[$i][2] = _similar($csvdata[0][0], utf8_decode($daten[$i]->csfd_company)); $arr_res[$i][3] = 'company_check'; } } return $arr_res; } function check_adress($csvdata) { $sql = new mySQL(online); // Verbindung zur online Datenbank aufbauen. $daten = $sql->select("SELECT csfd_id,csfd_company,csfd_street,csfd_streetnumber,csfd_zip, csfd_city FROM classifieds"); // Datenbank Abfrage $ary_res = array (); for ($i = 0; $i < count($daten); $i++) { // Für jeden Datensatz in der Tabelle classifieds folgendes machen if (_similar($csvdata[0][4], utf8_decode($daten[$i]->csfd_city)) > 80 ) { if (_similar($csvdata[0][3], utf8_decode($daten[$i]->csfd_zip)) > 40 ) { if (_similar($csvdata[0][1], utf8_decode($daten[$i]->csfd_street)) > 80 ) { if (_similar($csvdata[0][2], utf8_decode($daten[$i]->csfd_streetnumber)) > 80 ) { $arr_res[$i][0] = $csvdata[0]; $arr_res[$i][1] = $daten[$i]; $arr_res[$i][2] = (( (_similar($csvdata[0][4], utf8_decode($daten[$i]->csfd_city))) +(_similar($csvdata[0][3], utf8_decode($daten[$i]->csfd_zip))) +(_similar($csvdata[0][2], utf8_decode($daten[$i]->csfd_streetnumber))) +(_similar($csvdata[0][1], utf8_decode($daten[$i]->csfd_street))) )/4) ; $arr_res[$i][3] = 'adress_check'; } } } } } return $arr_res; }

20.10.2008, 09:15	#4 (permalink)
Chriz Moderator Registriert seit: 11.05.2008 Beiträge: 3.294	Gehts dir also jetzt nurnoch um die Performance oder klappt das ganze Skript nicht? CSV in die MySQL druecken: MySQL :: MySQL 5.0 Reference Manual :: 12.2.6 LOAD DATA INFILE Syntax Levenshtein als STORED PROCEDURE: codejanitor Levenshtein Distance as a MySQL Stored Function

20.10.2008, 09:42	#5 (permalink)
elTorito Neuer Benutzer Registriert seit: 26.09.2008 Beiträge: 3	Geht mir nur noch um die Performance, mit den Ergebnissen des Skripts bin ich sehr zufrieden, meine Vorgehensweise ist das ich mir alle möglichen Dubletten auflisten lasse, um dann anschliessend Manuell zu entscheiden was eine Dublette ist. Schaue mir das mit dem MySql auch nochmal an, theoritisch waere möglich das ich die CSV in eine Temporaere Tabelle einlese um dann von dort aus weiter zu arbeiten, muss ich mal mit dem Admin klaeren. Danke.