Class Bzip2HuffmanAllocator


  • final class Bzip2HuffmanAllocator
    extends java.lang.Object
    An in-place, length restricted Canonical Huffman code length allocator.
    Based on the algorithm proposed by R. L. Milidi'u, A. A. Pessoa and E. S. Laber in In-place Length-Restricted Prefix Coding and incorporating additional ideas from the implementation of shcodec by Simakov Alexander.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) static void allocateHuffmanCodeLengths​(int[] array, int maximumLength)
      Allocates Canonical Huffman code lengths in place based on a sorted frequency array.
      private static void allocateNodeLengths​(int[] array)
      A final allocation pass with no code length limit.
      private static void allocateNodeLengthsWithRelocation​(int[] array, int nodesToMove, int insertDepth)
      A final allocation pass that relocates nodes in order to achieve a maximum code length limit.
      private static int findNodesToRelocate​(int[] array, int maximumLength)
      Finds the number of nodes to relocate in order to achieve a given code length limit.
      private static int first​(int[] array, int i, int nodesToMove)  
      private static void setExtendedParentPointers​(int[] array)
      Fills the code array with extended parent pointers.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • Bzip2HuffmanAllocator

        private Bzip2HuffmanAllocator()
    • Method Detail

      • first

        private static int first​(int[] array,
                                 int i,
                                 int nodesToMove)
        Parameters:
        array - The code length array
        i - The input position
        nodesToMove - The number of internal nodes to be relocated
        Returns:
        The smallest k such that nodesToMove <= k <= i and i <= (array[k] % array.length)
      • setExtendedParentPointers

        private static void setExtendedParentPointers​(int[] array)
        Fills the code array with extended parent pointers.
        Parameters:
        array - The code length array
      • findNodesToRelocate

        private static int findNodesToRelocate​(int[] array,
                                               int maximumLength)
        Finds the number of nodes to relocate in order to achieve a given code length limit.
        Parameters:
        array - The code length array
        maximumLength - The maximum bit length for the generated codes
        Returns:
        The number of nodes to relocate
      • allocateNodeLengths

        private static void allocateNodeLengths​(int[] array)
        A final allocation pass with no code length limit.
        Parameters:
        array - The code length array
      • allocateNodeLengthsWithRelocation

        private static void allocateNodeLengthsWithRelocation​(int[] array,
                                                              int nodesToMove,
                                                              int insertDepth)
        A final allocation pass that relocates nodes in order to achieve a maximum code length limit.
        Parameters:
        array - The code length array
        nodesToMove - The number of internal nodes to be relocated
        insertDepth - The depth at which to insert relocated nodes
      • allocateHuffmanCodeLengths

        static void allocateHuffmanCodeLengths​(int[] array,
                                               int maximumLength)
        Allocates Canonical Huffman code lengths in place based on a sorted frequency array.
        Parameters:
        array - On input, a sorted array of symbol frequencies; On output, an array of Canonical Huffman code lengths
        maximumLength - The maximum code length. Must be at least ceil(log2(array.length))