Transducer Layer


Datatypes



typedef TransducerHandle TransducerHandle
 A finite state transducer (FST).

Constructive and Destructive Functions for Elementary Transducers

TransducerHandle create_empty_transducer ()
 Create an empty transducer.
TransducerHandle create_epsilon_transducer ()
 Create an epsilon transducer.
TransducerHandle define_transducer (Key k)
 Create a transducer that accepts one occurrence of key identity pair k:k.
TransducerHandle define_transducer (KeyPair *p)
 Create a transducer that accepts one occurrence of key pair p.
TransducerHandle define_transducer (KeySet *ss)
 Create a transducer that accepts the union of the key identity pairs in a set ss.
TransducerHandle define_transducer (KeyPairSet *Pi)
 Create a transducer that accepts the union of the key pairs in a set Pi.
void display_symbols (TransducerHandle t)
KeyPairSetdefine_keypair_set (TransducerHandle t)
 Define a set of pairs by collecting all key pairs in transducer t.
KeySetdefine_key_set (TransducerHandle t)
 Define a set of keys by collecting all keys in transducer t.
TransducerHandle add_weight (TransducerHandle t, float w)
 Add weight w to transducer t.
void delete_transducer (TransducerHandle t)
 Delete transducer t.

Basic Algebraic Functions

TransducerHandle compose (TransducerHandle t1, TransducerHandle t2, bool destructive=true)
 Composition of t1 and t2.
TransducerHandle concatenate (TransducerHandle t1, TransducerHandle t2)
 Concatenation of t1 and t2.
TransducerHandle copy (TransducerHandle t)
 A deep copy of t.
TransducerHandle disjunct (TransducerHandle t1, TransducerHandle t2)
 Disjunction of t1 and t2.
TransducerHandle disjunct_transducers_as_tries (TransducerHandle t1, TransducerHandle t2)
 Disjunction of t1 and t2 that are both tries. The resulting transducer is also a trie.
TransducerHandle disjunct_as_trie (TransducerHandle t, KeyVector *key_string, float weight=0)
 Add the KeyVector * key_string as a path to the trie t.
TransducerHandle disjunct_as_trie (TransducerHandle t, KeyPairVector *key_pair_string, float weight=0)
 Add the KeyPairVector * key_pair_string as a path to the trie t.
TransducerHandle extract_input_language (TransducerHandle t)
 Extract the input language of t.
TransducerHandle extract_output_language (TransducerHandle t)
 Extract the output language of t.
TransducerHandle intersect (TransducerHandle t1, TransducerHandle t2)
 Intersection of t1 and t2.
TransducerHandle intersecting_composition (TransducerHandle t, vector< TransducerHandle > *v)
 The intersecting composition of t with the transducers in v.
TransducerHandle invert (TransducerHandle t)
 Switch input and output in the pairs of transducer t.
TransducerHandle negate (TransducerHandle t, KeyPairSet *Pi)
 Complement of t with regard to a set of key pairs Pi.
TransducerHandle optionalize (TransducerHandle t)
 Disjunction of t and epsilon.
TransducerHandle repeat_le_n (TransducerHandle t, int n)
 Transducer t repeated at most n times.
TransducerHandle repeat_n (TransducerHandle t, int n)
 t catenated n times.
TransducerHandle repeat_plus (TransducerHandle t)
 Transducer t +.
TransducerHandle repeat_star (TransducerHandle t)
 Transducer t *.
TransducerHandle reverse (TransducerHandle t)
 Reverse transducer t.
TransducerHandle subtract (TransducerHandle t1, TransducerHandle t2)
 t1 minus t2.

Substitution, Insertion and Removal functions

TransducerHandle add_input_language (TransducerHandle t, KeyPairSet *Pi)
 Add input language to t using a set of feasible pairs in Pi.
TransducerHandle add_output_language (TransducerHandle t, KeyPairSet *Pi)
 Add output language to t using a set of feasible pairs in Pi.
TransducerHandle insert_freely (TransducerHandle t, KeyPair *p)
 Freely insert key pair p into t.
TransducerHandle remove_pair (TransducerHandle t, KeyPair *p)
 Remove transitions that are equal to key pair p.
TransducerHandle remove_pairs (TransducerHandle t, KeySet *ss)
 Remove transitions where a key from ss is used on both the input and output sides.
TransducerHandle shuffle (TransducerHandle t1, TransducerHandle t2)
 Shuffle t1 and t2.
TransducerHandle substitute_key (TransducerHandle t, Key k1, Key k2)
 In all transitions, substitute key k1 with key k2.
TransducerHandle substitute_key (TransducerHandle t, KeySet *ks, Key k2)
 In all transitions, if a key is equal to some key in key set ks, substitute it with key k2.
TransducerHandle substitute_with_pair (TransducerHandle t, KeyPair *p1, KeyPair *p2)
 Substitute all transitions equal to p1 with a copy of p2.
TransducerHandle substitute_with_transducer (TransducerHandle t, KeyPair *p, TransducerHandle tr)
 Substitute all transitions in transducer t equal to p with a copy of transducer tr.

Optimizing and Converting Functions

TransducerHandle determinize (TransducerHandle t)
 Determinize t.
vector< TransducerHandlefind_all_paths (TransducerHandle t, bool unique=false)
 Find all paths from initial to final state in transducer t.
TransducerHandle find_best_paths (TransducerHandle t, int n, bool unique=false)
 n best paths from initial to final state in transducer t. unique defines whether equal paths are included only once.
TransducerHandle minimize (TransducerHandle t)
 Minimize t.
TransducerHandle push_weights (TransducerHandle t, bool initial)
 Push weights in transducer t towards the initial state, if initial is true, otherwise towards the final state.
TransducerHandle remove_epsilons (TransducerHandle t)
 Remove transitions whose input and output labels are epsilons from t.

Testing Functions

bool are_equivalent (TransducerHandle t1, TransducerHandle t2)
 Whether t1 and t2 are equivalent.
bool are_disjoint (TransducerHandle t1, TransducerHandle t2)
 Whether t1 and t2 have an empty intersection.
float get_weight (TransducerHandle t)
 The total weight of one-path transducer t.
bool is_automaton (TransducerHandle t)
 Whether for every transition in t the input symbol is the same as the output symbol.
bool is_cyclic (TransducerHandle t)
 Whether t is cyclic.
bool is_deterministic (TransducerHandle t)
 Whether t is deterministic.
bool is_empty (TransducerHandle t)
 Whether t is the empty transducer.
bool is_epsilon (TransducerHandle t)
 Whether t is the epsilon transducer.
bool is_minimal (TransducerHandle t)
 Whether t is a minimal transducer.
bool is_subset (TransducerHandle t1, TransducerHandle t2)
 Whether t1 is a subset of t2.

Input/Output Functions

Transducers in this layer are not aware of any restrictions to their alphabet or any attributes. Thus the file format for these transducers neither list the known keys nor the properties of the transducer.

int read_format (istream &is=cin)
 Read the format of the next transducer in the input stream is.
TransducerHandle read_transducer (istream &is=cin)
 Read transducer in binary form from input stream is.
TransducerHandle read_transducer (const char *filename)
 Read a binary transducer from file filename.
TransducerHandle read_transducer_number (istream &is)
 Read a transducer in AT&T number format from file.
void write_transducer (TransducerHandle t, ostream &os=cout, bool backwards_compatibility=false)
 Write Transducer t in binary form to ostream os.
void write_transducer (TransducerHandle t, const char *filename, bool backwards_compatibility=false)
 Write transducer t to file filename.
void write_runtime_transducer (TransducerHandle t, KeyTable *kt, FILE *output_file, char *symbol_file_name)
 Write a transducer t with key table kt into file output_file. Write its symbols into the file with name symbol_file_name.
TransducerHandle read_runtime_transducer (FILE *f)
void print_transducer_number (TransducerHandle t, bool print_weights=true, ostream &os=cout)
 Print transducer in number format to ostream os. print_weights defines whether weights are printed.

Functions

KeyVectorVectorlookup_all (TransducerHandle t, vector< Key > *input_string)
 Look up the output-strings corresponding to string input_string. Return NULL, if there are no output-strings for input-string.
KeyVectorlookup_first (TransducerHandle t, vector< Key > *input_string)
 Look up the first found output-string corresponding to string input_string. Return NULL, if there are no output-strings for input-string.

Detailed Description

Datatypes and functions related to transducer calculus and support. This layer depends on the Key Layer .

Typedef Documentation

A finite state transducer (FST).

A transducer is a weighted or unweighted synchronic finite-state transducer i.e. an automaton representing a set of strings of symbol pairs.

Definition at line 21 of file transducer-layer.h.


Function Documentation

TransducerHandle add_input_language ( TransducerHandle  t,
KeyPairSet Pi 
)

Add input language to t using a set of feasible pairs in Pi.

Equal to a composition of transducer t and a transducer accepting any number of pairs in Pi.

TransducerHandle add_output_language ( TransducerHandle  t,
KeyPairSet Pi 
)

Add output language to t using a set of feasible pairs in Pi.

Equal to a composition of a transducer accepting any number of pairs in Pi and transducer t.

TransducerHandle add_weight ( TransducerHandle  t,
float  w 
)

Add weight w to transducer t.

Set the weight of all final states in transducer t to w.

Note:
Does nothing if the underlying library does not support weights.

bool are_disjoint ( TransducerHandle  t1,
TransducerHandle  t2 
)

Whether t1 and t2 have an empty intersection.

bool are_equivalent ( TransducerHandle  t1,
TransducerHandle  t2 
)

Whether t1 and t2 are equivalent.

The same that has been said of alignment in function intersect goes for are_equivalent. For example, both [a:b] and [a:0 0:b] map the string "a" to "b", but they are not equivalent because the alignment is different.

Postcondition:
t1 and t2 are not deleted.

TransducerHandle compose ( TransducerHandle  t1,
TransducerHandle  t2,
bool  destructive = true 
)

Composition of t1 and t2.

Parameters:
destructive Whether the argument transducers are deleted.
Composition of t1 and t2 maps "a" to "c" iff t1 maps "a" to some "b" and t2 maps "b" to "c".

Determinizing or minimizing the arguments makes composition computationally easier, at least in HWFST.

Postcondition:
The resulting transducer may be nondeterministic and not minimal. t1 and t2 are deleted.

TransducerHandle concatenate ( TransducerHandle  t1,
TransducerHandle  t2 
)

Concatenation of t1 and t2.

If t1 maps the string "a" to "b" and t2 maps "c" to "d", then concatenation of t1 and t2 maps the string "ac" to "bd".

Postcondition:
The resulting transducer may contain epsilons and be nondeterministic and not minimal. t1 and t2 are deleted.

A deep copy of t.

Postcondition:
t is not deleted.

TransducerHandle create_empty_transducer (  ) 

Create an empty transducer.

Returns:
A transducer that has one state that is not final and has no transitions, i.e. does not accept any string.

TransducerHandle create_epsilon_transducer (  ) 

Create an epsilon transducer.

Returns:
A transducer that has one state that is final and has no transitions, i.e. accepts the epsilon.

KeySet* define_key_set ( TransducerHandle  t  ) 

Define a set of keys by collecting all keys in transducer t.

Returns:
A set of keys that contains all keys (excluding epsilon) that occur in transitions of transducer t.

KeyPairSet* define_keypair_set ( TransducerHandle  t  ) 

Define a set of pairs by collecting all key pairs in transducer t.

Returns:
A set of pairs that contains all key pairs (excluding epsilon pairs) that occur in transitions of transducer t.

TransducerHandle define_transducer ( KeyPairSet Pi  ) 

Create a transducer that accepts the union of the key pairs in a set Pi.

Returns:
A disjunction of all key pairs in Pi.

TransducerHandle define_transducer ( KeySet ss  ) 

Create a transducer that accepts the union of the key identity pairs in a set ss.

Returns:
A disjunction of all key identity pairs in ss.

TransducerHandle define_transducer ( KeyPair p  ) 

Create a transducer that accepts one occurrence of key pair p.

Returns:
A transducer that has one transition of key pair p.

TransducerHandle define_transducer ( Key  k  ) 

Create a transducer that accepts one occurrence of key identity pair k:k.

Returns:
A transducer that has one transition of key identity pair k:k.

void delete_transducer ( TransducerHandle  t  ) 

Delete transducer t.

TransducerHandle determinize ( TransducerHandle  t  ) 

Determinize t.

Remove transitions whose input and output symbols are epsilons from t and determinize it. After determinization no state in t has two transitions with equal input and output labels.

Postcondition:
t is deleted.

Disjunction of t1 and t2.

Disjunction of t1 and t2 maps "a" to "b" iff t1 and/or t2 maps "a" to "b".

Postcondition:
t1 and t2 are deleted. The resulting transducer may have epsilons.

TransducerHandle disjunct_as_trie ( TransducerHandle  t,
KeyPairVector key_pair_string,
float  weight = 0 
)

Add the KeyPairVector * key_pair_string as a path to the trie t.

TransducerHandle disjunct_as_trie ( TransducerHandle  t,
KeyVector key_string,
float  weight = 0 
)

Add the KeyVector * key_string as a path to the trie t.

TransducerHandle disjunct_transducers_as_tries ( TransducerHandle  t1,
TransducerHandle  t2 
)

Disjunction of t1 and t2 that are both tries. The resulting transducer is also a trie.

TransducerHandle extract_input_language ( TransducerHandle  t  ) 

Extract the input language of t.

Maps "A" to "A" iff t maps "A" to some string "B". For example the argument transducer [ a:b [c:d | e:f] ] gives the result [ a:a [c:c | e:e] ].

Postcondition:
t is deleted.

TransducerHandle extract_output_language ( TransducerHandle  t  ) 

Extract the output language of t.

Maps "B" to "B" iff t maps some string "A" to "B". For example the argument transducer [ a:b [c:d | e:f] ] gives the result [ b:b [d:d | f:f] ].

Postcondition:
t is deleted.

vector<TransducerHandle> find_all_paths ( TransducerHandle  t,
bool  unique = false 
)

Find all paths from initial to final state in transducer t.

TransducerHandle find_best_paths ( TransducerHandle  t,
int  n,
bool  unique = false 
)

n best paths from initial to final state in transducer t. unique defines whether equal paths are included only once.

Returns n paths with smallest weight. If t is unweighted, returns n paths that are found first (not necessarily the shortest ones).

Parameters:
t The transducer where best paths are searched. Can be cyclic.
n Number of paths that are returned.
unique Whether equal paths are included only once.
Returns:
A disjunction of n best paths.

float get_weight ( TransducerHandle  t  ) 

The total weight of one-path transducer t.

In HWFST: The sum of all transition weights and the final weight in transducer t. In HFST: Returns always zero.

TransducerHandle insert_freely ( TransducerHandle  t,
KeyPair p 
)

Freely insert key pair p into t.

For example, freely inserting the key pair x:y into the transducer [a b] is equivalent to [x:y]* a [x:y]* b [x:y]*.

Postcondition:
t is deleted.

Intersection of t1 and t2.

Maps string S_1 to string S_2 (length of both strings is n) iff both t1 and t2 map S_1 to S_2 by aligning the i:th symbol in S_1 with the i:th symbol in S_2 for all i in n.

For example, [a:b] and [a:0 0:b] both map a to b, but their intersection is empty because the alignment is different.

Postcondition:
t1 and t2 are deleted.

TransducerHandle intersecting_composition ( TransducerHandle  t,
vector< TransducerHandle > *  v 
)

The intersecting composition of t with the transducers in v.

Intersecting composition of the transducer t and the transducers in the vector v is equivalent to the composition of t with the intersection of the transducers in v.

Postcondition:
The transducer t is deleted.

The transducers in the vector v are deleted.

The vector v is deleted.

The result is not minimized.

TransducerHandle invert ( TransducerHandle  t  ) 

Switch input and output in the pairs of transducer t.

Inversion of t maps "A" to "B" iff t maps "B" to "A". For example inversion of [a:b c:d e:f] is [b:a d:c f:e].

Postcondition:
t is deleted.

bool is_automaton ( TransducerHandle  t  ) 

Whether for every transition in t the input symbol is the same as the output symbol.

Postcondition:
t is not deleted.

bool is_cyclic ( TransducerHandle  t  ) 

Whether t is cyclic.

Postcondition:
t is not deleted.

bool is_deterministic ( TransducerHandle  t  ) 

Whether t is deterministic.

bool is_empty ( TransducerHandle  t  ) 

Whether t is the empty transducer.

t is the empty transducer if t has one state that is not final and has no transitions.

Postcondition:
t is not deleted.

bool is_epsilon ( TransducerHandle  t  ) 

Whether t is the epsilon transducer.

t is the epsilon transducer if it has one state that is final and has no transitions.

Postcondition:
t is not deleted.

bool is_minimal ( TransducerHandle  t  ) 

Whether t is a minimal transducer.

bool is_subset ( TransducerHandle  t1,
TransducerHandle  t2 
)

Whether t1 is a subset of t2.

KeyVectorVector* lookup_all ( TransducerHandle  t,
vector< Key > *  input_string 
)

Look up the output-strings corresponding to string input_string. Return NULL, if there are no output-strings for input-string.

KeyVector* lookup_first ( TransducerHandle  t,
vector< Key > *  input_string 
)

Look up the first found output-string corresponding to string input_string. Return NULL, if there are no output-strings for input-string.

TransducerHandle minimize ( TransducerHandle  t  ) 

Minimize t.

Remove epsilons from t and determinize and minimize it.

Postcondition:
t is deleted.
See also:
remove_epsilons determinize

TransducerHandle negate ( TransducerHandle  t,
KeyPairSet Pi 
)

Complement of t with regard to a set of key pairs Pi.

Complement is computed by subtraction: ~t = [.*] - t

Complement of transducer [t] maps the string 'a_1a_2 ... a_n' to 'b_1b_2 ... b_n' iff Pi contains 'a_i:b_i' for all 1 <= i <= n, and t & [a_1:b_1 a_2:b_2 ... a_n:b_n] is the empty transducer. Either a_i or b_i is allowed to be the empty symbol.

The same that has been said of alignment in function intersect goes for negation. For example, both [a:b] and [a:0 0:b] map the string "a" to "b", but the complement of [a:b] nevertheless includes 'a:0 0:b' because the alignment is different.

Postcondition:
t is deleted.

TransducerHandle optionalize ( TransducerHandle  t  ) 

Disjunction of t and epsilon.

Postcondition:
t is deleted.

void print_transducer_number ( TransducerHandle  t,
bool  print_weights = true,
ostream &  os = cout 
)

Print transducer in number format to ostream os. print_weights defines whether weights are printed.

See also:
print_transducer

TransducerHandle push_weights ( TransducerHandle  t,
bool  initial 
)

Push weights in transducer t towards the initial state, if initial is true, otherwise towards the final state.

Note:
Does nothing if the underlying implementation does not support weights.

int read_format ( istream &  is = cin  ) 

Read the format of the next transducer in the input stream is.

Returns:
  • 0 == ordinary unweighted transducer (HFST)
  • 1 == weighted transducer (HWFST)
  • 2 == compact unweighted transducer (HFST)
  • -1 == the end of file has been reached
  • -2 == transducer format is unknown or an error has occurred
Postcondition:
is is not changed.

TransducerHandle read_transducer ( const char *  filename  ) 

Read a binary transducer from file filename.

TransducerHandle read_transducer ( istream &  is = cin  ) 

Read transducer in binary form from input stream is.

TransducerHandle read_transducer_number ( istream &  is  ) 

Read a transducer in AT&T number format from file.

See also:
read_transducer_text

TransducerHandle remove_epsilons ( TransducerHandle  t  ) 

Remove transitions whose input and output labels are epsilons from t.

Create an equivalent transducer that has no transitions whose input and output labels are epsilons.

TransducerHandle remove_pair ( TransducerHandle  t,
KeyPair p 
)

Remove transitions that are equal to key pair p.

TransducerHandle remove_pairs ( TransducerHandle  t,
KeySet ss 
)

Remove transitions where a key from ss is used on both the input and output sides.

TransducerHandle repeat_le_n ( TransducerHandle  t,
int  n 
)

Transducer t repeated at most n times.

TransducerHandle repeat_n ( TransducerHandle  t,
int  n 
)

t catenated n times.

Parameters:
t Transducer to be catenated.
n How many times t is catenated. If n == 0, an epsilon transducer is returned.
Postcondition:
t is not deleted. [actually it cannot be used]

TransducerHandle repeat_plus ( TransducerHandle  t  ) 

Transducer t +.

Transducer that accepts one or more t.

Postcondition:
t is deleted.

TransducerHandle repeat_star ( TransducerHandle  t  ) 

Transducer t *.

Transducer that accepts any number of t.

Postcondition:
t is deleted.

TransducerHandle reverse ( TransducerHandle  t  ) 

Reverse transducer t.

Shuffle t1 and t2.

...

TransducerHandle substitute_key ( TransducerHandle  t,
KeySet ks,
Key  k2 
)

In all transitions, if a key is equal to some key in key set ks, substitute it with key k2.

TransducerHandle substitute_key ( TransducerHandle  t,
Key  k1,
Key  k2 
)

In all transitions, substitute key k1 with key k2.

TransducerHandle substitute_with_pair ( TransducerHandle  t,
KeyPair p1,
KeyPair p2 
)

Substitute all transitions equal to p1 with a copy of p2.

TransducerHandle substitute_with_transducer ( TransducerHandle  t,
KeyPair p,
TransducerHandle  tr 
)

Substitute all transitions in transducer t equal to p with a copy of transducer tr.

t1 minus t2.

t1 minus t2 is the transducer which accepts the strings accepted by t1 that are not accepted by t2. The same that has been said of alignment in function intersect goes for subtraction.

For example, both [a:b] and [a:0 0:b] map the string a to b, but the result of a:b - [a:0 0:b] is nevertheless [a:b] because the alignment is different.

Postcondition:
t1 and t2 are deleted.

void write_runtime_transducer ( TransducerHandle  t,
KeyTable kt,
FILE *  output_file,
char *  symbol_file_name 
)

Write a transducer t with key table kt into file output_file. Write its symbols into the file with name symbol_file_name.

void write_transducer ( TransducerHandle  t,
const char *  filename,
bool  backwards_compatibility = false 
)

Write transducer t to file filename.

void write_transducer ( TransducerHandle  t,
ostream &  os = cout,
bool  backwards_compatibility = false 
)

Write Transducer t in binary form to ostream os.


Generated on Fri Mar 27 12:56:17 2009 for Helsinki Finite-State Transducer Technology (HFST) interface by  doxygen 1.5.6