ghost/libentcode/bitree.h

   1 /*Implements Binary Indexed Trees for cumulative probability tables, based
   2    upon a combination of the techniques described in \cite{Fen93,Fen95,Mof99}.
   3   This is a really, amazingly elegant data structure, that maintains
   4    cumulative frequency tables in logarithmic time, using exactly the same
   5    space as an ordinary frequency table.
   6   In addition, the non-cumulative frequency can be retrieved in constant
   7    amortized time (under 2 memory references per symbol on average).
   8
   9   We are dealing primarily with relatively small alphabets and are not sorting
  10    symbols by frequency, and so we adopt Fenwick's tree organization strategy.
  11   It's complexity has better constant factors, and although it is logarithmic
  12    in n (the alphabet size) instead of s (the index of the symbol), the latter
  13    is not expected to be appreciably smaller.
  14   We modify it however, to remove the special cases surrounding the element 0,
  15    which greatly streamlines the code.
  16   Our scheme has the added benefit that for alphabet sizes that are a power of
  17    2, the last element of the array is the total cumulative frequency count.
  18
  19   We choose Moffat's approach to halving the entire frequency table, which is
  20    over twice as fast in practice as that suggested by Fenwick, even though
  21    they have the same number of memory accesses.
  22   We also adapt Moffat's suggestion for an omnibus decode function that updates
  23    the count of the symbol being decoded while it is searching for it.
  24   We also have it retain and return the cumulative frequency count needed to
  25    update the arithmetic decoder.
  26
  27   See bitrenc.h and bitrdec.h for encoding- and decoding-specific functions.
  28
  29   @TECHREPORT{Fen93,
  30    author     ="Peter Fenwick",
  31    title      ="A new data structure for cumulative probability tables",
  32    institution="The University of Auckland, Department of Computer Science",
  33    year       =1993,
  34    number     =88,
  35    month      =May,
  36    URL        ="http://www.cs.auckland.ac.nz/~peter-f/FTPfiles/TechRep88.ps"
  37   }
  38   @TECHREPORT{Fen95,
  39    author     ="Peter Fenwick",
  40    title      ="A new data structure for cumulative probability tables: an
  41                 improved frequency to symbol algorithm",
  42    institution="The University of Auckland, Department of Computer Science",
  43    year       =1995,
  44    number     =110,
  45    month      =Feb,
  46    URL        ="http://www.cs.auckland.ac.nz/~peter-f/FTPfiles/TechRep110.ps"
  47   }
  48   @ARTICLE{Mof99,
  49     author    ="Alistair Moffat",
  50     title     ="An improved data structure for cumulative probability tables",
  51     journal   ="Software Practice and Experience",
  52     volume    =29,
  53     number    =7,
  54     pages     ="647--659",
  55     year      =1999
  56   }*/
  57 #if !defined(_bitree_H)
  58 # define _bitree_H (1)
  59
  60 /*Converts an array of frequency counts to our cumulative tree representation.
  61   _sz: The size of the table.*/
  62 void ec_bitree_from_counts(unsigned *_this,int _sz);
  63
  64 /*Converts our cumulative tree representation to an array of frequency counts.
  65   _sz:    The size of the table.
  66   _split: The largest power of two less than OR EQUAL to the table size.*/
  67 void ec_bitree_to_counts(unsigned *_this,int _sz,int _split);
  68
  69 /*Gets the cumulative frequency of the symbols less than the given one.
  70   _sym: The symbol to obtain the cumulative frequency for.
  71   Return: The sum of the frequencies of the symbols less than _sym.*/
  72 unsigned ec_bitree_get_cumul(const unsigned *_this,int _sym);
  73
  74 /*Gets the frequency of a single symbol.
  75   _sym: The symbol to obtain the frequency for.
  76   Return: The frequency of _sym.*/
  77 unsigned ec_bitree_get_freq(const unsigned *_this,int _sym);
  78
  79 /*Halves the frequency of each symbol, rounding up.
  80   _sz: The size of the table.
  81   _split: The largest power of two less than OR EQUAL to the table size.*/
  82 void ec_bitree_halve(unsigned *_this,int _sz,int _split);
  83
  84 #endif