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 *ks) |
Create a transducer that accepts the union of the key identity pairs in a set ks. | |
TransducerHandle | define_transducer (KeyPairSet *Pi) |
Create a transducer that accepts the union of the key pairs in a set Pi. | |
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, bool sum_weights=false) |
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, bool sum_weights=false) |
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, KeyTable *kt=NULL) |
The intersecting composition of t with the transducers in v. | |
TransducerHandle | invert (TransducerHandle t) |
Switch input and output in the transition 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 *ks) |
Remove transitions where a key from ks 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, bool ignore_epsilon_pairs=false) |
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. unique defines whether t is determinized before finding paths. | |
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 | find_random_paths (TransducerHandle t, int max_number, bool unique=false) |
For unweighted transducers: find a maximum of max_number random paths 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 | modify_weights (TransducerHandle t, float(*modify)(float), bool modify_transition_weights=false) |
Modify final weights of transducer t according to function modify. modify_transition_weights defines whether transition weights are modified as well. | |
TransducerHandle | remove_epsilons (TransducerHandle t) |
Remove from t transitions whose input and output labels are epsilons. | |
Testing Functions | |
These functions do not delete their arguments. | |
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_infinitely_ambiguous (TransducerHandle t, bool output=true, KeyVector *kv=NULL) |
Whether t has infinitely many output strings for some input string (or for a certain input string kv), if output is true and whether it has infinitely many input strings for some output string (or for a certain output string kv), if output is false. | |
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. | |
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. | |
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 lists 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 istream is. | |
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 | print_transducer_number (TransducerHandle t, bool print_weights=true, ostream &os=cout) |
Print transducer t in number format to ostream os. print_weights defines whether weights are printed. |
typedef TransducerHandle TransducerHandle |
A finite state transducer (FST).
A FST is a weighted or an unweighted synchronous 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 | |||
) |
TransducerHandle add_output_language | ( | TransducerHandle | t, | |
KeyPairSet * | Pi | |||
) |
TransducerHandle add_weight | ( | TransducerHandle | t, | |
float | w | |||
) |
bool are_disjoint | ( | TransducerHandle | t1, | |
TransducerHandle | t2 | |||
) |
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.
t1 | first transducer in composition operation | |
t2 | second transducer in composition operation | |
destructive | Whether the argument transducers 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".
TransducerHandle copy | ( | TransducerHandle | t | ) |
TransducerHandle create_empty_transducer | ( | ) |
TransducerHandle create_epsilon_transducer | ( | ) |
KeySet* define_key_set | ( | TransducerHandle | t | ) |
KeyPairSet* define_keypair_set | ( | TransducerHandle | t | ) |
TransducerHandle define_transducer | ( | KeyPairSet * | Pi | ) |
TransducerHandle define_transducer | ( | KeySet * | ks | ) |
TransducerHandle define_transducer | ( | KeyPair * | p | ) |
TransducerHandle define_transducer | ( | Key | k | ) |
void delete_transducer | ( | TransducerHandle | t | ) |
TransducerHandle determinize | ( | TransducerHandle | t | ) |
TransducerHandle disjunct | ( | TransducerHandle | t1, | |
TransducerHandle | t2 | |||
) |
TransducerHandle disjunct_as_trie | ( | TransducerHandle | t, | |
KeyPairVector * | key_pair_string, | |||
float | weight = 0 , |
|||
bool | sum_weights = false | |||
) |
TransducerHandle disjunct_as_trie | ( | TransducerHandle | t, | |
KeyVector * | key_string, | |||
float | weight = 0 , |
|||
bool | sum_weights = false | |||
) |
Add the KeyVector * key_string as a path to the trie t.
t | The trie where the path is added. | |
key_string | A KeyVector representing the path. | |
weight | The weight of the path. | |
sum_weights | If the path already exists with a different weight: whether (1) a new path is added or (2) the weight of the old path is modified by summing the weights. |
TransducerHandle disjunct_transducers_as_tries | ( | TransducerHandle | t1, | |
TransducerHandle | t2 | |||
) |
TransducerHandle extract_input_language | ( | TransducerHandle | t | ) |
TransducerHandle extract_output_language | ( | TransducerHandle | t | ) |
vector<TransducerHandle> find_all_paths | ( | TransducerHandle | t, | |
bool | unique = false | |||
) |
Find all paths from initial to final state in transducer t. unique defines whether t is determinized before finding paths.
t | The transducer where best paths are searched. Cannot be cyclic. | |
unique | Whether equal paths are included only once (i.e whether t is determinized before finding paths). |
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 (i.e whether t is determinized before finding paths). |
TransducerHandle find_random_paths | ( | TransducerHandle | t, | |
int | max_number, | |||
bool | unique = false | |||
) |
For unweighted transducers: find a maximum of max_number random paths in transducer t. unique defines whether equal paths are included only once.
For weighted transducer: the same as find_best_paths. For unweighted transducers, the paths returned and their number may vary randomly.
t | The transducer where best paths are searched. Can be cyclic. | |
max_number | A maximum number of paths that are returned. | |
unique | Whether t is determinized before finding paths. |
float get_weight | ( | TransducerHandle | t | ) |
TransducerHandle insert_freely | ( | TransducerHandle | t, | |
KeyPair * | p | |||
) |
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, | |||
KeyTable * | kt = NULL | |||
) |
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. If kt is not NULL, then the keys in kt, which correspond to Xerox-style flag-diacritics will be treated as epsilons, i.e. the will be in the result-transducer, but will not affect the rules in any way.
The transducers in the vector v are deleted.
The vector v is deleted.
The result is not minimized.
TransducerHandle invert | ( | TransducerHandle | t | ) |
bool is_automaton | ( | TransducerHandle | t | ) |
bool is_cyclic | ( | TransducerHandle | t | ) |
bool is_deterministic | ( | TransducerHandle | t | ) |
bool is_empty | ( | TransducerHandle | t | ) |
bool is_epsilon | ( | TransducerHandle | t | ) |
bool is_infinitely_ambiguous | ( | TransducerHandle | t, | |
bool | output = true , |
|||
KeyVector * | kv = NULL | |||
) |
Whether t has infinitely many output strings for some input string (or for a certain input string kv), if output is true and whether it has infinitely many input strings for some output string (or for a certain output string kv), if output is false.
bool is_minimal | ( | TransducerHandle | t | ) |
bool is_subset | ( | TransducerHandle | t1, | |
TransducerHandle | 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 modify_weights | ( | TransducerHandle | t, | |
float(*)(float) | modify, | |||
bool | modify_transition_weights = false | |||
) |
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 | ) |
void print_transducer_number | ( | TransducerHandle | t, | |
bool | print_weights = true , |
|||
ostream & | os = cout | |||
) |
Print transducer t in number format to ostream os. print_weights defines whether weights are printed.
TransducerHandle push_weights | ( | TransducerHandle | t, | |
bool | initial | |||
) |
int read_format | ( | istream & | is = cin |
) |
Read the format of the next transducer in the input stream is.
TransducerHandle read_transducer | ( | const char * | filename | ) |
TransducerHandle read_transducer | ( | istream & | is = cin |
) |
TransducerHandle read_transducer_number | ( | istream & | is | ) |
TransducerHandle remove_epsilons | ( | TransducerHandle | t | ) |
TransducerHandle remove_pair | ( | TransducerHandle | t, | |
KeyPair * | p | |||
) |
TransducerHandle remove_pairs | ( | TransducerHandle | t, | |
KeySet * | ks | |||
) |
TransducerHandle repeat_le_n | ( | TransducerHandle | t, | |
int | n | |||
) |
TransducerHandle repeat_n | ( | TransducerHandle | t, | |
int | n | |||
) |
TransducerHandle repeat_plus | ( | TransducerHandle | t | ) |
TransducerHandle repeat_star | ( | TransducerHandle | t | ) |
TransducerHandle reverse | ( | TransducerHandle | t | ) |
TransducerHandle shuffle | ( | TransducerHandle | t1, | |
TransducerHandle | t2 | |||
) |
TransducerHandle substitute_key | ( | TransducerHandle | t, | |
KeySet * | ks, | |||
Key | k2 | |||
) |
TransducerHandle substitute_key | ( | TransducerHandle | t, | |
Key | k1, | |||
Key | k2, | |||
bool | ignore_epsilon_pairs = false | |||
) |
TransducerHandle substitute_with_pair | ( | TransducerHandle | t, | |
KeyPair * | p1, | |||
KeyPair * | p2 | |||
) |
TransducerHandle substitute_with_transducer | ( | TransducerHandle | t, | |
KeyPair * | p, | |||
TransducerHandle | 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_transducer | ( | TransducerHandle | t, | |
const char * | filename, | |||
bool | backwards_compatibility = false | |||
) |
void write_transducer | ( | TransducerHandle | t, | |
ostream & | os = cout , |
|||
bool | backwards_compatibility = false | |||
) |