blob: efb712c2da2e0388b5f8c1c6d2f322b030387d76 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#include "coding/simple_dense_coding.hpp"
#include "base/assert.hpp"
#include "std/algorithm.hpp"
#include "std/limits.hpp"
#if defined(__clang__)
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wunused-local-typedef"
#endif
#include <boost/range/adaptor/transformed.hpp>
#if defined(__clang__)
#pragma clang diagnostic pop
#endif
namespace coding
{
namespace
{
size_t const kAlphabetSize = static_cast<size_t>(numeric_limits<uint8_t>::max()) + 1;
// Calculates frequences for data symbols.
void CalcFrequences(vector<uint8_t> const & data, uint64_t frequency[])
{
memset(frequency, 0, sizeof(*frequency) * kAlphabetSize);
for (uint8_t symbol : data)
++frequency[symbol];
}
} // namespace
SimpleDenseCoding::SimpleDenseCoding(vector<uint8_t> const & data)
{
// This static initialization isn't thread safe prior to C++11.
uint64_t frequency[kAlphabetSize]; // Maps symbols to frequences.
CalcFrequences(data, frequency);
uint8_t symbols[kAlphabetSize]; // Maps ranks to symbols.
uint8_t rank[kAlphabetSize]; // Maps symbols to ranks.
for (size_t i = 0; i < kAlphabetSize; ++i)
symbols[i] = i;
auto frequencyCmp = [&frequency](uint8_t lsym, uint8_t rsym)
{
return frequency[lsym] > frequency[rsym];
};
sort(symbols, symbols + kAlphabetSize, frequencyCmp);
for (size_t r = 0; r < kAlphabetSize; ++r)
rank[symbols[r]] = r;
auto getRank = [&rank](uint8_t sym)
{
return rank[sym];
};
using namespace boost::adaptors;
succinct::elias_fano_compressed_list(data | transformed(getRank)).swap(m_ranks);
m_symbols.assign(symbols);
}
SimpleDenseCoding::SimpleDenseCoding(SimpleDenseCoding && rhs)
{
m_ranks.swap(rhs.m_ranks);
m_symbols.swap(rhs.m_symbols);
}
uint8_t SimpleDenseCoding::Get(uint64_t i) const
{
ASSERT_LESS(i, Size(), ());
return m_symbols[m_ranks[i]];
}
} // namespace coding
|
