Package nltk_lite :: Package contrib :: Package fst :: Module fst :: Class FST
[hide private]
[frames] | no frames]

Class FST

source code

object --+
         |
        FST

A finite state transducer. Each state is uniquely identified by a label, which is typically a string name or an integer id. A state's label is used to access and modify the state. Similarly, each arc is uniquely identified by a label, which is used to access and modify the arc.

The set of arcs pointing away from a state are that state's outgoing arcs. The set of arcs pointing to a state are that state's incoming arcs. The state at which an arc originates is that arc's source state (or src), and the state at which it terminates is its destination state (or dst).

It is possible to define an FST object with no initial state. This is represented by assigning a value of None to the initial_state variable. FSTs with no initial state are considered to encode an empty mapping. I.e., transducing any string with such an FST will result in failure.

Instance Methods [hide private]
 
__init__(self, label)
Create a new finite state transducer, containing no states.
source code

Inherited from object: __delattr__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__

    State Information
 
states(self)
Return an iterator that will generate the state label of each state in this FST.
source code
 
has_state(self, label)
Return true if this FST contains a state with the given label.
source code
 
_get_initial_state(self) source code
 
_set_initial_state(self, label) source code
 
incoming(self, state)
Return an iterator that will generate the incoming transition arcs for the given state.
source code
 
outgoing(self, state)
Return an iterator that will generate the outgoing transition arcs for the given state.
source code
 
is_final(self, state)
Return true if the state with the given state label is final.
source code
 
finalizing_string(self, state)
Return the output string associated with the given final state.
source code
 
state_descr(self, state)
Return the description for the given state, if it has one; or None, otherwise.
source code
    Transition Arc Information
 
arcs(self)
Return an iterator that will generate the arc label of each transition arc in this FST.
source code
 
src(self, arc)
Return the state label of this transition arc's source state.
source code
 
dst(self, arc)
Return the state label of this transition arc's destination state.
source code
 
in_string(self, arc)
Return the given transition arc's input string, a (possibly empty) tuple of input symbols.
source code
 
out_string(self, arc)
Return the given transition arc's output string, a (possibly empty) tuple of output symbols.
source code
 
arc_descr(self, arc)
Return the description for the given transition arc, if it has one; or None, otherwise.
source code
 
arc_info(self, arc)
Return a tuple (src, dst, in_string, out_string) for the given arc, where:
source code
    FST Information
 
is_sequential(self)
Return true if this FST is sequential.
source code
 
is_subsequential(self)
Return true if this FST is subsequential.
source code
    State Modification
 
add_state(self, label=None, is_final=True, finalizing_string=(), descr=None)
Create a new state, and return its label.
source code
 
del_state(self, label)
Delete the state with the given label.
source code
 
set_final(self, state, is_final=True)
If is_final is true, then make the state with the given label final; if is_final is false, then make the state with the given label non-final.
source code
 
set_finalizing_string(self, state, finalizing_string)
Set the given state's finalizing string.
source code
 
set_descr(self, state, descr)
Set the given state's description string.
source code
 
dup_state(self, orig_state, label=None)
Duplicate an existing state.
source code
    Transition Arc Modification
 
add_arc(self, src, dst, in_string, out_string, label=None, descr=None)
Create a new transition arc, and return its label.
source code
 
del_arc(self, label)
Delete the transition arc with the given label.
source code
    Transformations
 
inverted(self)
Swap all in_string/out_string pairs.
source code
 
reversed(self)
Reverse the direction of all transition arcs.
source code
 
trimmed(self) source code
 
relabeled(self, label=None, relabel_states=True, relabel_arcs=True)
Return a new FST that is identical to this FST, except that all state and arc labels have been replaced with new labels.
source code
 
_relabel_state_ids(self, state, ids)
A helper function for relabel(), which decides which new label should be assigned to each state.
source code
 
determinized(self, label=None)
Return a new FST which defines the same mapping as this FST, but is determinized.
source code
 
_all_equal(self, lst)
Return true if all elements in the list are equal
source code
 
_common_prefix(self, sequences)
Return the longest sequence that is a prefix of all of the given sequences.
source code
    Misc
 
copy(self, label=None) source code
 
__str__(self)
str(x)
source code
 
dotgraph(self)
Return an AT&T graphviz dot graph.
source code
    Transduction
 
transduce_subsequential(self, input, step=True) source code
 
step_transduce_subsequential(self, input, step=True)
This is implemented as a generator, to make it easier to support stepping.
source code
 
transduce(self, input) source code
 
step_transduce(self, input, step=True)
This is implemented as a generator, to make it easier to support stepping.
source code
    Helper Functions
 
_pick_label(self, label, typ, used_labels)
Helper function for add_state and add_arc that chooses a label for a new state or arc.
source code
Static Methods [hide private]
    Misc
 
load(filename) source code
 
parse(label, s) source code
Instance Variables [hide private]
  label
A label identifying this FST.
    State Information
  _initial_state
The label of the initial state, or None if this FST does not have an initial state.
  _incoming
A dictionary mapping state labels to lists of incoming transition arc labels.
  _outgoing
A dictionary mapping state labels to lists of outgoing transition arc labels.
  _is_final
A dictionary mapping state labels to boolean values, indicating whether the state is final.
  _finalizing_string
A dictionary mapping state labels of final states to output strings.
  _state_descr
A dictionary mapping state labels to (optional) state descriptions.
    Transition Arc Information
  _src
A dictionary mapping each transition arc label to the label of its source state.
  _dst
A dictionary mapping each transition arc label to the label of its destination state.
  _in_string
A dictionary mapping each transition arc label to its input string, a (possibly empty) tuple of input symbols.
  _out_string
A dictionary mapping each transition arc label to its output string, a (possibly empty) tuple of input symbols.
  _arc_descr
A dictionary mapping transition arc labels to (optional) arc descriptions.
Properties [hide private]

Inherited from object: __class__

    State Information
  initial_state
The label of the initial state (R/W).
Method Details [hide private]

__init__(self, label)
(Constructor)

source code 

Create a new finite state transducer, containing no states.

Overrides: object.__init__

incoming(self, state)

source code 

Return an iterator that will generate the incoming transition arcs for the given state. The effects of modifying the FST's state while iterating are undefined, so if you plan to modify the state, you should copy the incoming transition arcs into a list first.

outgoing(self, state)

source code 

Return an iterator that will generate the outgoing transition arcs for the given state. The effects of modifying the FST's state while iterating are undefined, so if you plan to modify the state, you should copy the outgoing transition arcs into a list first.

finalizing_string(self, state)

source code 

Return the output string associated with the given final state. If the FST terminates at this state, then this string will be emitted.

arc_info(self, arc)

source code 

Return a tuple (src, dst, in_string, out_string) for the given arc, where:

  • src is the label of the arc's source state.
  • dst is the label of the arc's destination state.
  • in_string is the arc's input string.
  • out_string is the arc's output string.

add_state(self, label=None, is_final=True, finalizing_string=(), descr=None)

source code 

Create a new state, and return its label. The new state will have no incoming or outgoing arcs. If label is specified, then it will be used as the state's label; otherwise, a new unique label value will be chosen. The new state will be final iff is_final is true. descr is an optional description string for the new state.

Arguments should be specified using keywords!

del_state(self, label)

source code 

Delete the state with the given label. This will automatically delete any incoming or outgoing arcs attached to the state.

dup_state(self, orig_state, label=None)

source code 

Duplicate an existing state. I.e., create a new state s such that:

  • s is final iff orig_state is final.
  • If orig_state is final, then s.finalizing_string is copied from orig_state
  • For each outgoing arc from orig_state, s has an outgoing arc with the same input string, output string, and destination state.

Note that if orig_state contained self-loop arcs, then the corresponding arcs in s will point to orig_state (i.e., they will not be self-loop arcs).

The state description is not copied.

Parameters:
  • label - The label for the new state. If not specified, a unique integer will be used.

add_arc(self, src, dst, in_string, out_string, label=None, descr=None)

source code 

Create a new transition arc, and return its label.

Arguments should be specified using keywords!

Parameters:
  • src - The label of the source state.
  • dst - The label of the destination state.
  • in_string - The input string, a (possibly empty) tuple of input symbols. Input symbols should be hashable immutable objects.
  • out_string - The output string, a (possibly empty) tuple of output symbols. Output symbols should be hashable immutable objects.

relabeled(self, label=None, relabel_states=True, relabel_arcs=True)

source code 

Return a new FST that is identical to this FST, except that all state and arc labels have been replaced with new labels. These new labels are consecutive integers, starting with zero.

Parameters:
  • relabel_states - If false, then don't relabel the states.
  • relabel_arcs - If false, then don't relabel the arcs.

determinized(self, label=None)

source code 

Return a new FST which defines the same mapping as this FST, but is determinized.

The algorithm used is based on [...].

Raises:
  • ValueError - If the determinization algorithm was unable to determinize this FST. Typically, this happens because a precondition is not met.
Requires:
  • All arcs in this FST must have exactly one input symbol.
  • The mapping defined by this FST must be deterministic.

__str__(self)
(Informal representation operator)

source code 

str(x)

Overrides: object.__str__
(inherited documentation)

Instance Variable Details [hide private]

label

A label identifying this FST. This is used for display & debugging purposes only.

_finalizing_string

A dictionary mapping state labels of final states to output strings. This string should be added to the output if the FST terminates at this state.


Property Details [hide private]

initial_state

The label of the initial state (R/W).

Get Method:
_get_initial_state(self)
Set Method:
_set_initial_state(self, label)