1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// algo_test.h 2f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 3f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Licensed under the Apache License, Version 2.0 (the "License"); 4f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// you may not use this file except in compliance with the License. 5f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// You may obtain a copy of the License at 6f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 7f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// http://www.apache.org/licenses/LICENSE-2.0 8f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 9f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Unless required by applicable law or agreed to in writing, software 10f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distributed under the License is distributed on an "AS IS" BASIS, 11f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See the License for the specific language governing permissions and 13f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// limitations under the License. 14f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 15f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Copyright 2005-2010 Google, Inc. 16f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Author: riley@google.com (Michael Riley) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Regression test for various FST algorithms. 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_TEST_ALGO_TEST_H__ 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_TEST_ALGO_TEST_H__ 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/fstlib.h> 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/random-weight.h> 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonDECLARE_int32(repeat); // defined in ./algo_test.cc 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Mapper to change input and output label of every transition into 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// epsilons. 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass EpsMapper { 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson EpsMapper() {} 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson A operator()(const A &arc) const { 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return A(0, 0, arc.weight, arc.nextstate); 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 Properties(uint64 props) const { 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson props &= ~kNotAcceptor; 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson props |= kAcceptor; 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson props &= ~kNoIEpsilons & ~kNoOEpsilons & ~kNoEpsilons; 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson props |= kIEpsilons | kOEpsilons | kEpsilons; 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson props &= ~kNotILabelSorted & ~kNotOLabelSorted; 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson props |= kILabelSorted | kOLabelSorted; 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return props; 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; } 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS;} 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;} 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// This class tests a variety of identities and properties that must 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// hold for various algorithms on weighted FSTs. 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc, class WeightGenerator> 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass WeightedTester { 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Label Label; 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson WeightedTester(int seed, const Fst<Arc> &zero_fst, const Fst<Arc> &one_fst, 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &univ_fst, WeightGenerator *weight_generator) 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : seed_(seed), zero_fst_(zero_fst), one_fst_(one_fst), 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson univ_fst_(univ_fst), weight_generator_(weight_generator) {} 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Test(const Fst<Arc> &T1, const Fst<Arc> &T2, const Fst<Arc> &T3) { 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TestRational(T1, T2, T3); 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TestMap(T1); 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TestCompose(T1, T2, T3); 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TestSort(T1); 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TestOptimize(T1); 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TestSearch(T1); 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Tests rational operations with identities 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void TestRational(const Fst<Arc> &T1, const Fst<Arc> &T2, 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &T3) { 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check destructive and delayed union are equivalent."; 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> U1(T1); 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Union(&U1, T2); 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U2(T1, T2); 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(U1, U2)); 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check destructive and delayed concatenation are equivalent."; 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C1(T1); 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C1, T2); 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C2(T1, T2); 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C1, C2)); 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C3(T2); 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(T1, &C3); 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C3, C2)); 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check destructive and delayed closure* are equivalent."; 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C1(T1); 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Closure(&C1, CLOSURE_STAR); 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ClosureFst<Arc> C2(T1, CLOSURE_STAR); 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C1, C2)); 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check destructive and delayed closure+ are equivalent."; 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C1(T1); 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Closure(&C1, CLOSURE_PLUS); 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ClosureFst<Arc> C2(T1, CLOSURE_PLUS); 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C1, C2)); 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check union is associative (destructive)."; 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> U1(T1); 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Union(&U1, T2); 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Union(&U1, T3); 129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> U3(T2); 131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Union(&U3, T3); 132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> U4(T1); 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Union(&U4, U3); 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(U1, U4)); 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check union is associative (delayed)."; 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U1(T1, T2); 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U2(U1, T3); 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U3(T2, T3); 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U4(T1, U3); 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(U2, U4)); 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check union is associative (destructive delayed)."; 152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U1(T1, T2); 153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Union(&U1, T3); 154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U3(T2, T3); 156f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U4(T1, U3); 157f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 158f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(U1, U4)); 159f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 160f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 161f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 162f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check concatenation is associative (destructive)."; 163f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C1(T1); 164f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C1, T2); 165f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C1, T3); 166f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 167f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C3(T2); 168f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C3, T3); 169f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C4(T1); 170f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C4, C3); 171f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 172f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C1, C4)); 173f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 174f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 175f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 176f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check concatenation is associative (delayed)."; 177f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C1(T1, T2); 178f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C2(C1, T3); 179f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 180f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C3(T2, T3); 181f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C4(T1, C3); 182f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 183f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C2, C4)); 184f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 185f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 186f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 187f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check concatenation is associative (destructive delayed)."; 188f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C1(T1, T2); 189f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C1, T3); 190f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 191f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C3(T2, T3); 192f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C4(T1, C3); 193f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 194f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C1, C4)); 195f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 196f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 197f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Weight::Properties() & kLeftSemiring) { 198f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check concatenation left distributes" 199f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << " over union (destructive)."; 200f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 201f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> U1(T1); 202f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Union(&U1, T2); 203f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C1(T3); 204f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C1, U1); 205f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 206f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C2(T3); 207f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C2, T1); 208f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C3(T3); 209f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C3, T2); 210f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> U2(C2); 211f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Union(&U2, C3); 212f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 213f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C1, U2)); 214f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 215f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 216f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Weight::Properties() & kRightSemiring) { 217f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check concatenation right distributes" 218f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << " over union (destructive)."; 219f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> U1(T1); 220f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Union(&U1, T2); 221f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C1(U1); 222f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C1, T3); 223f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 224f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C2(T1); 225f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C2, T3); 226f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C3(T2); 227f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C3, T3); 228f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> U2(C2); 229f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Union(&U2, C3); 230f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 231f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C1, U2)); 232f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 233f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 234f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Weight::Properties() & kLeftSemiring) { 235f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check concatenation left distributes over union (delayed)."; 236f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U1(T1, T2); 237f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C1(T3, U1); 238f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 239f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C2(T3, T1); 240f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C3(T3, T2); 241f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U2(C2, C3); 242f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 243f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C1, U2)); 244f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 245f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 246f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Weight::Properties() & kRightSemiring) { 247f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check concatenation right distributes over union (delayed)."; 248f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U1(T1, T2); 249f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C1(U1, T3); 250f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 251f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C2(T1, T3); 252f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C3(T2, T3); 253f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U2(C2, C3); 254f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 255f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C1, U2)); 256f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 257f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 258f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 259f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Weight::Properties() & kLeftSemiring) { 260f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check T T* == T+ (destructive)."; 261f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S(T1); 262f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Closure(&S, CLOSURE_STAR); 263f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C(T1); 264f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C, S); 265f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 266f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P(T1); 267f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Closure(&P, CLOSURE_PLUS); 268f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 269f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C, P)); 270f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 271f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 272f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 273f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Weight::Properties() & kRightSemiring) { 274f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check T* T == T+ (destructive)."; 275f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S(T1); 276f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Closure(&S, CLOSURE_STAR); 277f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C(S); 278f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C, T1); 279f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 280f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P(T1); 281f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Closure(&P, CLOSURE_PLUS); 282f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 283f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C, P)); 284f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 285f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 286f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Weight::Properties() & kLeftSemiring) { 287f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check T T* == T+ (delayed)."; 288f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ClosureFst<Arc> S(T1, CLOSURE_STAR); 289f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C(T1, S); 290f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 291f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ClosureFst<Arc> P(T1, CLOSURE_PLUS); 292f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 293f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C, P)); 294f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 295f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 296f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Weight::Properties() & kRightSemiring) { 297f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check T* T == T+ (delayed)."; 298f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ClosureFst<Arc> S(T1, CLOSURE_STAR); 299f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> C(S, T1); 300f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 301f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ClosureFst<Arc> P(T1, CLOSURE_PLUS); 302f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 303f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C, P)); 304f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 305f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 306f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 307f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Tests map-based operations. 308f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void TestMap(const Fst<Arc> &T) { 309f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 310f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 311f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check destructive and delayed projection are equivalent."; 312f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P1(T); 313f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Project(&P1, PROJECT_INPUT); 314f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ProjectFst<Arc> P2(T, PROJECT_INPUT); 315f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(P1, P2)); 316f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 317f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 318f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 319f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 320f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check destructive and delayed inversion are equivalent."; 321f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> I1(T); 322f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Invert(&I1); 323f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson InvertFst<Arc> I2(T); 324f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(I1, I2)); 325f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 326f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 327f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 328f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check Pi_1(T) = Pi_2(T^-1) (destructive)."; 329f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P1(T); 330f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> I1(T); 331f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Project(&P1, PROJECT_INPUT); 332f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Invert(&I1); 333f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Project(&I1, PROJECT_OUTPUT); 334f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(P1, I1)); 335f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 336f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 337f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 338f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check Pi_2(T) = Pi_1(T^-1) (destructive)."; 339f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P1(T); 340f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> I1(T); 341f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Project(&P1, PROJECT_OUTPUT); 342f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Invert(&I1); 343f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Project(&I1, PROJECT_INPUT); 344f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(P1, I1)); 345f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 346f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 347f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 348f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check Pi_1(T) = Pi_2(T^-1) (delayed)."; 349f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ProjectFst<Arc> P1(T, PROJECT_INPUT); 350f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson InvertFst<Arc> I1(T); 351f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ProjectFst<Arc> P2(I1, PROJECT_OUTPUT); 352f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(P1, P2)); 353f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 354f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 355f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 356f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 357f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check Pi_2(T) = Pi_1(T^-1) (delayed)."; 358f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ProjectFst<Arc> P1(T, PROJECT_OUTPUT); 359f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson InvertFst<Arc> I1(T); 360f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ProjectFst<Arc> P2(I1, PROJECT_INPUT); 361f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(P1, P2)); 362f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 363f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 364f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 365f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 366f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check destructive relabeling"; 367f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const int kNumLabels = 10; 368f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // set up relabeling pairs 369f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Label> labelset(kNumLabels); 370f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; i < kNumLabels; ++i) labelset[i] = i; 371f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; i < kNumLabels; ++i) { 372f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson swap(labelset[i], labelset[rand() % kNumLabels]); 373f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 374f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 375f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<pair<Label, Label> > ipairs1(kNumLabels); 376f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<pair<Label, Label> > opairs1(kNumLabels); 377f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; i < kNumLabels; ++i) { 378f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ipairs1[i] = make_pair(i, labelset[i]); 379f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opairs1[i] = make_pair(labelset[i], i); 380f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 381f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> R(T); 382f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Relabel(&R, ipairs1, opairs1); 383f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 384f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<pair<Label, Label> > ipairs2(kNumLabels); 385f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<pair<Label, Label> > opairs2(kNumLabels); 386f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; i < kNumLabels; ++i) { 387f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ipairs2[i] = make_pair(labelset[i], i); 388f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opairs2[i] = make_pair(i, labelset[i]); 389f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 390f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Relabel(&R, ipairs2, opairs2); 391f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(R, T)); 392f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 393f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check on-the-fly relabeling"; 394f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RelabelFst<Arc> Rdelay(T, ipairs1, opairs1); 395f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 396f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RelabelFst<Arc> RRdelay(Rdelay, ipairs2, opairs2); 397f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(RRdelay, T)); 398f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 399f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 400f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 401f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check encoding/decoding (destructive)."; 402f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> D(T); 403f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint32 encode_props = 0; 404f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (rand() % 2) 405f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson encode_props |= kEncodeLabels; 406f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (rand() % 2) 407f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson encode_props |= kEncodeWeights; 408f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson EncodeMapper<Arc> encoder(encode_props, ENCODE); 409f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Encode(&D, &encoder); 410f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Decode(&D, encoder); 411f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(D, T)); 412f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 413f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 414f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 415f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check encoding/decoding (delayed)."; 416f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint32 encode_props = 0; 417f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (rand() % 2) 418f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson encode_props |= kEncodeLabels; 419f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (rand() % 2) 420f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson encode_props |= kEncodeWeights; 421f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson EncodeMapper<Arc> encoder(encode_props, ENCODE); 422f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson EncodeFst<Arc> E(T, &encoder); 423f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> Encoded(E); 424f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DecodeFst<Arc> D(Encoded, encoder); 425f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(D, T)); 426f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 427f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 428f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 429f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check gallic mappers (constructive)."; 430f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ToGallicMapper<Arc> to_mapper; 431f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FromGallicMapper<Arc> from_mapper; 432f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst< GallicArc<Arc> > G; 433f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> F; 434f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcMap(T, &G, to_mapper); 435f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcMap(G, &F, from_mapper); 436f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, F)); 437f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 438f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 439f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 440f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check gallic mappers (delayed)."; 441f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ToGallicMapper<Arc> to_mapper; 442f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FromGallicMapper<Arc> from_mapper; 443f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcMapFst<Arc, GallicArc<Arc>, ToGallicMapper<Arc> > 444f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson G(T, to_mapper); 445f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcMapFst<GallicArc<Arc>, Arc, FromGallicMapper<Arc> > 446f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson F(G, from_mapper); 447f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, F)); 448f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 449f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 450f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 451f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Tests compose-based operations. 452f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void TestCompose(const Fst<Arc> &T1, const Fst<Arc> &T2, 453f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &T3) { 454f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!(Weight::Properties() & kCommutative)) 455f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 456f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 457f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S1(T1); 458f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S2(T2); 459f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S3(T3); 460f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 461f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ILabelCompare<Arc> icomp; 462f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson OLabelCompare<Arc> ocomp; 463f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 464f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&S1, ocomp); 465f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&S2, ocomp); 466f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&S3, icomp); 467f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 468f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 469f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check composition is associative."; 470f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFst<Arc> C1(S1, S2); 471f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 472f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFst<Arc> C2(C1, S3); 473f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFst<Arc> C3(S2, S3); 474f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFst<Arc> C4(S1, C3); 475f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 476f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C2, C4)); 477f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 478f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 479f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 480f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check composition left distributes over union."; 481f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U1(S2, S3); 482f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFst<Arc> C1(S1, U1); 483f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 484f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFst<Arc> C2(S1, S2); 485f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFst<Arc> C3(S1, S3); 486f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U2(C2, C3); 487f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 488f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C1, U2)); 489f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 490f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 491f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 492f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check composition right distributes over union."; 493f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U1(S1, S2); 494f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFst<Arc> C1(U1, S3); 495f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 496f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFst<Arc> C2(S1, S3); 497f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFst<Arc> C3(S2, S3); 498f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U2(C2, C3); 499f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 500f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C1, U2)); 501f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 502f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 503f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> A1(S1); 504f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> A2(S2); 505f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> A3(S3); 506f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Project(&A1, PROJECT_OUTPUT); 507f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Project(&A2, PROJECT_INPUT); 508f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Project(&A3, PROJECT_INPUT); 509f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 510f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 511f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check intersection is commutative."; 512f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson IntersectFst<Arc> I1(A1, A2); 513f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson IntersectFst<Arc> I2(A2, A1); 514f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(I1, I2)); 515f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 516f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 517f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 518f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check all epsilon filters leads to equivalent results."; 519f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef Matcher< Fst<Arc> > M; 520f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFst<Arc> C1(S1, S2); 521f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFst<Arc> C2( 522f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson S1, S2, 523f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFstOptions<Arc, M, AltSequenceComposeFilter<M> >()); 524f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFst<Arc> C3( 525f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson S1, S2, 526f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ComposeFstOptions<Arc, M, MatchComposeFilter<M> >()); 527f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 528f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C1, C2)); 529f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(C1, C3)); 530f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 531f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 532f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 533f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Tests sorting operations 534f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void TestSort(const Fst<Arc> &T) { 535f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ILabelCompare<Arc> icomp; 536f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson OLabelCompare<Arc> ocomp; 537f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 538f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 539f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check arc sorted Fst is equivalent to its input."; 540f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S1(T); 541f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&S1, icomp); 542f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, S1)); 543f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 544f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 545f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 546f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check destructive and delayed arcsort are equivalent."; 547f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S1(T); 548f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&S1, icomp); 549f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSortFst< Arc, ILabelCompare<Arc> > S2(T, icomp); 550f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(S1, S2)); 551f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 552f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 553f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 554f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check ilabel sorting vs. olabel sorting with inversions."; 555f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S1(T); 556f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S2(T); 557f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&S1, icomp); 558f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Invert(&S2); 559f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&S2, ocomp); 560f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Invert(&S2); 561f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(S1, S2)); 562f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 563f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 564f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 565f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check topologically sorted Fst is equivalent to its input."; 566f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S1(T); 567f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TopSort(&S1); 568f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, S1)); 569f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 570f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 571f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 572f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check reverse(reverse(T)) = T"; 573f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst< ReverseArc<Arc> > R1; 574f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> R2; 575f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Reverse(T, &R1); 576f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Reverse(R1, &R2); 577f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, R2)); 578f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 579f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 580f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 581f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Tests optimization operations 582f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void TestOptimize(const Fst<Arc> &T) { 583f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 tprops = T.Properties(kFstProperties, true); 584f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 wprops = Weight::Properties(); 585f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 586f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> A(T); 587f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Project(&A, PROJECT_INPUT); 588f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 589f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 590f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check connected FST is equivalent to its input."; 591f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C1(T); 592f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Connect(&C1); 593f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, C1)); 594f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 595f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 596f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((wprops & kSemiring) == kSemiring && 597f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (tprops & kAcyclic || wprops & kIdempotent)) { 598f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check epsilon-removed FST is equivalent to its input."; 599f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> R1(T); 600f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilon(&R1); 601f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, R1)); 602f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 603f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check destructive and delayed epsilon removal" 604f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << "are equivalent."; 605f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonFst<Arc> R2(T); 606f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(R1, R2)); 607f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 608f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check an FST with a large proportion" 609f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << " of epsilon transitions:"; 610f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Maps all transitions of T to epsilon-transitions and append 611f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // a non-epsilon transition. 612f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> U; 613f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcMap(T, &U, EpsMapper<Arc>()); 614f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> V; 615f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson V.SetStart(V.AddState()); 616f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Arc arc(1, 1, Weight::One(), V.AddState()); 617f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson V.AddArc(V.Start(), arc); 618f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson V.SetFinal(arc.nextstate, Weight::One()); 619f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&U, V); 620f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Check that epsilon-removal preserves the shortest-distance 621f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // from the initial state to the final states. 622f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Weight> d; 623f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistance(U, &d, true); 624f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight w = U.Start() < d.size() ? d[U.Start()] : Weight::Zero(); 625f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> U1(U); 626f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilon(&U1); 627f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistance(U1, &d, true); 628f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight w1 = U1.Start() < d.size() ? d[U1.Start()] : Weight::Zero(); 629f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(ApproxEqual(w, w1, kTestDelta)); 630f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonFst<Arc> U2(U); 631f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistance(U2, &d, true); 632f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight w2 = U2.Start() < d.size() ? d[U2.Start()] : Weight::Zero(); 633f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(ApproxEqual(w, w2, kTestDelta)); 634f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 635f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 636f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((wprops & kSemiring) == kSemiring && tprops & kAcyclic) { 637f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check determinized FSA is equivalent to its input."; 638f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DeterminizeFst<Arc> D(A); 639f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(A, D)); 640f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 641f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 642f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int n; 643f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 644f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check size(min(det(A))) <= size(det(A))" 645f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << " and min(det(A)) equiv det(A)"; 646f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> M(D); 647f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson n = M.NumStates(); 648f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Minimize(&M); 649f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(D, M)); 650f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(M.NumStates() <= n); 651f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson n = M.NumStates(); 652f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 653f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 654f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (n && (wprops & kIdempotent) == kIdempotent && 655f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson A.Properties(kNoEpsilons, true)) { 656f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check that Revuz's algorithm leads to the" 657f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << " same number of states as Brozozowski's algorithm"; 658f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 659f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Skip test if A is the empty machine or contains epsilons or 660f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // if the semiring is not idempotent (to avoid floating point 661f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // errors) 662f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> R; 663f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Reverse(A, &R); 664f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilon(&R); 665f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DeterminizeFst<Arc> DR(R); 666f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> RD; 667f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Reverse(DR, &RD); 668f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DeterminizeFst<Arc> DRD(RD); 669f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> M(DRD); 670f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK_EQ(n + 1, M.NumStates()); // Accounts for the epsilon transition 671f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // to the initial state 672f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 673f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 674f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 675f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Arc::Type() == LogArc::Type() || Arc::Type() == StdArc::Type()) { 676f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check reweight(T) equiv T"; 677f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Weight> potential; 678f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> RI(T); 679f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> RF(T); 680f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (potential.size() < RI.NumStates()) 681f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson potential.push_back((*weight_generator_)()); 682f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 683f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Reweight(&RI, potential, REWEIGHT_TO_INITIAL); 684f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, RI)); 685f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 686f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Reweight(&RF, potential, REWEIGHT_TO_FINAL); 687f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, RF)); 688f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 689f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 690f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((wprops & kIdempotent) || (tprops & kAcyclic)) { 691f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check pushed FST is equivalent to input FST."; 692f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Pushing towards the final state. 693f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (wprops & kRightSemiring) { 694f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P1; 695f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Push<Arc, REWEIGHT_TO_FINAL>(T, &P1, kPushLabels); 696f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, P1)); 697f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 698f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P2; 699f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Push<Arc, REWEIGHT_TO_FINAL>(T, &P2, kPushWeights); 700f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, P2)); 701f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 702f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P3; 703f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Push<Arc, REWEIGHT_TO_FINAL>(T, &P3, kPushLabels | kPushWeights); 704f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, P3)); 705f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 706f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 707f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Pushing towards the initial state. 708f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (wprops & kLeftSemiring) { 709f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P1; 710f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Push<Arc, REWEIGHT_TO_INITIAL>(T, &P1, kPushLabels); 711f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, P1)); 712f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 713f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P2; 714f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Push<Arc, REWEIGHT_TO_INITIAL>(T, &P2, kPushWeights); 715f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, P2)); 716f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P3; 717f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Push<Arc, REWEIGHT_TO_INITIAL>(T, &P3, kPushLabels | kPushWeights); 718f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, P3)); 719f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 720f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 721f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 722f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((wprops & (kPath | kCommutative)) == (kPath | kCommutative)) { 723f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check pruning algorithm"; 724f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 725f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check equiv. of constructive and destructive algorithms"; 726f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight thresold = (*weight_generator_)(); 727f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P1(T); 728f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Prune(&P1, thresold); 729f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P2; 730f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Prune(T, &P2, thresold); 731f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(P1,P2)); 732f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 733f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 734f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 735f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check prune(reverse) equiv reverse(prune)"; 736f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight thresold = (*weight_generator_)(); 737f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst< ReverseArc<Arc> > R; 738f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P1(T); 739f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P2; 740f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Prune(&P1, thresold); 741f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Reverse(T, &R); 742f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Prune(&R, thresold.Reverse()); 743f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Reverse(R, &P2); 744f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(P1, P2)); 745f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 746f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 747f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check: ShortestDistance(T- prune(T))" 748f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << " > ShortestDistance(T) times Thresold"; 749f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight thresold = (*weight_generator_)(); 750f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> P; 751f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Prune(A, &P, thresold); 752f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DifferenceFst<Arc> C(A, DeterminizeFst<Arc> 753f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (RmEpsilonFst<Arc> 754f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (ArcMapFst<Arc, Arc, 755f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmWeightMapper<Arc> > 756f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (P, RmWeightMapper<Arc>())))); 757f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight sum1 = Times(ShortestDistance(A), thresold); 758f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight sum2 = ShortestDistance(C); 759f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Plus(sum1, sum2) == sum1); 760f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 761f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 762f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (tprops & kAcyclic) { 763f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check synchronize(T) equiv T"; 764f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SynchronizeFst<Arc> S(T); 765f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(T, S)); 766f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 767f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 768f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 769f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Tests search operations 770f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void TestSearch(const Fst<Arc> &T) { 771f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 wprops = Weight::Properties(); 772f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 773f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> A(T); 774f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Project(&A, PROJECT_INPUT); 775f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 776f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((wprops & (kPath | kRightSemiring)) == (kPath | kRightSemiring)) { 777f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check 1-best weight."; 778f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> path; 779f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestPath(T, &path); 780f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight tsum = ShortestDistance(T); 781f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight psum = ShortestDistance(path); 782f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(ApproxEqual(tsum, psum, kTestDelta)); 783f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 784f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 785f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((wprops & (kPath | kSemiring)) == (kPath | kSemiring)) { 786f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check n-best weights"; 787f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> R(A); 788f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilon(&R); 789f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int nshortest = rand() % kNumRandomShortestPaths + 2; 790f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> paths; 791f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestPath(R, &paths, nshortest, true, false, 792f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight::Zero(), kNumShortestStates); 793f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Weight> distance; 794f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistance(paths, &distance, true); 795f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId pstart = paths.Start(); 796f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (pstart != kNoStateId) { 797f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcIterator< Fst<Arc> > piter(paths, pstart); 798f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (; !piter.Done(); piter.Next()) { 799f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId s = piter.Value().nextstate; 800f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight nsum = s < distance.size() ? 801f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Times(piter.Value().weight, distance[s]) : Weight::Zero(); 802f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> path; 803f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestPath(R, &path); 804f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight dsum = ShortestDistance(path); 805f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(ApproxEqual(nsum, dsum, kTestDelta)); 806f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcMap(&path, RmWeightMapper<Arc>()); 807f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S; 808f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Difference(R, path, &S); 809f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson R = S; 810f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 811f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 812f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 813f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 814f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 815f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Tests if two FSTS are equivalent by checking if random 816f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // strings from one FST are transduced the same by both FSTs. 817f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Equiv(const Fst<Arc> &fst1, const Fst<Arc> &fst2) { 818f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check FSTs for sanity (including property bits)."; 819f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Verify(fst1)); 820f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Verify(fst2)); 821f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 822f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UniformArcSelector<Arc> uniform_selector(seed_); 823f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RandGenOptions< UniformArcSelector<Arc> > 824f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opts(uniform_selector, kRandomPathLength); 825f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return RandEquivalent(fst1, fst2, kNumRandomPaths, kTestDelta, opts); 826f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 827f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 828f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Random seed 829f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int seed_; 830f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 831f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // FST with no states 832f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> zero_fst_; 833f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 834f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // FST with one state that accepts epsilon. 835f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> one_fst_; 836f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 837f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // FST with one state that accepts all strings. 838f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> univ_fst_; 839f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 840f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Generates weights used in testing. 841f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson WeightGenerator *weight_generator_; 842f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 843f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Maximum random path length. 844f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const int kRandomPathLength; 845f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 846f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Number of random paths to explore. 847f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const int kNumRandomPaths; 848f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 849f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Maximum number of nshortest paths. 850f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const int kNumRandomShortestPaths; 851f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 852f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Maximum number of nshortest states. 853f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const int kNumShortestStates; 854f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 855f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Delta for equivalence tests. 856f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const float kTestDelta; 857f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 858f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DISALLOW_COPY_AND_ASSIGN(WeightedTester); 859f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 860f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 861f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 862f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A, class WG> 863f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst int WeightedTester<A, WG>::kRandomPathLength = 25; 864f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 865f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A, class WG> 866f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst int WeightedTester<A, WG>::kNumRandomPaths = 100; 867f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 868f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A, class WG> 869f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst int WeightedTester<A, WG>::kNumRandomShortestPaths = 100; 870f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 871f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A, class WG> 872f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst int WeightedTester<A, WG>::kNumShortestStates = 10000; 873f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 874f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A, class WG> 875f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst float WeightedTester<A, WG>::kTestDelta = .05; 876f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 877f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// This class tests a variety of identities and properties that must 878f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// hold for various algorithms on unweighted FSAs and that are not tested 879f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// by WeightedTester. Only the specialization does anything interesting. 880f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc> 881f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass UnweightedTester { 882f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 883f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnweightedTester(const Fst<Arc> &zero_fsa, const Fst<Arc> &one_fsa, 884f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &univ_fsa) {} 885f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 886f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Test(const Fst<Arc> &A1, const Fst<Arc> &A2, const Fst<Arc> &A3) {} 887f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 888f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 889f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 890f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Specialization for StdArc. This should work for any commutative, 891f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// idempotent semiring when restricted to the unweighted case 892f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// (being isomorphic to the boolean semiring). 893f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <> 894f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass UnweightedTester<StdArc> { 895f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 896f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef StdArc Arc; 897f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef Arc::Label Label; 898f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef Arc::StateId StateId; 899f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef Arc::Weight Weight; 900f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 901f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnweightedTester(const Fst<Arc> &zero_fsa, const Fst<Arc> &one_fsa, 902f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &univ_fsa) 903f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : zero_fsa_(zero_fsa), one_fsa_(one_fsa), univ_fsa_(univ_fsa) {} 904f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 905f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Test(const Fst<Arc> &A1, const Fst<Arc> &A2, const Fst<Arc> &A3) { 906f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TestRational(A1, A2, A3); 907f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TestIntersect(A1, A2, A3); 908f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TestOptimize(A1); 909f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 910f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 911f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 912f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Tests rational operations with identities 913f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void TestRational(const Fst<Arc> &A1, const Fst<Arc> &A2, 914f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &A3) { 915f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 916f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 917f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check the union contains its arguments (destructive)."; 918f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> U(A1); 919f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Union(&U, A2); 920f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 921f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Subset(A1, U)); 922f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Subset(A2, U)); 923f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 924f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 925f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 926f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check the union contains its arguments (delayed)."; 927f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U(A1, A2); 928f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 929f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Subset(A1, U)); 930f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Subset(A2, U)); 931f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 932f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 933f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 934f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check if A^n c A* (destructive)."; 935f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C(one_fsa_); 936f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int n = rand() % 5; 937f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (int i = 0; i < n; ++i) 938f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&C, A1); 939f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 940f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S(A1); 941f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Closure(&S, CLOSURE_STAR); 942f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Subset(C, S)); 943f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 944f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 945f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 946f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check if A^n c A* (delayed)."; 947f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int n = rand() % 5; 948f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Fst<Arc> *C = new VectorFst<Arc>(one_fsa_); 949f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (int i = 0; i < n; ++i) { 950f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ConcatFst<Arc> *F = new ConcatFst<Arc>(*C, A1); 951f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete C; 952f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson C = F; 953f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 954f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ClosureFst<Arc> S(A1, CLOSURE_STAR); 955f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Subset(*C, S)); 956f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete C; 957f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 958f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 959f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 960f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Tests intersect-based operations. 961f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void TestIntersect(const Fst<Arc> &A1, const Fst<Arc> &A2, 962f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &A3) { 963f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S1(A1); 964f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S2(A2); 965f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> S3(A3); 966f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 967f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ILabelCompare<Arc> comp; 968f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 969f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&S1, comp); 970f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&S2, comp); 971f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&S3, comp); 972f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 973f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 974f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check the intersection is contained in its arguments."; 975f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson IntersectFst<Arc> I1(S1, S2); 976f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Subset(I1, S1)); 977f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Subset(I1, S2)); 978f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 979f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 980f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 981f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check union distributes over intersection."; 982f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson IntersectFst<Arc> I1(S1, S2); 983f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U1(I1, S3); 984f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 985f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U2(S1, S3); 986f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U3(S2, S3); 987f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSortFst< Arc, ILabelCompare<Arc> > S4(U3, comp); 988f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson IntersectFst<Arc> I2(U2, S4); 989f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 990f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(U1, I2)); 991f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 992f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 993f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C1; 994f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C2; 995f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Complement(S1, &C1); 996f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Complement(S2, &C2); 997f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&C1, comp); 998f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&C2, comp); 999f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1000f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1001f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 1002f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check S U S' = Sigma*"; 1003f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U(S1, C1); 1004f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(U, univ_fsa_)); 1005f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1006f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1007f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 1008f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check S n S' = {}"; 1009f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson IntersectFst<Arc> I(S1, C1); 1010f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(I, zero_fsa_)); 1011f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1012f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1013f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 1014f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check (S1' U S2') == (S1 n S2)'"; 1015f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U(C1, C2); 1016f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1017f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson IntersectFst<Arc> I(S1, S2); 1018f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C3; 1019f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Complement(I, &C3); 1020f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(U, C3)); 1021f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1022f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1023f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 1024f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check (S1' n S2') == (S1 U S2)'"; 1025f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson IntersectFst<Arc> I(C1, C2); 1026f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1027f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnionFst<Arc> U(S1, S2); 1028f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> C3; 1029f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Complement(U, &C3); 1030f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(I, C3)); 1031f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1032f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1033f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1034f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Tests optimization operations 1035f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void TestOptimize(const Fst<Arc> &A) { 1036f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 1037f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check determinized FSA is equivalent to its input."; 1038f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DeterminizeFst<Arc> D(A); 1039f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(A, D)); 1040f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1041f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1042f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 1043f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check minimized FSA is equivalent to its input."; 1044f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int n; 1045f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson { 1046f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonFst<Arc> R(A); 1047f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DeterminizeFst<Arc> D(R); 1048f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> M(D); 1049f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Minimize(&M); 1050f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Equiv(A, M)); 1051f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson n = M.NumStates(); 1052f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1053f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1054f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (n) { // Skip test if A is the empty machine 1055f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check that Hopcroft's and Revuz's algorithms lead to the" 1056f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << " same number of states as Brozozowski's algorithm"; 1057f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> R; 1058f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Reverse(A, &R); 1059f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilon(&R); 1060f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DeterminizeFst<Arc> DR(R); 1061f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> RD; 1062f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Reverse(DR, &RD); 1063f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DeterminizeFst<Arc> DRD(RD); 1064f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> M(DRD); 1065f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK_EQ(n + 1, M.NumStates()); // Accounts for the epsilon transition 1066f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // to the initial state 1067f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1068f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1069f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1070f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1071f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Tests if two FSAS are equivalent. 1072f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Equiv(const Fst<Arc> &fsa1, const Fst<Arc> &fsa2) { 1073f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check FSAs for sanity (including property bits)."; 1074f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Verify(fsa1)); 1075f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Verify(fsa2)); 1076f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1077f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> vfsa1(fsa1); 1078f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> vfsa2(fsa2); 1079f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilon(&vfsa1); 1080f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilon(&vfsa2); 1081f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DeterminizeFst<Arc> dfa1(vfsa1); 1082f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DeterminizeFst<Arc> dfa2(vfsa2); 1083f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1084f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Test equivalence using union-find algorithm 1085f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool equiv1 = Equivalent(dfa1, dfa2); 1086f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1087f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Test equivalence by checking if (S1 - S2) U (S2 - S1) is empty 1088f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ILabelCompare<Arc> comp; 1089f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> sdfa1(dfa1); 1090f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&sdfa1, comp); 1091f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> sdfa2(dfa2); 1092f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&sdfa2, comp); 1093f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1094f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DifferenceFst<Arc> dfsa1(sdfa1, sdfa2); 1095f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DifferenceFst<Arc> dfsa2(sdfa2, sdfa1); 1096f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1097f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> ufsa(dfsa1); 1098f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Union(&ufsa, dfsa2); 1099f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Connect(&ufsa); 1100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool equiv2 = ufsa.NumStates() == 0; 1101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Check two equivalence tests match 1103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK((equiv1 && equiv2) || (!equiv1 && !equiv2)); 1104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return equiv1; 1106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Tests if FSA1 is a subset of FSA2 (disregarding weights). 1109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Subset(const Fst<Arc> &fsa1, const Fst<Arc> &fsa2) { 1110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check FSAs (incl. property bits) for sanity"; 1111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Verify(fsa1)); 1112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Verify(fsa2)); 1113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<StdArc> vfsa1; 1115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<StdArc> vfsa2; 1116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilon(&vfsa1); 1117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilon(&vfsa2); 1118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ILabelCompare<StdArc> comp; 1119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&vfsa1, comp); 1120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcSort(&vfsa2, comp); 1121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson IntersectFst<StdArc> ifsa(vfsa1, vfsa2); 1122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DeterminizeFst<StdArc> dfa1(vfsa1); 1123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DeterminizeFst<StdArc> dfa2(ifsa); 1124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return Equivalent(dfa1, dfa2); 1125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Returns complement Fsa 1128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Complement(const Fst<Arc> &ifsa, MutableFst<Arc> *ofsa) { 1129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonFst<Arc> rfsa(ifsa); 1130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DeterminizeFst<Arc> dfa(rfsa); 1131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DifferenceFst<Arc> cfsa(univ_fsa_, dfa); 1132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson *ofsa = cfsa; 1133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // FSA with no states 1136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> zero_fsa_; 1137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // FSA with one state that accepts epsilon. 1139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> one_fsa_; 1140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // FSA with one state that accepts all strings. 1142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> univ_fsa_; 1143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DISALLOW_COPY_AND_ASSIGN(UnweightedTester); 1145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 1146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// This class tests a variety of identities and properties that must 1149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// hold for various FST algorithms. It randomly generates FSTs, using 1150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// function object 'weight_generator' to select weights. 'WeightTester' 1151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// and 'UnweightedTester' are then called. 1152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc, class WeightGenerator> 1153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass AlgoTester { 1154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 1155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Label Label; 1156f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 1157f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 1158f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1159f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AlgoTester(WeightGenerator generator, int seed) : 1160f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson weight_generator_(generator), seed_(seed) { 1161f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson one_fst_.AddState(); 1162f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson one_fst_.SetStart(0); 1163f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson one_fst_.SetFinal(0, Weight::One()); 1164f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1165f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson univ_fst_.AddState(); 1166f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson univ_fst_.SetStart(0); 1167f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson univ_fst_.SetFinal(0, Weight::One()); 1168f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (int i = 0; i < kNumRandomLabels; ++i) 1169f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson univ_fst_.AddArc(0, Arc(i, i, Weight::One(), 0)); 1170f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1171f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1172f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Test() { 1173f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "weight type = " << Weight::Type(); 1174f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1175f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (int i = 0; i < FLAGS_repeat; ++i) { 1176f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Random transducers 1177f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> T1; 1178f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> T2; 1179f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> T3; 1180f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RandFst(&T1); 1181f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RandFst(&T2); 1182f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RandFst(&T3); 1183f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson WeightedTester<Arc, WeightGenerator> 1184f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson weighted_tester(seed_, zero_fst_, one_fst_, 1185f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson univ_fst_, &weight_generator_); 1186f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson weighted_tester.Test(T1, T2, T3); 1187f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1188f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> A1(T1); 1189f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> A2(T2); 1190f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> A3(T3); 1191f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Project(&A1, PROJECT_OUTPUT); 1192f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Project(&A2, PROJECT_INPUT); 1193f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Project(&A3, PROJECT_INPUT); 1194f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcMap(&A1, rm_weight_mapper); 1195f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcMap(&A2, rm_weight_mapper); 1196f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcMap(&A3, rm_weight_mapper); 1197f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson UnweightedTester<Arc> unweighted_tester(zero_fst_, one_fst_, univ_fst_); 1198f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson unweighted_tester.Test(A1, A2, A3); 1199f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1200f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1201f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1202f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 1203f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Generates a random FST. 1204f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void RandFst(MutableFst<Arc> *fst) { 1205f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Determines direction of the arcs wrt state numbering. This way we 1206f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // can force acyclicity when desired. 1207f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson enum ArcDirection { ANY_DIRECTION = 0, FORWARD_DIRECTION = 1, 1208f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson REVERSE_DIRECTION = 2, NUM_DIRECTIONS = 3 }; 1209f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1210f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcDirection arc_direction = ANY_DIRECTION; 1211f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (rand()/(RAND_MAX + 1.0) < kAcyclicProb) 1212f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arc_direction = rand() % 2 ? FORWARD_DIRECTION : REVERSE_DIRECTION; 1213f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1214f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->DeleteStates(); 1215f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId ns = rand() % kNumRandomStates; 1216f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1217f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (ns == 0) 1218f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 1219f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId s = 0; s < ns; ++s) 1220f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->AddState(); 1221f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1222f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId start = rand() % ns; 1223f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->SetStart(start); 1224f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1225f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t na = rand() % kNumRandomArcs; 1226f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t n = 0; n < na; ++n) { 1227f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId s = rand() % ns; 1228f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Arc arc; 1229f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arc.ilabel = rand() % kNumRandomLabels; 1230f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arc.olabel = rand() % kNumRandomLabels; 1231f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arc.weight = weight_generator_(); 1232f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arc.nextstate = rand() % ns; 1233f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1234f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (arc_direction == ANY_DIRECTION || 1235f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (arc_direction == FORWARD_DIRECTION && arc.ilabel > arc.olabel) || 1236f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (arc_direction == REVERSE_DIRECTION && arc.ilabel < arc.olabel)) 1237f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->AddArc(s, arc); 1238f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1239f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1240f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId nf = rand() % (ns + 1); 1241f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId n = 0; n < nf; ++n) { 1242f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId s = rand() % ns; 1243f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight final = weight_generator_(); 1244f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->SetFinal(s, final); 1245f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1246f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "Check FST for sanity (including property bits)."; 1247f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CHECK(Verify(*fst)); 1248f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1249f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Get/compute all properties. 1250f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props = fst->Properties(kFstProperties, true); 1251f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1252f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Select random set of properties to be unknown. 1253f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 mask = 0; 1254f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (int n = 0; n < 8; ++n) { 1255f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mask |= rand() & 0xff; 1256f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mask <<= 8; 1257f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1258f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mask &= ~kTrinaryProperties; 1259f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->SetProperties(props & ~mask, mask); 1260f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 1261f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1262f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Generates weights used in testing. 1263f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson WeightGenerator weight_generator_; 1264f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1265f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Random seed 1266f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int seed_; 1267f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1268f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // FST with no states 1269f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> zero_fst_; 1270f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1271f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // FST with one state that accepts epsilon. 1272f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> one_fst_; 1273f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1274f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // FST with one state that accepts all strings. 1275f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<Arc> univ_fst_; 1276f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1277f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Mapper to remove weights from an Fst 1278f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmWeightMapper<Arc> rm_weight_mapper; 1279f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1280f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Maximum number of states in random test Fst. 1281f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const int kNumRandomStates; 1282f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1283f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Maximum number of arcs in random test Fst. 1284f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const int kNumRandomArcs; 1285f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1286f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Number of alternative random labels. 1287f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const int kNumRandomLabels; 1288f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1289f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Probability to force an acyclic Fst 1290f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const float kAcyclicProb; 1291f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1292f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Maximum random path length. 1293f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const int kRandomPathLength; 1294f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1295f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Number of random paths to explore. 1296f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const int kNumRandomPaths; 1297f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1298f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DISALLOW_COPY_AND_ASSIGN(AlgoTester); 1299f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 1300f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1301f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A, class G> const int AlgoTester<A, G>::kNumRandomStates = 10; 1302f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1303f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A, class G> const int AlgoTester<A, G>::kNumRandomArcs = 25; 1304f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1305f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A, class G> const int AlgoTester<A, G>::kNumRandomLabels = 5; 1306f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1307f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A, class G> const float AlgoTester<A, G>::kAcyclicProb = .25; 1308f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1309f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A, class G> const int AlgoTester<A, G>::kRandomPathLength = 25; 1310f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1311f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A, class G> const int AlgoTester<A, G>::kNumRandomPaths = 100; 1312f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1313f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 1314f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 1315f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_TEST_ALGO_TEST_H__ 1316