Strings auf Ähnlichkeit (nicht Gleichheit) vergleichen

Java-Forum Allgemeine Themen
1

Hi :slight_smile:

Ich bräuchte einen Weg um Strings auf Ähnlichkeit zu vergleichen.

String a = "play card 1 on target 1";
String b = "play card 1 and target 1";
String c = "play card 1 target 1";
String d = "play card 1 on 1";

// vom Prinzip her sind das alles die gleichen Aussagen. Spiele Karte 1 auf Gegner 1. Aber der Inhalt ist halt nicht exakt gleich. Als Mensch mag man
// das zwar verstehen, aber wie bringe ich dem PC sowas auch bei? :)
// Gibt es da irgendwelche Algorithmen die das vielleicht schaffen und die ich implementieren muss? 
//
// Das ist noch ein simples Beispiel. Zwar sind die Strings nicht allgemein länger, jedoch habe ich dutzende davon...

Ich hoffe das Problem ist klar geworden. Danke im voraus!

2
3

Dankeschön, sowas meinte ich! Eine frage habe ich aber noch:
Mein Problem bei der Sache ist, dass ich einen Eingangsstring habe, z.B.

"play card 1 on target 1"

Diese Strings sind sozusagen Befehle. Da das Programm aber weit über 100 Befehle kennt und all diese in einer Map gespeichert werden (Der Schlüssel ist der String, mit dem die Ähnlichkeit überprüft werden soll. Falls dies so ist dann soll der Wert (hier ein Consumer) genommen werden und der Eingangsstring wird verarbeitet).

Klartext: Ich müsste jeden Key durchlaufen, diesen mit dem Eingangsstring vergleichen und dann gucken, ob eine gewisse Ähnlichkeit besteht. Da sich Strings in der Map ziemlich stark untereinander unterscheiden, kann ich, nachdem ich einen hohen Treffer habe, aufhören zu iterieren.

Ich kann mir vorstellen, dass dieser Ansatz ziemlich langsam ist, daher wollte ich noch wissen, ob ihr irgendwelche Verbesserungen habt, die ich anwenden könnte. Vielleicht eine andere Datenstruktur oder einen komplett anderen Ansatz. Vielen Dank!

4

falls die zu analysierenden Befehle eingetippt werden kannst du für Zeit jedes Tippen eines (!) Buchstabens tausende bis Millionen Vergleiche machen,
das muss nicht kritisch sein

die Ähnlichkeit ist aber immer eine wackelige Sache,
ein nicht ganz so gutes, aber grob das Problem darstellendes Beispiel:
‚play card 1 on target 1‘ könnte zu einem Referenzstring ‚sell card 1 on target 1‘ ähnlicher sein als zu Referenzstring ‚play card 1 on 1‘
(wobei hier unwahrscheinlich dass der eine Referenzstring target verwendet, der andere nicht…)

für mehr Sicherheit wie auch deine gewünschte Beschleunigung Gedanke:
kann man sagen dass der erste Begriff als Kommando erhöhte Bedeutung hat, dass der wohl immer richtig eingetippt wird?
dann könnte man diesem ersten Wort entsprechend deutlich verwenden, das ‚play‘ extrahieren und in Datenstrukturen nachschauen,
welche Befehle auch mit ‚play‘ anfangen, vielleicht nur einer oder ein paar zum Stringvergleich

oder etwas allgemeiner könntest du alle wichtigen Begriffe wie ‚play‘ und ‚card‘, ‚target‘ aus den Referenzstrings extrahieren
und denen als Tags zuordnen,
außerdem andersrum zu allen einzelnen Tags eine Liste von Befehlen verwalten die sie enthalten

die Auswertung einer Eingabe ist dann auch wiederum Extrahieren von Tags und Kombination derselben zu wenigen übrigbleibenden Befehlen

evtl. diese Tags bewerten, ‚play‘ und ‚card‘ sind so wichtig dass sie unbedingt vorkommen müssen, ‚target‘ darf fehlen usw.,

oder auch einem Referenzbefehl „play card 1 on target 1“ (bzw. allen Befehlen der zugeordneten Kategorie ‚x auf y‘)
sematisch zuordnen dass auch ‚and‘ ein passender Tag ist,
so dass für eine Eingabe mit ‚and‘ der Referenzbefehl auch eine etwas höhere Bewertung bekommt, obwohl der gar nicht ‚and‘ enthält

denkbar, die Referenz schlicht nur noch ‚play card‘ zu benennen, oder überhaupt nur noch ein Befehl-Objekt/ Enum-Wert ohne echten String,
aber zugeordnete Hauptschlagwörter ‚play‘ und ‚card‘ sowie durch die manuelle Kategorie ‚x auf y‘ lauter übliche Verdächtige wie ‚on‘, ‚and‘, ‚target‘,
gar zwei Zahlen verlangen, was man auch wieder prüfen könnte

je weiter ich schreibe, desto mehr entfernt sich das vom ursprünglichen Gedanken der Referenzstrings,
desto komplizierter und mehr Arbeit :wink: aber so genauer wird es evtl.,

wirklich eindeutig wird es aber nie, egal wieviel Aufwand man betreibt, wenn ‚play sell card‘ eingetippt wird dann aufgeschmissen

5

Man könnte sich auch eine Synonymliste zulegen in der man für einen Begriff verschiedene Worte speichert. Ansonsten wie schon angedeutet schauen ich habe den Befehl Play, bei diesem können danach dann Folgende weitere Parameter angegeben werden. Generell kann man vielleicht verschiedene Pattern analysieren,…

6

[quote=SlaterB]falls die zu analysierenden Befehle eingetippt werden kannst du für Zeit jedes Tippen eines (!) Buchstabens tausende bis Millionen Vergleiche machen,
das muss nicht kritisch sein[/quote]
Der Befehl kommt als ganzes an.

[quote=SlaterB;126759]dann könnte man diesem ersten Wort entsprechend deutlich verwenden, das ‘play’ extrahieren und in Datenstrukturen nachschauen,
welche Befehle auch mit ‘play’ anfangen, vielleicht nur einer oder ein paar zum Stringvergleich[/quote]
Der Ansatz klingt gar nicht mal so schlecht! Ich glaube dass ist so die Sache die man am schnellsten implementieren könnte.

In den Datensätzen, die hier gerade so vor mir liegen, scheint der allerschwerste Springvergleich dann doch dieser hier zu sein:


"on target 1"
"and target 1"
"target 1"

Alle anderen Strings unterscheiden sich erheblich. Damit meine ich, dass der eine zum Beispiel

"buy car 1 and sell 2"

ist und der andere

"go home and chill out"

, also sich ziemlich stark voneinander unterscheiden. Daher denke ich mal, dass eine Aufteilung nach ‘Schlüsselwörtern’ ziemlich gut ist.
Der Input des Programms ist auch zu einem gewissen Maße begrenzt, sodass grobe Fehler und inkorrekte Strings ausgefiltert werden bevor überhaupt der ganze Kram passiert.

Mir ist gerade eine Idee gekommen:
Gibt es vllt eine Methode, die bevor irgendein Vergleich passiert, eine Art Tabelle kalkuliert indem es die erwarteten Strings analysiert? Somit müsste man dann diese Tabelle einmal erstellen (kann dann natürlich auch etwas zeitintensiver und resourcenintensiver sein), das nachschlagen müsste dann aber schneller gehen, da nur noch die Eingabe nach dem gleichen Prinzip berechnet werden muss und man dann guckt, wie die Differenz der beiden Ergebnisse ist.
Sowas ähnliches macht man nämlich oft in der Fotoerkennung. Man kann ja z.B. die Hashes der verwendeten Fotos, die als Vergleich dienen, schonmal anlegen bevor überhaupt verglichen wird und dann die Differenz der Hashes einfach berechnen.
Rich denke mal, dass ein Vergleich von Hashes hier nicht gut ist, da sich selbst bei einem einzigen char unterschied schon große unterschiede ergeben (und nicht wie bei Fotos wo der Hash dann nur minimal abweicht und man daher dann sagen kann, dass die Fotos sich bis zu einem gewissen Punkt ähneln).

7

das Bild hat den Vorteil fester Größe, auf das notfalls auch hin zu skalieren,

wenn in einem Satz fester Länge “abc def ghi jkl” das jkl durch xyz ersetzt wird,
dann ist das gleichbedeutend mit einem Bild in welchem das untere rechte Viertel getauscht wird

einen Hash von String braucht es nicht, der String selber ist der Hash, Differenzberechnung darauf gleich,

und so doll ist die Sache bei den Fotos ja anscheinend auch nicht, je nach Verfahren,
Berechnung eines Wertes bringt für sich nicht viel Aussage,
man muss wie du es auch schreibst mit allen anderen Differenz berechnen?

das ist eben wie der Anfang hier, mit allen Referenzen vergleichen,
jeder String-Vergleich liegt durchaus näher an einer Hash-Differenz als Vergleich ganzer Bilder

für konkrete Einzelwerte, von aktueller Berechnung auf einen Schlag einen bestimmten Bereich bestimmt, fehlt meist das Sortierkriterium,
bei Bildern vielleicht Farb- oder Helligkeitswerte als finalen Abdruck,
geht man bei Strings nach ersten Buchstaben, zweiten Buchstaben usw. dann ist das wieder der Fall bei dem alle ‘play’-Befehle nahe beieinander stehen

bei Bildern habe ich gerade an interessanten Links angeschaut
Detecting duplicate images using Python - The Iconfinder Blog
https://www.pureftpd.org/project/libpuzzle
letzterer in seiner Übersichts-Kürze mit dem bemerkenswerten Satz “Similar signatures share identical “words”, ie. identical sequences of values at the same positions.”

hier willst du dich zumindest im hinteren Teil gewiss nicht auf exakte Positionen beschränken,
aber das zeigt was der Word-Ansatz alles bringen kann, bei Strings umso natürlicher nach Vorkommen konkreter Wörter zu schauen

8

Hab jetzt ab Post #6 unten nicht mehr alles gelesen … nur noch überflogen
Grundsätzlich würde ich rein aus Gewohnheit “gegen” die Grund-Idee sprechen eine Ähnlichkeit suchen zu wollen sondern gleich den syntaktischen Befehlsaufbau. Wenn der User Schrott eingibt bekommt er eben die Meldung “X kann ich nich” … man erinnere sich an die alten Telnet-Muds … oder an DOTT bei dem “ungültige” Kombinationen schlicht mit nem lässigen Spruch kommentiert werden.

Vorteil: man braucht nicht irgendwie gucken “könnte passen” sondern gibt eine feste Struktur definitiv vor und weist fehlerhafte Eingaben direkt zurück.
Auch muss ich sagen dass die Idee “alle möglichen Kombinationen” als einen eigenen “Befehl” abzulegen recht schlecht ist. Denn letztlich hast du ein Command WAS zu tun ist, dann noch Parameter WIE und ggf. WOMIT … sowie ggf. Verkettungen.

Beispiel:
Warum willst du “buy car 1 and sell car 2” als EIN Command registireren ? Und dann noch Abarten wie “buy car 2 and buy car 3” … etc
Schon mal viel zu viel Aufwand für eine einfach Aufgabe.
Du nimmst erstmal das Command “buy” - damit hast du die Aktion die getätigt werden soll.
Dann nimmst du “car 1” - damit hast du das WOMIT mit dem du was machen willst - zerlegst dieses weiter in “car” und “1” und weist so: es geht um eine bestimmte Karre X … und X ist n.
Als nächstes kommt das “AND” - einfaches Keyword der Verkettung -> loop drum bauen mit do{}while(hasNext());

Um dein #1 zu analysieren:

“play” “card” “x” “y”
Was zwischen X und Y steht ist also schon mal komplett egal - fällt raus und braucht nicht weiter beachtet zu werden - genau wie alles zwischen den Keywords - in anbetracht das nach dem strip dieses Grundlayout bleibt.

Findest du nach “play” irgendwas anderes als “card” “item” “what-ever” was halt nicht in der liste der gültigen Operanden steht > Syntax-Fehler und abbrechen - gar nicht erst weiter versuchen was parsen zu wollen wo vermutlich zwar noch was kommt - könnte man aus Bequemlichkeit zum user noch versuchen … aber die Fehlerrate und DAS dann wieder gerade ziehen … da muss man schon viel langeweile haben.

9

@Sen-Mithrarin trifft gut das was ich auch gemeit hatte. Du kannst jedoch wie gesagt auch noch eine Liste mit Synonymen aufstellen, so das “play” und “spielen” das selbe bedeuten,… Aber das macht es schon deutlich komplizierter.

10

Das erinnert ein wenig an SQL. Schon mal geschaut, wie so ein Parser funktioniert und dann auf deinen Anwendungsfalls abgewandelt?

play card 1 on target 1
klingt ja wie
[SQL]INSERT INTO target1 VALUES (“Card 1”); [/SQL]

11

Man könnte es auch komplett übertrieben auch mit Locale basteln dass dann im Hintergrund automatisch das „Übersetzen“ der jeweiligen Landessprache in die eigentlichen Commands übernimmt. Dann braucht man das nicht hardcoden sondern kanns in properties auslagern. Klar, wäre machbar, und auch noch deutlich erweiterbar wie z.B. Syntax-Fehler ignorieren und trotzdem versuchen ein sinnvolles Command zu parsen. Dafür muss man aber dann doch wieder mit Heuristik arbeiten um die Fehlerquote nicht zu groß werden zu lassen. Z.B. Tippfehler können dann bei ungünstigen Umständen zur kompletten Fehlinterpretation führen. Kann man sicher vermeiden in dem man noch zwischendrin ne Prüfung einbaut: „Welche Commands mit welchen Params sind zum aktuellen Zeitpunk überhaupt zulässig?“.
Ich hatte diese Möglichkeiten nur nicht angesprochen da ich selbst 1.) nur re-aktiv auf Community-Wunsch sowas basteln würde und 2.) es ja auch nicht direkt zur gestellten Frage gehört was man denn noch so drumrumbasteln könnte.