Sich wiederholende substrings finden

Diskutiere Sich wiederholende substrings finden im Allgemeine Java-Themen Forum; Hallo zusammen, Ich arbeite gerade an einem Programm, das verschlüsselte Texte ohne viel Informationen wieder entschlüsseln, also quasi knacken...

  1. xxMarlonXX
    xxMarlonXX Neues Mitglied
    Hallo zusammen,
    Ich arbeite gerade an einem Programm, das verschlüsselte Texte ohne viel Informationen wieder entschlüsseln, also quasi knacken kann. Es ist auch schon fertig, hat nur noch 1, 2 Schönheitsfehler. Undzwar ist das einzige was das Programm braucht, Informationen darüber, ob in dem verschlüsselten Text bestimmte Zeichenfolgen (ab einer Länge von 3 Zeichen) wiederholt auftreten. Solche Zeichenfolgen müssen ausfindig gemacht werden. Meistens reicht es aus, wenn man 2-3 solcher substrings mit jeweils 3-4 Zeichen findet. Bis jetzt habe ich das von Hand gemacht, also die Texte schriftlich analysiert. Es wäre jedoch schöner wenn das Programm selbst die substrings findet, aber ich weiß nicht so recht wie ich das anstellen soll. Mit bei contains, indexof etc. muss die gesuchte Zeichenkette ja vorher bekannt sein, ist sie aber nicht. Jetzt ist die Frage, wie ich meinen verschlüsselten Text zerlegen und prüfen muss um die Wiederholungen zu finden. Hoffe das Problem ist verständlich und dass ihr mir weiterhelfen könnt :)
    LG

    P. S. Wem es weiterhilft: Es geht um Texte, die mit Vigenere verschlüsselt wurden.
     
  2. Vielleicht hilft dir dieser Kurs hier weiter --> (hier klicken)
  3. Nuiton
    Nuiton Mitglied
    Poste mal das, was du bereits hast.
     
  4. Joose
    Joose Super-Moderator Mitarbeiter
    Wie gehst du denn vor wenn du es per Hand machst? Schaust du nur ob dir optisch Wiederholungen ins Auge stechen oder gehst du da jedes Zeichen einzeln durch usw.?
    Genau dieses vorgehen mit Hand versuche in Code umzusetzen. Es ist vielleicht nicht gleich die optimalste Lösung, aber du solltest zu einem Ziel kommen.
    Danach kann man den Code immer noch optimieren.
     
  5. xxMarlonXX
    xxMarlonXX Neues Mitglied
    Danke für eure Antworten erstmal.
    Ja ich habe quasi geschaut wo es relativ offensichtliche Wiederholungen gibt, bin also nicht jedes Zeichen einzeln durchgegangen, das wäre bei etwas längeren Texten ja viel zu umständlich. Hab es wie folgt programmiert und es klappt auch alles, aber vielleicht habt ihr ja noch Verbesserungsvorschläge:

    Code (Java):
    public static ArrayList<String> findRepeatingSubstrings(String s){
         
            String[][] groups = new String[3][s.length()];
            char[] text = s.toCharArray();
            ArrayList<String> substrings = new ArrayList<String>();
         
            //1. TEXT IN ALLE MOEGLICHEN FÜNFER GRUPPEN SPLITTEN -> groups[0]  
            int count = 0;
            for(int i = 0; i < s.length(); i++){
                if(i+4 > s.length()-1){
                    break;
                }
                groups[0][count++] = (text[i]  + "") + (text[i+1]  + "") + (text[i+2]  + "") + (text[i+3]  + "") + (text[i+4]  + "");
            }
         
            //2. TEXT IN ALLE MOEGLICHEN VIERER GRUPPEN SPLITTEN -> groups[1]      
            count = 0;
            for(int i = 0; i < s.length(); i++){
                if(i+3 > s.length()-1){
                    break;
                }
                groups[1][count++] = (text[i]  + "") + (text[i+1]  + "") + (text[i+2]  + "") + (text[i+3]  + "");
            }
         
            //3. TEXT IN ALLE MOEGLICHEN DREIER GRUPPEN (TRIPLETS) SPLITTEN    -> groups[2]  
                count = 0;
                for(int i = 0; i < s.length(); i++){
                    if(i+2 > s.length()-1){
                        break;
                    }
                    groups[2][count++] = (text[i]  + "") + (text[i+1]  + "") + (text[i+2] + "");
         
                }      

         
            //Die einzelnen Gruppen nach Wiederholungen durchsuchen
            for(int i = 0; i < 3; i++){
                for(int k = 0; k < groups[i].length; k++){
                    if(groups[i][k] ==  null){
                        break;
                    }
                    String [] strings = s.split(groups[i][k]);
                    if(strings.length >= 4){
                        if(!Arrays.asList(substrings).contains(groups[i][k]))
                        substrings.add(groups[i][k]);
                    }
                }
            }
             
            return substrings;
        }
    LG
     
  6. Joose
    Joose Super-Moderator Mitarbeiter
    Deine for-Schleifen sehen sich ziemlich ähnlich. Hier könnte man die for-Schleife in eine Methode auslagern. Der Vorteil der sich daraus ergibt -> man muss bei einer Änderung nur noch eine Schleife statt 3 warten ;)

    Wenn du mit der Methode "substring" arbeitest ersparst du dir das zusammenhängen der einzelnen Zeichen.

    Ansonsten könntest du noch das 2dimensionale String Array durch verschachtelte Listen ersetzen. Dadurch wirst du dynamischer wenn du nicht mehr nur 5er, 4er und 3er Gruppen finden willst sondern auch andere Größen.

    Ich habe den Code mal "etwas" überarbeitet ;) ist aber ungetestet könnte sich also vielleicht auch ein Fehler eingeschlichen haben.

    Code (Java):
    public static ArrayList<String> findRepeatingAllSubstrings(String text) {
       ArrayList<ArrayList<String>> allGroups = new ArrayList<ArrayList<String>>();
       int maxGroupSize = 5;
       int minGroupSize = 3;

       for(; minGroupSize <= maxGroupSize; minGroupSize++) {
         ArrayList<String> group = new ArrayList<String>();  
         splitTextInGroups(text, group, minGroupSize);
         allGroups.add(group);
       }

       ArrayList<String> allSubstrings = new ArrayList<String>();
       //Die einzelnen Gruppen nach Wiederholungen durchsuchen
       for(ArrayList<String> group : allGroups) {
         for(String substring : group) {
           if(substring == null) {
             break;
           }
           String[] parts = s.split(substring);
           if(parts.length >= 4 && !allSubstrings.contains(substring)) {
             allSubstrings.add(substring);
           }
         }
       }
       return allSubstrings;
    }

    private static void splitTextInGroups(String text, ArrayList<String> group, int groupSize) {
       if(groupSize < 1) {
         throw new IllegalArgumentException("Die groupSize muss größer als 0 sein!");
       }
       for(int i = 0; i < s.length(); i++) {
         if(i + groupSize > s.length()) {
           break;
         }
         group.add(text.substring(i, i + groupSize);
       }
    }
    Mir ist noch aufgefallen dass man die eine oder andere Überprüfung noch einbauen kann/sollte.
     
    Zuletzt bearbeitet: 2. Dez. 2016
  7. xxMarlonXX
    xxMarlonXX Neues Mitglied
    Ich habe die Anpassungen gemacht Danke dafür. Nach ein paar weiteren Modifikationen ist mein Code auch um ein vielfaches schneller geworden! :D
    Ich bin mit dem Gesamtprojekt schon ein ganzes Stück weiter, mein Programm schafft es alle Texte, die mit einem bis zu vierstelligen Schlüsselwort verschlüsselt wurden zu knacken (Info über die Verschlüsselung: 1. https://de.wikipedia.org/wiki/Vigenère-Chiffre , 2. https://de.wikipedia.org/wiki/Kasiski-Test) . Warum es ab fünf Stellen gelegentlich Fehler gibt liegt (denke ich) immer noch an meiner Implementierung zur Auswahl der richtigen SubStrings (kann ja immer sein, dass manche Wiederholungen Zufall sind) und später dann in gelegentlichen Unregelmäßigkeiten bei der Häufigkeitsanalyse. Ich will nicht nerven aber gibt es irgendwo eine Möglichkeit über ganze Projekte zu diskutieren? Du oder andere User könnten mir bestimmt noch den eben genannten Problemen helfen...
    LG
     
  8. Joose
    Joose Super-Moderator Mitarbeiter
Die Seite wird geladen...

Sich wiederholende substrings finden - Ähnliche Themen

Matcher und Pattern bei sich wiederholenden Werten
Matcher und Pattern bei sich wiederholenden Werten im Forum Java Basics - Anfänger-Themen
Pufferproblem bei sich wiederholenden MouseEvents
Pufferproblem bei sich wiederholenden MouseEvents im Forum Spiele- und Multimedia-Programmierung
sich wiederholende arrayfelder ersetzen for-schleife
sich wiederholende arrayfelder ersetzen for-schleife im Forum Java Basics - Anfänger-Themen
Regulärer Ausdruck um sich wiederholende Zeichen zu finden.
Regulärer Ausdruck um sich wiederholende Zeichen zu finden. im Forum Allgemeine Java-Themen
Pdf-Document lässt sich im Servlet nicht öffnen
Pdf-Document lässt sich im Servlet nicht öffnen im Forum Java Basics - Anfänger-Themen
Thema: Sich wiederholende substrings finden