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 RandGen operation.


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);
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);
fstequivalent --random [-npath=$n] [--delta=$delta] [--seed=$seed] [--max_length=$max_length] in1.fst in2.fst


randequiv1.png randequiv2.png

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

fstequivalent --random --npath=$npaths a.fst b.fst

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

See Also

Equal, Equivalent, Isomorphic

Topic attachments
I Attachment History Action Size Date Who Comment
PNGpng randequiv1.png r4 r3 r2 r1 manage 11.3 K 2009-03-27 - 20:17 CyrilAllauzen RandEquivalent: first input FST
PNGpng randequiv2.png r3 r2 r1 manage 11.1 K 2009-03-27 - 20:38 CyrilAllauzen RandEquivalent: second input FST
Topic revision: r2 - 2014-04-23 - MichaelRiley
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback