Strohhalm

Sprung zu Navigation. Sprung zu Privat. Sprung zu StyleSwitcher. Sprung zum Inhalt.

 

Sprung zu Navigation. Sprung zu Privat. Sprung zu StyleSwitcher. Sprung zum Inhalt.

Privat

 

Anmelde-Formular



Als Strohhalm-Mitglied registrieren.

 

Sprung zu Navigation. Sprung zu Privat. Sprung zu StyleSwitcher. Sprung zum Inhalt.

Sprung zu Navigation. Sprung zu Privat. Sprung zu StyleSwitcher. Sprung zum Inhalt.

Archiv

 

strohhalm.org / Archiv / Programmierung Serverseitig / Eintrag lesen

Liste mit 30.000 Elementen auf Ähnlichkeit vergleichen

  1. Liste mit 30.000 Elementen auf Ähnlichkeit vergleichen

    anonymus 09. Dezember 2004, 19:13

    Hallo,

    in einer MySQL-Tabelle sind ca. 30.000 Datensätze. Mir geht es um ein Datenfeld, hier als "string" bezeichnet.

    Ziel soll es sein, Datensätze, dessen Datenfeld "string" in mehr als 80% übereinstimmen (ähnlich sind) zu bündeln und am Ende die einzelnen Bündel (Arrays) zurückzuliefern.

    Das Vergleichen selbst würde ich similar_text() überlassen, erste Tests scheinen ganz vernünftig zu sein.

    Mir würde als erstes in den Sinn kommen, jeden Datensatz mit jeweils allen anderen Datensätzen, insbesondere dem Datenfeld "string", zu vergleichen. Die Ergebnisse dann in einer Vielzahl von Arrays zu speichern und am Ende auszuwerten/auszugeben.

    Gibt es für ca. 30.000 Datensätze eine bessere Lösung, ähnliche Datensätze (80% müssen die beiden "string"-Datenfelder ähnlich sein) als "Paket" gebündelt auszugeben?

  2. Re: Liste mit 30.000 Elementen auf Ähnlichkeit vergleichen

    wahsaga 09. Dezember 2004, 21:07

    huh, das klingt auf jeden fall erst mal nach einer ziemlich performance-fressenden aufgabe ...


    mein erster denkansatz wäre, dass über ein mehrdimensionales array und evtl. rekursion zu lösen.

    $sortierung = array();
    $sortierung[0] = array();
    ersten datensatz in $sortierung[0][] reinwerfen.

    mit zweitem datensatz vergleichen - wenn ähnlichkeit > 80 %, diesen datensatz ebenfalls in $sortierung[0][] reinpacken - wenn nein, dann eine ebene höher in neues array rein packen - in $sortierung[1][].

    mit dem nächsten datensatz ähnlich verfahren - auf allen haupt-ebenen des arrays mit allen darunter bereits enthaltenen datensätzen vergleichen, durchschnittswert bilden.
    wenn dabei arrays sind, in denen die durchschnittliche übereinstimmung > 80% ist, dann datensatz in das array mit reinpacken, das den höchsten durchschnittswert aufweist.
    wenn nicht - wieder neuen arrayeintrag auf oberster ebene anlegen, datensatz reinpacken.

    und dann usw. usf. - für jeden weiteren datensatz durchschnittliche übereinstimmung mit den datensätzen aller unter-arrays berechnen, datensatz in das unter-array mit der größten durchschnittl. übereinstimmung packen, oder wenn keine > 80%, wieder neues array aufmachen ...


    ist allerdings nur ein konzeptueller schnellschuß ohne viel weiteres nachdenken über sinnhaftigkeit - kann also sein, dass dabei auch nur murks rauskommt, oder dass die ergebnisse je nach ursprungsreihenfolge der datensätze vollkommen andere sind!
    also im zweifelsfalle mal ausprobieren, sofern keine besseren vorschläge kommen.


    ach ja, btw: die max_execution_time würde ich dann aber gleich präventiv mal massiv heraufsetzen, bzw. gleich auf unendlich ;-)

  3. Re: Liste mit 30.000 Elementen auf Ähnlichkeit vergleichen

    jailkey 10. Dezember 2004, 00:43

    Hallo,
    wenn es nicht unbedingt eine 80% Übereinstimmung sein muss, sondern es auch ähnlich klingende Strings sein dürfen, könnte man es vielleicht so machen:

    SELECT SOUNDEX(string) as newstring GROUP BY newstring

    Ansonst würde ich mich wohl auch Wahsagas Methode anschließen.

    Gruß jailkey

  4. Re: Liste mit 30.000 Elementen auf Ähnlichkeit vergleichen

    Earl 10. Dezember 2004, 12:50

    @Wahsaga:

    Schönes Konzept, da schreibt man auch schnell mal ne Endlosschleife :-)

  5. Re: Liste mit 30.000 Elementen auf Ähnlichkeit vergleichen

    wahsaga 10. Dezember 2004, 13:55

    > @Wahsaga:
    >
    > Schönes Konzept, da schreibt man auch schnell mal ne Endlosschleife :-)

    in wie fern?

    der "worst case" wäre m.E., dass überhaupt keine zwei datensätze eine übereinstimmung von > 80% aufweisen - woraufhin du dann nachher wieder ein array mit 30.000 "unter-arrays" mit jeweils nur einem element hättest.

  6. Re: Liste mit 30.000 Elementen auf Ähnlichkeit vergleichen

    gooseman 11. Dezember 2004, 09:59

    Moin,

    also bei 30.000 Datensätzen, dann noch mit Rekursion frage ich mich schon ob nicht langsam das Speichelimit von PHP zu einem Problem wird. Steht ja auch nirgends wie lang die strings in dem Feld sind. Ich würde eher dazu tendieren das Problem datenbankseitig anzugehen, etwa wie oben beschrieben.

    gooseman

  7. Re: Liste mit 30.000 Elementen auf Ähnlichkeit vergleichen

    wahsaga 11. Dezember 2004, 14:35

    > also bei 30.000 Datensätzen, dann noch mit Rekursion

    na ja, rekursion kommt ja in meinem konzept gar nicht mehr vor ...
    war am anfang als schlagwort dahingeworfen, wurde dann aber doch nicht mehr gebraucht :-)


    > frage ich mich schon ob nicht langsam das Speichelimit von PHP zu einem Problem wird.

    na ja, dass es von der performance her sicher nicht so der hit wird, war ja von anfang an klar. und das ggf. limits heraufgesetzt werden müssen, auch.

    und ich gehe auch davon aus, dass das eher eine einmalaktion ist (bzw. regelmässig durchgeführt wird), aber nicht bei jedem seitenaufruf ...

  8. Re: Liste mit 30.000 Elementen auf Ähnlichkeit vergleichen

    anonymus 12. Dezember 2004, 15:22

    Hallo Wahsage, Jailkey & Earl,

    es handelt sich um eine ständig wiederkehrende Aufgabe, keine Einmallösung. Von daher ist die Performance schon sehr wichtig. Trotzdem vielen Dank an Wahsage für deine Idee, auch wenn die wahrscheinlich alle "Kapazitäten" sprengen würde ;)

    Ich denke, dass ich mir Jailkeys Lösung mal genauer anscheuen werde. Ich melde mich, wenn es geklappt hat.

    Danke an Euch.

 
Nach oben springen

.(c) 2002 - 2019 strohhalm.org Community.Server powered by Manitu.Software powered by Mathias Bank
.Impressum + Team.Datenschutz