Hufint

De Lillois Fractale Wiki
Aller à la navigation Aller à la recherche

Purpose

A Hufint is a variable-length-coded integer, with an optimal compression perspective.

Hufint stands for Huffman integer, or Huffman coded integer.

The contract of this coding tool is:

  • allow to encode any positive integer (including 0) a a set of bits
  • allow a non-ambiguous decoding algorithm
  • use less bits for smaller integer
  • allow non-ambiguous encoding/decoding for arrays of integers.

Hufint are used in the Matscape projects, wherever

  • integer values are likely to be small (example: number of child)
  • integer values are allowed to be large (but rather seldom)
  • integer statistical distribution is roughly an exponential decrease
  • encoding size is critical
  • speed for math operations on the values is not critical

Hufint base

The Hufint base is the slice size for the Hufint bitset representation.

Matscape uses Hufint-6 representations (Hufint base = 6), where

  • numbers from 0 to 2^5-1 (31) are represented on 6 bits
  • numbers from 2^5 (32) to 2^10-1 (1023) are represented on 12 bits
  • numbers from 2^10 (1024) to 2^15-1 (1023) are represented on 18 bits
  • etc...

Algorithm

The algorithm is rather starightforward but not documented here.

At least two public functions (in a java lib) are defined:

int f(BitSet) /* conversion of bitSet into a positive integer - decoding */

BitSet f(int) /* conversion of a positive integer into bitSet - encoding */ 

Similar functions are available for arrays of integers.
Various other convenience functions aredefined for reporting and checking.