У меня проблемы с определением приоритета для каждого узла, содержащего символ Чтобы распаковать мой сжатый файл.
Итак, когда я сжимаю файл, он дает мне текстовый файл, содержащий что-то вроде этого:
Я сжал: Привет, мир, это тест.
@ 111 ^ а @ 10000 ^ # @ 10001 ^ д @ 10011 ^ е @ 1010 ^ Н @ 0000 ^ H @ 10110 ^ я @ 1101 ^ л @ 001 ^. @ 0001 ^ о @ 1100 ^ г @ 10010 ^ s @ 011 ^ т @ 010 ^ ш @ 10111 ^%
00001010001001110011110111110010010001100111110101011011010111111101011111100001110101010011010000110001
Первые две строки имеют двоичное представление каждого символа, содержащегося в сжатом файле.
Вторые две строки - это фактический сжатый текст.
Класс сжатия создает дерево, устанавливая приоритет узлов, равный числу вхождений.
Однако класс сжатия не записывает количество вхождений для каждого символа в выходной файл.
Чтобы определить приоритет, я подумал, что могу сделать это по длине двоичной строки для каждого символа. Если длина строки больше, то она используется реже. С другой стороны, если он меньше, он используется больше.
Однако это, похоже, не создавало дерево так, как я хотел, поскольку оно дало мне неправильный вывод.
Мне удалось получить правильный вывод, отредактировав то, что сжатый файл записывает в выходной файл. В основном, просто передавая частоты персонажей. Но как бы я это сделал, не имея этих ценностей - мой главный вопрос.
Я также думал, что я мог бы просто сделать дерево на основе фактической двоичной строки для каждого символа. Что-то вроде создания фиктивного корневого узла. Если charAt (i) в строке равно 0, то идите влево, а затем - вправо. Я думаю, что мой код может быть немного для этого, потому что я получаю исключения нулевого указателя при попытке пройти по дереву. Я отправлю код ниже.
Это короткая простая версия, если нужно, я могу выложить больше
public class Decompress {
private static Node root;
private static HashMap<Character, String> values = new HashMap<Character, String>();
private static HashMap<Character, Integer> freq = new HashMap<Character, Integer>();
public Decompress() {
root = null;
}
private static class Node implements Comparable {
public Character value;
public Integer number;
public Node left;
public Node right;
// necessary in order for the priority queue to work
// since it uses the compareTo to determine priority.
public int compareTo(Object o) {
Node other = (Node) o;
if (other.number < number) {
return 1;
}
if (other.number == number) {
return 0;
}
return -1;
}
public static void main(String args[]) throws IOException {
BufferedReader fin = new BufferedReader(new FileReader("output" + ".txt"));
String binaryDigits = insertListHelper(fin); // contains the compressed txt
root = createTree(binaryDigits); // Grabs the root node from method
Node hold = root;
// code for traversing the tree to find the character
for (int i = 0; i < binaryDigits.length(); i++) {
if (binaryDigits.charAt(i) == '1') {
root = root.right;
} else if (binaryDigits.charAt(i) == '0') {
root = root.left;
}
if (root.left == null && root.right == null) {
System.out.println(root.value);
root = hold;
}
}
}
// works when I have the correct frequency
public static Node createTree(String binaryDigit) {
PriorityQueue<Node> pq = new PriorityQueue<Node>();
// insert all 1 node trees into pq
Set<Character> s = values.keySet();
for (Character c : s) {
Node temp = new Node();
temp.value = c;
temp.number = values.get(c).length();
temp.left = null;
temp.right = null;
pq.add(temp);
}
Node eof = new Node();
eof.value = '#';
eof.number = 1;
eof.left = null;
eof.right = null;
pq.add(eof);
while (pq.size() > 1) {
Node left = pq.poll();
Node right = pq.poll();
Node temp = new Node();
temp.value = null;
temp.number = left.number + right.number;
temp.left = left;
temp.right = right;
pq.add(temp);
}
return pq.peek();
}
// does not work any suggestions?
public static Node createTree2() {
String[] binaryRep = new String[values.size()];
int k = 0;
int lengthOfStr = 0;
Set<Character> s1 = values.keySet();
for (Character c : s1) {
binaryRep[k] = values.get(c);
System.out.println(c + " String : " + binaryRep[k]);
Node root = new Node();
root.value = 'R';
root.left = null;
root.right = null;
Node hold = root;
lengthOfStr = binaryRep[k].length();
for (int i = 0; i < binaryRep[k].length(); i++) {
if (binaryRep[k].charAt(i) == '1' && root.right != null) {
root = root.right;
} else if (binaryRep[k].charAt(i) == '0' && root.left != null) {
root = root.left;
} else if (binaryRep[k].charAt(i) == '1' && root.right == null && lengthOfStr == 0) {
// found our place to insert
Node temp = new Node();
temp.left = null;
temp.right = null;
temp.number = 1;
temp.value = c;
root.right = temp;
// move forward to the temp var
root = root.right;
root = hold;
lengthOfStr--;
} else if (binaryRep[k].charAt(i) == '0' && root.left == null && lengthOfStr == 0) { // should be a leaf
// node
// found our place to insert
Node temp = new Node();
temp.left = null;
temp.right = null;
temp.number = 0;
temp.value = c;
root.left = temp;
// move forward to the temp var
root = root.right;
root = hold;
lengthOfStr--;
} else if (binaryRep[k].charAt(i) == '1' && root.right == null) {
// found our place to insert
Node temp = new Node();
temp.left = null;
temp.right = null;
temp.number = 1;
temp.value = null;
root.right = temp;
// move forward to the temp var
root = root.right;
lengthOfStr--;
} else if (binaryRep[k].charAt(i) == '0' && root.left == null) {
// found our place to insert
Node temp = new Node();
temp.left = null;
temp.right = null;
temp.number = 0;
temp.value = null;
root.left = temp;
// move forward to the temp var
root = root.left;
lengthOfStr--;
}
}
k++;
}
return root;
}
}