Kleine Knobelei zur Wortklauberei



  • Servus,

    jemand einen Tipp für den Lösungsweg: ich habe einen Sack mit Wörtern, alle Wörter werden miteinander verglichen. Am Ende liegen im Sack nur noch Wörter die mindestens zu 20 Prozent und höchstens zu 90 Prozent ähnlich sind. Ähnlich bedeutet hier den zeichenweisen Vergleich der Wörter an einer bestimmten Position. Furz und kurz wären also zu 75 Prozent ähnlich.

    Danke vorab für die ein oder andere Idee. Bisher habe ich einen Ansatz mit einigen Sets im Kopf, aber der ist fernab von genial 🙂


  • Mod

    Was ist jetzt das Problem?



  • Naja ich sitze gerade hier und sehe mich gedanklich immer in den wortsack fassen und wenn ich denke ich habe eine sinnmachende Strategie überlege ich wie der Pseudocode dazu aussieht.

    Ich dachte ich erhalte ein paar Pseudocode-Ideen zur Herangehensweise. Je effizienter die Idee desto besser, ich denke das ist das Problem ....


  • Mod

    Formulier doch mal das Problem anständig: Was hast du und was _genau_ willst du?

    So wie das jetzt formuliert ist reicht es ja, dass du ein passendes Paar findest und dann den Rest wegwirfst.



  • Aehnlichkeitsfunktion implementieren, jedes Wort mit jedem vergleichen (Aehnlichkeitsmatrix), Clusteringalgorithmus anwenden, groessten Cluster behalten.



  • Klingt so, als sollten wir deine Hausaufgabe machen.



  • Hier 2 Schlagwoerter fuer dich, bis du uns genauer sagst wo dein Problem liegt:

    http://en.wikipedia.org/wiki/Levenshtein_distance
    http://en.wikipedia.org/wiki/Multiple_sequence_alignment



  • Okay, also die Ähnlichkeitsberechnung bzw. die Distanz-Berechnung ist nicht das Problem. Trotzdem zur Verdeutlichung: Identisches Zeichen an identischer Position ist ein Hit, die Anzahl der Hits muss 20 Prozent der Zeichenlänge überschreiten und 90 Prozent unterschreiten. Sagen wir als Methodeneingangsparameter haben wir eine Liste oder ein Set mit 10 Strings gleicher Länge.

    Das Problem ist das Ablaufen, erst ging ich so vor: ich nutzte zwei for-Schleifen die verschachtelt waren, ich verglich Seq1 als aktuelle Basissequenz (for-aussen: 'kurz') mit Seq2 als StringToCompare (for-innen: 'furz') und stelle eine Ähnlichkeit von 75 Prozent fest. Dann nehme ich die nächste Sequenz der Liste und vergleiche diese mit 'kurz' ... Ging der Vergleich mit allen Sequenzen gut, dann kommt Seq1 in das Zielset, dem Methodenausgangsparameter. Ging der Vergleich einmal schief, dann landet die currentSeq im Müll. Auf diese Art und Weise filtere ich aber zuviele Sequenzen, denn:
    Ist Seq5 in der for-außen als Basissequenz dran, kann es sein, dass diese an Seq1 scheitert, die aber eh schon für den Müll vorgemerkt wurde und eigentlich gar nicht mehr bedacht werden sollte.

    Mein nächster Versuch: ich lege alle Sequenzen in ein Set, den PflückDaAlleSequenzenDerReiheNachRaus-Haufen. Ebenso habe ich ein Set, das MeineGefiltertenSeqs fasst, was das Zielset und die Rückgabe der Methode darstellt. Okay, erst landen alle Sequenzem im Pflückset. Dann folgt eine for-Schleife, die Seq1 bis Seq10 als currentSequence rausnimmt. Dieser currentString landet vorerst im Zielset und dann wird die Ähnlichkeit mit jeder Sequenz im Pflückset verglichen - gibts keinen Ähnlichkeits-Alarm, bleibt die currentSequenz im Zielset, gibts einen Alarm, wird die currentSequenz sowohl aus dem Zielset als auch aus dem Pflückset entfernt. Die nächste currentSequence muss sich dann mit den einmal aufgefallenen Sequenzen gar nicht mehr rumschlagen.

    Ich dachte so sollte es klappen, aber ich filtere immer noch zuviele Sequenzen heraus, sprich mein Zielset ist zu klein. Ich weiss das, weil ich eine Liste der Methodeneingangssequenzen und das Zielset vor mir liegen habe.

    Ich hoffe, dass nun mein Problem klarer geworden ist und freue mich auf die ein oder andere Idee, wie man derartige Probleme zielstrebig löst - danke vorab.



  • knivil schrieb:

    Aehnlichkeitsfunktion implementieren, jedes Wort mit jedem vergleichen (Aehnlichkeitsmatrix), Clusteringalgorithmus anwenden, groessten Cluster behalten.

    Okay, das klingt vielversprechend, bis zur Aehnlichkeitsmatrix kann ich dir folgen. Ich überlege dann mal, wie ich es dann hinbekomme, dass ich auf die richtige Art und Weise die zu streichenden Sequenzen erkenne, bzw. versuche zu klären, ob das mit dem Clustern mich ans Ziel führt - da muss ich noch mehr nachlesen und dies gedanklich durchdringen. Danke in jedem Fall für den Tipp.



  • Ist Seq5 in der for-außen als Basissequenz dran, kann es sein, dass diese an Seq1 scheitert, die aber eh schon für den Müll vorgemerkt wurde und eigentlich gar nicht mehr bedacht werden sollte.

    Ne, falsch. Denn dann kommt es auf einmal auf die Reihenfolge der Wörter beim Testen an, ob ein Wort gefiltert wird oder nicht.

    Oder ums an deinem Sackbeispiel darzustellen:

    Du hast 100 Elemente in deinem Sack. Und am Anfang haben wir die Elemente
    a,b,c,d,e,f,...

    mit folgenden Eigenschaften:
    a hat genau 92 Nachbarn
    f hat 22 Nachbarn
    b,c,d,e, haben genau die Nachbarn a und f.

    Nun ziehen wir mal unterschiedliche Sequenzen:
    1. a,f,b,c,d,e
    a ist nicht drin, weil es 2 Nachbarn zu viel hat.
    f ist drin, weil es 22>20 Nachbarn hat.
    b,c,d,e haben zu wenig Nachbarn, fliegen raus

    2. a,b,c,d,e,f
    a ist nicht drin, weil es 2 Nachbarn zu viel hat.
    b,c,d,e haben zu wenig Nachbarn, fliegen raus
    f ist nicht drin, weil es 18<20 Nachbarn hat.

    3. f,b,c,d,e,a
    f ist drin, weil es 22>20 Nachbarn hat.
    b,c,d,e haben zu wenig Nachbarn, fliegen raus
    a ist drin, weil es nur noch 88<90 Nachbarn hat.

    Du musst immer alle mit allen testen. sonst geht es nicht.

    Und nochwas:
    Wenn ich deine formulierung richtig verstanden habe, und am Ende für alle Elemente a,b im Sack 20<ähnlichkeit(a,b)<90 gelten soll, und du da smaximale set suchst, dann muss ich sagen:

    dein Problem ist NP-vollständig.

    //edit hab mich klarifiziert



  • Okay, um das Problem etwas greifbarer und die Lösung bzw. die Strategie
    für mich verständlicher zu machen, habe ich hier mal ein Beispiel
    gebaut. Eingabe ist eine Liste von Sequenzen, Ausgabe ein Set, das nur
    noch Sequenzen beinhaltet, die untereinander zu mehr als 20 und weniger
    als 90 Prozent ähnlich sind. Ähnlich bedeutet, dass ein Zeichen an
    gleicher Stelle vorkommt, HURZ und KURZ sind zu 75 % identisch.

    Eingabe:
    AFURZFURZA; (0)
    AKURZKURZA; (1)
    AHURZKURZZ; (2)
    AKURZKURZA; (3)
    BKURZFURZA; (4)
    GANZANDERS; (5)

    Wie man sieht, sollten die Sequenzen, 0, 1, 2 und 4 im Zielset liegen. 3
    ist identisch mit 1, 3 sollte also gefiltert werden, denn es
    überschreitet die 90%-Ähnlichkeit. 5 sollte ebenfalls raus, es
    unterschreitet die 20%-Schwelle.

    1. Schritt: die Ähnlichkeitsfunktion
    ... ich vergleiche die Buchstaben und fertig - passt soweit.

    2. Schritt: das for-Konstrukt
    ... mit zwei verschachtelten for-Schleifen jede Sequenz mit jeder vergleichen.
    for ( alleSequenzenAussen ) {
    string baseSeq = alleSequenzenAussen.at( i );
    for ( alleSequenzenInnen ) {
    string compareSeq = alleSequenzenInnen.at( j );

    // Schritt 3 Matrixeintrag bilden
    matrixRow( baseSeq, aehnlichkeitSeq0, aehnlihckeitSeq1, aehnlichkeitSeq2, aehnlichkeitSeq3, aehnlichkeitSeq4, aehnlichkeitSeq5 );
    }
    }

    3. Schritt: Matrix befüllen
    ... siehe Schritt zwei.

    4. Schritt: Lösung aus Matrix auslesen
    set<string> zielSet;

    for ( matrixLines )
    {
    // Eintraege als struct siehe MatrixRow
    }

    Hier weiß ich nicht weiter, wie ich da geschickt vorgehen kann,
    aufmerksam muss ich ja werden, wenn eine Ähnlichkeit hoeher als 90 oder
    weniger als 20 % ist.

    Danke vorab für einen weiteren Hinweis oder Lesetipp.



  • 1. Dein Beispiel ist für die Problemstellung zu einfach. Was machst du in folgendem Fall?

    aa
    ab
    ac
    dd
    de
    df
    dg
    db //meinetwegen auch ohne dieses Element

    2. Das Stichwort wurde schon genannt: Clustering. Ist nur leider ein NP-hartes Problem.



  • Okay, unter Clustering findet man sehr viel via Google, ich denke die Clusteranalyse ist das was ich brauche. Ich bemerkte auch, dass es diverse Ideen gibt, wie man aus der Ähnlichkeitsmatrix zu den Clustern kommt. Man muss sich vorher schon überlegen, ob ein Objekt etwa Teil mehrerer Cluster sein darf oder nicht ... naja, meine Ähnlichkeitsmatrix sieht ja etwa so aus (Sequenznummer als Beschriftung, Ähnlichkeit in den Zellen):

    | 0 1 2 3 4 5
    ----------------------------------
    0 | 1 0.8 0.8 0.8 0.8 0
    ----------------------------------
    1 | 0.8 1 0.8 1 0.8 0
    ----------------------------------
    2 | ...
    ----------------------------------
    3 | ...
    ----------------------------------
    4 | ...
    ----------------------------------
    5 | 0 0 0 0 0 1
    ----------------------------------

    Mein Ziel ist ja, dass im Sack nur noch Sequenzen drin sind, die untereinander 20-90 Prozent ähnlich sind - wie geht ihr da vor ? Ich denke und probiere selbst noch an einer Lösung, bin für Vorschläge natürlich dankbar.



  • Okay, ich wiederhole mich:

    Egal was du machst, du wirst nicht wesentlich schneller sein als "probiere alle möglichen Cluster aus und wähle den Besten". Zumindest nicht, solange du die optimale Lösung suchst.

    Wenn du eine Greedy Strategie möchtest, würde ich eventuell sowas versuchen:

    Liste l;
    fülle l mit Clustern der größe 1 (jedes Wort=1 Cluster).
    solange l.size() != 1:
        c=l.pop();
        durchsuche l nach Cluster c1 der die Bedingung am Besten erfüllt
        wenn c1 gefunden:
            enntferne c1 aus Liste
            erstelle cluster c2=(c,c1);
            l.push_back(c2);
    

    sollte klappen. Liefert aber bei weitem keine optimalen Ergebnisse.



  • Danke für deine Hartnäckigkeit - ich weiß nicht wie ich alle Cluster bilden kann, daran haperts.



  • Jay1980 schrieb:

    Danke für deine Hartnäckigkeit - ich weiß nicht wie ich alle Cluster bilden kann, daran haperts.

    ist nicht so schlimm. bei mehr als sagen wir 40 Wörtern würde es eh die Rechenpower deines Rechners sprengen 🙂



  • Schade, hatte gehofft ich erfahre noch, wie ich einen einzigen Cluster bilde ...


Anmelden zum Antworten