velesdb_core/compression/
dictionary.rs

1//! Dictionary Encoding for column compression.
2//!
3//! Replaces repeated values with compact integer codes.
4//! Ideal for columns with low cardinality (e.g., country, category).
5
6#![allow(clippy::cast_possible_truncation)]
7#![allow(clippy::cast_precision_loss)]
8
9use rustc_hash::FxHashMap;
10use std::hash::Hash;
11use std::mem::size_of;
12
13/// Compression statistics.
14#[derive(Debug, Clone, Default)]
15pub struct CompressionStats {
16    /// Number of unique values in dictionary.
17    pub unique_values: usize,
18    /// Total number of encoded values.
19    pub total_values: usize,
20    /// Dictionary size in bytes.
21    pub dictionary_size_bytes: usize,
22    /// Encoded data size in bytes.
23    pub encoded_size_bytes: usize,
24    /// Compression ratio (original / compressed).
25    pub compression_ratio: f64,
26}
27
28/// Dictionary codebook mapping values to codes.
29#[derive(Debug, Clone)]
30pub struct DictCodebook<V> {
31    /// Value to code mapping.
32    value_to_code: FxHashMap<V, u32>,
33    /// Code to value mapping.
34    code_to_value: Vec<V>,
35}
36
37impl<V: Hash + Eq + Clone> Default for DictCodebook<V> {
38    fn default() -> Self {
39        Self {
40            value_to_code: FxHashMap::default(),
41            code_to_value: Vec::new(),
42        }
43    }
44}
45
46/// Dictionary encoder for column compression.
47///
48/// Encodes values as compact integer codes using a codebook.
49#[derive(Debug, Clone)]
50pub struct DictionaryEncoder<V: Hash + Eq + Clone> {
51    /// The codebook.
52    codebook: DictCodebook<V>,
53    /// Number of values encoded (including duplicates).
54    total_encoded: usize,
55}
56
57impl<V: Hash + Eq + Clone> DictionaryEncoder<V> {
58    /// Create a new dictionary encoder.
59    #[must_use]
60    pub fn new() -> Self {
61        Self {
62            codebook: DictCodebook::default(),
63            total_encoded: 0,
64        }
65    }
66
67    /// Check if the dictionary is empty.
68    #[must_use]
69    pub fn is_empty(&self) -> bool {
70        self.codebook.code_to_value.is_empty()
71    }
72
73    /// Get the number of unique values in the dictionary.
74    #[must_use]
75    pub fn len(&self) -> usize {
76        self.codebook.code_to_value.len()
77    }
78
79    /// Encode a single value, returning its code.
80    ///
81    /// If the value is new, it's added to the dictionary.
82    pub fn encode(&mut self, value: V) -> u32 {
83        self.total_encoded += 1;
84
85        if let Some(&code) = self.codebook.value_to_code.get(&value) {
86            return code;
87        }
88
89        // Reason: Dictionary size is bounded by available memory; u32::MAX codes is ~4B entries
90        // which would require terabytes of RAM. Saturate to prevent panic in extreme edge cases.
91        let code = u32::try_from(self.codebook.code_to_value.len()).unwrap_or(u32::MAX);
92        self.codebook.value_to_code.insert(value.clone(), code);
93        self.codebook.code_to_value.push(value);
94        code
95    }
96
97    /// Decode a code back to its value.
98    #[must_use]
99    pub fn decode(&self, code: u32) -> Option<&V> {
100        self.codebook.code_to_value.get(code as usize)
101    }
102
103    /// Encode a batch of values.
104    pub fn encode_batch(&mut self, values: &[V]) -> Vec<u32> {
105        values.iter().map(|v| self.encode(v.clone())).collect()
106    }
107
108    /// Decode a batch of codes.
109    #[must_use]
110    pub fn decode_batch(&self, codes: &[u32]) -> Vec<V> {
111        codes
112            .iter()
113            .filter_map(|&code| self.decode(code).cloned())
114            .collect()
115    }
116
117    /// Clear the encoder.
118    pub fn clear(&mut self) {
119        self.codebook.value_to_code.clear();
120        self.codebook.code_to_value.clear();
121        self.total_encoded = 0;
122    }
123
124    /// Get compression statistics.
125    #[must_use]
126    pub fn stats(&self) -> CompressionStats {
127        let unique = self.len();
128        let total = self.total_encoded;
129
130        // Estimate sizes
131        let value_size = size_of::<V>();
132        let original_size = total * value_size;
133        let dict_size = unique * value_size + unique * 4; // value + code
134        let encoded_size = total * 4; // u32 codes
135        let compressed_size = dict_size + encoded_size;
136
137        let ratio = if compressed_size > 0 {
138            original_size as f64 / compressed_size as f64
139        } else {
140            0.0
141        };
142
143        CompressionStats {
144            unique_values: unique,
145            total_values: total,
146            dictionary_size_bytes: dict_size,
147            encoded_size_bytes: encoded_size,
148            compression_ratio: ratio,
149        }
150    }
151
152    /// Get the codebook.
153    #[must_use]
154    pub fn codebook(&self) -> &DictCodebook<V> {
155        &self.codebook
156    }
157}
158
159impl<V: Hash + Eq + Clone> Default for DictionaryEncoder<V> {
160    fn default() -> Self {
161        Self::new()
162    }
163}
velesdb_core/compression/dictionary.rs

velesdb_core/compression/
dictionary.rs
