private static void generateHuffmanCodeLengths ( final int alphabetSize , final int [ ] symbolFrequencies , final int [ ] codeLengths ) { final int [ ] mergedFrequenciesAndIndices = new int [ alphabetSize ] ; final int [ ] sortedFrequencies = new int [ alphabetSize ] ; // The Huffman allocator needs its input symbol frequencies to be sorted, but we need to // return code lengths in the same order as the corresponding frequencies are passed in. // The symbol frequency and index are merged into a single array of // integers - frequency in the high 23 bits, index in the low 9 bits. // 2^23 = 8,388,608 which is higher than the maximum possible frequency for one symbol in a block // 2^9 = 512 which is higher than the maximum possible alphabet size (== 258) // Sorting this array simultaneously sorts the frequencies and // leaves a lookup that can be used to cheaply invert the sort. for ( int i = 0 ; i < alphabetSize ; i ++ ) { mergedFrequenciesAndIndices [ i ] = ( symbolFrequencies [ i ] << 9 ) | i ; } Arrays . sort ( mergedFrequenciesAndIndices ) ; for ( int i = 0 ; i < alphabetSize ; i ++ ) { sortedFrequencies [ i ] = mergedFrequenciesAndIndices [ i ] >>> 9 ; } // Allocate code lengths - the allocation is in place, // so the code lengths will be in the sortedFrequencies array afterwards Bzip2HuffmanAllocator . allocateHuffmanCodeLengths ( sortedFrequencies , HUFFMAN_ENCODE_MAX_CODE_LENGTH ) ; // Reverse the sort to place the code lengths in the same order as the symbols whose frequencies were passed in for ( int i = 0 ; i < alphabetSize ; i ++ ) { codeLengths [ mergedFrequenciesAndIndices [ i ] & 0x1ff ] = sortedFrequencies [ i ] ; } }
Generate a Huffman code length table for a given list of symbol frequencies .