Edinburgh Speech Tools  2.4-release
 All Classes Functions Variables Typedefs Enumerations Enumerator Friends Pages
EST_lattice.h
1 /*************************************************************************/
2 /* */
3 /* Centre for Speech Technology Research */
4 /* University of Edinburgh, UK */
5 /* Copyright (c) 1995,1996 */
6 /* All Rights Reserved. */
7 /* */
8 /* Permission is hereby granted, free of charge, to use and distribute */
9 /* this software and its documentation without restriction, including */
10 /* without limitation the rights to use, copy, modify, merge, publish, */
11 /* distribute, sublicense, and/or sell copies of this work, and to */
12 /* permit persons to whom this work is furnished to do so, subject to */
13 /* the following conditions: */
14 /* 1. The code must retain the above copyright notice, this list of */
15 /* conditions and the following disclaimer. */
16 /* 2. Any modifications must be clearly marked as such. */
17 /* 3. Original authors' names are not deleted. */
18 /* 4. The authors' names are not used to endorse or promote products */
19 /* derived from this software without specific prior written */
20 /* permission. */
21 /* */
22 /* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
23 /* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
24 /* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
25 /* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
26 /* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
27 /* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
28 /* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
29 /* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
30 /* THIS SOFTWARE. */
31 /* */
32 /*************************************************************************/
33 /* Author : Simon King */
34 /* Date : November 1996 */
35 /*-----------------------------------------------------------------------*/
36 /* Lattice/Finite State Network */
37 /* */
38 /*=======================================================================*/
39 
40 
41 #ifndef __EST_LATTICE_H__
42 #define __EST_LATTICE_H__
43 
44 #include "EST_types.h"
45 #include "EST_Track.h"
46 
47 class Lattice {
48 
49 public:
50 
51  /*
52  struct quantised_label_table_entry_t{
53  int index;
54  float value;
55  };
56  */
57 
58  /*
59  struct name_map_entry_t{
60  int index;
61  String name;
62  };
63  */
64 
65  struct symbol_t{
66  int qmap_index;
67  int nmap_index;
68 
69  symbol_t operator += (const symbol_t s2);
70  bool operator != (const symbol_t &s2) const;
71  };
72 
73  struct Node;
74  struct Arc;
75 
76  struct Arc{
77  int label;
78  Node *to;
79  };
80 
81 
82  struct Node{
83  EST_IList name; // list of ints, referring to the table of names
84  EST_TList<Arc*> arcs_out;
85  };
86 
87 private:
88 
89 protected:
90 
91  // not necessarily defined or used ...
92  //friend inline ostream& operator<<(ostream &s, Lattice::quantised_label_table_entry_t &q);
93  //friend inline ostream& operator<<(ostream& s, Lattice::name_map_entry_t &n);
94  friend inline ostream& operator<<(ostream& s, const Lattice::symbol_t &sy);
95  friend inline ostream& operator<<(ostream& s, const Lattice::Node &n);
96  friend inline ostream& operator<<(ostream& s, const Lattice::Arc &n);
97 
98 
99  // maps, for speed
100  float qmap_error_margin; // only used in construction, so remove .. to do
101 
102  // quantised log probabilities
103  EST_FVector qmap;
104 
105  // 'words'
107 
108  // not used
109  EST_String name_as_string(EST_IList &l); // given a list of nmap indices
110 
111  // the finite state machines alphabet
112  EST_TVector<symbol_t> alphabet;
113  int e_move_symbol_index;
114  //int enter_move_symbol_index;
115 
116  //symbol_t* alphabet_lookup(int nmap_index, int qmap_index);
117  //symbol_t* alphabet_lookup_from_end(int nmap_index, int qmap_index);
118 
119 
120  int alphabet_index_lookup(int nmap_index, int qmap_index); // return index
121  //int alphabet_index_lookup_from_end(int nmap_index, int qmap_index); // return index
122 
123 
124  // the nodes
125  EST_TList<Node*> nodes;
126 
127  //Node* start_node; // a subset of nodes
128 
129  EST_TList<Node*> final_nodes; // a subset of nodes
130 
131  bool final(Node *n);
132 
133  // an alternative representation is a transition function
134  // useful (fast) for dense networks, but inefficient for sparse ones
135  int **tf; // indexed [node index][symbol index], contains destination node
136  bool build_transition_function();
137 
138  bool build_distinguished_state_table(bool ** &dst);
139  bool build_distinguished_state_table_direct(bool ** &dst);
140  bool build_distinguished_state_table_from_transition_function(bool ** &dst);
141 
142  void sort_arc_lists();
143  bool link(Node *n1, Node *n2, int label); //, EST_TList<Arc*> *l = NULL);
144 
145  void merge_nodes(EST_TList<Node*> &l);
146  void merge_arcs();
147  void prune_arc(Node *node, Arc *arc);
148  void prune_arcs(Node *node, EST_TList<Arc*> arcs);
149  void remove_arc_from_nodes_out_list(Node *n, Arc *a);
150 
151  int node_index(Node *n); // only for output in HTK format
152 
153 // SIMONK FIX THIS
154 // bool build_qmap(Bigram &g, float error_margin=0);
155 // bool build_nmap(Bigram &g);
156 
157 public:
158  Lattice();
159  ~Lattice();
160 
161 // SIMONK FIX THIS
162 // bool construct_alphabet(Bigram &g);
163 // bool construct(Bigram &g);
164  bool determinise();
165  bool prune();
166  bool minimise();
167  bool expand();
168 
169  Node *start_node();
170 
171  // traversing functions
172  bool accepts(EST_TList<symbol_t*> &string);
173  float viterbi_transduce(EST_TList<EST_String> &input,
174  EST_TList<Arc*> &path,
175  EST_Litem *current_symbol = NULL,
176  Node *start_node = NULL);
177 
178  // observations are indexed same as wordlist, excluding !ENTER and !EXIT
179  float viterbi_transduce(EST_Track &observations,
180  EST_TList<Arc*> &path,
181  float &score,
182  int current_frame = 0,
183  Node *start_node = NULL);
184 
185  // map lookup functions
186 
187  float qmap_index_to_value(int index);
188  int qmap_value_to_index(float value);
189 
190  EST_String nmap_index_to_name(int index);
191  int nmap_name_to_index(const EST_String &name);
192 
193  symbol_t* alphabet_index_to_symbol(int index);
194  int alphabet_symbol_to_index(symbol_t *sym);
195 
196 
197  friend bool save(Lattice &lattice, EST_String filename);
198  friend bool load(Lattice &lattice, EST_String filename);
199 
200  friend class Lattice_Language_Model;
201 
202 };
203 
204 /*
205 inline int
206 operator > (const Lattice::name_map_entry_t &n1,
207  const Lattice::name_map_entry_t &n2)
208 {
209  return (n1.name > n2.name);
210 };
211 
212 inline int
213 operator < (const Lattice::name_map_entry_t &n1,
214  const Lattice::name_map_entry_t &n2)
215 {
216  return (n1.name < n2.name);
217 };
218 */
219 
220 inline int
221 operator > (const Lattice::symbol_t s1,
222  const Lattice::symbol_t s2)
223 {
224  if(s1.qmap_index > s2.qmap_index)
225  return true;
226 
227  if(s1.qmap_index < s2.qmap_index)
228  return false;
229 
230  return (s1.nmap_index > s2.nmap_index);
231 }
232 
233 inline int
234 operator < (const Lattice::symbol_t s1,
235  const Lattice::symbol_t s2)
236 {
237  if(s1.qmap_index < s2.qmap_index)
238  return true;
239 
240  if(s1.qmap_index > s2.qmap_index)
241  return false;
242 
243  return (s1.nmap_index < s2.nmap_index);
244 }
245 
246 inline Lattice::symbol_t
247 operator + (const Lattice::symbol_t s1,
248  const Lattice::symbol_t s2)
249 {
250  (void) s1;
251  (void) s2;
252  cerr << "operator + makes no sense for Lattice::symbol_t !" << endl;
253  return Lattice::symbol_t();
254 
255 }
256 
257 // used for sorting arcs lists
258 inline int operator > (Lattice::Arc a1, Lattice::Arc a2)
259 {
260  return (a1.label > a2.label);
261 }
262 
263 inline int operator < (Lattice::Arc a1, Lattice::Arc a2)
264 {
265  return (a1.label < a2.label);
266 }
267 
268 inline int operator >= (Lattice::Arc a1, Lattice::Arc a2)
269 {
270  return (a1.label >= a2.label);
271 }
272 
273 inline int operator <= (Lattice::Arc a1, Lattice::Arc a2)
274 {
275  return (a1.label <= a2.label);
276 }
277 
278 inline int operator == (Lattice::Arc a1, Lattice::Arc a2)
279 {
280  return (a1.label == a2.label);
281 }
282 
283 inline int operator == (Lattice::symbol_t s1, Lattice::symbol_t s2)
284 {
285  return ((s1.nmap_index == s2.nmap_index) &&
286  (s1.qmap_index == s2.qmap_index) );
287 }
288 
289 
290 /*
291 inline ostream& operator<<(ostream &s, Lattice::quantised_label_table_entry_t &q){
292  s << q.value;
293  return s;
294 }
295 */
296 
297 /*
298 inline ostream& operator<<(ostream& s, Lattice::name_map_entry_t &n)
299 {
300  s << n.index << "=" << n.name;
301  return s;
302 }
303 */
304 
305 inline ostream& operator<<(ostream& s, const Lattice::symbol_t &sm)
306 {
307  s << "[q=" << sm.qmap_index << ",n=" << sm.nmap_index << "]";
308  return s;
309 }
310 
311 
312 inline ostream& operator<<(ostream& s, const Lattice::Node &n)
313 {
314  s << "Node:" << n.name;
315  return s;
316 }
317 
318 inline ostream& operator<<(ostream &s, const Lattice::Arc &a)
319 {
320  s << a.label;
321  return s;
322 }
323 
324 
325 void sort_by_label(EST_TList<Lattice::Arc*> &l);
326 
327 
328 #endif