2 Strings auf Ähnlichkeit überprüfen

  • GM 8

  • 2 Strings auf Ähnlichkeit überprüfen

    Ich habe mal eine Frage, die bestimmt nicht neu ist.
    Und zwar würde ich gerne 2 Strings auf Ähnlichkeit überprüfen.
    (irgendwie str_compare(string1,string2) gibt dann einen Wert zwischen 0 und 100 zurück oder so)

    Also bspw.
    str_compare("Hallo Welt","Hallo Welt") = 100
    str_compare("Hallo Welt","Hallo Erde") = 50
    str_compere("Hallo Welt","Tschüss Mond") = 0

    Hat jemand ein Script dazu schonmal geschrieben?
    Die Methode, wie verglichen wird, ist mir relativ wurscht.

    Sollte keiner ein Scirpt zur Verfügung stellen können und ich muss doch selbst was proggen,
    welche Methode wäre denn am besten und vor Allem am wenigsten rechenintensiv?

    Hoffe mir kann weitergeholfen werden. 8)

  • Dein Problem kannst du doch ganz einfach selbst lösen. Alles was du brauchst ist eigentlich nur:

    GML-Quellcode

    1. string_char_at(str,index)


    So kannst du mit einer Schleife durch beide Strings laufen, wobei die Schleifenlänge

    GML-Quellcode

    1. string_length(str)

    des kleineren Strings beträgt, und jeweils die einzelnen Zeichen der Strings vergleichen und eine Bewertungsvariable nach oben zählen lassen, falls die Zeichen identisch sind. Dann kannst du das, wenn du möchtest, am Ende noch mit der String-Länge verrechnen und schon hast du, was du willst! :)

    Ist doch garnicht so schwer - probier es doch jetzt selbst erst einmal aus... dann fällt dir das nächste mal bei einem ähnlichen Problem die Lösung bestimmt selbst ein. :)

  • Dass ich was hinbekommen würde, hatte ich auch nicht angezweifelt. ;)
    Ich wollte halt nur fragen, ob es nicht da schon was gibt, und falls nicht,
    wie ich es am besten lösen kann. ;)

    Vielleicht könnte ich ja auch vorher erstmal abfragen, ob der eine String in dem andern enthalten ist?

    Und einfach mit string_chat_at die buchstaben zu vergleichen, könnte problematisch werden, wenn man z.B. hat:
    woifjeakl
    awoifjeak
    Die stimmen ja bis auf vorne und hinten schon ziemlich viel überein, nur eben nicht genau an jeder Stelle. ;)

  • Hier mal der Weg zum Script:

    1.Schritt
    Die Worte vergleichen könntest du, indem du mit dem split_string script aus dem Scriptarchiv eine
    list aller Wörter in den Sätzen erstellst. Benutz dazu einfach " ", also das Leerzeichen als Trennung.
    Nun überprüfst du, für jeden Wert aus einer der beiden listen, ob dieser in der anderen vorkommt.
    Wenn ja, setzt du den counter um eins höher.
    Dann teilst du den Counter durch die Anzahl der Worte der Liste, mit der verglichen wird und nimmst
    das Ergebnis mal hundert. Nun hast du den prozentualen Anteil der Übereinstimmung der Worte.
    Soweit eigentlich ganz einfach.

    2.Schritt
    Was passiert aber, wenn die eine list ("Hallo","Hallo","Hallo","Hallo","Hallo","Hallo")
    und die andere ("Hallo", "Tschüss", "Tschüss", "Tschüss", "Tschüss", "Tschüss") ist?

    100 % Übereinstimmung?

    Um das zuvermeiden solltest du, wenn ein Vergleich erfolgreich war,
    Den Eintrag aus der List löschen und zum nächsten Feld gehen.
    Also ("Me", "Gusta", "Tschüss") - "Me" war erfolgreich. Nun löscht du den Wert "Me" und
    setzt "Gusta" an Position 1 und "Tschüss" and Position 2, Position 3 setzt du am besten zu " "
    oder löschst sie (Weiß gerade nicht so richtig, ob das geht.)
    Jetzt sollte der prozenttuale Anteil an Worten stimmen.

    3.Schritt
    Listen löschen. Nur zur Erinnerung ^_^


    OPTIONAL:
    Die Reihenfolge kannst du bestimmen, indem du den 1 mit dem 1 Wert der Liste vergleichst,
    den 2 mit der 2 und so weiter. Das wäre wesentlich weniger arbeitsaufwändig zu erstellen
    und für den PC weniger rechenintensiv. Jedoch ist für eine KI der obere Weg besser.

    Groß- und Kleinschreibung:
    Das ist so eine Sache. Im Moment fällt mir keine gute Möglichkeit ein,
    das zu bewerkstelligen ohne, dass der Benutzer einen High End Prozessor benötigt.
    Wenn mir was einfällt, sage ich sofort bescheid.

    split_string:

    GML-Quellcode

    1. //Mit ds_list_find_value(split_string(str,Teiler),pos)
    2. //kann aus dem String str ein Wert an der Position pos herausgegeben werden.
    3. //Teiler ist das Zeichen oder die Zeichenfolge zum Abgrenzen.
    4. var _list,_str;
    5. _list=ds_list_create();
    6. _str=argument0;
    7. while(string_count(argument1,_str)>0)
    8. {
    9. ds_list_add(_list,string_copy(_str,1,string_pos(argument1,_str)-1));
    10. _str=string_delete(_str,1,string_pos(argument1,_str)+string_length(argument1)-1);
    11. }
    12. ds_list_add(_list,_str);
    13. return _list;
    Alles anzeigen


    EDIT: Hm, n' bisschen spät. Vielleicht hilft es ja.

  • Dafür solltest du ghost's Methode nehmen und einfach mittels der Funktionen überprüfen ob der Buchstabe an eienr bestimmten stelle, der selbe ist wie der Buchstabe der selben Stelle des anderen Wortes.
    Ein Bereits fertige Funktion kenn ich nicht, aber sie lässt sich einfach coden...

    Willst du auf diese Drachen und -eier klicken?
    Sie werden sich freuen ;)

  • Ich denke ein vernünftiger Ansatz ist beispielsweise die Verwendung der Levenshtein-Distanz.

    Die Levenshtein-Distanz zwischen zwei Zeichenketten ist die minimale Anzahl von Einfüge-, Lösch- und Ersetz-Operationen, um die erste Zeichenkette in die zweite umzuwandeln.

    Im verlinkten Wikipedia Artikel ist auch ein Algorithmus zur Bestimmung dieser Metrik zu finden. Diesen gibt's auch schon in GML, z.B. hier in der GMC.

  • Oh, interessant. Mir war auch noch so, als hätte ich den Begriff Levenshtein früher schon mal gehört. Jetzt weiß ich auch wo ^^
    Bin gar nicht auf die Idee gekommen, hier im Forum nach diesem Begriff zu suchen.

    Habe mir bei der Gelegenheit mal angeschaut, wie du die Levenshtein-Distanz auf einen Wert zwischen 0 und 1 umrechnest. Du machst das mit 1/(d+1), wobei d die Distanz ist. Dadurch sinkt der Wert natürlich am Anfang relativ schnell ab. Bei d=1 hat man ja bereits nur noch 0,5. Ich hätte da eher vorgeschlagen 1-d/max(n,m), wobei n und m die Längen der beiden Zeichenketten sind. Die Idee ist, dass die Levenshtein-Distanz höchstens so groß ist, wie die Länge des längeren Wortes (kann man sich leicht überlegen).

  • Das lässt sich ja glücklicher weise wieder umrechnen.

    Die von meiner Funktion wiedergegebenen Distanz zu 'richtiger'/einfacher Distanz: -(d-1)/d
    Die von meiner Funktion wiedergegebenen Distanz zu Bl@cksp@rks Distanz: 1+(d-1)/(d*max(len1,len2))

    Wo d der wiedergegebene Wert und len1, len2 die länge der Wörter ist.

    MfG SDX

  • Benutzer online 1

    1 Besucher