Edinburgh Speech Tools 2.4-release
 
Loading...
Searching...
No Matches
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
47class Lattice {
48
49public:
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
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
87private:
88
89protected:
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
157public:
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,
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/*
205inline int
206operator > (const Lattice::name_map_entry_t &n1,
207 const Lattice::name_map_entry_t &n2)
208{
209 return (n1.name > n2.name);
210};
211
212inline int
213operator < (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
220inline int
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
233inline int
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
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
259{
260 return (a1.label > a2.label);
261}
262
264{
265 return (a1.label < a2.label);
266}
267
269{
270 return (a1.label >= a2.label);
271}
272
274{
275 return (a1.label <= a2.label);
276}
277
279{
280 return (a1.label == a2.label);
281}
282
284{
285 return ((s1.nmap_index == s2.nmap_index) &&
286 (s1.qmap_index == s2.qmap_index) );
287}
288
289
290/*
291inline ostream& operator<<(ostream &s, Lattice::quantised_label_table_entry_t &q){
292 s << q.value;
293 return s;
294}
295*/
296
297/*
298inline ostream& operator<<(ostream& s, Lattice::name_map_entry_t &n)
299{
300 s << n.index << "=" << n.name;
301 return s;
302}
303*/
304
306{
307 s << "[q=" << sm.qmap_index << ",n=" << sm.nmap_index << "]";
308 return s;
309}
310
311
312inline ostream& operator<<(ostream& s, const Lattice::Node &n)
313{
314 s << "Node:" << n.name;
315 return s;
316}
317
318inline ostream& operator<<(ostream &s, const Lattice::Arc &a)
319{
320 s << a.label;
321 return s;
322}
323
324
325void sort_by_label(EST_TList<Lattice::Arc*> &l);
326
327
328#endif