Difference: DisambiguateDoc (1 vs. 7)

Revision 72018-04-27 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Disambiguate

Line: 17 to 17
 |
template <class Arc>
void Disambiguate(const Fst<Arc> &ifst, MutableFst<Arc> *ofst);
Changed:
<
<
| doc [bad link?] |
>
>
|
 

Examples

Revision 62014-05-20 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Disambiguate

Line: 56 to 56
 

References

Changed:
<
<
>
>
 
META FILEATTACHMENT attachment="disamb1.jpg" attr="" comment="" date="1398209152" name="disamb1.jpg" path="disamb1.jpg" size="16427" user="MichaelRiley" version="2"
META FILEATTACHMENT attachment="disamb2.jpg" attr="" comment="" date="1398209172" name="disamb2.jpg" path="disamb2.jpg" size="13114" user="MichaelRiley" version="1"

Revision 52014-04-24 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"
Changed:
<
<

Disambiguate Work in progress, under construction

>
>

Disambiguate

 

Description

This operation disambiguates a weighted transducer. The result will be

Revision 42014-04-23 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Disambiguate Work in progress, under construction

Line: 47 to 47
 
  • Disambiguate: exponential (polynomial in the size of the output)
  • Non-disambiguable: does not terminate
Changed:
<
<
The disambiguable automata include all unweighted and all acyclic input. There are disambiguable automata that are not determinizable.
>
>
The disambiguable automata include all unweighted, all acyclic and all determinizable input. There are disambiguable automata that are not determinizable.

See Also

Determinize, RmEpsilon

 

References

Revision 32014-04-23 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Disambiguate Work in progress, under construction

Line: 40 to 40
  disamb3.jpg
Changed:
<
<
(For comparison since deterministic implies unambiguous.)
>
>
(For comparison since deterministic implies unambiguous.)
 

Complexity

Disambiguate:

Revision 22014-04-23 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Disambiguate Work in progress, under construction

Line: 40 to 40
  disamb3.jpg
Changed:
<
<
(For comparison)
>
>
(For comparison since deterministic implies unambiguous.)
 

Complexity

Disambiguate:
  • Disambiguate: exponential (polynomial in the size of the output)
  • Non-disambiguable: does not terminate
Changed:
<
<
The disambiguable automata include all unweighted and all acyclic input.
>
>
The disambiguable automata include all unweighted and all acyclic input. There are disambiguable automata that are not determinizable.
 

References

Revision 12014-04-22 - MichaelRiley

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="FstQuickTour"

Disambiguate Work in progress, under construction

Description

This operation disambiguates a weighted transducer. The result will be an equivalent FST that has the property that no two successful paths have the same input labeling. For this algorithm, epsilon transitions are treated as regular symbols (cf. RmEpsilon).

The transducer must be functional. The weights must be (weakly) left divisible (valid for TropicalWeight and LogWeight for instance) and zero-sum-free.

Usage

template <class Arc>
void Disambiguate(const Fst<Arc> &ifst, MutableFst<Arc> *ofst);
doc [bad link?]

Examples

A:

disamb1.jpg

(TropicalWeight)

Disambiguate of A:

disamb2.jpg

Disambiguate(A, &out);
fstdisambiguate a.fst out.fst

Determinize of A:

disamb3.jpg

(For comparison)

Complexity

Disambiguate:
  • Disambiguate: exponential (polynomial in the size of the output)
  • Non-disambiguable: does not terminate

The disambiguable automata include all unweighted and all acyclic input.

References

META FILEATTACHMENT attachment="disamb1.jpg" attr="" comment="" date="1398209152" name="disamb1.jpg" path="disamb1.jpg" size="16427" user="MichaelRiley" version="2"
META FILEATTACHMENT attachment="disamb2.jpg" attr="" comment="" date="1398209172" name="disamb2.jpg" path="disamb2.jpg" size="13114" user="MichaelRiley" version="1"
META FILEATTACHMENT attachment="disamb3.jpg" attr="" comment="" date="1398209221" name="disamb3.jpg" path="disamb3.jpg" size="25857" user="MichaelRiley" version="1"
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback