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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

use failure::Fallible;

use crate::arc::Arc;
use crate::fst_traits::{ExpandedFst, FinalStatesIterator, MutableFst};
use crate::semirings::Semiring;
use crate::EPS_LABEL;

/// Performs the concatenation of two wFSTs. If `A` transduces string `x` to `y` with weight `a`
/// and `B` transduces string `w` to `v` with weight `b`, then their concatenation
/// transduces string `xw` to `yv` with weight `a ⊗ b`.
///
/// # Example
/// ```
/// # #[macro_use] extern crate rustfst;
/// # use rustfst::utils::transducer;
/// # use rustfst::semirings::{Semiring, IntegerWeight};
/// # use rustfst::fst_impls::VectorFst;
/// # use rustfst::fst_traits::PathsIterator;
/// # use rustfst::FstPath;
/// # use rustfst::algorithms::concat;
/// # use failure::Fallible;
/// # use std::collections::HashSet;
/// # fn main() -> Fallible<()> {
/// let fst_a : VectorFst<IntegerWeight> = fst![2 => 3];
/// let fst_b : VectorFst<IntegerWeight> = fst![6 => 5];
///
/// let fst_res : VectorFst<IntegerWeight> = concat(&fst_a, &fst_b)?;
/// let paths : HashSet<_> = fst_res.paths_iter().collect();
///
/// let mut paths_ref = HashSet::<FstPath<IntegerWeight>>::new();
/// paths_ref.insert(fst_path![2,6 => 3,5]);
///
/// assert_eq!(paths, paths_ref);
/// # Ok(())
/// # }
/// ```
pub fn concat<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 fst_out = F3::new();

    let mapping_states_fst_1 = fst_out.add_fst(fst_1)?;
    let mapping_states_fst_2 = fst_out.add_fst(fst_2)?;

    // Start state is the start state of the first fst
    if let Some(old_start_state) = fst_1.start() {
        fst_out.set_start(mapping_states_fst_1[&old_start_state])?;
    }

    // Final states of the first fst are connected to the start state of the second fst with an
    // epsilon transition
    if let Some(old_start_state_2) = fst_2.start() {
        let start_state_2 = &mapping_states_fst_2[&old_start_state_2];
        for old_final_state_1 in fst_1.final_states_iter() {
            let final_state_1 = mapping_states_fst_1[&old_final_state_1.state_id];
            fst_out.add_arc(
                final_state_1,
                Arc::new(
                    EPS_LABEL,
                    EPS_LABEL,
                    old_final_state_1.final_weight,
                    *start_state_2,
                ),
            )?;
        }
    }

    // Final states are final states of the second fst
    for old_final_state in fst_2.final_states_iter() {
        let final_state = mapping_states_fst_2[&old_final_state.state_id];
        fst_out.set_final(final_state, old_final_state.final_weight)?;
    }

    // FINISH

    Ok(fst_out)
}

#[cfg(test)]
mod tests {
    use super::*;
    use counter::Counter;
    use failure::format_err;
    use failure::ResultExt;
    use itertools::Itertools;

    use crate::fst_impls::VectorFst;
    use crate::fst_traits::PathsIterator;
    use crate::semirings::IntegerWeight;
    use crate::test_data::vector_fst::get_vector_fsts_for_tests;

    #[test]
    fn test_concat_generic() -> Fallible<()> {
        for data in get_vector_fsts_for_tests().combinations(2) {
            let fst_1 = &data[0].fst;
            let fst_2 = &data[1].fst;

            let mut paths_ref = Counter::new();
            for path_fst_1 in fst_1.paths_iter() {
                for path_fst_2 in fst_2.paths_iter() {
                    let mut new_path = path_fst_1.clone();
                    new_path.concat(path_fst_2)?;
                    paths_ref.update(vec![new_path]);
                }
            }

            let concat_fst: VectorFst<IntegerWeight> = concat(fst_1, fst_2).with_context(|_| {
                format_err!(
                    "Error when performing concat operation of {:?} and {:?}",
                    &data[0].name,
                    &data[1].name
                )
            })?;

            let paths: Counter<_> = concat_fst.paths_iter().collect();

            assert_eq!(
                paths, paths_ref,
                "Test failing for concat between {:?} and {:?}",
                &data[0].name, &data[1].name
            );
        }
        Ok(())
    }
}