Struct ContextTree 

pub struct ContextTree {
    pub contexts: HashMap<Vec<String>, ContextNode>,
    pub max_order: usize,
}

Context tree for storing variable-order Markov chain contexts

Fields

contexts: HashMap<Vec<String>, ContextNode>

Map from context sequences to context nodes

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 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

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_context_node(&self, context: &[String]) -> Option<&ContextNode>

Get a context node for the given context

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

impl ContextTree

Context pruning for memory optimization

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

Remove low-frequency contexts to reduce memory usage

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

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

Remove contexts with low entropy (deterministic contexts)

Contexts with very low entropy provide little information and can be pruned to reduce memory usage while maintaining detection accuracy.

pub fn keep_top_contexts(&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.

pub fn estimate_memory_usage(&self) -> usize

Estimate memory usage of the context tree

pub fn get_context_statistics(&self) -> ContextStatistics

Get context statistics for analysis

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.