Struct DfaLearning 

pub struct DfaLearning<A>
where
    A: BlackBoxAutomaton<Output = bool>,
{
    automaton: A,
    prefixes: Vec<Vec<usize>>,
    suffixes: Vec<Vec<usize>>,
    table: Vec<BitSet>,
    row_map: HashMap<BitSet, usize>,
}

Fields

automaton: A

prefixes: Vec<Vec<usize>>

suffixes: Vec<Vec<usize>>

table: Vec<BitSet>

row_map: HashMap<BitSet, usize>

Implementations

impl<A> DfaLearning<A>

where A: BlackBoxAutomaton<Output = bool>,

pub fn new(automaton: A) -> Self

fn add_prefix(&mut self, prefix: Vec<usize>) -> usize

Examples found in repository

crates/competitive/src/algorithm/automata_learning.rs (line 320)

    pub fn new(automaton: A) -> Self {
        let mut this = Self {
            automaton,
            prefixes: vec![],
            suffixes: vec![],
            table: vec![],
            row_map: HashMap::new(),
        };
        this.add_suffix(vec![]);
        this.add_prefix(vec![]);
        this
    }
    fn add_prefix(&mut self, prefix: Vec<usize>) -> usize {
        let row: BitSet = self
            .suffixes
            .iter()
            .map(|s| {
                self.automaton
                    .behavior(prefix.iter().cloned().chain(s.iter().cloned()))
            })
            .collect();
        *self.row_map.entry(row.clone()).or_insert_with(|| {
            let idx = self.table.len();
            self.table.push(row);
            self.prefixes.push(prefix);
            idx
        })
    }
    fn add_suffix(&mut self, suffix: Vec<usize>) {
        if self.suffixes.contains(&suffix) {
            return;
        }
        for (prefix, table) in self.prefixes.iter_mut().zip(&mut self.table) {
            table.push(
                self.automaton
                    .behavior(prefix.iter().cloned().chain(suffix.iter().cloned())),
            );
        }
        self.suffixes.push(suffix);
        self.row_map.clear();
        for (i_prefix, row) in self.table.iter().enumerate() {
            self.row_map.insert(row.clone(), i_prefix);
        }
    }
    pub fn construct_dfa(&mut self) -> DeterministicFiniteAutomaton {
        let sigma = self.automaton.sigma();
        let mut dfa = DeterministicFiniteAutomaton {
            states: vec![],
            initial_state: 0,
        };
        let mut i_prefix = 0;
        while i_prefix < self.prefixes.len() {
            let mut delta = vec![];
            for x in 0..sigma {
                let prefix: Vec<usize> =
                    self.prefixes[i_prefix].iter().cloned().chain([x]).collect();
                let index = self.add_prefix(prefix);
                delta.push(index);
            }
            dfa.states.push(DfaState {
                delta,
                accept: self.table[i_prefix].get(0),
            });
            i_prefix += 1;
        }
        dfa
    }
    pub fn train_sample(&mut self, dfa: &DeterministicFiniteAutomaton, sample: &[usize]) -> bool {
        let expected = self.automaton.behavior(sample.iter().cloned());
        if expected == dfa.behavior(sample.iter().cloned()) {
            return false;
        }
        let n = sample.len();
        let mut states: Vec<(usize, usize)> = Vec::with_capacity(n + 1);
        let mut s = 0usize;
        states.push((s, 0));
        for (k, &x) in sample.iter().enumerate() {
            s = dfa.states[s].delta[x];
            states.push((s, k + 1));
        }
        let split = states.partition_point(|&(state, k)| {
            self.automaton.behavior(
                self.prefixes[state]
                    .iter()
                    .cloned()
                    .chain(sample[k..].iter().cloned()),
            ) == expected
        });
        let new_prefix = sample[..split].to_vec();
        let new_suffix = sample[split..].to_vec();
        self.add_suffix(new_suffix);
        self.add_prefix(new_prefix);
        true
    }

fn add_suffix(&mut self, suffix: Vec<usize>)

Examples found in repository

crates/competitive/src/algorithm/automata_learning.rs (line 319)

    pub fn new(automaton: A) -> Self {
        let mut this = Self {
            automaton,
            prefixes: vec![],
            suffixes: vec![],
            table: vec![],
            row_map: HashMap::new(),
        };
        this.add_suffix(vec![]);
        this.add_prefix(vec![]);
        this
    }
    fn add_prefix(&mut self, prefix: Vec<usize>) -> usize {
        let row: BitSet = self
            .suffixes
            .iter()
            .map(|s| {
                self.automaton
                    .behavior(prefix.iter().cloned().chain(s.iter().cloned()))
            })
            .collect();
        *self.row_map.entry(row.clone()).or_insert_with(|| {
            let idx = self.table.len();
            self.table.push(row);
            self.prefixes.push(prefix);
            idx
        })
    }
    fn add_suffix(&mut self, suffix: Vec<usize>) {
        if self.suffixes.contains(&suffix) {
            return;
        }
        for (prefix, table) in self.prefixes.iter_mut().zip(&mut self.table) {
            table.push(
                self.automaton
                    .behavior(prefix.iter().cloned().chain(suffix.iter().cloned())),
            );
        }
        self.suffixes.push(suffix);
        self.row_map.clear();
        for (i_prefix, row) in self.table.iter().enumerate() {
            self.row_map.insert(row.clone(), i_prefix);
        }
    }
    pub fn construct_dfa(&mut self) -> DeterministicFiniteAutomaton {
        let sigma = self.automaton.sigma();
        let mut dfa = DeterministicFiniteAutomaton {
            states: vec![],
            initial_state: 0,
        };
        let mut i_prefix = 0;
        while i_prefix < self.prefixes.len() {
            let mut delta = vec![];
            for x in 0..sigma {
                let prefix: Vec<usize> =
                    self.prefixes[i_prefix].iter().cloned().chain([x]).collect();
                let index = self.add_prefix(prefix);
                delta.push(index);
            }
            dfa.states.push(DfaState {
                delta,
                accept: self.table[i_prefix].get(0),
            });
            i_prefix += 1;
        }
        dfa
    }
    pub fn train_sample(&mut self, dfa: &DeterministicFiniteAutomaton, sample: &[usize]) -> bool {
        let expected = self.automaton.behavior(sample.iter().cloned());
        if expected == dfa.behavior(sample.iter().cloned()) {
            return false;
        }
        let n = sample.len();
        let mut states: Vec<(usize, usize)> = Vec::with_capacity(n + 1);
        let mut s = 0usize;
        states.push((s, 0));
        for (k, &x) in sample.iter().enumerate() {
            s = dfa.states[s].delta[x];
            states.push((s, k + 1));
        }
        let split = states.partition_point(|&(state, k)| {
            self.automaton.behavior(
                self.prefixes[state]
                    .iter()
                    .cloned()
                    .chain(sample[k..].iter().cloned()),
            ) == expected
        });
        let new_prefix = sample[..split].to_vec();
        let new_suffix = sample[split..].to_vec();
        self.add_suffix(new_suffix);
        self.add_prefix(new_prefix);
        true
    }

pub fn construct_dfa(&mut self) -> DeterministicFiniteAutomaton

Examples found in repository

crates/competitive/src/algorithm/automata_learning.rs (line 409)

    pub fn train(
        &mut self,
        samples: impl IntoIterator<Item = Vec<usize>>,
    ) -> DeterministicFiniteAutomaton {
        let mut dfa = self.construct_dfa();
        for sample in samples {
            if self.train_sample(&dfa, &sample) {
                dfa = self.construct_dfa();
            }
        }
        dfa
    }

pub fn train_sample( &mut self, dfa: &DeterministicFiniteAutomaton, sample: &[usize], ) -> bool

Examples found in repository

crates/competitive/src/algorithm/automata_learning.rs (line 411)

    pub fn train(
        &mut self,
        samples: impl IntoIterator<Item = Vec<usize>>,
    ) -> DeterministicFiniteAutomaton {
        let mut dfa = self.construct_dfa();
        for sample in samples {
            if self.train_sample(&dfa, &sample) {
                dfa = self.construct_dfa();
            }
        }
        dfa
    }

pub fn train( &mut self, samples: impl IntoIterator<Item = Vec<usize>>, ) -> DeterministicFiniteAutomaton

Trait Implementations

impl<A> Clone for DfaLearning<A>

where A: BlackBoxAutomaton<Output = bool> + Clone,

fn clone(&self) -> DfaLearning<A>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<A> Debug for DfaLearning<A>

where A: BlackBoxAutomaton<Output = bool> + Debug,

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

Formats the value using the given formatter.