use rayon::prelude::*;
use rustc_hash::FxHashMap;
#[derive(Clone, Copy)]
pub struct NextLocationConfig {
pub order: usize,
pub backoff: bool,
}
impl NextLocationConfig {
pub fn new(order: usize, backoff: bool) -> Self {
NextLocationConfig { order, backoff }
}
}
#[derive(Default, Clone)]
struct TrieNode {
children: Vec<(u16, u32)>,
transitions: Vec<(u16, u32)>,
}
pub struct MarkovLocationModel {
order: usize,
backoff: bool,
local_to_global: Vec<u32>,
arena: Vec<TrieNode>,
}
fn record_transition(node: &mut TrieNode, next: u16) {
for entry in node.transitions.iter_mut() {
if entry.0 == next {
entry.1 += 1;
return;
}
}
node.transitions.push((next, 1));
}
fn child_or_insert(arena: &mut Vec<TrieNode>, node_idx: u32, loc: u16) -> u32 {
if let Some(&(_, child_idx)) = arena[node_idx as usize]
.children
.iter()
.find(|&&(code, _)| code == loc)
{
return child_idx;
}
let child_idx = arena.len() as u32;
arena.push(TrieNode::default());
arena[node_idx as usize].children.push((loc, child_idx));
child_idx
}
fn fit_one_user(seq: &[u32], config: &NextLocationConfig) -> Result<MarkovLocationModel, String> {
let mut global_to_local: FxHashMap<u32, u16> = FxHashMap::default();
let mut local_to_global: Vec<u32> = Vec::new();
let mut local_seq: Vec<u16> = Vec::with_capacity(seq.len());
for &global in seq {
let local = match global_to_local.get(&global) {
Some(&code) => code,
None => {
let next_code = local_to_global.len();
if next_code > u16::MAX as usize {
return Err(format!(
"user has more than {} distinct locations, exceeding the u16 \
dense-coding limit used by the context-trie backend",
u16::MAX as usize + 1
));
}
let code = next_code as u16;
local_to_global.push(global);
global_to_local.insert(global, code);
code
}
};
local_seq.push(local);
}
let mut arena: Vec<TrieNode> = vec![TrieNode::default()];
let n = local_seq.len();
for i in 0..n {
let next = local_seq[i];
record_transition(&mut arena[0], next);
let max_steps = config.order.min(i);
let mut node_idx: u32 = 0;
for step in 1..=max_steps {
let loc = local_seq[i - step];
node_idx = child_or_insert(&mut arena, node_idx, loc);
record_transition(&mut arena[node_idx as usize], next);
}
}
Ok(MarkovLocationModel {
order: config.order,
backoff: config.backoff,
local_to_global,
arena,
})
}
pub fn markov_fit_indexed(
location_codes: &[u32],
sorted_indices: &[usize],
ends: &[usize],
config: &NextLocationConfig,
) -> Result<Vec<MarkovLocationModel>, String> {
for &idx in sorted_indices {
if idx >= location_codes.len() {
return Err("index must be within location_codes bounds".to_string());
}
}
(0..ends.len())
.into_par_iter()
.map(|i| {
let start = if i == 0 { 0 } else { ends[i - 1] };
let end = ends[i];
let seq: Vec<u32> = sorted_indices[start..end]
.iter()
.map(|&idx| location_codes[idx])
.collect();
fit_one_user(&seq, config)
})
.collect()
}
struct PredictionResult {
codes: Vec<u32>,
probs: Vec<f64>,
}
fn by_count_desc(a: &(u32, u32), b: &(u32, u32)) -> std::cmp::Ordering {
b.1.cmp(&a.1).then(a.0.cmp(&b.0))
}
fn select_top_k(items: &mut Vec<(u32, u32)>, top_k: usize) {
if items.len() > top_k {
if top_k == 0 {
items.clear();
return;
}
items.select_nth_unstable_by(top_k - 1, by_count_desc);
items.truncate(top_k);
}
items.sort_by(by_count_desc);
}
fn predict_one(model: &MarkovLocationModel, context: &[u32], top_k: usize) -> PredictionResult {
let max_k = model.order.min(context.len());
let mut node_idx: u32 = 0;
let mut reached_depth: usize = 0;
for step in 1..=max_k {
let global = context[context.len() - step];
let Some(local) = model
.local_to_global
.iter()
.position(|&code| code == global)
else {
break;
};
let local = local as u16;
let Some(&(_, child_idx)) = model.arena[node_idx as usize]
.children
.iter()
.find(|&&(code, _)| code == local)
else {
break;
};
node_idx = child_idx;
reached_depth = step;
}
if reached_depth < max_k && !model.backoff {
return PredictionResult {
codes: Vec::new(),
probs: Vec::new(),
};
}
let node = &model.arena[node_idx as usize];
if node.transitions.is_empty() {
return PredictionResult {
codes: Vec::new(),
probs: Vec::new(),
};
}
let total: u32 = node.transitions.iter().map(|&(_, count)| count).sum();
let mut items: Vec<(u32, u32)> = node
.transitions
.iter()
.map(|&(local, count)| (model.local_to_global[local as usize], count))
.collect();
select_top_k(&mut items, top_k);
PredictionResult {
codes: items.iter().map(|&(global, _)| global).collect(),
probs: items
.iter()
.map(|&(_, count)| f64::from(count) / f64::from(total))
.collect(),
}
}
pub fn markov_predict_batch(
models: &[MarkovLocationModel],
context_codes: &[u32],
context_starts: &[usize],
context_ends: &[usize],
top_k: usize,
) -> Result<(Vec<u32>, Vec<f64>, Vec<usize>, Vec<usize>), String> {
if models.len() != context_starts.len() || models.len() != context_ends.len() {
return Err(
"models, context_starts, and context_ends must have the same length".to_string(),
);
}
let n_users = models.len();
let mut out_codes = Vec::new();
let mut out_probs = Vec::new();
let mut out_starts = Vec::with_capacity(n_users);
let mut out_ends = Vec::with_capacity(n_users);
for i in 0..n_users {
let start = context_starts[i];
let end = context_ends[i];
if start > end || end > context_codes.len() {
return Err(
"context_starts/context_ends must be within context_codes bounds".to_string(),
);
}
let context = &context_codes[start..end];
let result = predict_one(&models[i], context, top_k);
out_starts.push(out_codes.len());
out_codes.extend(result.codes);
out_probs.extend(result.probs);
out_ends.push(out_codes.len());
}
Ok((out_codes, out_probs, out_starts, out_ends))
}
#[cfg(test)]
mod tests {
use super::*;
fn fit(seq: &[u32], config: &NextLocationConfig) -> MarkovLocationModel {
fit_one_user(seq, config).expect("test sequences never exceed the u16 dense-coding limit")
}
#[test]
fn order_1_predicts_deterministic_cycle_perfectly() {
let seq: Vec<u32> = (0..12).map(|i| i % 3).collect();
let config = NextLocationConfig::new(1, true);
let model = fit(&seq, &config);
let pred = predict_one(&model, &[0], 1);
assert_eq!(pred.codes, vec![1]);
assert_eq!(pred.probs, vec![1.0]);
let pred = predict_one(&model, &[1], 1);
assert_eq!(pred.codes, vec![2]);
let pred = predict_one(&model, &[2], 1);
assert_eq!(pred.codes, vec![0]);
}
#[test]
fn order_0_is_most_frequent_location_baseline() {
let seq = vec![5u32, 5, 5, 7, 9];
let config = NextLocationConfig::new(0, true);
let model = fit(&seq, &config);
let pred = predict_one(&model, &[], 1);
assert_eq!(pred.codes, vec![5]);
}
#[test]
fn backoff_falls_back_to_lower_order_on_unseen_context() {
let seq = vec![1u32, 2, 1, 2, 1, 2, 3];
let config = NextLocationConfig::new(2, true);
let model = fit(&seq, &config);
let pred = predict_one(&model, &[9, 9], 1);
assert!(!pred.codes.is_empty());
}
#[test]
fn no_backoff_returns_empty_on_unseen_context() {
let seq = vec![1u32, 2, 1, 2];
let config = NextLocationConfig::new(2, false);
let model = fit(&seq, &config);
let pred = predict_one(&model, &[9, 9], 1);
assert!(pred.codes.is_empty());
}
#[test]
fn top_k_returns_multiple_candidates_sorted_by_count_desc() {
let seq = vec![0u32, 1, 0, 2, 0, 1, 0, 1];
let config = NextLocationConfig::new(1, true);
let model = fit(&seq, &config);
let pred = predict_one(&model, &[0], 2);
assert_eq!(pred.codes, vec![1, 2]);
assert!(pred.probs[0] > pred.probs[1]);
}
#[test]
fn no_backoff_still_predicts_when_full_order_context_is_known() {
let seq = vec![1u32, 2, 3, 1, 2, 3, 1, 2, 3];
let config = NextLocationConfig::new(2, false);
let model = fit(&seq, &config);
let pred = predict_one(&model, &[1, 2], 1);
assert_eq!(pred.codes, vec![3]);
}
#[test]
fn partially_known_context_backs_off_by_one_level_not_to_zero() {
let seq = vec![1u32, 2, 1, 2, 1, 2, 1, 9];
let config = NextLocationConfig::new(2, true);
let model = fit(&seq, &config);
let pred = predict_one(&model, &[42, 1], 1);
assert_eq!(pred.codes, vec![2]);
}
#[test]
fn user_local_dense_coding_handles_non_contiguous_global_codes() {
let seq = vec![900_001u32, 42, 900_001, 42, 900_001, 7];
let config = NextLocationConfig::new(1, true);
let model = fit(&seq, &config);
let pred = predict_one(&model, &[900_001], 1);
assert_eq!(pred.codes, vec![42]);
}
fn naive_fit(seq: &[u32], order: usize) -> Vec<FxHashMap<Vec<u32>, FxHashMap<u32, u32>>> {
let mut tables: Vec<FxHashMap<Vec<u32>, FxHashMap<u32, u32>>> =
(0..=order).map(|_| FxHashMap::default()).collect();
let n = seq.len();
for (k, table) in tables.iter_mut().enumerate() {
for i in k..n {
let context = seq[i - k..i].to_vec();
*table.entry(context).or_default().entry(seq[i]).or_insert(0) += 1;
}
}
tables
}
fn naive_predict_set(
tables: &[FxHashMap<Vec<u32>, FxHashMap<u32, u32>>],
context: &[u32],
order: usize,
backoff: bool,
) -> Option<FxHashMap<u32, u32>> {
let max_k = order.min(context.len());
let mut k = max_k;
loop {
let ctx_key: Vec<u32> = if k == 0 {
Vec::new()
} else {
context[context.len() - k..].to_vec()
};
if let Some(next_counts) = tables[k].get(&ctx_key)
&& !next_counts.is_empty()
{
return Some(next_counts.clone());
}
if k == 0 || !backoff {
return None;
}
k -= 1;
}
}
struct Lcg(u64);
impl Lcg {
fn next(&mut self) -> u64 {
self.0 = self.0.wrapping_mul(6364136223846793005).wrapping_add(1);
self.0 >> 33
}
fn range(&mut self, n: u64) -> u64 {
self.next() % n
}
}
#[test]
fn differential_matches_naive_nested_hashmap_reference() {
let mut rng = Lcg(0x5EED_u64);
for trial in 0..200 {
let seq_len = 1 + (rng.range(40) as usize);
let vocab = 1 + (rng.range(6) as usize); let order = (rng.range(4)) as usize; let backoff = rng.range(2) == 0;
let top_k = 1 + (rng.range(3) as usize);
let seq: Vec<u32> = (0..seq_len)
.map(|_| (1_000_000 + rng.range(vocab as u64)) as u32) .collect();
let config = NextLocationConfig::new(order, backoff);
let trie_model = fit(&seq, &config);
let naive_tables = naive_fit(&seq, order);
let mut contexts: Vec<Vec<u32>> =
(0..=seq_len).map(|i| seq[seq_len - i..].to_vec()).collect();
contexts.push(vec![999_999_999u32, 999_999_998u32]);
for context in contexts {
let trie_pred = predict_one(&trie_model, &context, top_k);
let naive_set = naive_predict_set(&naive_tables, &context, order, backoff);
match naive_set {
None => {
assert!(
trie_pred.codes.is_empty(),
"trial {trial}: naive found nothing but trie predicted {:?} \
(seq={seq:?}, order={order}, backoff={backoff}, context={context:?})",
trie_pred.codes
);
}
Some(expected_counts) => {
assert!(
!trie_pred.codes.is_empty(),
"trial {trial}: naive found {expected_counts:?} but trie predicted \
nothing (seq={seq:?}, order={order}, backoff={backoff}, \
context={context:?})"
);
let total: u32 = expected_counts.values().sum();
let mut expected_sorted: Vec<(u32, u32)> =
expected_counts.iter().map(|(&c, &n)| (c, n)).collect();
expected_sorted.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(&b.0)));
expected_sorted.truncate(top_k);
assert_eq!(
trie_pred.codes,
expected_sorted.iter().map(|&(c, _)| c).collect::<Vec<_>>(),
"trial {trial}: top-k code mismatch (seq={seq:?}, order={order}, \
backoff={backoff}, context={context:?})"
);
let expected_probs: Vec<f64> = expected_sorted
.iter()
.map(|&(_, n)| f64::from(n) / f64::from(total))
.collect();
for (got, want) in trie_pred.probs.iter().zip(expected_probs.iter()) {
assert!(
(got - want).abs() < 1e-12,
"trial {trial}: prob mismatch {got} vs {want} \
(seq={seq:?}, order={order}, backoff={backoff}, \
context={context:?})"
);
}
}
}
}
}
}
}