Edinburgh Speech Tools  2.4-release
 All Classes Functions Variables Typedefs Enumerations Enumerator Friends Pages
wfst_aux.cc
1 /*************************************************************************/
2 /* */
3 /* Centre for Speech Technology Research */
4 /* University of Edinburgh, UK */
5 /* Copyright (c) 1997 */
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 : Alan W Black */
34 /* Date : November 1997 */
35 /*-----------------------------------------------------------------------*/
36 /* */
37 /* internal classes, methods and function used in minimization and */
38 /* determinization of WFST. */
39 /* */
40 /*=======================================================================*/
41 #include <iostream>
42 #include "EST_WFST.h"
43 #include "wfst_aux.h"
44 
45 wfst_marks::wfst_marks(int x)
46 {
47  // Set up mark table
48  int i,j;
49 
50  // Triangular matrix
51  p_x = x;
52  p_mark_table = new char *[x];
53  for (i=0; i < x; i++)
54  {
55  p_mark_table[i] = new char[i+1];
56  for (j=0; j < i+1; j++)
57  p_mark_table[i][j] = '?';
58  }
59 
60 }
61 
62 wfst_marks::~wfst_marks()
63 {
64  int i;
65 
66  for (i=0; i < p_x; i++)
67  delete [] p_mark_table[i];
68  delete [] p_mark_table;
69  p_mark_table = 0;
70 }
71 
72 void wfst_marks::find_state_map(EST_IVector &state_map,int &num_new_states)
73 {
74  // Find the mapping from old state names to new
75  int i,j,new_name;
76 
77  state_map.resize(p_x);
78 
79  for (i=0,new_name=0; i < p_x; i++)
80  {
81  state_map[i] = -1;
82  for (j=0; j < i; j++)
83  if (!distinguished(j,i))
84  {
85  state_map[i] = state_map[j];
86  break;
87  }
88  if (state_map[i] == -1)
89  state_map[i] = new_name++;
90  }
91 
92  num_new_states = new_name;
93 }
94 
95 void add_assumption(int y,int z,wfst_assumes &assumptions)
96 {
97  // Add a binding of y to z, and z to y to assumptions
98  EST_Litem *p;
99  int y_ok = FALSE;
100  int z_ok = FALSE;
101 
102  for (p=assumptions.list.head(); p != 0; p=p->next())
103  {
104  if (assumptions.list(p).k == y)
105  {
106  assumptions.list(p).v.append(z);
107  y_ok = TRUE;
108  }
109  if (assumptions.list(p).k == z)
110  {
111  assumptions.list(p).v.append(y);
112  z_ok = TRUE;
113  }
114  if (z_ok && y_ok)
115  break;
116  }
117  if (!z_ok)
118  {
119  EST_IList b;
120  b.append(y);
121  assumptions.add_item(z,b);
122  }
123  if (!y_ok)
124  {
125  EST_IList b;
126  b.append(z);
127  assumptions.add_item(y,b);
128  }
129 }
130 
131 int equivalent_to(int y,int z,wfst_assumes &assumptions)
132 {
133  // true if y == z or z is assumed to be equivalent to y
134  EST_Litem *p,*q;
135 
136  if (y==z)
137  return TRUE;
138  else
139  {
140  for (p=assumptions.list.head(); p != 0; p=p->next())
141  {
142  if (assumptions.list(p).k == y)
143  {
144  EST_IList &b = assumptions.list(p).v;
145  for (q=b.head(); q != 0; q=q->next())
146  if (z == b(q))
147  return TRUE;
148  }
149  if (assumptions.list(p).k == z)
150  {
151  EST_IList &b = assumptions.list(p).v;
152  for (q=b.head(); q != 0; q=q->next())
153  if (y == b(q))
154  return TRUE;
155  }
156  }
157  return FALSE;
158  }
159 }
160 
161 void mark_undistinguished(wfst_marks &marks,wfst_assumes &assumptions)
162 {
163  EST_Litem *p, *q;
164 
165  for (p=assumptions.list.head(); p != 0; p=p->next())
166  {
167  int x = assumptions.list(p).k;
168  EST_IList &b = assumptions.list(p).v;
169  for (q=b.head(); q != 0; q=q->next())
170  marks.undistinguish(x,b(q));
171  }
172 }
173 
174 VAL_REGISTER_CLASS(wfst,EST_WFST)
175 
176 
177 
178 
179 
180