Best Match / Best Fit auf Strings

Status
Nicht offen für weitere Antworten.

micbur

Bekanntes Mitglied
Hallo,

kennt jemand einen Best Match-Algorithmus auf Strings?

Ich habe eine Stringrepräsentation eines Identifiers (zum Beispiel: java.lang.String). Nun habe ich noch die Package-List des Javadocs und möchte darin möglichst viel meines Identifiers wiederfinden. In diesem Fall ist das 'java.lang'.

Allgemein:
In der Package-List befindet sich eine Liste von Strings
a.b.c
a.b.c.d
a.b.c.e
a.b.f
a.g

Ich habe einen Identifier a.b.c.d.X und möchte nun die Zeile 'a.b.c.d' finden. Falls 'a.b.c.d' aber nicht existiert, wäre 'a.b.c' die logische Wahl.

Egal, was ich mir ausdenke, ich komme auf keinen gescheiten Algorithmus. Im Internet ist es auch nur so allgemein beschrieben, nach der Art: "wir haben vor". Aber wenn es dann konkret werden soll, ist das Dokument zuende.

Vielleicht hat ja jemand in seinem Studium aufgepasst ;-) Ich bin Datenbankler, ich kenne nur stark strukturierte Daten. Entweder passt es, oder es passt nicht.

Ciao, micbur
 

micbur

Bekanntes Mitglied
Achso, falls es noch jemanden interessiert oder jemand einen Verbesserungsvorschlag hat ...

Code:
	/**
	 * Compares two strings char by char. Dots (.) will be ignored. The methode jumps over dots. 
	 * @param arg1
	 * @param arg2
	 * @return how many chars are equal from the beginning of the given strings.
	 */
	private int compare(String arg1, String arg2) {
		
		int equilationLevel = 0; // number of equal chars, begin at pos 0, inital uncompared strings = 0
		int shorter = (arg1.length() <= arg2.length()) ? arg1.length() : arg2.length();
		// Ignore Dots
		// Punkte müssen ignoriert werden. Auf String-Ebene ist 'java.lang.reg' ähnlicher 
		// zu 'java.lang.String' als 'java.lang', dabei ist 'java.lang' das Ziel, was wir 
		// suchen. 

		for (int i = 0; i < shorter; i++) {
			// an beiden Stellen der Strings dürfen keine Punkte sein. Wenn an der Stelle des 
			// einen Strings ein Punkt ist und am anderen nicht, sind die Strings eh ungleich. 
			if ( (arg1.charAt(i) != '.') && (arg2.charAt(i) != '.')
					&&  (arg1.charAt(i) == arg2.charAt(i)) ) {
					equilationLevel++;
			}
		}
		
		return equilationLevel;
	}

	/**
	 * Compares two strings to a <code>matcher</code>. Returns one of the given strings 
	 * which matches best with a given <code>matcher</code> string. If <code>arg1</code> better matches 
	 * than <code>arg2</code>, <code>arg1</code> will be returned. If <code>arg2</code> better matches 
	 * than <code>arg1</code>, <code>arg2</code> will be returned.
	 * 
	 * The methode beginns to compare strings at the beginning of the strings. 
	 * 
	 * If <code>arg1</code> is <code>null</code>, <code>arg2</code> will be returned. 
	 * If <code>arg2</code> is <code>null</code>, <code>arg1</code> will be returned. 
	 * If <code>matcher</code> is <code>null</code>, <code>null</code> will be returned. 
	 * If <code>arg1</code> and <code>arg2</code> are <code>null</code>, <code>null</code> will be returned. 
	 * @param arg1
	 * @param arg2
	 * @param matcher
	 * @return
	 */
	public String findBestMatch(String arg1, String arg2, String matcher) {

		if (arg1 == null) {
			return arg2;
		}
		else if (arg2 == null) {
			return arg1;
		}
		else if (matcher == null) {
			return null;
		}

		int compare1Matcher = this.compare(arg1, matcher);
		int compare2Matcher = this.compare(arg2, matcher);
//		if (debug) {
//			System.out.println(arg1 + "("+compare1Matcher+"), " + arg2 + "("+compare2Matcher+"), " + matcher);
//		}
		// ich möchte 'best match'. maximale Übereinstimmung bei der kürzesten Länge.
		// haben zwei String dieselbe Bewertung beim Match, ist der kürzere die bessere Wahl
		if (compare1Matcher > compare2Matcher) {
			return arg1;
		}
		else if (compare1Matcher == compare2Matcher) {
			if (arg2.length() > arg1.length()) {
				return arg1;
			}
			else {
				return arg2;
			}
			// if (  ( arg2.length() == arg1.length() )  &&  ( compare1Matcher == compare2Matcher )  ) 
			//     ==> arg1 == arg2, kann also weggelassen werden
		}
		else {
			// compare1Matcher < compare2Matcher
			return arg2;
		}
	}

Ciao, micbur
 
S

SlaterB

Gast
gesucht:
a.b.c.d.e

dann ist
a.f.c.d.e (4)
näher dran als
a.b.c (3)

ist das gewollt?

-----------

außerdem würde zu deinem Beispiel
a.b.c.d.X

a.b.c.d eher zugeordner als a.b.c da länger (wenn a.b.c.e nicht da)
das widerspricht deiner Anforderung im ersten Post?

was soll überhaupt passeren wenn z.B.
a.b.c.d.X
gesucht ist
aber nur
a.b.c.e
mit falschem Ende 'e' zur Verfügung steht, oder ist das nicht möglich?

--------
ich würde da gleichzeitig vergleichen,

gesucht:
a.b.c.d.e

ersten Buchstaben a mit den beiden Kandidaten vergleichen
(oder gleichzeitig auch mit beliebig vielen weiteren Kandidaten)
dann die Buchstaben weiter durchgehen,
Punkt ignorieren oder auch nicht, macht wohl keinen Unterschied oder was stört dich daran?

wenn erstmals ein Kandidat nicht mehr passt und der andere noch passt, dann den anderen zurückgeben,
ansonsten auf Länge prüfen usw.,
die Spezialfälle muss man da natürlich neu bedenken,

falls beliebig viele Kandidaten zur Verfügung stehen:
nicht passende Kandidaten aus der Liste der Kandidaten entfernen,
wiederum den Spezialfall beachten, dass die x letzten Kandidaten in der gleichen Runde wegfallen könnten
und dann nach anderen Kritierien nochmal unter all diesen x Kandidaten gewählt werden muss
 

micbur

Bekanntes Mitglied
Oh man, das sind ja viele Fragen. :bahnhof:

gesucht:
a.b.c.d.e

dann ist
a.f.c.d.e (4)
näher dran als
a.b.c (3)
Nein, ich glaube nicht, dass das wirklich das Ergebnis ist. Eigentlich sollte a.b.c gefunden werden und a.f.c.d.e den Wert 1 erhalten. Die Funktion fängt am Anfang des Strings (also left-to-right) an zu vergleichen.

a.b.c.d eher zugeordner als a.b.c da länger (wenn a.b.c.e nicht da)
das widerspricht deiner Anforderung im ersten Post?
Ja, da hast du irgendwie Recht. Aber dann auch wieder nicht.
--- Nachtrag ---
Man könnte best match auch anders definieren, wenn ein 100% des Suchstring einem Teil des Matchstring entspricht, dann ist der Suchstring ein Kandidat. Gibt es zwei Suchstring mit 100%, so wähle den längeren. Im Prinzip ist hier die Aussage nur vertauscht, der Inhalt sollte aber derselbe sein.
---

Beispiel:
suche: java.lang.String
habe:
java.lang
java.lang.ref

Würde ich das längere derselben Bewertung raussuchen, so würde mir das Programm java.lang.ref ausspucken, aber java.lang ist gesucht.

Verbesserungsvorschlag?

Punkt ignorieren oder auch nicht, macht wohl keinen Unterschied oder was stört dich daran?
Wenn ich den Punkt nicht ignoriere, werden andere Packages rausgesucht, obwohl der Punkt keine Aussagekraft hat.

Beispiel:
suche: java.lang.String
habe:
java.lang
java.lang.ref

Offenbar ist 'java.lang.' (=> java.lang.ref) ähnlicher zu 'java.lang.String' als 'java.lang'. Da der Punkt aber keine Bedeutung an dieser Stelle hat, muss ich ihn ignorieren. Nur auf Stringebene ist er wichtig.

Bisher hat meine Methode ganz gut bestanden. Wahrscheinlich aber auch nur, weil die Package-List sortiert ist. Das nehme ich dann vorerst in die Anforderung an die Packagelist auf.

Ciao, micbur
 
S

SlaterB

Gast
micbur hat gesagt.:
gesucht:
a.b.c.d.e

dann ist
a.f.c.d.e (4)
näher dran als
a.b.c (3)
Nein, ich glaube nicht, dass das wirklich das Ergebnis ist. Eigentlich sollte a.b.c gefunden werden und a.f.c.d.e den Wert 1 erhalten. Die Funktion fängt am Anfang des Strings (also left-to-right) an zu vergleichen.
mir ist es ja egal, du solltest es testen (statt glauben) fall es dir wichtig ist,

dein Code sieht nun mal so, als wenn er Zeichen 0, 1, 2 usw. alle nacheinander vergleicht,
a = a, b != f, aber danach c = c, d = d, e= e also Level 4 und damit besser als a.b.c (3)

-------------

a.b.c.d eher zugeordner als a.b.c da länger (wenn a.b.c.e nicht da)
das widerspricht deiner Anforderung im ersten Post?
Ja, da hast du irgendwie Recht. Aber dann auch wieder nicht.

Beispiel:
suche: java.lang.String
habe:
java.lang
java.lang.ref

Würde ich das längere derselben Bewertung raussuchen, so würde mir das Programm java.lang.ref ausspucken, aber java.lang ist gesucht.

Verbesserungsvorschlag?
du wählst bei Gleichheit den längeren aus,
Lösung: den kürzeren auswählen?!..


ist nur das Problem wenn es keinen passenden gibt,
also das Beispiel was ich schon nannte:
java.lang.String

zur Wahl
java.util.List
java.swing.JList


was soll denn gewählt werden?
das ist eine inhaltliche Frage, da kann man keinen Verbesserungsvorschlag an den Algorithmus stellen wenn inhaltlich noch gar nicht klar ist, was gesucht ist,

oder gehts du davon aus, dass immer java.lang auch mit drin sein muss?
dann wie gesagt den kürzesten wählen stt den längsten,

--------

das mit den Punkten macht nun Sinn, ja
 

micbur

Bekanntes Mitglied
SlaterB hat gesagt.:
mir ist es ja egal, du solltest es testen (statt glauben) fall es dir wichtig ist,

dein Code sieht nun mal so, als wenn er Zeichen 0, 1, 2 usw. alle nacheinander vergleicht,
a = a, b != f, aber danach c = c, d = d, e= e also Level 4 und damit besser als a.b.c (3)

Kurz: nö, macht das Programm nicht. Ist alles getestet ... OK, sehe gerade, dass du Recht haben könntest, aber nur in einem theoretischen Spezialfall. Vorher stand dort eine while-Schleife und daher kommt auch noch der Kommentar. Thx, wird geändert.

SlaterB hat gesagt.:
du wählst bei Gleichheit den längeren aus,
Lösung: den kürzeren auswählen?!..

ist nur das Problem wenn es keinen passenden gibt,
also das Beispiel was ich schon nannte:
java.lang.String

zur Wahl
java.util.List
java.swing.JList
Hmmm, eine gute Frage, da der Identifier aber aus dem Code eines Java-Programms kommt, ist es recht unwahrscheinlich, dass ich gar nichts finde.

Naja, erwarte halt nicht zu viel von Datenbanklern. Habe auch noch nie Code gesehen für best match. Deine Einwände sind schon zum Teil korrekt, aber eine Lösung dafür habe ich auch nicht. Ich könnte initial höchsten einen leeren String als ein Comparator übergeben, dann ist ein leerer String der kürzeste String des maximalen Match, wenn es keine Übereinstimmung gibt.

Ciao, micbur
 

micbur

Bekanntes Mitglied
OK, habe die for-Schleife durch eine while-Schleife ersetzt. Nun wird die Schleife bei der ersten Ungleichheit abgeprochen.

Code:
        int y = 0;
        while ( y < shorter && (arg1.charAt(y) == arg2.charAt(y))) {
            if ((arg1.charAt(y) != '.') && (arg2.charAt(y) != '.') ) {
                equilationLevel++;
            }
            y++;
        }
 

micbur

Bekanntes Mitglied
Außerdem gibt es nun auch in der Methode findBestMatch(String, String, String) noch die Zeilen:

Code:
        // falls gar kein Parameter übereinstimmt
        if ( (compare1Matcher == 0) && (compare2Matcher == 0) ) {
            return "";
        }

dies wird gemacht, bevor compare1Matcher und compare2Matcher bzw. arg1 und arg2 verglichen werden.

Das löst alle angesprochenen Probleme.

Habe ich was vergessen?

Ich habe die Test hinzugefügt.

Code:
assertEquals("", myNavi.findBestMatch("org.eclipse", "com.ibm", "java.lang.String"));
assertEquals("test", myNavi.findBestMatch("testxr", "test", "tester"));

Vielen Dank & Ciao, micbur


*bibber* sonst noch ein Fehler?
 
S

SlaterB

Gast
kleine Vereinfachung:
Code:
if (arg1.charAt(y) != '.' ) { 
      equilationLevel++; 
}
reicht statt
Code:
if ((arg1.charAt(y) != '.') && (arg2.charAt(y) != '.') ) { 
      equilationLevel++; 
}
da die Zeichen eh gleich sein müssen
-----------

du hast eine Menge zu
assertEquals("", myNavi.findBestMatch("org.eclipse", "com.ibm", "java.lang.String"));
geschrieben, was ich selber noch gar nicht berücksicht habe,

mir gings um den Fall, dass ein Teil am Anfang stimmt, am Ende aber nichts komplett passt,
in assert ausgedrückt:

assertEquals(??, myNavi.findBestMatch("org.eclipse", "org.ibm", "org.lang.String"));

also immer noch zwei Frage:
was soll da passieren (??)
und dann natürlich für dich die Frage wie du es umsetzen möchtest,
oder ob die aktuelle Version das schon kann
 

micbur

Bekanntes Mitglied
Da wird 'org' gefunden. Das reicht. Ich benutze die Angaben aus der Package-List, damit ich die Javadoc-HTML-Seiten besser finden kann.

Es gibt noch eine Methode 'guessPathes(URI baseURI, String identifier)' die ruft 'findBestMatch(String, String, String)' auf. guessPathes hat die Aufgabe, zu einem Identifier eine Liste möglicher URIs zu erstellen. Ich benutze die Package-List, damit ich nicht zu viele unsinnige Paths erraten/generieren muss.

Wo ist der Sinn dahinter?
Wenn ich einen Identifier bekomme 'java.lang.String', weiß ich nicht, wo die Datei ab baseURI liegt. Ich könnte ja auch eine Inner Class haben oder noch schlimmer eine Methode oder ein Feld einer Inner Class. Damit sähe der Identifier dann etwa so aus: java.lang.Character.UnicodeBlock.THAI. Ich kann anhand des String aber nicht erkennen, was ein Konstruktor, ein Feld oder eine Methode ist, also weiß ich nicht, welchen Pfad ich nehmen soll.

Also wird alles Mögliche generiert. Damit ich diese Menge minimiere, nehme ich vorher die Package-List und versuche einen Teil des Pfades schon 'zu wissen'. Damit ist es völlig wurscht, ob ich das exact richtige Package finde. Ich darf nur kein Falsches finden.

Puh, lange Erklärung, aber ich denke, es lohnt sich.

Zu deiner Frage:
bei 'assertEquals("org", myNavi.findBestMatch("org.eclipse", "org.ibm", "org.lang.String"));'
reicht mir 'org'.

Ciao, micbur


PS: ja die andere Optimierung ist mir auch aufgefallen. Sie bleibt aber, weil sie kaum was frist und 'sicher ist sicher ist sicher'.
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
Ameise03 Best&Worst Case bei Insertionsort Allgemeine Java-Themen 10
T Best Practice überprüfen von Übergabeparametern Allgemeine Java-Themen 17
S Best Practices CopyConstrutor mit ArrayList Allgemeine Java-Themen 1
S best practice: Einordnung Enitity und Datenklasse Allgemeine Java-Themen 11
temi best practice: Parameter überprüfen, wo? Allgemeine Java-Themen 9
Airwolf89 JUnit: Vorschläge/ Best Practice Allgemeine Java-Themen 7
F Error Logging - best practices? Allgemeine Java-Themen 3
M Best Practice: Daten aufnehmen-speichern-bereitstellen Allgemeine Java-Themen 8
H Best Practice zu vielen konstanten Objekten? Allgemeine Java-Themen 10
M Best Practices für Undo/Redo Allgemeine Java-Themen 16
G Best Practices Software-Engineering‏ Allgemeine Java-Themen 3
G Best Practices Allgemeine Java-Themen 10
F best practice Allgemeine Java-Themen 5
J Input/Output Dateien bearbeiten - "Best Practice" Allgemeine Java-Themen 3
M Best Practices Exception Handling für eigene library Allgemeine Java-Themen 8
R Statische Klasse: Best practice mit flags (2) Allgemeine Java-Themen 3
musiKk Best Practice für kleine Variationen in gegebenen Modellklassen Allgemeine Java-Themen 11
S best practise Allgemeine Java-Themen 6
J Best Practice für implementierung von equals(...) Allgemeine Java-Themen 7
Daniel_L Best Practice zum Löschen von Log-Files? Allgemeine Java-Themen 8
S Array: Anzahl Elemente mit best. Wert zählen Allgemeine Java-Themen 4
M Matcher-Klasse findet match nicht Allgemeine Java-Themen 6
S Pattern.Match Suche: For Schleife einbinden und in Liste schreiben Allgemeine Java-Themen 3
T Nur innerhalb des regex-Match ersetzen Allgemeine Java-Themen 9
G signer information does not match signer information of. Allgemeine Java-Themen 3

Ähnliche Java Themen

Neue Themen


Oben