DNA-komprimieren

[zuAltdafür]

Hallo zusammen,

ich soll eine DNA in Form eines Strings komprimieren. Wenn der String so lautet: aaabbbccccddd soll daraus werden: 3a3b3c3d. Mein Code funktioniert für den String "aaaa", aber sobald Buchstaben vermischt werden funktioniert es nicht. Kann mir jemand sagen, wo mein Fehler ist?

[CODE lang="java" title="comprimise"]public class Komprimieren {

static char x;
static int zähler;

public static String comprimise(String testString) {

String ergebnisString = "";

char [] chars = testString.toCharArray();

for(int i = 0 ; i < chars.length; i++) {

x = chars;

}

for(int j = 0 ; ((j < chars.length) && (x != chars[j + 1])); j++) {

ergebnisString += chars[j];

}

for(int j = 0; ((j < chars.length - 1) && (x == chars[j + 1])); j++) {

zähler ++;
}

if(zähler < 2) {
ergebnisString += x;
}
else if(zähler >= 2) {
ergebnisString = ergebnisString + (zähler + 1) + x;
}




return ergebnisString;
}



}[/CODE]

 

[kneitzel]

Ein Fehler, der sofort auffällt:

        for(int i = 0 ; i < chars.length; i++) {
             x = chars[i];
        }

ist nichts anderes als

        x = chars[chars.length];

Denn alle vorherigen Durchgänge schreiben einen Wert in x, der sofort wieder überschrieben wird im nächsten Durchgang.

Generell wäre meine Empfehlung, das erst einmal unabhängig von Java zu schreiben. Wie würdest Du das Vorgehen beschreiben? Du gibst also irgend jemandem, der keine Ahnung hat, um was es geht, einen Zettel mit "aaabbbccccddd" und Du erwartest, dass er dann einen Zettel zurück gibt mit "3a3b4c3d" (Vermutlich Tippfehler - das c ist 4 mal vorgekommen in Deinem Beispiel!)

Dabei muss das ein Depp machen - dem kannst Du nicht sagen: zähl mal. Aber er kann sich Zahlen merken und kann die erhöhen und so ... Also wirklich ausführlich beschreiben!

so eine ausführliche Beschreibung kann man dann super 1:1 in Code umsetzen.

 

[zuAltdafür]

• wandel den übergebenen Text in ein char-Array
• setze einen Zähler i auf 0
• solange i kleiner ist als die Länge des String (äußere Schleife): - merke das aktuelle Zeichen - setze einen zweiten Zähler auf 0 - tritt in eine innere Schleife ein. Diese Schleife wird durchlaufen, solange i kleiner ist als die Länge des Texts und das aktuelle Zeichen dem „gemerkten“ Zeichen entspricht (innere Schleife): o erhöhe den (zweiten) Zähler um 1 o erhöhe i um 1 - falls nach Beendigung der inneren Schleife der (zweite) Zähler kleiner ist als 2, hänge das „gemerkte“ Zeichen an den Ergebnisstring an - andernfalls hänge den Zähler, gefolgt vom aktuellen Zeichen, an den Ergebnisstring an
• liefere den Ergebnisstring zurück

Das ist die Aufgabe hierzu.

x = chars[chars.length];

Wozu soll ich x einer Konstanten zuweisen? Schließlich soll ich ja zwei Buchstaben, welche nebeneinander sind, vergleichen. Mir ist immernoch nicht ganz klar, was ich anders machen soll 😅

 

[kneitzel]

Wozu soll ich x einer Konstanten zuweisen?

Das macht ja eben keinen Sinn. (Wobei ich mich da vertippt hatte. Da fehlte natürlich ein -1) Ich hatte da nur einen Stück Code von Dir genommen um aufzuzeigen, dass der Ansatz an sich noch nicht gut durchdacht war um eben dann diesen Text-Ansatz als neuen Ansatz vorzuschlagen.

Deine Beschreibung sieht auf den ersten Blick erst einmal gut aus. Ich neige da teilweise zu größerer Detailtiefe, aber das ist schon ein super Ansatz. Hast Du mal versucht, Deine Beschreibung jetzt in Code umzusetzen um zu sehen, was da raus kommt? (Die Bezeichner sind evtl. verbesserungswürdig, aber sie sind jetzt erst einmal auch ok):

setze einen Zähler i auf 0

int i = 0;

solange i kleiner ist als die Länge des String (äußere Schleife):

while (i < chars.length) {
    // ....
}

Das sieht schon etwas mehr nach dem aus, was Du da als for Schleife hattest. Nur eben siehst Du schon: Da scheint viel mehr in die Schleife zu gehören, als Du da rein gepackt hast. Und i wird da nicht nur in der Schleife hochgezählt, daher ist eine while-Schleife der schönere Ansatz und würde auch der Beschreibung eher entsprechen.

Das "Übersetzen" kannst Du so weiter treiben - dann sollte schon ein etwas besserer Code bei raus kommen als der erste Ansatz denke ich mal...

 

[zuAltdafür]

Ich habe es versucht mit den while-Schleifen umzusetzten. Nun kriege ich über den statischen println-Abruf der Methode gar keine Ausgabe mehr. Ich bin total am verzweifeln und wäre über einer Hilfe sehr dankbar.

Hier der Code:
[CODE lang="java" title="comprimise"]public class Komprimieren {

static char gemerktesZeichen;
static char aktuellesZeichen;
static String ergebnisString = "";

public static String comprimise(String testString) {

char [] chars = testString.toCharArray();
int i = 0;
while (i < chars.length) {
chars = gemerktesZeichen;
int zählerZwei = 0;
while((aktuellesZeichen != gemerktesZeichen) && (aktuellesZeichen < chars.length - 1)) {
i++;
aktuellesZeichen = chars;
zählerZwei ++;
}
if(zählerZwei < 2) {
ergebnisString += gemerktesZeichen;
}
else if(zählerZwei >= 2){ergebnisString += zählerZwei + gemerktesZeichen;}
}

return ergebnisString;
}


}[/CODE]

 

[kneitzel]

chars[i] = gemerktesZeichen;

Die Zuweisung ist erst einmal falsch herum. Das gemerkte Zeichen soll doch das Zeichen aus dem Array sein.

Dann in der Bedingung der inneren while Schleife:
aktuellesZeichen < chars.length - 1)
Da willst du sicher stellen, dass i kleiner ist ....

 

[kneitzel]

Und davor: so lange die Zeichen gleich sind gehst du weiter ... Nicht so lange sie ungleich sind.

Und bei dem if / else benötigst du kein weiteres if. Entweder ist die Zahl kleiner 2 oder die ist es nicht. Im Else Zweig musst du also >= nicht mehr prüfen.

Das einfach mal auf die Schnelle, was auf dem Handy direkt aufgefallen ist.

 

[zuAltdafür]

Hallo nochmal!

Danke für deine Tipps die haben mir weitergeholfen. Nun habe ich die Implementierung der Methode so weit fertig. Ich habe nur ein Problem: Da ich immer einen char mit dem rechten Nachbarn vergleiche, hört der Index der while-Schleifen bei chars.length - 1 auf. Dies führt dazu, dass der letzte Char, also chars[chars.length - 1] von der Methode nicht bearbeitet wird. Eine Lösung wäre es, am Ende der ersten while-Schleife eine if-Verzweigung zu implementieren und diesen Index gesondert zu bearbeiten. Dies würde den Code jedoch zu kompliziert machen. Hast du vielleicht eine elegantere Lösung?

public class Komprimieren {
    
    static char gemerktesZeichen;
    static String ergebnisString = "";
    
    
    
    public static String comprimise(String testString) {
        
        char [] chars = testString.toCharArray();
        int i = 0;
        while (i < chars.length - 1) {
            
            gemerktesZeichen = chars[i];
            i++;
            int zählerZwei = 1;
            while((chars[i] == gemerktesZeichen) && (i < chars.length - 1)) {
                i++;
                zählerZwei++;   
            }
            if(zählerZwei < 2) {
                ergebnisString += Character.toString(gemerktesZeichen);
                
                }
            else {   
                ergebnisString += Integer.toString(zählerZwei) + Character.toString(gemerktesZeichen);
                }
        }   
        return ergebnisString;     
    }
}

 

[Barista]

Das Rausschreiben auf den 'ergebnisString' kannst Du immer beim Wechsel des aktuellen Zeichens und dann noch mal nach der Schleife für den übrig gebliebenen Rest machen.

Alternativ fragst Du innerhalb der Schleife nach Zeichenwechsel oder nach dem Ende des char-Arrays.

Das -1 in der Schleifenbedingung ist nicht üblich.

 

[mihe7]

@zuAltdafür Du machst Dir das Leben unnötig kompliziert.

Grundsätzlich geht es doch dazum, Zeichen zu zählen. Wir machen wir das, ganz allgemein? Naja, man merkt sich in einem Zähler wie viele Zeichen man bereits gezählt hat und bei jedem weiteren Zeichen inkrementiert man den Zähler.

        char [] chars = testString.toCharArray();
        int count = 0;      
        for(int i = 0 ; i < chars.length; i++) {
            count++;
        }

Das ist zugegebenermaßen nicht besonders aufregend, schließlich zählen wir hier einfach alle Zeichen und damit die Länge des Strings. Tatsächlich ist das aber schon fast die Lösung!

Für Strings, die ausschließlich aus gleichen Zeichen bestehen, liefert count bereits die korrekte Anzahl, so ist count für "aaaa" nach dem letzten Hochzählen 4. Wir müssen also lediglich die Fälle berücksichtigen, in denen auf das aktuelle Zeichen nicht das gleiche Zeichen folgt:

1. es gibt kein weiteres Zeichen oder
2. das nächste Zeichen unterscheidet sich vom aktuellen

In diesen Fällen kann die Ausgabe erfolgen und wir können von vorne zu zählen beginnen. Man muss sich das ggf. auf dem Papier klar machen: haben wir bislang 3 gezählt und ist das aktuelle Zeichen ein a, dann müssen die zwei vorhergehenden Zeichen ebenfalls 'a' gewesen sein. Ist das nächste Zeichen kein a, dann können wir also sofort 3a, d. h. Zähler und aktuelles Zeichen ausgeben.

 

[zuAltdafür]

@mihe7 deine Implementierung läuft ja auch darauf hinaus, dass du ein Zeichen mit dem Nachbar-Zeichen vergleichst und entsprechend den Bedingungen Code implementierst. Meine Implementierung funktioniert ja für den ganzen String, außer dem letzten Zeichen. Wie umgehst du also das Problem mit dem letzten Zeichen?

 

[MiHimbert]

Hallo
ich würde das Problem wie folgt lösen.
Bitte beachtet bei deinem Thema die Performance. Der DNA Strang kann sehr lang sein. Ich habe die Stellen für die Performance entsprechend kommentiert:

siehe unten den Code im Java Stil.

 

[kneitzel]

Code bitte immer in Code Tags packen (</> Knopf über dem Eingabefeld). Danke

 

[MiHimbert]

public String start(String[] args) {
        String fehler = "";
        String kette = "aaaabbbbbbccd";

        int x = -1;
        int y = 0;

        // die Länge verändert sich nicht, darum kann sie einmal ermittelt werden
        int z = kette.length();
        String A = "";

        // Stringbuffer auf die maximale Größe ausrichten
        // sonst wird er immer wieder zwischendurch kopiert und verlängert.
        StringBuffer bu = new StringBuffer(30000);

        // mit den String direkt arbeiten, ist schneller als mit char[] Konstruktionen
        while (true) {
            x++;
            // die Schleife beenden sobald der String abgearbeitet ist
            if (x + 1 > z)
                break;

            if (kette.substring(x, x + 1).equals(A)) {
                y++;
            } else {
                if (!A.equals("")) {
                    // Sringbuffer ist schneller als Strings zusammenfügen
                    bu.append(y + "").append(A);
                }
                y = 1;
                A = kette.substring(x, x + 1);
            }
        }
        // das Letzte Zeichen auch noch mitnehmen in den Stringbuffer
        if (y > 0) {
            bu.append(y + "").append(A);
        }
        System.out.println(bu.toString());
        return fehler;
    }

Ergebnis:
4a6b2c1d

 

[mihe7]

@mihe7 deine Implementierung läuft ja auch darauf hinaus, dass du ein Zeichen mit dem Nachbar-Zeichen vergleichst und entsprechend den Bedingungen Code implementierst. Meine Implementierung funktioniert ja für den ganzen String, außer dem letzten Zeichen. Wie umgehst du also das Problem mit dem letzten Zeichen?

Das wäre Fall 1, der in der Schleife genauso abgeprüft und behandelt wird wie Fall 2.

 

[MiHimbert]

Beachte aber bitte, dass mein Code nur funktioniert in der Größenordnung von positiven Integer und du dem Programm genügend Speicher mitgibst.
Wenn deine DNA im Petabereich liegt, so musst du den String entsprechend aufteilen. Aber das wird wohl eine andere fachliche Aufgabe sein.

 

[mihe7]

@MiHimbert StringBuffer ist thread-safe und bringt damit völlig unnötigen Overhead mit -> StringBuilder. Für die Angabe der initialen Kapazität wäre kette.length() mehr als ausreichend: wenn das Ergebnis größer als die Eingabe wird, rentiert sich die Komprimierung offensichtlich nicht.

Nachtrag: Dein Code ist auch noch etwas zu kompliziert. Darüber hinaus wandelst Du mit einer String-Konkatenation die Zahl in einen String um, bevor Du sie an den StringBuffer hängst. Nicht sonderlich effizient, zumal dabei in der Regel jeweils ein StringBuilder erzeugt wird.

Nachtrag 2: seit Java 9 wird "" + x mit Hilfe von StringConcatFactory.makeConcatWithConstants optimiert durchgeführt. Bis Java 8 wurde jedenfalls ein StringBuilder erzeugt.

 

[kneitzel]

Wenn man wirklich sowas auf ganz lange Strings anwenden müsste, dann würde es doch auch eher auf eine Stream Lösung hinaus laufen, oder?

Dann liest man Zeichen für Zeichen ein und gibt bei Wechsel oder geschlossenem Thread etwas aus ...

Dann ist egal, wie groß die Datenmenge ist - dann geht das auch mit zig TB an Daten

 

[MiHimbert]

Prima einem geholfen und selbst was dazu gelernt.
Habe die Verbesserungen von mihe7 eingebaut.

public class JavaForum {

    // main methode habe ich im aufrufenden Programm.
    public void start(String[] args) {
        
        String kette = "aaaabbbbbbccd";

        int x = -1;
        int y = 0;

        // die Länge verändert sich nicht, darum kann sie einmal ermittelt werden
        int z = kette.length();
        String A = "";

        // StringBuilder auf die maximale Größe ausrichten
        // sonst wird er immer wieder zwischendurch kopiert und verlängert.
        StringBuilder bu = new StringBuilder(z);

        // mit den String direkt arbeiten, ist schneller als mit char[] Konstruktionen
        while (true) {
            x++;
            // die Schleife beenden sobald der String abgearbeitet ist
            if (x + 1 > z)
                break;

            if (kette.substring(x, x + 1).equals(A)) {
                y++;
            } else {
                if (!A.equals("")) {
                    // StringBuilder ist schneller als Strings zusammenfügen
                    bu.append(y + "").append(A);
                }
                y = 1;
                A = kette.substring(x, x + 1);
            }
        }
        // das Letzte Zeichen auch noch mitnehmen in den StringBuilder
        if (y > 0) {
            bu.append(y + "").append(A);
        }
        System.out.println(bu.toString());
        
    }

}

 

[MiHimbert]

Die Komprimierung könnte theoretisch auch zu einem längen String führen:
DNA-Kette: abcabcabc
Ergebnis: 1a1b1c1a1b1c1a1b1c
In diesem rein theoretischen Fall würde der StringBuilder einmal vergrößert werden.

 

[kneitzel]

Die Komprimierung könnte theoretisch auch zu einem längen String führen:
DNA-Kette: abcabcabc
Ergebnis: 1a1b1c1a1b1c1a1b1c
In diesem rein theoretischen Fall würde der StringBuilder einmal vergrößert werden.

Die Zahl wird erst ab 2 Elementen geschrieben. Dein Beispiel wäre also unverändert.

 

[mihe7]

Prima einem geholfen und selbst was dazu gelernt.

Das ist Sinn und Zweck der Sache

Jetzt nochmal in "schön":

public String encodeByRunLength(String text) {
    StringBuilder b = new StringBuilder();
    int count = 0;
    for (int i = 0, n = text.length(); i < n; i++) {
        count++;
        char ch = text.charAt(i);
        if (i+1 >= n || ch != text.charAt(i+1)) {
            if (count > 1) {
                b.append(count);
            }
            b.append(ch);
            count = 0;
        }
    }
    return b.toString();
}

Auf die gleiche Weise funktioniert das auch mit Streams, hier wird die Intention sogar noch deutlicher:

public void encodeByRunLength(Reader reader, Writer writer) throws IOException {
    long count = 0L;
    int current = reader.read();
    while (current != -1) {
        count = Math.incrementExact(count);
        int next = reader.read();
        if (next != current) {
            if (count > 1) {
                writer.write(Long.toString(count));
            }
            writer.write(current);
            count = 0L;
        }
        current = next;
    }
}

Damit kannst Du nun endlose Zeichenfolgen komprimieren, wobei maximal 2^63-1 gleiche Zeichen aufeinanderfolgen dürfen. Durch incrementExact wird ein Überlaufen von count verhindert (es wird dann eine ArithmeticException geworfen).

Der String-Fall ließe sich damit auch schreiben als:

public String encodeByRunLength(String text) {
    StringWriter writer = new StringWriter();
    try {
        encodeByRunLength(new StringReader(text), writer);
    } catch (IOException ex) {
        ex.printStackTrace();
    }
    return writer.toString();
}

 

[MiHimbert]

Habe obigen Code von mihe7 mal ausprobiert indem ich die input-Datei erstmal erstellt habe.
1,5 GB werden gelesen und in 800 MB komprimiert.
for (int i = 0; i < 100000000; i++) {
bWriter.write("aaaabbbbcccceee");
}

JavaForum 24.05.2021 11:02 start
Datei erstellen : 24.05.2021 11:02:21.50
Datei konvertieren: 24.05.2021 11:02:27.56
Ende : 24.05.2021 11:02:50.58
JavaForum 24.05.2021 11:02 ende

 

[zuAltdafür]

Hallo zusammen!

Vielen Dank für euren Input zu meiner Aufgabe. Ich bin noch ein Anfänger im Thema programmieren und habe durch eure Post´s Einiges dazugelernt. Aufgrund der o.g Vorteile habe ich einen Stringbuilder für meinen Code verwendet. Diese Klasse, verbunden mit der append()-Methode kannte ich vorher nicht. Nun ist diese Aufgabe ein Teil meiner Hausarbeit, also ich reiche die Lösung Online ein. Daher kann ich eure Lösungen, obwohl die offensichtlich besser sind, leider nicht verwenden. Mir ist es leider nicht gelungen, aus eurer Methodik abzuleiten, wie ich die Problematik des letzten Buchstabens in meinem Code lösen kann (siehe unten). Aber dennoch vielen Dank

[CODE lang="java" title="comprimise"]package hausArbeitaufgabeDrei;

public class Komprimieren{

static char gemerktesZeichen;
static StringBuilder e = new StringBuilder("");

public static String comprimise(String dna) {

char [] chars = dna.toCharArray();
int i = 0;
while (i < chars.length - 1) {
gemerktesZeichen = chars;
i++;
int zählerZwei = 1;
while((chars == gemerktesZeichen) && (i < chars.length - 1)) {
i++;
zählerZwei++;
}
if(zählerZwei < 2) {
e.append(gemerktesZeichen);
}
else {
e.append(zählerZwei);
e.append(gemerktesZeichen);
}
}
return e.toString();
}
}[/CODE]

 

[mihe7]

wie ich die Problematik des letzten Buchstabens in meinem Code lösen kann (siehe unten).

Zwei Dinge: erstens Du darfst von .length nicht noch 1 abziehen, da Du ja mit < vergleichst. Zweitens muss die Prüfung, ob das letzte Zeichen erreicht wurde, in der Bedingung zuerst stehen, da Du ansonsten eine ArrayIndexOutOfBoundsException bekommst.

Also nicht:

while((chars[i] == gemerktesZeichen) && (i < chars.length - 1)) {

sondern

while((i  < chars.length) && (chars[i] == gemerktesZeichen)) {

In Zeile 12 muss das -1 natürlich auch weg.

 

[mrBrown]

// mit den String direkt arbeiten, ist schneller als mit char[] Konstruktionen

Wie kommst du darauf?
Direkt mit chars und char-Arrays zu arbeiten ist deutlich schneller, mit Strings erzeugst du ziemlich viele überflüssig Instanzen und hast außerdem immer den Overhead von Strings dabei, die in dem Fall ja nur ein Wrapper um das Char-Array sind.

 

[zuAltdafür]

Endlich habe ich das Problem gelöst! Ich habe deine Anpassung vorgenommen und nur eine kleine if-Schleife nach der äußeren while-Schleife vorgenommen (siehe Code) und es funktioniert, danke

if(gemerktesZeichen != chars[chars.length - 1]) {
            e.append(chars[i]);   
        }

Ich hätte noch eine Verständnisfrage:

while (true) {

Ich habe so eine Implementierung einer while-Schleife schon öfters gesehen aber NIEEE verstanden!
Denn es ist vorher kein boolean initialisiert worden, der entweder true oder falsch sein soll. Daher irritiert mich das total 😕 Für eine Erklärung bin ich schonmal im Voraus dankbar 😊.

 

[mihe7]

Denn es ist vorher kein boolean initialisiert worden, der entweder true oder falsch sein soll. Daher irritiert mich das total 😕 Für eine Erklärung bin ich schonmal im Voraus dankbar 😊.

Die Schleifenbedingung muss ein Ausdruck sein, der ein boolean liefert. Da true selbst ein boolean ist, kannst Du das natürlich auch einsetzen. Die Bedingung ist dann immer wahr, so dass die Schleife anderweitig abgebrochen werden muss (return/break), sonst läuft die endlos.

 

[CyborgIstDoof]

Für diesen Anwendungsfall dürfte das schneller sein:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

public class Test {
    public static void encode(String fn1, String fn2) throws IOException {
        try (BufferedReader r = new BufferedReader(new FileReader(fn1));
                BufferedWriter w = new BufferedWriter(new FileWriter(fn2))) {
            int c1 = r.read();
            while (c1 != -1) {
                int count = 1;
                int c2;
                while ((c2 = r.read()) == c1) {
                    count++;
                }
                if (count != 1) {
                    w.write(count + "");
                }
                w.write(c1);
                c1 = c2;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        encode("a.dna.txt", "b.dna.txt");
    }
}