Сложность с Цезарем Шифр ​​Ши-Squared

Question

Если вы не знакомы с шифром. Идея состоит в том, чтобы иметь возможность кодировать сообщение, перемещая буквы в алфавите. Ex. d сдвиг 3 -> a. Затем сможете декодировать сообщение с использованием метода трещины. Метод трещины делает массив полным значений квадрата (по сравнению с естественными алфавитными частотами в таблице) для каждого возможного сдвига (его индекс) и проверяет, имеет ли значение сдвига наименьшее значение. Затем он принимает это значение и декодирует его, используя эту величину сдвига.

Проблема, я получаю наименьшее значение квадрата квадрата в неправильном адресе массива, чтобы его можно было точно декодировать. Я не ищу, чтобы кто-то дал мне ответ, просто для того, где я должен посмотреть в своем коде, чтобы внести исправление.

Заранее спасибо.

import java.util.Arrays; 

public class Cipher { 
//alphabet frequency 
static double[] table = {8.2, 1.5, 2.8, 4.3, 12.7, 2.2, 2.0, 6.1, 7.0, 0.2, 0.8, 4.0, 2.4, 6.7, 
    7.5, 1.9, 0.1, 6.0, 6.3, 9.1, 2.8, 1.0, 2.4, 0.2, 2.0, 0.1}; 

//convert letter to number 
static int let2nat(char c) 
{ 
    return ((int) c) - 97; 
} 
//convert number to letter 
static char nat2let(int code) 
{ 
    return (char) (code + 97); 
} 
//shift a letter to another letter shftAmt spaces away 
static char shift(int shftAmt, char c) 
{ 
    if (let2nat(c) < 0 || let2nat(c) > 25) 
     return c; 
    return nat2let((let2nat(c) + shftAmt) % 26); 

} 
//encodes a string using the given shift amount 
static String encode(int shftAmt, String str) 
{ 
    char[] encodedStr = new char[str.length()]; 
    for(int i = 0; i < str.length(); i++) 
     encodedStr[i] = shift(shftAmt, str.charAt(i)); 
    return new String(encodedStr); 
} 
//performs the inverse method to encode 
static String decode(int shftAmt, String str) 
{ 
    char[] decodedStr = new char[str.length()]; 
    for(int i = 0; i < str.length(); i++) 
     decodedStr[i] = shift(0 - shftAmt, str.charAt(i)); 
    return new String(decodedStr); 
} 
//determines how many lowercase letters are in the string str 
static int lowers(String str) 
{ 
    int count = 0; 
    for(int i = 0; i < str.length(); i++) 
     if(let2nat(str.charAt(i)) >= 0 && let2nat(str.charAt(i)) <= 25) 
      count++; 
    return count; 
} 
//calculates the number of a character in a string 
static int count(char c, String str) 
{ 
    int counter = 0; 
    for(int i = 0; i < str.length(); i++) 
     if(c == str.charAt(i)) 
      counter++; 
    return counter; 
} 
//calculates the percent off num1 to num2 
static double percent(int num1, int num2) 
{ 
    return ((double) num1/num2 * 100); 
} 
//find the ratio frequency of all letters in the string str 
static double[] freqs(String str) 
{ 
    double[] count = new double[26]; 
    for(int i = 0; i < str.length(); i++) 
     if(let2nat(str.charAt(i)) >= 0 && let2nat(str.charAt(i)) <= 25) 
      count[let2nat(str.charAt(i))]++; 
    for(int i = 0; i < 26; i++) 
     count[i] = percent((int)count[i], lowers(str)); 
    return count; 
} 
//rotates a list n places to the left 
static double[] rotate(int n, double[] list) 
{ 
    int j = 0; 
    while(j<n){ 
     double starter = list[0]; 
     //shift one left 
     for(int i = 0; i < list.length-1; i++) 
      list[i] = list[i+1]; 
     list[list.length-1] = starter; 
     j++; 
    } 
    return list; 
} 
//calculates the chi square value 
static double chisqr(double[] os) 
{ 
    double chitotal = 0; 
    for(int i = 0; i < os.length; i++) 
     chitotal += ((Math.pow((os[i] - table[i]), 2))/table[i]); 
    return chitotal; 
} 
//returns the first position at whcih a value occurs,if returns 999999 then it doesnt exist in the array 
static int position(double a, double[] list) 
{ 
    for(int i = 0; i < list.length; i++) 
     if(list[i] == a) 
      return i; 
    return 999999; 
} 
static String crack(String str) 
{ 
    double[] frequencies = freqs(str); 
    double[] chisqrValues = new double[26]; 
    for(int i = 0; i < 26; i++) 
     chisqrValues[i] = chisqr(rotate(i, frequencies)); 
    int smallestIndex = 0; 
    for(int i = 1; i < 26; i++) 
     if(chisqrValues[i] < chisqrValues[smallestIndex]) 
      smallestIndex = i; 
    return decode(smallestIndex, str); 
} 
public static void main(String[] args) 
{ 
    System.out.println(crack(encode(3, "haskellisfun"))); 
} 

} 

Answer 1

Как уже говорилось в комментарии, ваш код сдвига является неправильным, когда отрицательные числа используются в качестве параметра индекса, и это из-за того, как Java обрабатывает отрицательные значения, когда используется оператор %. Чтобы быть в безопасности, вы должны сделать что-то вроде:

// shift a letter to another letter shftAmt spaces away 
static char shift(int shftAmt, char c) { 
    if (let2nat(c) < 0 || let2nat(c) > Z_TO_A - 1) { 
    return c; 
    } else { 
    // do a safe shift 
    int result = (let2nat(c) + shftAmt) % Z_TO_A; 
    result += Z_TO_A; 
    result %= Z_TO_A; 
    return nat2let(result); 
    } 
} 

Но, как и упоминалось в комментариях, это не является причиной вашей ошибки, и найти эту ошибку, вы должны проверить каждый метод, лучше всего с модульного тестирования , или если нет, то у вас есть свои собственные методы тестирования, чтобы быть уверенным в том, что они все ведут себя так, как ожидалось, а если нет, по крайней мере, позволяя вам изолировать вашу ошибку, которая поможет вам решить проблему на полпути.

Как в стороне, моя собственная проблема заключается в том, чтобы не игнорировать буквы верхнего регистра, как ваш код, но поскольку они являются частью частоты текстовых букв, они должны использоваться при вычислении нашей собственной частоты букв. Что-то вроде этого могло бы хорошо работать:

/** 
* 
* @author hovercraft 
* {@link http://stackoverflow.com/q/31303332/522444} 
*/ 
public class Cipher2 { 
    // just ban "magic" numbers 
    public static final int A_VALUE = (int) 'a'; 
    public static final int Z_TO_A = (int) ('z' - 'a') + 1; 
    // alphabet frequency 
    static double[] table = { 8.2, 1.5, 2.8, 4.3, 12.7, 2.2, 2.0, 6.1, 7.0, 0.2, 
     0.8, 4.0, 2.4, 6.7, 7.5, 1.9, 0.1, 6.0, 6.3, 9.1, 2.8, 1.0, 2.4, 0.2, 
     2.0, 0.1 }; 

    // convert letter to number 
    static int let2nat(char c) { 
     return ((int) c) - A_VALUE; 
    } 

    // convert number to letter 
    static char nat2let(int code) { 
     return (char) (code + A_VALUE); 
    } 

    // shift a letter to another letter shftAmt spaces away 
    static char shift(int shftAmt, char c) { 
     if (let2nat(c) < 0 || let2nat(c) > Z_TO_A - 1) { 
     return c; 
     } else { 
     // do a safe shift 
     int result = (let2nat(c) + shftAmt) % Z_TO_A; 
     result += Z_TO_A; 
     result %= Z_TO_A; 
     return nat2let(result); 
     } 
    } 

    private static String crack(String encrypted) { 
     int[] letterCount = new int[Z_TO_A]; 
     for (char c : encrypted.toCharArray()) { 
     letterCount[let2nat(c)]++; 
     } 
     double[] letterFrequency = new double[Z_TO_A]; 
     for (int i = 0; i < letterCount.length; i++) { 
     letterFrequency[i] = (double) letterCount[i] * 100/Z_TO_A; 
     } 

     int index = 0; 
     double minChiSqrSum = calcChiSqrSum(index, letterFrequency); 
     for (int i = 0; i < Z_TO_A; i++) { 
     double chiSqrSum = calcChiSqrSum(i, letterFrequency); 
     if (chiSqrSum < minChiSqrSum) { 
      minChiSqrSum = chiSqrSum; 
      index = i; 
     } 
     } 
     return encode(index, encrypted); 
    } 

    private static double calcChiSqrSum(int i, double[] letterFrequency) { 
     double sum = 0.0; 
     for (int j = 0; j < letterFrequency.length; j++) { 
     double observed = letterFrequency[j]; 
     int tableIndex = (i + j + Z_TO_A) % Z_TO_A; 
     double expected = table[tableIndex]; 
     double delta = observed - expected; 
     double chiSqr = delta * delta/expected; 
     sum += chiSqr; 
     } 
     return sum; 
    } 

    private static String encode(int shift, String text) { 
     StringBuilder sb = new StringBuilder(); 
     for (char c : text.toCharArray()) { 
     // convert all upper case to lower case 
     // this is a judgment call on my part 
     c = Character.toLowerCase(c); 
     if (let2nat(c) >= 0 && let2nat(c) < Z_TO_A) { 
      sb.append(shift(shift, c)); 
     } 
     } 
     return sb.toString(); 
    } 

    public static void main(String[] args) { 
     String test1 = "Hello world. How is it going? It's going fine with me"; 
     String test2 = "When, in the course of human events, it becomes " 
      + "necessary for one portion of the family of man to assume " 
      + "among the people of the earth a position different from " 
      + "that which they have hitherto occupied, but one to which " 
      + "the laws of nature and of nature's God entitle them, " 
      + "a decent respect to the opinions of mankind"; 

     // let's throw it for a complete loop: ... but it works! 
     String test3 = "Lorem ipsum dolor sit amet, consectetur adipiscing " 
      + "elit, sed do eiusmod tempor incididunt ut labore et dolore " 
      + "magna aliqua. Ut enim ad minim veniam, quis nostrud " 
      + "exercitation ullamco laboris nisi ut aliquip ex ea commodo " 
      + "consequat. Duis aute irure dolor in reprehenderit in " 
      + "voluptate velit esse cillum dolore eu fugiat nulla pariatur. " 
      + "Excepteur sint occaecat cupidatat non proident, sunt in " 
      + "culpa qui officia deserunt mollit anim id est laborum."; 

     // an unfair test: 
     String test4 = "abcdefghijklmnopqrstuvwxyz"; 

     String test5 = "haskellisfun"; 
     String[] tests = { test1, test2, test3, test4, test5 }; 

     for (String test : tests) { 
     System.out.println(crack(encode(6, test))); 
     } 
    } 
}