[Kurze Frage] Ähnlichkeit zweier Strings ermitteln

[data89]

Hallo,

diesmal nur eine sehr kurze Frage: Wie ermittle ich die Ähnlichkeit zweier Strings (am Besten relativ)? In PHP gibt es diverse Funktionen - nur nicht in Java!

Danke,
data89

 

[hdi]

Was heisst für dich ähnlich?

es gibt zB equalsIgnoreCase(), der wertet dann "hAuS" und "Haus" als gleich.

 

[Wildcard]

http://de.wikipedia.org/wiki/Levenshtein-Distanz

 

[data89]

@Was heisst für dich ähnlich?

Ich gebe "Tier" und "Tor" ein und erhalte als Ergebnis: Ähnlichkeit 0,xyz (z.B. 0,59645 * 100 = 59,6 %).

 

[hdi]

Ja, und ist das jetzt das was Wildcard gepostet hat?
Und wie kommst du auf den Wert (wenn nicht)? War das jetzt nur ein Bsp?

Also was ja zB auch sehr leicht ist ist das ganze anhand der Anzahl von
unterschiedlichen Buchstaben festzulegen:

Tot + Tat = 66,6% gleich (2 von 3 Buchstaben)
Tier + Tot = 25% gleich (1 von 4 Buchstaben)

oder so

 

[Wildcard]

Also was ja zB auch sehr leicht ist ist das ganze anhand der Anzahl von
unterschiedlichen Buchstaben festzulegen:

Einfach ist das definitiv nicht. Siehe Link.
Beispiel

Ich bin zu Hause
Ichbin zu Hause

Nur ein Tippfehler, aber nur die ersten 3 Zeichen sind identisch.

 

[hdi]

Okay bei ganzen Sätzen könnte es doof werden. Natürlich kann man Whitespaces ignorieren,
aber das ist ja das gleiche nur andersrum.
Gehen würde es weiterhin irgendwie, aber dann nicht mehr leicht, stimmt.

Aber der Sinn versteckt sich hier bei dem ganzen eh n bisschen finde ich

PS: Ich sage nicht dass der Link kein Sinn macht, das sicherlich.Aber vllt will er ja
speziell nur irgendwas bestimmtes vergleichen, ich wollt ihm nur ne Anregung geben.

 

[Wildcard]

Okay bei ganzen Sätzen könnte es doof werden. Natürlich kann man Whitespaces ignorieren,
aber das ist ja das gleiche nur andersrum.

Bringt herzlich wenig. Ich hätte stattdessen auch einen Buchstaben zuviel einfügen können

 

[hdi]

Lies nochmal den von mir zitierten Text in deinem Post durch Ich weiss man freut sich schnell
wenn man's jemandem reinreiben kann, da überliest man oft was

 

[Wildcard]

Habe ich getan, verstehe den zweiten Halbsatz nach wie vor nicht.

aber das ist ja das gleiche nur andersrum.

?

 

[hdi]

Ok, bei erneutem Lesen versteh ich ihn auch nicht mehr
Ich dachte da grad an sowas wie:

[Da ist ein toller] "Wasserfall"
und
[Ich hab Angst dass ich in's] "Wasser fall"

Bei White-Space-Ignore würde das als gleich gewertet werden.
Ich dachte mir dass das ja nicht sein sollte. Aber rein vom Aufbau des Strings
wäre es ja wirklich fast das gleiche.

Naja ok, Wildcard 1 : 0 hdi

Insgesamt: Ca. Wildcard 234 : hdi 9

 

[masta // thomas]

Also ich würd da auch eher auf einen bewährten Algorithmus setzen statt mir selbst etwas zusammenzufrickeln

 

[Javalist]

Auf gehts:
http://de.wikipedia.org/wiki/Levenshtein-Distanz
http://de.wikipedia.org/wiki/Soundex
http://de.wikipedia.org/wiki/Kölner_Phonetik
http://de.wikipedia.org/wiki/Pattern_Matching
http://de.wikipedia.org/wiki/Stemming

Viel Spaß beim Lesen.

 

[noobadix]

Hallo!

Als Realisierung der Levenshtein-Distanz habe ich was ausgebrütet, das aber mir zu lange dauert. Eine Wortdatenbank soll auf einen Suchbegriff (pattern) durchsucht werden, sodass Treffer bei z.B. contious - conscious ermittelt werden. Verbesserungsvorschläge?

(Comparing ist eine abstrakte Klasse, die nur zum Implementieren von compare(String s) zwingen soll.)

class Resemble extends Comparing{
		int difference = 2;
		public boolean compare(String dataBaseEntry){
			dataBaseEntry=dataBaseEntry.trim();
			if(dataBaseEntry.length()-pattern.length()<-1 || dataBaseEntry.length()-pattern.length()>1) return false;
			if(!considerCase)dataBaseEntry = dataBaseEntry.toLowerCase();
			if(dataBaseEntry.contains(pattern) || pattern.contains(dataBaseEntry)) return true;
			return (dropLetters(difference,dataBaseEntry,pattern,false) || dropLetters(difference,pattern,dataBaseEntry,false));
		}
		
		private boolean dropLetters(int count,String pattern, String toDrop, boolean switched){
			String cut;
			char[] oChars = toDrop.toCharArray();
			for(int i=0;i<oChars.length;i++){
				cut="";
				for(int r=0;r<oChars.length;r++){
					if(r!=i)cut+=oChars[r];
				}
				if(pattern.contains(cut)&&pattern.length()-cut.length()<difference)return true;
				else{
					if(count>1 && oChars.length>2 && dropLetters(count-1,pattern,cut,false))return true;
					if(!switched&&count>1&&pattern.length()>1 && dropLetters(count,cut, pattern,true)) return true;
				}
			}
			return false;
		}
	}

 

[SlaterB]

gutes Suchen fängt immer mit Indexen an,

dein Comparing-Code zeigt nicht wie die Aufrufe drumherum aussehen, aber auf String-Länge zu vergleichen scheint ziemlich unnötig,
wird die gesamte Liste vorhandener Wörter durchlaufen und einzeln vergleichen?

nein, du brauchst z.B. einen Index nach Länge,
wenn man einen String mit 25 Buchstaben hat, muss man ihn auch nur mit allen anderen mit 25 Buchstaben vergleichen,
damit dürften 97.5% der Vergleiche (mit allen anderen Wörtern) wegfallen bzw. die Suche beschleunigt sich um den Faktor 25

der Preis des Geschwindigkeitszuwachses ist natürlich immer erhöhter Speicheraufwand für den Index und sonstige Hilfsstrukturen,
auch erhöhter Aufwand beim Speichern, Einfügen in Indexe

 

[noobadix]

Es ist so, dass ich in einem Vektor diverse Strings aus einem Wörterbuch halte, der auf Treffer durchforstet werden soll. Dazu biete ich verschiedene Suchmethoden wie Suchbegriff gleicht/ähnelt/ist Anagramm des/enthält Wörterbucheintrag(es). Jede Suchmethode ist als Erweiterung der abstrakten Klasse Comparing realisiert, die die Methode compare(String s) entsprechend gestaltet. comparator ist die Referenz auf dieses Comparing-Objekt.
Die Suche geschieht dann einfach mit

for(String s : words){
   if(comparator.compare(s)) return true;
}

Die Länge der Strings vergleiche ich am anfang der Methode um Zeit zu sparen, denn bei einer Levenshtein-Differenz von 2 kann ein Wort der Länge 3 einem der Länge 25 unmöglich ähneln. Wenn die Längen passen, "schaut sich die Methode den Sachverhalt näher an".

Was Du mit "indexen" meinst verstehe ich nicht. Magst Du das ausführen oder mir Schlagwörter zum googlen geben?

Dankö vorab!

 

[hdi]

Was Du mit "indexen" meinst verstehe ich nicht. Magst Du das ausführen oder mir Schlagwörter zum googlen geben?

Er meint Indizes. Plural von Index. Unter Index versteht man (hier) die Position eines Buchstabens innerhalb des Strings. Indizes sind null-basiert, d.h. erster Buchstabe hat Position 0, letzter Buchstabe hat Position string.length - 1. Viele Methoden der Klasse String arbeiten Index-basiert, zB charAt(int index) usw.

Allgemeiner: Ein Index ist die Position innerhalb eines Arrays. Strings sind intern char-Arrays.

 

[Gast2]

Nein, er meint eher einen Index im Sinne einer Indexstruktur. Also ne spezielle Struktur in der man besonders schnell bestimmte Sachen nachschlagen kann. Wie z.b. das Beispiel mit der Länge des Strings.

Welche Indices in dem Beispiel sinnvoll sind müsste man dann mal analysieren.

 

[noobadix]

Yo, hdi, das ist so weit klar, nur den Zusammenhang zur Problemstellung konnte ich noch nicht herstellen.

 

[hdi]

Nein, er meint eher einen Index im Sinne einer Indexstruktur. Also ne spezielle Struktur in der man besonders schnell bestimmte Sachen nachschlagen kann.

Achso, ok sorry das habe ich dann missverstanden. Also Stichwort Hashing?

HashMap<Integer, List<String>> // Strings mit Länge <Integer>

edit: Auweia, eine Map mit Integer als Key.. Passiert mir immer wieder mal. Aber 10 Sekunden später fällt mir auf wie dumm das ist.. Also dann einfach List<List<String>>, oder wieso reicht das nicht?