Questions about ACM Problem

[Manrolo]

Hello community.

The problem belongs to ACM International Collegiate Programming Contest 2013.

 

Problem I - Inverting Huffman

Static Huffman coding is an encoding algorithm used mainly for text compression. Given a text of certain size made of N different characters, the algorithm chooses N codes, one for each different character. The text is compressed using these codes. To choose the codes, the algorithm builds a binary rooted tree having N leaves. For N≥2 the tree can be built as follows.


1. For each different character in the text build a tree containing just a single node, and assign to it a weight coincident with the number of occurrences of the character within the text.
2. Build a set s containing the above N trees.
3. While s contains more than one tree:
(a) Choose t1 Є s with minimum weight and remove it from s.
(b) Choose t2 Є s with minimum weight and remove it from s.
© Build a new tree t with t1 as its left subtree and t2 as its right subtree, and assign to t the sums of the weights of t1 and t2.
(d) Include t into s.
4. Return the only tree that remains in s.
For the text "abracadabra", the tree produced by the above procedure can look like the one on the left of the following picture, where each internal node is labeled with the weight of the subtree rooted at that node. Notice that the obtained tree can also look like the one on the right of the picture, among others, because at steps 3a and 3b the set s may contain several trees with minimum weight.



For each different character in the text, its code depends on the path that exists, in the nal tree, from the root to the leaf corresponding to the character. The length of the code is the number of edges in that path (which is coincident with the number of internal nodes in the path). Assuming the tree on the left was built by the algorithm, the code for \r" has length 3 while the code for "d" has length 4.
Your task is, given the lengths of the N codes chosen by the algorithm, nd the minimum size (total number of characters) that the text can have so as the generated codes have those N lengths.
Input
The rst line contains an integer N (2 ≤ N ≤ 50) representing the number of different characters that appear in the text. The second line contains N integers Li indicating the lengths of the codes chosen by Huffman algorithm for the different characters (1 ≤ Li ≤ 50 for i = 1; 2;...;N). You may assume that there exists at least one tree, built as described, that produces codes with the given lengths.
Output
Output a line with an integer representing the minimum size (total number of characters) that the text can have so as the generated codes have the given lengths.

The questions are:

-What mathematical resources are useful for working the problem?
-I'm working with Java and I need useful resources of this language to solve this problem
-How is the general analysis to model a possible solution?

Thanks for your attention, any contribution is welcome.

[fiveworlds]

Is this homework? How far have you gotten yourself?

 

 

1. For each different character in the text build a tree containing just a single node, and assign to it a weight coincident with the number of occurrences of the character within the text.

 

 

 

You obviously can't make a 'tree' in java you will need to use a multi-dimensional array or arrayList. You need to keep track of the letter and the number of occurances of that letter in the text.

[Sensei]

You obviously can't make a 'tree' in java you will need to use a multi-dimensional array or arrayList.

Obviously you can make tree in Java. Like in any OO environment.

You just have to make class with left branch of tree, and right branch of tree. If it's binary tree.

Eventually containing information whether it's 'leaf' or 'branch', and eventually containing quantity of elements, or other things related to project. f.e. 3D KD-Tree has axis integer and median float/double.

 

There are also trees with other quantity of branches or leafs. The most common Octree.

[fiveworlds]

Obviously you can make tree in Java. Like in any OO environment

 

 

 

Obviously I meant for the Op to think about the problem through using arrays...

 

 

package acm;

 

import java.util.ArrayList;

import java.util.BitSet;

import java.util.Collections;

import java.util.Scanner;

 

public class StaticHuffman {

public static void main(String[] args) {

System.out.println("Type the string to be encoded.");

Scanner Scanner = new Scanner(System.in);

String decoded = Scanner.nextLine().toLowerCase();

ArrayList List = generateList(decoded);

Collections.sort(List, Collections.reverseOrder());

 

//Convert the string to zeros and ones

String replacement = "10", header = "", encoded = decoded;

for (String counter : List) {

encoded = encoded.replaceAll(counter.substring(counter.length() - 1), replacement);

replacement = "1" + replacement;

header = header + counter.substring(counter.length() - 1);

}

 

//data prior to binary encoding

System.out.println("header:" + header + "\n" + "Binary Data:" + encoded);

 

//data is then binary encoded

BitSet binaryencoded = fromString(encoded);

 

//encoded binary is then decoded

String decodedBinary = toString(binaryencoded);

System.out.println("header:" + header + "\n" + "Binary Data:" + decodedBinary);

 

//convert the string from zeros and ones to text

replacement = "";

for(int t = header.length(); t>0; t--){

replacement = "";

for(int k=0; k replacement = replacement + "1";

}

replacement = replacement + "0";

decodedBinary = decodedBinary.replaceAll(replacement, String.valueOf(header.charAt(t-1)));

}

System.out.println(decodedBinary);

 

//close the scanner

Scanner.close();

}

 

//generate binary 'tree' array

private static ArrayList generateList(String tempDecoded) {

ArrayList tree = new ArrayList();

while (tempDecoded.length() > 0) {

String c = tempDecoded.toLowerCase().substring(0, 1);

int length = tempDecoded.length();

tempDecoded = tempDecoded.replaceAll(String.valueOf©, "");

length = length - tempDecoded.length();

tree.add(length + " " + c);

}

return tree;

}

 

//convert from String to binary BitSet

private static BitSet fromString(final String s) {

BitSet temp = new BitSet(s.length());

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

if (s.charAt(i) == '1') {

temp.set(i, true);

} else {

temp.set(i, false);

}

}

return temp;

}

 

//convert from binary BitSet to string

private static String toString(BitSet bs) {

String binaryData = "";

for (int t = 0; t < bs.length() + 1; t++) {

if (bs.get(t)) {

binaryData = binaryData + "1";

} else {

binaryData = binaryData + "0";

}

}

return binaryData;

}

 

}

 

;>

[Sensei]

 

Obviously I meant for the Op to think about the problem through using arrays...

 

I can't believe my own eyes...

 

Did you read entire my post... ?

[Manrolo]

Is this homework? How far have you gotten yourself?

 

 

 

 

You obviously can't make a 'tree' in java you will need to use a multi-dimensional array or arrayList. You need to keep track of the letter and the number of occurances of that letter in the text.

 

It's a proyect for the University. I need to solve this problem but this must be in stages and I'm beginning

[Zont]

Hello, everyone I am Manrolo classmate and partner working in the same problem, although i thanks fiveworlds, because the code was helpfull to understand in a better way the static huffman algorithm, we were looking for a way in how to work with the problem. The problem which is looking for the shortest "word" that we con form with the lenghts given by a static huffman binary tree.

We began working using thinking that creating an empty binary tree and then filling it would be the best way to work our way in the problem, but we came to know that i may be possible to do this problem using a greedy algorithm, which regretably we don't know how to use, if there is someone who can point us a direction it would be incredible helpfull.

Thanks.