Given a vector of elements, how can I calculate the length of the Huffman codewords without generating the Huffman code itself?
Using Matlab, I was able to compute the Huffman code and and get the length of the codewords but is it possible to get the lengths alone without computing the codewords?
You can count the distribution of frequency of the alphabet you want to Huffman encode.
If this distribution is skewed Huffman encoding will perform poorly.
See: When would the worst case for Huffman coding occur?
If this distribution is flat Huffman encoding will perform well.
The more letters in your possible alphabet do not occur in your text the better Huffman performs.
If however you have a flat distribution and most or all of the possible encoding space in your alphabet is used, then Huffman encoding will not be able to compress it.
If you want to generate the lengths of the codes that Huffman would create without actually doing Huffman encoding you will need to create a algorithm so close to Huffman as to not make very much difference, especially not in running time.
Note that the bulk of the running time of Huffman encoding is taken up by frequency counting.
For a text of length $n$ with an alphabet of $a$ characters the running time of Huffman is $O(n+a)$ and because $a$ is almost always insignificant (as well as being a constant) in comparison to $n$. The running time is $O(n)$.
You can skip the counting step if you want by making assumptions about your input.
For instance if you know your input is English text or C-source code, than you can simply use the average frequencies for typical English texts (or C-source code) to generate your Huffman code.
If so you will already know the lengths of your codes, because you are simply loading a precomputed table of Huffman codes.
Needless to say this risks suboptimal compression.
