FST  openfst-1.7.2
OpenFst Library
elias.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Compresses and decompresses unweighted FSTs.
5 
6 #ifndef FST_EXTENSIONS_COMPRESS_ELIAS_H_
7 #define FST_EXTENSIONS_COMPRESS_ELIAS_H_
8 
9 #include <stack>
10 #include <vector>
11 
12 #include <fst/compat.h>
13 namespace fst {
14 
15 template <class Var>
16 class Elias {
17  public:
18  // Gamma encoding is a subroutine for Delta encoding
19  static void GammaEncode(const Var &input, std::vector<bool> *code);
20 
21  // Elias Delta encoding for a single integer
22  static void DeltaEncode(const Var &input, std::vector<bool> *code);
23 
24  // Batch decoding of a set of integers
25  static void BatchDecode(const std::vector<bool> &input,
26  std::vector<Var> *output);
27 };
28 
29 template <class Var>
30 void Elias<Var>::GammaEncode(const Var &input, std::vector<bool> *code) {
31  Var input_copy = input;
32  std::stack<bool> reverse_code;
33  while (input_copy > 0) {
34  reverse_code.push(input_copy % 2);
35  input_copy = input_copy / 2;
36  }
37  for (Var auxvar = 0; auxvar < reverse_code.size() - 1; auxvar++)
38  code->push_back(0);
39  while (reverse_code.empty() != 1) {
40  code->push_back(reverse_code.top());
41  reverse_code.pop();
42  }
43 }
44 template <class Var>
45 void Elias<Var>::DeltaEncode(const Var &input, std::vector<bool> *code) {
46  Var input_copy = input + 1;
47  std::stack<bool> reverse_remainder;
48  Var auxvar = 0;
49  while (input_copy != 0) {
50  reverse_remainder.push(input_copy % 2);
51  input_copy = input_copy / 2;
52  auxvar = auxvar + 1;
53  }
54  GammaEncode(auxvar, code);
55  reverse_remainder.pop();
56  while (reverse_remainder.empty() != 1) {
57  code->push_back(reverse_remainder.top());
58  reverse_remainder.pop();
59  }
60 }
61 
62 template <class Var>
63 void Elias<Var>::BatchDecode(const std::vector<bool> &input,
64  std::vector<Var> *output) {
65  Var lead_zeros = 0;
66  Var remainder_bits = 0;
67  Var current_word = 1;
68  Var value = 1;
69  std::vector<bool>::const_iterator it = input.begin();
70  while (it != input.end()) {
71  lead_zeros = 0;
72  remainder_bits = 0;
73  current_word = 1;
74  value = 1;
75  while (*it != 1) {
76  it++;
77  lead_zeros++;
78  }
79  it++;
80  while (lead_zeros > 0) {
81  lead_zeros--;
82  current_word = 2 * current_word + *it;
83  it++;
84  }
85  current_word--;
86  while (current_word > 0) {
87  value = 2 * value + *it;
88  current_word--;
89  it++;
90  }
91  output->push_back(value - 1);
92  }
93 }
94 
95 } // namespace fst
96 
97 #endif // FST_EXTENSIONS_COMPRESS_ELIAS_H_
static void GammaEncode(const Var &input, std::vector< bool > *code)
Definition: elias.h:30
static void BatchDecode(const std::vector< bool > &input, std::vector< Var > *output)
Definition: elias.h:63
static void DeltaEncode(const Var &input, std::vector< bool > *code)
Definition: elias.h:45