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) |
KeyPairSet * | define_keypair_set (TransducerHandle t) |
Define a set of pairs by collecting all key pairs in transducer t. | |
KeySet * | define_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< 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. | |
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 | |
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. |
typedef TransducerHandle TransducerHandle |
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.
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.
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.
TransducerHandle compose | ( | TransducerHandle | t1, | |
TransducerHandle | t2, | |||
bool | destructive = true | |||
) |
Composition of t1 and t2.
destructive | Whether the argument transducers are deleted. |
Determinizing or minimizing the arguments makes composition computationally easier, at least in HWFST.
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".
TransducerHandle copy | ( | TransducerHandle | t | ) |
A deep copy of t.
TransducerHandle create_empty_transducer | ( | ) |
Create an empty transducer.
TransducerHandle create_epsilon_transducer | ( | ) |
Create an epsilon transducer.
KeySet* define_key_set | ( | TransducerHandle | t | ) |
Define a set of keys by collecting all keys in transducer t.
KeyPairSet* define_keypair_set | ( | TransducerHandle | t | ) |
Define a set of pairs by collecting all key pairs in transducer t.
TransducerHandle define_transducer | ( | KeyPairSet * | Pi | ) |
Create a transducer that accepts the union of the key pairs in a set Pi.
TransducerHandle define_transducer | ( | KeySet * | ss | ) |
Create a transducer that accepts the union of the key identity pairs in a set ss.
TransducerHandle define_transducer | ( | KeyPair * | p | ) |
Create a transducer that accepts one occurrence of key pair p.
TransducerHandle define_transducer | ( | Key | k | ) |
Create a transducer that accepts one occurrence 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.
TransducerHandle disjunct | ( | TransducerHandle | t1, | |
TransducerHandle | t2 | |||
) |
Disjunction of t1 and t2.
Disjunction of t1 and t2 maps "a" to "b" iff t1 and/or t2 maps "a" to "b".
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] ]
.
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] ]
.
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).
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. |
float get_weight | ( | TransducerHandle | t | ) |
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]*
.
TransducerHandle intersect | ( | TransducerHandle | t1, | |
TransducerHandle | t2 | |||
) |
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.
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.
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]
.
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.
t is the empty transducer if t has one state that is not final and has no transitions.
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.
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.
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.
TransducerHandle optionalize | ( | TransducerHandle | t | ) |
Disjunction of t and epsilon.
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.
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.
int read_format | ( | istream & | is = cin |
) |
Read the format of the next transducer in the input stream is.
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 | ) |
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.
t | Transducer to be catenated. | |
n | How many times t is catenated. If n == 0, an epsilon transducer is returned. |
TransducerHandle repeat_plus | ( | TransducerHandle | t | ) |
Transducer t +.
Transducer that accepts one or more t.
TransducerHandle repeat_star | ( | TransducerHandle | t | ) |
Transducer t *.
Transducer that accepts any number of t.
TransducerHandle reverse | ( | TransducerHandle | t | ) |
Reverse transducer t.
TransducerHandle shuffle | ( | TransducerHandle | t1, | |
TransducerHandle | t2 | |||
) |
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.
TransducerHandle subtract | ( | TransducerHandle | t1, | |
TransducerHandle | t2 | |||
) |
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.
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.