3. Zwei Strings auf prozentuale Übereinstimmung vergleichen

Zwei Strings auf prozentuale Übereinstimmung vergleichen

  • C

    fischi1401 schrieb:

    Bei compare blicke ich bei dem Beispiel nicht durch: http://www.cplusplus.com/reference/string/string/compare/
    Ich bin mir nicht sicher, ob ich die Levenshtein-Distanz suche... eher sowas wie MATCH würde ich denken?

    string::compare dürfte nicht das sein, was du suchst - das führt einen exakten Vergleich durch und liefert zurück, welcher String größer ist. Ich denke mal, Levenstein klingt für deine Anwendung brauchbar (gibt es allerdings afaik nicht vorgefertigt).

    0
  • ?

    https://secure.wikimedia.org/wikibooks/en/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C.2B.2B

    0
  • F

    Ok. Danke.

    Das Levenshtein Verfahren scheint mir aber nicht das zu sein, was ich suche,
    denn es wird anscheinend nur geschaut, wieviele Buchstaben verschieden sind?!

    http://www.merriampark.com/ld.htm
    http://www.merriampark.com/ldcpp.htm

    Bei MATCH dachte ich jetzt an das Full Text Search (FTS3) in SQLite...

    0

  • @fischi1401:
    Handelt es sich bei den Strings immer nur um einzelne Wörter? Oder auch um Phrasen bzw. sogar ganze Sätze?

    Falls es einzelne Wörter sind, dann guck in den Link von seldon (Edit-Distance). Damit bekommst du raus, wie viele Änderungen nötig sind, um aus einem String den anderen zu machen. (Wobei jede Änderungen das Löschen, Hinzufügen oder Ersetzen eines Buchstaben sein kann - Verschiebungen zählen IIRC als 2 Operationen, 1x Löschen und 1x Einfügen)

    Natürlich kann man das auch für ganze Phrasen oder Sätze ausrechnen, aber da macht es IMO weniger Sinn.

    0
  • F

    Es sind meistens einzelne Wörter, aber auch öfters mal 2 oder 3 wörter...

    0
  • O

    fischi1401 schrieb:

    Das Levenshtein Verfahren scheint mir aber nicht das zu sein, was ich suche,
    denn es wird anscheinend nur geschaut, wieviele Buchstaben verschieden sind?!

    Nein, es wird geschaut, welche der Operationen Vertauschung, wechsel oder Löschen notwendig sind um aus dem einen Wort das andere zu erzeugen.

    0
  • C

    fischi1401 schrieb:

    Das Levenshtein Verfahren scheint mir aber nicht das zu sein, was ich suche,
    denn es wird anscheinend nur geschaut, wieviele Buchstaben verschieden sind?!

    Wolltest du nicht genau das wissen? Je kleiner die Distanz ist, desto ähnlicher sind sich die Wörter. Wenn du die Übereinstimmung in Prozent benötigst, mußt du den Wert nur passend umrechnen: Ähnlichkeit = (len-LD)/len

    0

  • Wobei ich die Vorgehensweise sowieso für Fragwürdig halte.
    Ich meine, man sollte die Vokabeln dann schon auch richtig schreiben können...
    Und es gibt genug Wörter, die mit minimalen Änderungen schon ein ganz anderes gültiges Wort ergeben. Was dann was ganz anderes bedeutet.

    0
  • F

    Ja... ich war die ganze Zeit etwas verwirrt was das Levenshtein Verfahren anbelangt.

    Ich würde das dann doch mal probieren und dann das Verhältnis bilden, wie CStoll geschrieben hat.

    Dann begebe ich mich mal auf die Suche nach einer C++ implementation.

    @hustbaer: Du hast recht... aber man muss auch einen gewissen Spielraum geben, bevor man sagen kann -> falsch... ich versuche schon alle Zeichen rauszunehmen, die nicht relevant sind...

    0

  • Also ich würde eher eine fixe Grenze verwenden, Edit-Distance 1 oder max. 2.
    Und für Wörter die relativ kurz sind überhaupt 0.

    ich versuche schon alle Zeichen rauszunehmen, die nicht relevant sind

    Welche sollten das sein?
    Im Prinzip sind sogar sämtliche "combining marks" wichtig, also Accents, die Umlaut-Punkte etc.

    Und falls es alternative Schreibweisen gibt (wie z.B. die ca. 100 Schreibweisen von Caffee), das ist eine Sache die der Vokabeltrainer vermutlich sowieso unterstützen muss.

    0
  • F

    Es sind die Satzzeichen und Klammerinhalte, die ich ignoriere: "Hilfe!" "Hilfe bei ..." "OMG (Ausdruck)"
    Ich möchte eben keinen Button [Doch richtig gewusst] verbauen, mit dem der User sich durchmogeln kann...
    Ich poste hier mal noch einen Link, wenn ich die dritte Beta veröffentliche...

    Ich halte es dennoch für sinnvoll Klammerinhalte und Punkte, Ausrufe/Fragezeichen zu ignorieren und dann nomal mit Stripslashes die Leerzeichen am Anfang und am Ende weg... Dann werde ich jetzt mal schauen wie ich diese Levenshtein-Distance einbaue und wie du sagtest, mache ich dann auch nur eine Distance von 1-3 je nach Phrasenlänge...

    0

  • Ja, OK, Satzzeichen etc. ignorieren macht vermutlich Sinn. Klammerinhalte auch, wenn die Vokabel so vorliegen, dass diverse Klassifizierungen/Hinweise direkt im String drinstehen, und nicht in eigenen Feldern.

    0
  • F

    Ich habe mich nochmal etwas mit der Levenshtein-Distance befasst und muss aber sagen, dass ich dort an meine Grenzen stoße...

    Ich habe hier nochmal was zum Thema Editierabstand gefunden:
    http://www.tillmann-wegst.de/fuzzy/index.htm

    Der Editierabstand ist definiert als die kleinste Menge elementarer Operationen, mit denen ein bestimmter String in einen bestimmten anderen String verändert werden kann. [...] Aus dem Editierabstand, der den Unterschied zwischen den Strings ausdrückt, kann der Wert für deren Ähnlichkeit abgeleitet werden.

    Das scheint eigentlich auch zu funktionieren, bzw. für meinen Problemfall passend zu sein...
    Die Frage ist jetzt von mir nur nochmal, mit welchen Funktionen mache ich das, wonach kann ich suchen bzw. ist das string::compare das was ich brauche?

    Ich habe in C++ noch nicht ganz so viele Jahre Erfahrung... 😕

    Mit freundlichen Grüßen
    fischi1401

    0
  • O

    musst du selber schreiben. Sowa sgibt e sin C++ von haus aus nicht. Und wie bereits gesagrt wurde, macht Compare etwas vollständig anderes.

    ps: was iam komplett fertigen beispielcode der hier verlinkt wurde bringt dich denn an deine Grenzen?

    0
  • F

    Naja... ich habe den C++ Programmcode von https://secure.wikimedia.org/wikibooks/en/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C.2B.2B
    erfolgreich übernommen...

    nur habe ich keine Ahnung wie ich diese Funktion ansprechen soll, wie ich ihr die zwei Strings übergebe...

    Ich hätte instinktiv das gemacht, um den Wert zu bekommen:

    int ergebnis = edit_distance("hallo", "hello");

    Aber das geht nicht, weil der Compiler sagt:
    In function `unsigned int edit_distance(const T&, const T&) [with T = char[6]]':instantiated from here

    Das ist gerade mein Problem, wo ich nicht weiter weiß...

    0
  • P

    fischi1401 schrieb:

    Aber das geht nicht, weil der Compiler sagt:
    In function `unsigned int edit_distance(const T&, const T&) [with T = char[6]]':instantiated from here

    Nein, sagt er nicht. Er sagt noch viel mehr. Unter anderem, was ihn daran stört.

    Und was du daraus lernen solltest:

    1. Poste immer die ganze Fehlermeldung, mit Fragmenten kann dir nicht geholfen werden.
    2. Sag nicht "erfolgreich übernommen", wenn du "erfolgreich kopiert, aber nicht verstanden" meinst. Du hast dir offenbar den Code nichtmal angesehen, auch wenns nur 10 Zeilen sind. Sonst wäre dir aufgefallen, dass da size() auf den übergebenen Objekten aufgerufen wird, und die Methode gibts bei blanken Arrays nunmal nicht. Der Code ist nur für Container geeignet.
    0
  • F

    Ja du hast Recht.
    Der Compiler gibt mir das aus:

    In function `unsigned int edit_distance(const T&, const T&) [with T = char[6]]':
instantiated from here
request for member `size' in `s1', which is of non-class type `const char[6]'
request for member `size' in `s2', which is of non-class type `const char[6]'

    Sehe ich das richtig, dass "T" mit "<class T> unsigned int" deklariert wird?

    Als was / wie muss ich meine Texte der Funktion zuführen?

    Es muss irgendetwas mit class sein, wenn ich den Compiler richtig interpretiere?
    Hier fehlen mir eben die Kenntnisse, wie ich fortfahren muss...

    Gruß, fischi1401.

    0

  • Benutze z.B. die std::string-Klasse (mittels #include <string> einbinden):

    std::string s1("Hallo");
std::string s2("Hallo");

int result = edit_distance(s1, s2);
    0
  • F

    Genau so einfach hatte ich mir das vorgestellt...

    Danke Th69 - den Rest schaffe ich allein 😉

    Aber auch ein Dankeschön an pumuckl, der mich nochmal dazu gebracht hat, mich mit der Funktion auseinanderzusetzen... 😉

    0
Anmelden zum Antworten