# [Kurze Frage] Ähnlichkeit zweier Strings ermitteln



## data89 (24. Feb 2009)

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 (24. Feb 2009)

Was heisst für dich ähnlich?

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


----------



## Wildcard (24. Feb 2009)

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


----------



## data89 (25. Feb 2009)

@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 (25. Feb 2009)

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 (25. Feb 2009)

hdi hat gesagt.:


> 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 (25. Feb 2009)

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 (25. Feb 2009)

hdi hat gesagt.:


> 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 (25. Feb 2009)

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 (25. Feb 2009)

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


> aber das ist ja das gleiche nur andersrum.


?


----------



## hdi (25. Feb 2009)

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 (25. Feb 2009)

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


----------



## Javalist (26. Feb 2009)

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 (20. Okt 2011)

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 (20. Okt 2011)

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 (20. Okt 2011)

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 (20. Okt 2011)

> 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 (20. Okt 2011)

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 (20. Okt 2011)

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


----------



## hdi (20. Okt 2011)

> 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?


----------

