Deciphering Text Based on Letter Frequency

Question

I have a quick question on taking an encrypted text file's content and swapping out the corresponding letters based on a given frequency list.

For instance, the first few lines in the text file are:

XWJGFBVCCVUJYPXQZGCVXQHXKAZGPVPUHBZJYPUVMFCZVYXQZWJFZJCCMVMGHWZBZXQZFKBKUBKAZGJY

I created an ArrayList of the individual characters and then found how many times each letter appears in the file in the HashSet.

A: 6
B: 35
C: 30
D: 21
F: 31
G: 38
H: 16
I: 1
J: 61
K: 53
L: 16
M: 26
N: 7
O: 3
P: 33
Q: 61
R: 10
S: 8
U: 21
V: 37
W: 23
X: 67
Y: 36
Z: 80

import java.io.*;
import java.util.*;

public class lab9 {

  lab9() {

    try {

      String content = new Scanner(new File("Cipher.txt")).useDelimiter("\\Z").next();
      String letters = content.replaceAll("\\W", "");

      System.out.println(letters);

      List < String > list = new ArrayList < String > (Arrays.asList(letters.split("")));

      Set < String > unique = new HashSet < String > (list);
      for (String key: unique) {
        System.out.println(key + ": " + Collections.frequency(list, key));
      }

      String decipher = "ETAHOSINRDBLMWGUCYFJKVPXQZ";
      List < String > list2 = new ArrayList < String > (Arrays.asList(decipher.split("")));

      System.out.println(decipher);

    } catch (IOException e) {
      e.printStackTrace();
    }
  }
}

In the code snippet, you can see the String decipher which is a list of the most commonly used letters in the English language in descending order. Thus, I want to swap the letter Z with E in the text file. What would be an efficient way of doing this?

score 0 · Accepted Answer · edited May 23 '17 at 12:22

0

One way to do this would be to wrap the letter-frequency pairings in a Java object, representing letter frequencies. You would then implement a comparator for these objects to sort them based on frequency. You would do the same thing for an a prebuilt list of actual letter frequencies, leaving you with two sorted lists.

An efficient solution from this point would be to create a hash map between the encrypted and decrypted letters, then iterate through the string replacing each character with the proper value. This would give you a "decrypted" version of the message, although unless you have a larger body of encrypted text to work with, there will probably be some mistakes in this direct translation based on frequencies alone.

Here's a good answer for creating a comparator on custom objects: Sort ArrayList of custom Objects by property

edited May 23 '17 at 12:22

Community

1
1

answered Mar 23 '15 at 22:13

Aaron

596
1
5
15

I've managed to create a sorted LinkedHashMap of the encrypted letters based on their values of occurence or frequency. So the next step would be to combine these encrypted letters against the decrypted letters in a single HashMap? Also, you are right that there will be mistakes since some frequencies are the same so I'll have to make fixes accordingly. – Mar 24 '15 at 12:54
1

That is correct, you want a dictionary representing the relationship between each encrypted letter and its respective decrypted letter. The point of this HashMap is to be able to achieve an O(n) conversion runtime, since each of the lookups in the HashMap will be O(1). Based on your example, this conversion HashMap would contain the pairing `{ "Z" => "E" }`, along with the rest of the letter pairings. – Aaron Mar 24 '15 at 13:45

score 0 · Answer 2 · answered Mar 23 '15 at 22:37

Sort your ArrayList in descending order. Create Dictionary/Hashtable with key=letter, value=index position of that letter in your ArrayList.

Read the encrypted text character by character (charRead) from the beginning and replace each letter with decipher[Hashtable[charRead]]

You'll need to change the pseudocode above to Java

Deciphering Text Based on Letter Frequency

2 Answers2