void createBinaryTree ( ) { int [ ] point = new int [ VocabWord . MAX_CODE_LENGTH ] ; char [ ] code = new char [ VocabWord . MAX_CODE_LENGTH ] ; int [ ] count = new int [ vocabSize * 2 + 1 ] ; char [ ] binary = new char [ vocabSize * 2 + 1 ] ; int [ ] parentNode = new int [ vocabSize * 2 + 1 ] ; for ( int i = 0 ; i < vocabSize ; i ++ ) count [ i ] = vocab [ i ] . cn ; for ( int i = vocabSize ; i < vocabSize * 2 ; i ++ ) count [ i ] = Integer . MAX_VALUE ; int pos1 = vocabSize - 1 ; int pos2 = vocabSize ; // Following algorithm constructs the Huffman tree by adding one node at a time int min1i , min2i ; for ( int i = 0 ; i < vocabSize - 1 ; i ++ ) { // First, find two smallest nodes 'min1, min2' if ( pos1 >= 0 ) { if ( count [ pos1 ] < count [ pos2 ] ) { min1i = pos1 ; pos1 -- ; } else { min1i = pos2 ; pos2 ++ ; } } else { min1i = pos2 ; pos2 ++ ; } if ( pos1 >= 0 ) { if ( count [ pos1 ] < count [ pos2 ] ) { min2i = pos1 ; pos1 -- ; } else { min2i = pos2 ; pos2 ++ ; } } else { min2i = pos2 ; pos2 ++ ; } count [ vocabSize + i ] = count [ min1i ] + count [ min2i ] ; parentNode [ min1i ] = vocabSize + i ; parentNode [ min2i ] = vocabSize + i ; binary [ min2i ] = 1 ; } // Now assign binary code to each vocabulary word for ( int j = 0 ; j < vocabSize ; j ++ ) { int k = j ; int i = 0 ; while ( true ) { code [ i ] = binary [ k ] ; point [ i ] = k ; i ++ ; k = parentNode [ k ] ; if ( k == vocabSize * 2 - 2 ) break ; } vocab [ j ] . codelen = i ; vocab [ j ] . point [ 0 ] = vocabSize - 2 ; for ( k = 0 ; k < i ; k ++ ) { vocab [ j ] . code [ i - k - 1 ] = code [ k ] ; vocab [ j ] . point [ i - k ] = point [ k ] - vocabSize ; } } }
Create binary Huffman tree using the word counts . Frequent words will have short uniqe binary codes