Train a symbol table from a set of input strings. Uses iterative count-based selection: in each round, count how many bytes each candidate n-gram would save, pick the best, repeat.
(strings: &[&[u8]])
| 57 | /// Uses iterative count-based selection: in each round, count how many |
| 58 | /// bytes each candidate n-gram would save, pick the best, repeat. |
| 59 | fn train(strings: &[&[u8]]) -> Self { |
| 60 | if strings.is_empty() { |
| 61 | return Self { |
| 62 | symbols: Vec::new(), |
| 63 | }; |
| 64 | } |
| 65 | |
| 66 | let mut symbols: Vec<Vec<u8>> = Vec::new(); |
| 67 | let mut symbol_set: std::collections::HashSet<Vec<u8>> = std::collections::HashSet::new(); |
| 68 | let mut candidates: std::collections::HashMap<Vec<u8>, usize> = |
| 69 | std::collections::HashMap::new(); |
| 70 | |
| 71 | for _round in 0..TRAINING_ROUNDS { |
| 72 | // Count n-gram frequencies in the data (after encoding with current table). |
| 73 | candidates.clear(); |
| 74 | |
| 75 | for s in strings { |
| 76 | // Scan for n-grams of length 1-8 that are NOT already covered by symbols. |
| 77 | let mut pos = 0; |
| 78 | while pos < s.len() { |
| 79 | // Check if current position starts with a known symbol. |
| 80 | let existing_match = longest_symbol_match(&symbols, s, pos); |
| 81 | |
| 82 | if existing_match > 0 { |
| 83 | pos += existing_match; |
| 84 | continue; |
| 85 | } |
| 86 | |
| 87 | // No existing symbol matches — count new n-gram candidates. |
| 88 | for len in 1..=MAX_SYMBOL_LEN.min(s.len() - pos) { |
| 89 | let ngram = &s[pos..pos + len]; |
| 90 | *candidates.entry(ngram.to_vec()).or_insert(0) += 1; |
| 91 | } |
| 92 | pos += 1; |
| 93 | } |
| 94 | } |
| 95 | |
| 96 | if candidates.is_empty() { |
| 97 | break; |
| 98 | } |
| 99 | |
| 100 | // Score candidates by compression gain: frequency * (length - 1). |
| 101 | // Each symbol saves (length - 1) bytes per occurrence (1 byte for |
| 102 | // the symbol index vs `length` bytes raw). |
| 103 | let mut scored: Vec<(Vec<u8>, usize)> = candidates |
| 104 | .drain() |
| 105 | .map(|(ngram, freq)| { |
| 106 | let gain = freq * (ngram.len().saturating_sub(1)); |
| 107 | (ngram, gain) |
| 108 | }) |
| 109 | .filter(|(_, gain)| *gain > 0) |
| 110 | .collect(); |
| 111 | |
| 112 | scored.sort_by_key(|a| std::cmp::Reverse(a.1)); |
| 113 | |
| 114 | // Add top candidates that don't duplicate existing symbols. |
| 115 | for (ngram, _) in scored { |
| 116 | if symbols.len() >= MAX_SYMBOLS { |