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