RandEquivalentDoc < FST

FST Web>FstQuickTour>RandEquivalentDoc (2018-04-27, MichaelRiley) (raw view)

---+ !RandEquivalent

---++ Description

This operation test is two FSTs are equivalent by randomly generating _N_ paths alternatively in each of the two FSTs.  

For each randomly generated path, the algorithm computes for each
of the two FSTs the sum of the weights of all the successful paths
sharing the same input and output labels as the considered randomly
generated path and checks that these two values are within
'delta'.

The random generation can be specified in the same as for the [[RandGenDoc][RandGen]] operation.

---++ Usage

| <verbatim>
template <class Arc>
bool RandEquivalent(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
                    ssize_t num_paths, float delta = kDelta,
                    int seed = time(0), int path_length = INT_MAX);
</verbatim> | 
| <verbatim>
template<class Arc, class ArcSelector>
bool RandEquivalent(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
                    ssize_t num_paths, float delta,
                    const RandGenOptions<ArcSelector> &opts);
</verbatim> | 
| <verbatim>
fstequivalent --random [-npath=$n] [--delta=$delta] [--seed=$seed] [--max_length=$max_length] in1.fst in2.fst
</verbatim> | 

---++ Example

|   ==A==   |   ==B==   |
| %ATTACHURL%/randequiv1.png | %ATTACHURL%/randequiv2.png |

<verbatim>
RandEquivalent(A, B, npaths, kDelta, RandGenOptions<ArcSelector>());

fstequivalent --random --npath=$npaths a.fst b.fst
</verbatim>

| ==ArcSelector== | ==npaths== |  ==RandEquivalent(A, B)== |
| =UniformArcSelector= |    =10= |   =false=   |
| =LogProbArcSelector= |    =10= |   =true=   |
| ^ |    =1000000= |   =false=   |

---++ See Also

[[EqualDoc][Equal]], [[EquivalentDoc][Equivalent]], [[IsomorphicDoc][Isomorphic]]

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
png	randequiv2.png	r3 r2 r1	manage	11.1 K	2009-03-27 - 20:38	CyrilAllauzen	RandEquivalent: second input FST
png	randequiv1.png	r4 r3 r2 r1	manage	11.3 K	2009-03-27 - 20:17	CyrilAllauzen	RandEquivalent: first input FST

Topic revision: r3 - 2018-04-27 - MichaelRiley