Как посчитать количество бит в коде Хаффмана? - PullRequest
Новая
       46

Как посчитать количество бит в коде Хаффмана?

1 голос
/ 03 февраля 2020

Я пытаюсь посчитать байты текстового файла. Для этого мне нужно посчитать эффективность сжатия с кодированием Хаффмана. У меня есть три класса о Хаффмане.

В основном классе: 

Scanner s = new Scanner(System.in);
    // creating a priority queue q.
    // makes a min-priority queue(min-heap).
    PriorityQueue<HuffmanNode> q
            = new PriorityQueue<HuffmanNode>(count.length, new MyComparator());

    for (int i = 0; i < count.length; i++) {

        // creating a Huffman node object
        // and add it to the priority queue.
        HuffmanNode hn = new HuffmanNode();

        hn.c = alphabet[i];
        hn.data = count[i];

        hn.left = null;
        hn.right = null;

        // add functions adds
        // the huffman node to the queue.
        q.add(hn);
    }

    // create a root node
    HuffmanNode root = null;

    // Here we will extract the two minimum value
    // from the heap each time until
    // its size reduces to 1, extract until
    // all the nodes are extracted.
    while (q.size() > 1) {

        // first min extract.
        HuffmanNode x = q.peek();
        q.poll();

        // second min extarct.
        HuffmanNode y = q.peek();
        q.poll();

        // new node f which is equal
        HuffmanNode f = new HuffmanNode();

        // to the sum of the frequency of the two nodes
        // assigning values to the f node.
        f.data = x.data + y.data;
        f.c = '-';

        // first extracted node as left child.
        f.left = x;

        // second extracted node as the right child.
        f.right = y;

        // marking the f node as the root node.
        root = f;

        // add this node to the priority-queue.
        q.add(f);
    }

    // print the codes by traversing the tree
    Huffman.printCode(root, "");

Класс Хаффмана: 

public class Huffman {
// recursive function to print the
// huffman-code through the tree traversal.
// Here s is the huffman - code generated.
public static void printCode(HuffmanNode root, String s)
{
    // base case; if the left and right are null
    // then its a leaf node and we print
    // the code s generated by traversing the tree.
    if (root.left
            == null
            && root.right
            == null
            && Character.isLetter(root.c)) {

        // c is the character in the node
        System.out.println(root.c + ":" + s);

        return;
    }

    // if we go to left then add "0" to the code.
    // if we go to the right add"1" to the code.

    // recursive calls for left and
    // right sub-tree of the generated tree.
    printCode(root.left, s + "0");
    printCode(root.right, s + "1");
}

Существует еще два класса для настройки объектов и один для сравнения узлов. Хаффман работает отлично, и я беру следующий результат: 

t:000
c:00100
g:00101
d:0011
w:01000
u:01001
r:0101
e:011
s:1000
n:1001
h:1010
i:1011
o:1100
b:110100... //for the rest aphabet letters.

Мне нужно подсчитать, какие биты отображаются для каждой буквы, и сохранить их в целочисленный массив, например, t: 3 o: 4 (. ..)

Есть мысли?

1 Ответ

0 голосов
/ 13 февраля 2020

Вы хотите создать карту типа как закрытый атрибут класса Хаффмана. Затем внутри тела вашего оператора if вы хотите поместить новую пару на карту, где пара будет символом и вашей строкой. В вашем случае это будет root. c и s.

Поскольку это строка, вам, конечно, нужно будет преобразовать ее в целочисленный массив. Вы можете найти простые способы сделать это здесь: Преобразование строкового массива в целочисленный массив .

Затем вы можете создать метод, который вызывает атрибут (являющийся картой) из класса Хаффмана, а затем из вызова карты любой массив, который вы хотите.

Таким образом, ваш класс Хаффмана должен стать объект с конструктором, поэтому вы должны создать объект Хаффмана, затем запустить метод кода печати, а затем извлечь карту из объекта Хаффмана.

...