Methoden String text komprimieren und dekomprimieren

[Loddakwin]

Hallo Leute,

ich weiss nicht ob das hier richtig ist aber ich frag hier einfach mal nach. Ich hab von der Uni folgende Aufgabe bekommen vielleicht wisst ihr ob es da irgendwo etwas zum nachlesen gibt. Ich erwarte keine fertiggestellte Aufgabe!

Erstellen Sie eine Methode

public static String compress(String text)

die den String text auf folgende Weise komprimiert. Es soll ein Teilstring gefunden werden, der text vorangestellt wird (mit Doppelpunkt als Trennzeichen) und in text überall durch einen Punkt ersetzt wird. Es soll jener Teilstring gewählt werden, der die größte Einsparung an gesamter String-Länge bringt (d.h. inklusive vorangestelltem Teilstring). Gibt es mehrere solche, soll der längste gewählt werden. Gibt es mehrere solche, soll jener gewählt werden, der am weitesten links steht. Falls es beim Ersetzen mehrere Möglichkeiten gibt, soll auch jene am weitesten links gewählt werden.

Erstellen Sie auch eine Methode

public static String decompress(String text)

die einen komprimierten String wieder in den ursprünglichen zurück verwandelt.

Danke im voraus!

lg lodi

 

[rme]

Hm.. gibt es irgendeine Anforderung an die Laufzeit, zum Beispiel, dass es in O(n) laufen soll oder so?

Wenn nicht, könntest du (bildlich gedacht) eine Schablone über den Text schieben, die immer kleiner wird. Du fängst bei der Hälfte der Länge an, d.h. wenn der String die Länge 12 hat, prüfst du, ob die ersten 6 Zeichen identisch mit den letzten 6 sind.

Wenn nicht, machst du die Schablone kleiner (5 Zeichen im Beispiel) und schaust, ob der String in den entsprechenden Intervallen noch eine Übereinstimmung findet. Dabei musst du die Schablone aber schieben und nicht einfach dein Intervall unterteilen.

Das ist nur ein Denkanstoß, der noch weiter ausgebaut werden müsste 😉

 

[Loddakwin]

Sorry ich hab vergessen es wurde uns ein Beispiel mitgegeben sieht so aus:

Beispiele:

Ein Gedicht ist ein Gedicht ist ein Gedicht -> in Gedicht:E. ist e. ist e.

Trolo -> :Trolo

Trololo -> ol:Tr..o

Trolololo -> olo:Tr.l.

Trololololo -> olol:Tr..o

Danke für deinen Denkanstoß aber das lasst sich anhand dieses Beispiel wahrscheinlich so nicht lösen oder?

 

[rme]

Hilft dir der Ansatz oben nicht dabei oder haben wir uns nur zeitlich überschnitten? Denn das Beispiel passt genau zu der Idee, die ich kurz angerissen habe.

 

[Loddakwin]

Ich muss zugeben ich bin ziemlich neu in der java Programmierung und erlich gesagt tu ich mir ziemlich schwer so algorithmisch zu denken um das in Programmcode niederzuschreiben 🙁 aber ich versuchs jetzt mal mit deinem Lösungsansatz!

Runtime error meinst du ?

 

[Loddakwin]

Kann mir vielleicht noch jemand weiterhelfen ich bin nicht gerade viel weiter gekommen 🙁

 

[HarleyDavidson]

Ich würde (nachdem du die Beispiele gepostet hast) genau andersherum vorgehen als rme vorgeschlagen hat.
Du fängst mit einer kleinen Schablone an (2 Zeichen) und schaust, wie oft dieser Teilstring im Komplettstring vorkommt. Diese Anzahl merkst du dir.

Dann erweiterst du die Schablone um ein Zeichen und schaust wieder. Und wieder speicherst du den Wert.

Die Werte vergleichst du nachher und derjenige Teilstring, der am meisten im Gesamtstring vorkommt, benutzt du zum komprimieren.

 

[schleichdi]

Wie klein die Welt doch ist, das gleiche Problem hab ich auch :toll:

Bezüglich der schablone, soll ich mit dieser Methode:
static int occurrences(String text, String substring, int start)
arbeiten und die Erweiterung der Schablone mit einer Schleife machen.

Also 2 Zeichen prüfen, Schleifendurchlauf 3 Zeichen prüfen usw.
Das währ ein Denkanstoß aber wegen der Realisierung hab ich auch noch keine Lösung ;(
Bitte um einen Lösungsansatz 🙂

vielen dank

 

[HarleyDavidson]

Ich fand die Aufgabe so interessant, dass ich sie selbst mal implementiert habe.

Das ist der Ablauf fürs komprimieren:

1. Lese einen String ein
2. Übergebe ihn mit einem Zeichen an die Methode compress
3. Beginne mit einem Suchpattern der Länge 2 und suche nach Substrings im Gesamtstring
4. Die absolute Zeichenersparnis wird gespeichert und aktualisiert, wenn eine höhere gefunden wurde
5. Die Größe der Suchpattern wird bis zur Hälfte der Gesamtlänge des Strings erhöht
6. Das Pattern mit der größten Ersparnis wird ersetzt und als Ergebnis der Methode zurückgegeben.

Hier mal mein Code (Achtung Spoiler 😉 )

public class CompressString
{

    public static void main( String[] args )
    {
        String text = "Das ist ein Gedicht ist ein Gedicht ist ein Gedicht.";
        //text = "Trolololo";

        String compressedText = compress( text, "#" );
        System.out.println( compressedText );
        System.out.println( decompress( compressedText, "#") );
    }

    /**
     * Komprimiert einen String auf Basis vom Ersetzen von Substrings durch 
     * ein einzelnes Zeichen
     * @param text Der zu komprimierende String
     * @param compressChar Das Zeichen, dass die Substrings ersetzen soll
     * @return Den komprimierten String
     */
    public static String compress( String text, String compressChar )
    {
        System.out.println( "Länge Originalstring: "+text.length() );
        //Maximale Ersparnis wird gesucht
        int maxSavings = 0;
        String bestPattern = "";
        //Patternsuche von 2 Zeichen bis text.length / 2
        for ( int pattersize = 2; pattersize <= text.length() / 2; pattersize++ )
        {
            //Kompletten String durchgehen
            for ( int j = 0; j < (text.length() + 1) - pattersize; j++ )
            {
                //Pattern bauen
                String pattern = text.substring( j, j + pattersize );
                //Vorkommen zählen
                int found = getOccurences( text, pattern );
                //Ersparnis: Anzahl Funde * Länge Pattern - Länge des Patterns (weil der ja am Anfang wieder hin kommt)+ 1 wegen dem Doppelpunkt + Anzahl Funde wegen dem Char
                int savings = (found * pattern.length()) - (pattern.length()+1+found);
                //System.out.println( "Pattern: '" + pattern + "', found: " + found + " , Ersparnis: " + savings + " Zeichen" );
                //Die Ersparnis ist größer / gleich gut als das bisher gefundene
                if ( savings > maxSavings )
                {
                    //Das Pattern wird gemerkt
                    bestPattern = pattern;
                    //Ersparnis wird gemerkt
                    maxSavings = savings;
                }
            }
        }
        //System.out.println( "BestPattern: "+bestPattern );
        String resultString = bestPattern+":"+text.replaceAll( bestPattern, compressChar);
        System.out.println( "Länge komprimierter String: "+resultString.length() );
        return resultString;
    }
    
    /**
     * Dekomprimiert einen komprimierten String
     * @param text Der komprimierte String
     * @param compressChar Das Kompressionszeichen
     * @return Den dekomrimierten String
     */
    public static String decompress(String text, String compressChar)
    {
        //Komprimierten String splitten
        String[] info = text.split(":");
        //Pattern extrahieren
        String pattern = info[0];
        //Eigentlichen String extrahieren
        String result = info[1];
        //Pattern einsetzen
        return result.replaceAll( compressChar, pattern);
    }

    /**
     * Liefert die Anzahl zurück, wie oft ein Teilstring in einem String
     * vorkommt
     *
     * @param text Der Gesamttext
     * @param pattern Der Teilstring
     * @return Die Anzahl, wie oft der Teilstring im String vorkommt.
     */
    public static int getOccurences( String text, String pattern )
    {
        int occurences = 0;
        boolean eagerMatching = false;
        if ( 0 != pattern.length() )
        {
            for ( int index = text.indexOf( pattern, 0 ); index != -1; index = text
                    .indexOf( pattern, eagerMatching ? index + 1 : index + pattern.length() ) )
            {
                occurences++;
            }
            return occurences;
        }
        return 0;
    }
}

 

[Ikaron]

Bei der Lösung über mir darf kein Doppelpunkt im Text enthalten sein, vielleicht solltest du das noch ausbessern, da es ja keine Bedingung ist.

 

[HarleyDavidson]

Bei der Lösung über mir darf kein Doppelpunkt im Text enthalten sein, vielleicht solltest du das noch ausbessern, da es ja keine Bedingung ist.

Ja das stimmt, das habe ich dort noch nicht berücksichtigt. Kann man ja aber einfach abfangen und behandeln.

 

[Yanaya]

Ich bin auch gerade mit dieser Aufgabe beschäftigt und habe bei der Überprüfung von HarleyDavidsons Code folgendes Problem:

Wenn ich es beim Abgabesystem prüfen lassen will, kommt bei mir diese Fehlermeldung:

Could not find method "public static String compress (String text)" in class Bsp06!
Exception in thread "test" java.lang.NoSuchMethodException: Bsp06.compress(java.lang.String)
at java.lang.Class.getMethod(Class.java:1655)
at test.run(Unknown Source)

weiß jemand was das bedeuten kann oder hat das selbe Problem?
Immerhin ist ja "public static String compress (String text)" im Code vorhanden.
Oder versteh ich da was falsch?

 

[HarleyDavidson]

Hast du den Code der Methode in die Klasse Bsp06 kopiert?

Wo und wie wird die Methode aufgerufen? Zeig mal deinen Code.

 

[schleichdi]

@ HarleyDavidson
Vielen dank für deinen Lösungsvorschlag, musste ein paar Sachen anpassen bzw Reverse Engineeren 😉.
Habe auch die "." & ":" Abfrage auch eingebaut

Hast alles super erklärt bis auf die getOcurrences Methode.
Die Methode an sich habe ich gut aber bei der for Schleife bin ich mir nicht so ganz sicher

 for ( int index = text.indexOf( pattern, 0 ); index != -1; index = text
                    .indexOf( pattern, eagerMatching ? index + 1 : index + pattern.length() ) )

wenns geht erklär mir das mit dem eagerMatching und dem "Doppelpunkt" index + pattern.length...

Sonst super Ansatz


@ Yanaya. Die Fehlermeldung kommt, weil du die compress und decompress methode nicht genau nach dem vorgegebenen Schema erstellt hast.

Gesucht war:

public static String compress(String text)

Die von HarleyDavidson ist:

public static String compress( String text, String compressChar )

Musst die Methode genau wie bei der Vorgabe anpassen sonst spackt das Abgabesystem.

Derzeit habe ich diese Fehlermeldung:

> java -classpath '/tmp/autoc-einfprog-0.5.4-8-g9133f88/check-30-7-1385450341' -Duser.language=EN -Duser.region=US -Xmx512M Tester

Error while testing String compress(String text).
Exception in thread "test" java.lang.Exception: wrong result!
at test.run(Unknown Source)

Hab die Methode aber so angepasst, dass der Methodenkopf den Vorgaben entspricht.
Sollte passen.

Aber enough Java 4 today sitze schon seit Mitternacht daran, (tja weil ich es immer schaffe erst am letzten Abend damit anzufangen) :bloed:

 

[HarleyDavidson]

Stimmt... Nach der for - Schleife war ich mental so durch 😀 weil ich echt am Grübeln war.
Hier die Erklärung:

Grundlegender Aufbau einer for-Schleife:

for (Teil 1; Teil 2; Teil 3)

Teil 1: "int index = text.indexOf( pattern, 0 )"
Hier wird die Zählvariable initialisiert.
"indexOf" gibt das erste Vorkommen des Patterns zurück.
Ab hier wird also das Vorkommen des Patterns gezählt

Teil 2: "index != -1"
Die Schleife wird so lange durchlaufen, solange index ungleich -1 ist.
Das kommt daher, da indexOf den Wert -1 zurück gibt, wenn das Pattern
nicht gefunden wurde

Teil 3: "index = text.indexOf( pattern, eagerMatching ? index + 1 : index + pattern.length()"
Hier wird es spannend. Die Zählvariable index wird nicht wie gewohnt hochgezählt sondern
nach jedem Durchlauf wird entweder:

- bei eagerMatching = true: Die Zählvariable um 1 erhöht
- bei eagerMatching = false: Die Zählvariable um die Länge des Patterns erhöht

Und ab dort wird wieder nach dem Pattern gesucht. Wird dieser nicht mehr gefunden, dann bricht
die Schleife ab, wie in Teil 2 definiert.
eagerMatching war dabei so ein kleiner Test ob es zu einer Performanzsteigerung / Ungenauigkeit
kommt. Ich konnte keine feststellen, aber vielleicht beobachtet ja noch mehr was.

    /**
     * Dekomprimiert einen komprimierten String
     *
     * @param text Der komprimierte String
     * @param compressChar Das Kompressionszeichen
     * @return Den dekomrimierten String
     */
    public static String decompress( String text, String compressChar )
    {
        //Komprimierten String splitten
        String[] info = text.split( ":" );
        //Pattern extrahieren
        String pattern = info[0];
        //Eigentlichen String extrahieren
        String result = info[1];
        //Pattern einsetzen
        return result.replaceAll( compressChar, pattern );
    }

    /**
     * Liefert die Anzahl zurück, wie oft ein Teilstring in einem String
     * vorkommt
     *
     * @param text Der Gesamttext
     * @param pattern Der Teilstring
     * @return Die Anzahl, wie oft der Teilstring im String vorkommt.
     */
    public static int getOccurences( String text, String pattern )
    {
        int occurences = 0;
        boolean eagerMatching = true;
        if ( 0 != pattern.length() )
        {
            for ( int index = text.indexOf( pattern, 0 ); index != -1; index = text.indexOf( pattern, eagerMatching ? index + 1 : index + pattern.length() ) )
            {
                occurences++;
            }
            return occurences;
        }
        return 0;
    }