sicada 0.1.0

A weighted finite-state transducer (WFST) library, file-compatible with OpenFst
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

//! Swapping the two sides of a transducer.
//!
//! Port of OpenFst's `invert.h`.

use crate::algorithms::arc_map::{
    ArcMapper, MapFinalAction, MapSymbolsAction, arc_map, arc_map_to,
};
use crate::arc::Arc;
use crate::error::OpenFstError;
use crate::fst::{Fst, MutableFst};
use crate::properties::invert_properties;

/// Swaps an arc's input and output labels.
#[derive(Debug, Clone, Copy, Default)]
pub struct InvertMapper;

impl<A: Arc> ArcMapper<A, A> for InvertMapper {
    #[inline]
    fn map(&mut self, arc: &A) -> A {
        A::new(
            arc.olabel(),
            arc.ilabel(),
            arc.weight().clone(),
            arc.nextstate(),
        )
    }

    fn final_action(&self) -> MapFinalAction {
        MapFinalAction::NoSuperfinal
    }

    /// Both tables are cleared by the mapping and put back the other way round
    /// by [`invert`], which is the only thing that knows they should swap.
    fn input_symbols_action(&self) -> MapSymbolsAction {
        MapSymbolsAction::Clear
    }

    fn output_symbols_action(&self) -> MapSymbolsAction {
        MapSymbolsAction::Clear
    }

    fn properties(&self, props: u64) -> u64 {
        invert_properties(props)
    }
}

/// Inverts `fst` in place: what it read it now writes, and the other way round.
pub fn invert<A: Arc, F: MutableFst<A>>(fst: &mut F) -> Result<(), OpenFstError> {
    let input = fst.input_symbols();
    let output = fst.output_symbols();
    arc_map(fst, &mut InvertMapper)?;
    fst.set_input_symbols(output);
    fst.set_output_symbols(input);
    Ok(())
}

/// Writes the inverse of `ifst` into `ofst`.
pub fn invert_to<A: Arc, F1: Fst<A>, F2: MutableFst<A>>(
    ifst: &F1,
    ofst: &mut F2,
) -> Result<(), OpenFstError> {
    let input = ifst.input_symbols();
    let output = ifst.output_symbols();
    arc_map_to(ifst, ofst, &mut InvertMapper)?;
    ofst.set_input_symbols(output);
    ofst.set_output_symbols(input);
    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::AtomicRc;
    use crate::arc::StdArc;
    use crate::fst::ExpandedFst as _;
    use crate::fsts::vector_fst::StdVectorFst;
    use crate::symbol_table::SymbolTable;
    use crate::weights::float_weight::TropicalWeight;

    fn transducer() -> StdVectorFst {
        let mut fst = StdVectorFst::new();
        for _ in 0..3 {
            fst.add_state();
        }
        fst.set_start(0);
        fst.add_arc(0, StdArc::new(1, 10, TropicalWeight(1.0), 1));
        fst.add_arc(1, StdArc::new(2, 20, TropicalWeight(2.0), 2));
        fst.set_final(2, TropicalWeight(3.0));
        fst
    }

    fn labels(fst: &StdVectorFst) -> Vec<(i32, i32)> {
        (0..fst.num_states() as i32)
            .flat_map(|s| {
                fst.arcs(s)
                    .map(|a| (a.ilabel(), a.olabel()))
                    .collect::<Vec<_>>()
            })
            .collect()
    }

    #[test]
    fn inverting_swaps_the_two_sides() {
        let mut fst = transducer();
        invert(&mut fst).unwrap();
        assert_eq!(labels(&fst), vec![(10, 1), (20, 2)]);
        assert_eq!(fst.num_states(), 3);
        assert_eq!(fst.start(), Some(0));
        assert_eq!(fst.final_weight(2), TropicalWeight(3.0));
    }

    /// Inverting twice is the identity, which is the property that defines it.
    #[test]
    fn inverting_twice_gives_back_the_original() {
        let original = transducer();
        let mut fst = original.clone();
        invert(&mut fst).unwrap();
        invert(&mut fst).unwrap();
        assert_eq!(labels(&fst), labels(&original));
    }

    /// The symbol tables swap with the sides they describe.
    #[test]
    fn the_symbol_tables_swap_too() {
        let mut input = SymbolTable::new("input".to_string());
        input.add_symbol("<eps>", 0);
        input.add_symbol("a", 1);
        let mut output = SymbolTable::new("output".to_string());
        output.add_symbol("<eps>", 0);
        output.add_symbol("x", 10);

        let mut fst = transducer();
        fst.set_input_symbols(Some(AtomicRc::new(input)));
        fst.set_output_symbols(Some(AtomicRc::new(output)));

        invert(&mut fst).unwrap();
        assert_eq!(fst.input_symbols().unwrap().find_symbol(10), Some("x"));
        assert_eq!(fst.output_symbols().unwrap().find_symbol(1), Some("a"));
    }

    #[test]
    fn inverting_into_another_fst_leaves_the_input_alone() {
        let ifst = transducer();
        let mut ofst = StdVectorFst::new();
        invert_to(&ifst, &mut ofst).unwrap();
        assert_eq!(labels(&ofst), vec![(10, 1), (20, 2)]);
        assert_eq!(labels(&ifst), vec![(1, 10), (2, 20)]);
    }
}