rustfst 0.3.0

Library for constructing, combining, optimizing, and searching weighted finite-state transducers (FSTs).
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

use std::collections::hash_map::Entry;
use std::collections::HashMap;
use std::collections::VecDeque;

use failure::Fallible;

use crate::arc::Arc;
use crate::fst_traits::{ExpandedFst, MutableFst};
use crate::itertools::iproduct;
use crate::semirings::Semiring;

/// This operation computes the composition of two transducers.
/// If `A` transduces string `x` to `y` with weight `a` and `B` transduces `y` to `z`
/// with weight `b`, then their composition transduces string `x` to `z` with weight `a ⊗ b`.
///
/// # Example
/// ```
/// # #[macro_use] extern crate rustfst;
/// # use failure::Fallible;
/// # use rustfst::utils::transducer;
/// # use rustfst::semirings::{Semiring, IntegerWeight};
/// # use rustfst::fst_impls::VectorFst;
/// # use rustfst::algorithms::compose;
/// # fn main() -> Fallible<()> {
/// let fst_1 : VectorFst<IntegerWeight> = fst![1,2 => 2,3];
///
/// let fst_2 : VectorFst<IntegerWeight> = fst![2,3 => 3,4];
///
/// let fst_ref : VectorFst<IntegerWeight> = fst![1,2 => 3,4];
///
/// let composed_fst : VectorFst<_> = compose(&fst_1, &fst_2)?;
/// assert_eq!(composed_fst, fst_ref);
/// # Ok(())
/// # }
/// ```
pub fn compose<W, F1, F2, F3>(fst_1: &F1, fst_2: &F2) -> Fallible<F3>
where
    W: Semiring,
    F1: ExpandedFst<W = W>,
    F2: ExpandedFst<W = W>,
    F3: MutableFst<W = W>,
{
    let mut composed_fst = F3::new();
    let mut queue = VecDeque::new();

    let mut mapping_states = HashMap::new();

    if let (Some(state_state_1), Some(start_state_2)) = (fst_1.start(), fst_2.start()) {
        let start_state = composed_fst.add_state();
        mapping_states.insert((state_state_1, start_state_2), start_state);
        composed_fst.set_start(start_state)?;
        queue.push_back((state_state_1, start_state_2, start_state));
    }

    while !queue.is_empty() {
        let (q1, q2, q) = queue.pop_front().unwrap();

        if let (Some(rho_1), Some(rho_2)) = (fst_1.final_weight(q1), fst_2.final_weight(q2)) {
            composed_fst.set_final(q, rho_1.times(&rho_2)?)?;
        }

        let arcs_it1 = fst_1.arcs_iter(q1)?;
        let arcs_it2 = fst_2.arcs_iter(q2)?;

        for (arc_1, arc_2) in iproduct!(arcs_it1, arcs_it2) {
            if arc_1.olabel == arc_2.ilabel {
                let n1 = arc_1.nextstate;
                let n2 = arc_2.nextstate;

                let q_prime = match mapping_states.entry((n1, n2)) {
                    Entry::Vacant(v) => {
                        let q_prime = composed_fst.add_state();
                        v.insert(q_prime);
                        queue.push_back((n1, n2, q_prime));
                        q_prime
                    }
                    Entry::Occupied(o) => *o.get(),
                };

                composed_fst.add_arc(
                    q,
                    Arc::new(
                        arc_1.ilabel,
                        arc_2.olabel,
                        arc_1.weight.times(&arc_2.weight)?,
                        q_prime,
                    ),
                )?;
            }
        }
    }

    Ok(composed_fst)
}