gemeinsammen teilstring auslesen

[darkeye2]

Hallo,

ich versuche gerade aus zwei Strings den gleiche Stringteil zu extrahieren:
Bsp.:
String s1 = "Das ist ein Test String";
String s2 = "Und hier noch ein Test";
gs(s1, s2) wäre dann "ein Test";

Die einzigste Möglichkeit, die mir grad einfällt ist das ganze immer buchstabe für buchstabe durchgehen und testen, sprich:

String gemeinsamm;
 for(int i = 0; i<s1.length; i++){
    for(int j = i; j<s1.length; i++){
       if(s2.contains(s1.substring(i, j)){
           if(gemeinsamm.length<(j-i)){
              gemeinsamm = s1.substring(i, j);
           }else{
              break;
           }
       }
    }
 }

(hab das grad ohne editor geschrieben, also ohne highlighting, also könnten rechtschreibfehler oder fehlende klammern drin sein, aber der gedanke sollte verständlich sein)

Meine Frage nun, gibt es eine Möglichkeit, das ganze schneller, bzw effektiever zu machen?

 

[XHelp]

Longest common substring problem - Wikipedia, the free encyclopedia
Dort findest du auch einige Ansätze. Darüber hinaus wird dort ein Paper verlinkt, welches bestimmt weitere Informationen/Verlinkungen bereithält.

 

[darkeye2]

Danke für den Link, wusste nicht genau, wie ich danach suchen soll.

Aber da die ganzen algorithmen das genau so machen, wie mein erster gedanke ja auch war, scheint es wohl die "beste" variante zu sein, auch wenn es eigendlich von der durchlaufzeit her net so toll ist (muss das recht oft machen, da fällt es auf, auch wenn die Strings immer kurz sind).

 

[XHelp]

Naja, das mit den Bäumen sieht vielversprechender aus. Die Frage ist, wie oft und an welchen Daten du es machst und ob es sich überhaupt lohnt da Mühe in Optimierung reinzustecken.

 

[darkeye2]

also ich denke schon, dass es sinn machen würde, werde es erstmal so testen, und dann weiter schauen.

Die Strings die da geprüft werden sind alle recht kurz (ca. 50 - 120 zeichen) also halt nicht mehr als ein normaler satz, keine ganzen texte oder so. Allerdings wird diese methode sehr oft (viele tausend mal) benötigt, und da noch einige mehr oder weniger anspruchsvolle algorithmen ablaufen, ist es schon sinnvoll, wenn ich versuche alles maximal zu optimieren, schließlich soll die zeit, die das prog für einen durchlauf braucht so kurz wie möglich sein.

Werde das morgen mal so testen, und bescheidgeben, ob es nötig ist, da noch was zu tun.

 

[XHelp]

Da lohnt sich eher das ganze zu parallelisieren, imho. Aber das eine schließt das andere nicht aus.

 

[darkeye2]

also parallelisiert ist es schon so gut, es eben geht. Eine verbesserung des ganzen ist im moment auch scheinbar nicht nötig, da es auch so ganz passabel läuft, leider hab ich jetzt ein anderes "kleines" Problem, wollte jetzt keinen neuen Thread deswegen aufmachen:
Ich bin auch die nutzung von BigDecimal angewiesen (wenn ich keine eigene klasse schreiben will^^), und ich rechne viel damit rum, leider kriege ich es nicht hin, die länge der gespeicherten nachkommastellen zu regulieren, gibt es da eine einfache möglichkeit?

 

[XHelp]

a) sollte schon eine Frage ein Thread sein, zumal zweite Frage eine völlig andere ist
b) Über die Forumsuche würdest du bestimmt schnell eine Antwort finden
c)

BigDecimal big = new BigDecimal(1.23743176);
big = big.setScale( 2, BigDecimal.ROUND_HALF_UP );

rundet dir das ganze auf 2 Nachkommastellen.

 

[emailundlos]

dynamischen programmierung ist schon eins der komplexesten gebieten der programmierung. aber das hat das finden von teilstrings in strings denn jetzt mit BigDecimal zu tun? geht es hier immer nur um strings?

 

[darkeye2]

das hatte ich schonmal, aber scheinbar ist noch ein fehler drin, weil die ausgabe auf diese weise immer so aussieht: 0E-12, davor ohne das setScale war es einfach eine ewig lange zahl, die zwar (zumindest in den esten paar stellen) gestimmt hat, aber viel zu lang war.

BigDecimal curApprox = new BigDecimal("4");
BigInteger curPrime = new BigInteger("1");
//...  paar methoden und viel code

//methode, wo mit den zahlen gerechnet wird:
curApprox = curApprox.multiply((new BigDecimal(curPrime).divide(new BigDecimal(curPrime.add(BigInteger.ONE)).
                  RoundingMode.DOWN))).setScale(30, RoundingMode.DOWN);

@emailundlos also es ist alles in einem Programm untergebracht^^ aber ansonsten hat das nix mit einander zu tun, wollte eigendlich nur drauf verzichten, noch einen thread auf zu machen. Das mit dem Strings ist zwar definitief keine all zu schöne lösung, aber sie ist von der recheinzeit her vertretbar, da die anderen sachen, die da noch berechnet werden wesendlich länger brauchen. Die berechnung mit den BigDecimal läuft in einem eigenen Thread und sollte auch in einer vertretbaren zeit fertig werden, weil das Ergebniss relevant für die endgültige Ausgabe des Programms ist

 

[emailundlos]

@emailundlos also es ist alles in einem Programm untergebracht^^ aber ansonsten hat das nix mit einander zu tun, wollte eigendlich nur drauf verzichten, noch einen thread auf zu machen.

hier ist das problem, das widerspricht den gängigen forumrichtlinien (ja, sowas gibts)

das mit BigDecimal ist nicht lesbar und du solltest einen eigenen thread deswegen aufmachen.

wenn der aufwand vertretbar ist, da nicht alle anderen teile des programms wesentlich schneller sind und das auch nicht sein müssen, dann würde ich alles genauso machen.

 

[emailundlos]

wie sind denn die "aufwände" der beiden methoden (der der hierigen und der der auf wikipedia angegebenen) im vergleich?

 

[darkeye2]

so, hab jetzt fürs andere einen neuen Thread.

Der aufwand von dem Tree auf wikipedia ist von der zeit her etwas kürzer als die andere methode, aber vom speicherverbrauch her ist sie wesendlich intensiever, und da es dann doch nicht so viel bringt, nutze ich jetzt die for-schleifen methode.
Ich hab aber ansonsten auch keine bessere möglichkeit im Netz gefunden, ich glaube, damit muss man sich zufrieden geben.

 

[emailundlos]

Ab Zeile 4 würde ich doch, wenn contains nicht zutrifft, j sofort auf 0 (bzw. i, bzw. i+1) setzen sowie i inkrementieren (sprich, ich würde die Ausführung der inneren Schleife überspringen). Und dann vom Aufwand her etwa Omega(0.99n) und O(n^2) schätzen.