Sich wiederholende substrings finden

[xxMarlonXX]

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.

 

[Nuiton]

Poste mal das, was du bereits hast.

 

[Joose]

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.

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.

 

[xxMarlonXX]

Danke für eure Antworten erstmal.

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.?

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:

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

 

[Joose]

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.

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.

 

[xxMarlonXX]

Ich habe die Anpassungen gemacht Danke dafür. Nach ein paar weiteren Modifikationen ist mein Code auch um ein vielfaches schneller geworden!
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

 

[Joose]

Es gibt einen eigenen Bereich in welchem man Codeschipsel oder Projekte vorstellen bzw. diskutieren kann
http://www.java-forum.org/forum/codeschnipsel-u-projekte.16/