rustfst/algorithms/
optimize.rs

1use crate::algorithms::encode::EncodeType;
2use crate::algorithms::encode::EncodeType::*;
3use crate::algorithms::*;
4use crate::fst_properties::FstProperties;
5use crate::fst_traits::{AllocableFst, MutableFst};
6use crate::semirings::{SemiringProperties, WeaklyDivisibleSemiring, WeightQuantize};
7use crate::Semiring;
8use anyhow::Result;
9
10/// General optimization (determinization and minimization) of a WFST
11pub fn optimize<
12    W: Semiring + WeaklyDivisibleSemiring + WeightQuantize,
13    F: MutableFst<W> + AllocableFst<W>,
14>(
15    fst: &mut F,
16) -> Result<()>
17where
18    W::ReverseWeight: WeightQuantize,
19{
20    if fst.properties().contains(FstProperties::ACCEPTOR) {
21        optimize_acceptor(fst)
22    } else {
23        optimize_transducer(fst)
24    }
25}
26
27fn determinize<
28    W: Semiring + WeaklyDivisibleSemiring + WeightQuantize,
29    F: MutableFst<W> + AllocableFst<W>,
30>(
31    fst: &mut F,
32) -> Result<()> {
33    *fst = determinize::determinize(fst)?;
34    Ok(())
35}
36
37fn encode_deter_mini_decode<
38    W: Semiring + WeaklyDivisibleSemiring + WeightQuantize,
39    F: MutableFst<W> + AllocableFst<W>,
40>(
41    fst: &mut F,
42    encoder: EncodeType,
43) -> Result<()>
44where
45    W::ReverseWeight: WeightQuantize,
46{
47    let table = encode::encode(fst, encoder)?;
48    determinize(fst)?;
49    minimize(fst)?;
50    encode::decode(fst, table)
51}
52
53fn optimize_transducer<
54    W: Semiring + WeaklyDivisibleSemiring + WeightQuantize,
55    F: MutableFst<W> + AllocableFst<W>,
56>(
57    fst: &mut F,
58) -> Result<()>
59where
60    W::ReverseWeight: WeightQuantize,
61{
62    if !fst.properties().contains(FstProperties::NO_EPSILONS) {
63        rm_epsilon::rm_epsilon(fst)?;
64    }
65
66    tr_sum(fst);
67
68    if !W::properties().contains(SemiringProperties::IDEMPOTENT) {
69        if !fst.properties().contains(FstProperties::I_DETERMINISTIC) {
70            if fst.properties().contains(FstProperties::ACYCLIC) {
71                encode_deter_mini_decode(fst, EncodeLabels)?;
72            }
73        } else {
74            minimize(fst)?;
75        }
76    } else if !fst.properties().contains(FstProperties::I_DETERMINISTIC) {
77        if !fst.properties().intersects(
78            FstProperties::ACYCLIC | FstProperties::UNWEIGHTED | FstProperties::UNWEIGHTED_CYCLES,
79        ) {
80            encode_deter_mini_decode(fst, EncodeWeightsAndLabels)?;
81            tr_sum(fst);
82        } else {
83            encode_deter_mini_decode(fst, EncodeLabels)?;
84        }
85    } else {
86        minimize(fst)?;
87    }
88
89    Ok(())
90}
91
92fn optimize_acceptor<
93    W: Semiring + WeaklyDivisibleSemiring + WeightQuantize,
94    F: MutableFst<W> + AllocableFst<W>,
95>(
96    fst: &mut F,
97) -> Result<()>
98where
99    W::ReverseWeight: WeightQuantize,
100{
101    if !fst.properties().contains(FstProperties::NO_EPSILONS) {
102        rm_epsilon::rm_epsilon(fst)?;
103    }
104    tr_sum(fst);
105    if !W::properties().contains(SemiringProperties::IDEMPOTENT) {
106        if !fst.properties().contains(FstProperties::I_DETERMINISTIC) {
107            if fst.properties().contains(FstProperties::ACYCLIC) {
108                determinize(fst)?;
109                minimize(fst)?;
110            }
111        } else {
112            minimize(fst)?;
113        }
114    } else if !fst.properties().contains(FstProperties::I_DETERMINISTIC) {
115        if !fst.properties().intersects(
116            FstProperties::ACYCLIC | FstProperties::UNWEIGHTED | FstProperties::UNWEIGHTED_CYCLES,
117        ) {
118            encode_deter_mini_decode(fst, EncodeWeights)?;
119            tr_sum(fst)
120        } else {
121            determinize(fst)?;
122            minimize(fst)?;
123        }
124    } else {
125        minimize(fst)?;
126    }
127    Ok(())
128}
129
130#[cfg(test)]
131mod tests {
132    use super::*;
133    use crate::fst_traits::Fst;
134    use crate::prelude::{TropicalWeight, VectorFst};
135    use crate::SymbolTable;
136    use proptest::prelude::any;
137    use proptest::proptest;
138    use std::sync::Arc;
139
140    proptest! {
141        #[test]
142        fn test_proptest_optimize_keeps_symts(mut fst in any::<VectorFst::<TropicalWeight>>()) {
143            let symt = Arc::new(SymbolTable::new());
144            fst.set_input_symbols(Arc::clone(&symt));
145            fst.set_output_symbols(Arc::clone(&symt));
146
147            optimize(&mut fst).unwrap();
148
149            assert!(fst.input_symbols().is_some());
150            assert!(fst.output_symbols().is_some());
151        }
152    }
153}
rustfst/algorithms/optimize.rs

rustfst/algorithms/
optimize.rs
