Struct ContextTree 

pub struct ContextTree {
    pub max_order: usize,
    /* private fields */
}

Context tree for storing variable-order Markov chain contexts

Uses trie-based storage for memory efficiency through prefix sharing

Fields

max_order: usize

Maximum context order (length)

Implementations

impl ContextTree

pub fn new(max_order: usize) -> AnomalyGridResult<Self>

Create a new context tree with specified maximum order

pub fn with_interner( max_order: usize, interner: Arc<StringInterner>, ) -> AnomalyGridResult<Self>

Create a new context tree with existing string interner

pub fn build_from_sequence( &mut self, sequence: &[String], config: &AnomalyGridConfig, ) -> AnomalyGridResult<()>

Build the context tree from a training sequence

Complexity

• Time: O(n × max_order × |alphabet|) where n = sequence length
• Space: O(|alphabet|^max_order) in worst case

Performance Guarantees

• Memory usage is bounded by config.memory_limit if set
• Processing time scales linearly with sequence length
• Uses string interning to reduce memory duplication

pub fn get_transition_probability( &self, context: &[String], next_state: &str, ) -> Option<f64>

Get the transition probability for a given context and next state

pub fn get_transition_probability_with_config( &self, context: &[String], next_state: &str, config: &AnomalyGridConfig, ) -> Option<f64>

Get the transition probability with custom config

pub fn get_transition_probability_normalized( &self, context: &[String], next_state: &str, config: &AnomalyGridConfig, global_state_mapping: &HashMap<String, usize>, ) -> Option<f64>

Get the transition probability with proper normalization using global vocabulary

pub fn get_context_node(&self, context: &[String]) -> Option<&ContextNode>

Get a context node for the given context

pub fn get_context_count(&self, context: &[String]) -> Option<usize>

Get the total count for a given context (for adaptive context selection)

pub fn get_contexts_of_order(&self, order: usize) -> Vec<Vec<String>>

Get all contexts of a specific order

pub fn context_count(&self) -> usize

Get the number of contexts stored

pub fn interner(&self) -> &Arc<StringInterner>

Get access to the string interner

pub fn contexts(&self) -> HashMap<Vec<String>, ContextNode>

Get all contexts as a HashMap for compatibility with existing code

Note: This creates a temporary HashMap and should be used sparingly for compatibility with existing tests and code that expects the old interface

impl ContextTree

Context pruning for memory optimization

pub fn prune_low_frequency_contexts(&mut self, _min_count: usize) -> usize

Remove contexts with low frequency counts

This removes contexts that have been observed fewer than min_count times, which can significantly reduce memory usage for large alphabets.

Note: Currently disabled for trie-based storage - will be reimplemented

pub fn prune_low_entropy_contexts(&mut self, _min_entropy: f64) -> usize

Remove contexts with low entropy (deterministic contexts)

This removes contexts where the entropy is below the threshold, indicating highly predictable transitions.

Note: Currently disabled for trie-based storage - will be reimplemented

pub fn limit_context_count(&mut self, _max_contexts: usize) -> usize

Keep only the most frequent contexts up to a maximum count

This is useful for memory-constrained environments where you want to keep only the most important contexts.

Note: Currently disabled for trie-based storage - will be reimplemented

pub fn estimate_memory_usage(&self) -> usize

Estimate memory usage of the context tree

This provides an estimate of the total memory used by the context tree, including the trie structure, context nodes, and transition counts.

pub fn get_context_statistics(&self) -> ContextStatistics

Get context statistics for analysis

Returns detailed statistics about the context tree structure, including distribution by order and memory usage patterns.

Trait Implementations

impl Clone for ContextTree

fn clone(&self) -> ContextTree

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for ContextTree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.