Difference: ComposeDoc (20 vs. 21)

Revision 212012-01-19 - MichaelRiley

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

Compose

Line: 74 to 74
 Compose and fstcompose trim their output, ComposeFst does not (since it is a delayed operation).

The efficiency of composition can be strongly affected by several factors:

Changed:
<
<
  • the choice of which transducer is sorted - prefer sorting the FST that has the greater average out-degree;
  • the amount of non-determinism;
>
>
  • the choice of which transducer is sorted
    • prefer sorting the FST that has the greater average out-degree
    • sorting both transducers allows composition to automatically select the best transducer to match against (per state pair)
    • note stored sort properties of the FSTs are first checked in constant time followed by the minimum number of linear-time sort tests necessary to discover one sorted FST; thus composition may be unaware that both FSTs are sorted when those properties are not stored.
  • the amount of non-determinism
 
  • the presence and location of epsilon transitions - avoid epsilon transitions on the output side of the first transducer or the input side of the second transducer or prefer placing them later in a path since they
Changed:
<
<
delay matching and can introduce non-coaccessible states and transitions.
>
>
delay matching and can introduce non-coaccessible states and transitions
  -- MichaelRiley - 15 Jun 2007
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback