1 /*************************************************************************/ 2 /* */ 3 /* Centre for Speech Technology Research */ 4 /* University of Edinburgh, UK */ 5 /* Copyright (c) 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 : Alan W Black */ 34 /* Date : July 1996 */ 35 /*-----------------------------------------------------------------------*/ 36 /* */ 37 /* Simple statistics (for discrete probability distributions */ 38 /* */ 39 /*=======================================================================*/ 40 #ifndef __EST_SIMPLESTATS_H__ 41 #define __EST_SIMPLESTATS_H__ 42 43 #include "EST_String.h" 44 #include "EST_Token.h" 45 #include "EST_StringTrie.h" 46 #include "EST_TList.h" 47 #include "EST_TKVL.h" 48 #include "EST_types.h" 49 50 typedef size_t int_iter; 51 52 /** A class for managing mapping string names to integers and back again, 53 mainly used for representing alphabets in n-grams and grammars etc. 54 55 This offers an efficient way of mapping a known set of string names 56 to integers. It is initialised from a list of names and builds 57 a index of those names to a set of integers. 58 59 @author Alan W Black (awb@cstr.ed.ac.uk): July 1996 60 */ 61 class EST_Discrete { 62 private: 63 // for fast index->name 64 EST_StrVector namevector; 65 int p_def_val; 66 // for fast name->index 67 EST_StringTrie nametrie; 68 69 public: 70 /// EST_Discrete()71 EST_Discrete() {nametrie.clear(); p_def_val = -1;} 72 /// EST_Discrete(const EST_Discrete & d)73 EST_Discrete(const EST_Discrete &d) { copy(d); } 74 /// Initialise discrete class from given list of strings 75 EST_Discrete(const EST_StrList &vocab); 76 /// 77 ~EST_Discrete(); 78 /// 79 void copy(const EST_Discrete &d); 80 /// (re-)initialise 81 bool init(const EST_StrList &vocab); 82 83 /// The number of members in the discrete length(void)84 const int length(void) const { return namevector.length(); } 85 /** The int assigned to the given name, if it doesn't exists p\_def\_val 86 is returned (which is -1 by default) 87 */ index(const EST_String & n)88 const int index(const EST_String &n) const { 89 int *i; 90 return (((i=(int*)nametrie.lookup(n)) != NULL) ? *i : p_def_val); 91 }; 92 93 /// The name given the index name(const int n)94 const EST_String &name(const int n) const { return namevector(n); } 95 96 /// set the default value when a name isn't found (-1 by default) def_val(const EST_String & v)97 void def_val(const EST_String &v) { p_def_val = index(v); } 98 99 /// An alternative method for getting the int form the name name(const EST_String & n)100 int name(const EST_String &n) const { return index(n); }; 101 102 bool operator == (const EST_Discrete &d); 103 bool operator != (const EST_Discrete &d); 104 105 EST_String print_to_string(int quote=0); 106 friend ostream& operator <<(ostream& s, const EST_Discrete &d); 107 108 /// 109 EST_Discrete & operator = (const EST_Discrete &a) 110 { copy(a); return *this; } 111 112 }; 113 114 class Discretes { 115 private: 116 int max; 117 int next_free; 118 EST_Discrete **discretes; 119 public: Discretes()120 Discretes() {max=50;next_free=0;discretes=new EST_Discrete*[max];} 121 ~Discretes(); 122 const int def(const EST_StrList &members); discrete(const int t)123 EST_Discrete &discrete(const int t) const {return *discretes[t-10];} 124 EST_Discrete &operator [] (const int t) const {return *discretes[t-10];} 125 }; 126 127 /** A class for cummulating ``sufficient statistics'' for a set of 128 numbers: sum, count, sum squared. 129 130 This collects the number, sum and sum squared for a set of number. 131 Offering mean, variance and standard deviation derived from the 132 cummulated values. 133 134 @author Alan W Black (awb@cstr.ed.ac.uk): July 1996 135 */ 136 class EST_SuffStats { 137 private: 138 double n; // allows frequencies to be non-integers 139 double p_sum; 140 double p_sumx; 141 public: 142 /// EST_SuffStats()143 EST_SuffStats() {n = p_sum = p_sumx = 0.0;} 144 /// EST_SuffStats(double in,double isum,double isumx)145 EST_SuffStats(double in, double isum, double isumx) 146 {n = in; p_sum = isum; p_sumx = isumx;} 147 /// EST_SuffStats(const EST_SuffStats & s)148 EST_SuffStats(const EST_SuffStats &s) { copy(s); } 149 /// copy(const EST_SuffStats & s)150 void copy(const EST_SuffStats &s) 151 {n=s.n; p_sum = s.p_sum; p_sumx = s.p_sumx;} 152 /// reset internal values reset(void)153 void reset(void) {n = p_sum = p_sumx = 0.0;} set(double in,double isum,double isumx)154 void set(double in, double isum, double isumx) 155 {n = in; p_sum = isum; p_sumx = isumx;} 156 /// number of samples in set samples(void)157 double samples(void) {return n;} 158 /// sum of values sum()159 double sum() { return p_sum; } 160 /// sum of squared values sumx()161 double sumx() { return p_sumx; } 162 /// mean of currently cummulated values mean(void)163 double mean(void) const { return (n==0)?0.0:(p_sum / n); } 164 /// variance of currently cummulated values variance(void)165 double variance(void) const 166 { return ((n*p_sumx)-(p_sum*p_sum))/((double)n*(n-1)); } 167 /// standard deviation of currently cummulated values stddev(void)168 double stddev(void) const { return sqrt(variance()); } 169 170 void cumulate(double a,double count=1.0) 171 { n+=count; p_sum+=a*count; p_sumx+=count*(a*a); } 172 173 /// Used to cummulate new values 174 EST_SuffStats &operator +=(double a) 175 { cumulate(a,1.0); return *this;} 176 /// Used to cummulate new values 177 EST_SuffStats &operator + (double a) 178 { cumulate(a,1.0); return *this;} 179 /// 180 EST_SuffStats &operator = (const EST_SuffStats &a) 181 { copy(a); return *this;} 182 }; 183 184 enum EST_tprob_type {tprob_string, tprob_int, tprob_discrete}; 185 /** A class for representing probability distributions for a set of 186 discrete values. 187 188 This may be used to cummulate the probability distribution of a 189 class of values. Values are actually help as frequencies so both 190 frequency and probability information may be available. Note that 191 frequencies are not integers because using smoothing and backoff 192 integers are too restrictive so they are actually represented as 193 doubles. 194 195 Methods are provided to iterate over the values in a distribution, 196 for example 197 \begin{verbatim} 198 EST_DiscreteProbistribution pdf; 199 for (int i=pdf.item_start(); i < pdf.item_end(); i=pdf.item_next(i)) 200 { 201 EST_String name; 202 double prob; 203 item_prob(i,name,prob); 204 cout << name << ": prob " << prob << endl; 205 } 206 \end{verbatim} 207 208 @author Alan W Black (awb@cstr.ed.ac.uk): July 1996 209 */ 210 class EST_DiscreteProbDistribution { 211 private: 212 double num_samples; // because frequencies don't have to be integers 213 EST_tprob_type type; 214 /* For known vocabularies: tprob_discrete */ 215 const EST_Discrete *discrete; 216 // was int, but frequencies don't have to be integers 217 EST_DVector icounts; 218 /* For unknown vocabularies: tprob_string */ 219 EST_StrD_KVL scounts; 220 public: EST_DiscreteProbDistribution()221 EST_DiscreteProbDistribution() : type(tprob_string), discrete(NULL), icounts(0), scounts() {init();} 222 /// Create with copying from an existing distribution. 223 EST_DiscreteProbDistribution(const EST_DiscreteProbDistribution &b); 224 /// Create with given vocabulary EST_DiscreteProbDistribution(const EST_TList<EST_String> & vocab)225 EST_DiscreteProbDistribution(const EST_TList<EST_String> &vocab) 226 {init(); (void)init(vocab);} 227 /// Create using given \Ref{EST_Discrete} class as the vocabulary EST_DiscreteProbDistribution(const EST_Discrete * d)228 EST_DiscreteProbDistribution(const EST_Discrete *d) {init(); init(d);} 229 /** Create using given \Ref{EST_Discrete} class as vocabulary plus given 230 counts 231 */ 232 EST_DiscreteProbDistribution(const EST_Discrete *d, 233 const double n_samples, 234 const EST_DVector &counts); 235 236 /// Destructor function ~EST_DiscreteProbDistribution()237 ~EST_DiscreteProbDistribution() {clear();} 238 /// Copy all data from another DPD to this 239 void copy(const EST_DiscreteProbDistribution &b); 240 241 /// Reset, clearing all counts and vocabulary 242 void clear(void); 243 /// Initialise using given vocabulary 244 bool init(const EST_StrList &vocab); 245 /// Initialise using given \Ref{EST_Discrete} as vocabulary 246 void init(const EST_Discrete *d); 247 /// Initialise 248 void init(); 249 /// Total number of example found. samples(void)250 double samples(void) const { return num_samples; } 251 /// Add this observation, may specify number of occurrences 252 void cumulate(const EST_String &s,double count=1); 253 /// Add this observation, i must be with in EST\_Discrete range 254 void cumulate(EST_Litem *i,double count=1); 255 void cumulate(int i,double count=1); 256 /// Return the most probable member of the distribution 257 const EST_String &most_probable(double *prob = NULL) const; 258 /** Return the entropy of the distribution 259 \[ -\sum_{i=1}^N(prob(i)*log(prob(i))) \] 260 */ 261 double entropy(void) const; 262 /// 263 double probability(const EST_String &s) const; 264 /// 265 double probability(const int i) const; 266 /// 267 double frequency(const EST_String &s) const; 268 /// 269 double frequency(const int i) const; 270 /// Used for iterating through members of the distribution 271 EST_Litem *item_start() const; 272 /// Used for iterating through members of the distribution 273 EST_Litem *item_next(EST_Litem *idx) const; 274 /// Used for iterating through members of the distribution 275 int item_end(EST_Litem *idx) const; 276 277 /// During iteration returns name given index 278 const EST_String &item_name(EST_Litem *idx) const; 279 /// During iteration returns name and frequency given index 280 void item_freq(EST_Litem *idx,EST_String &s,double &freq) const; 281 /// During iteration returns name and probability given index 282 void item_prob(EST_Litem *idx,EST_String &s,double &prob) const; 283 284 /// Returns discrete vocabulary of distribution get_discrete()285 inline const EST_Discrete *const get_discrete() const { return discrete; }; 286 287 /** Sets the frequency of named item, modifies {\tt num\_samples} 288 accordingly. This is used when smoothing frequencies. 289 */ 290 void set_frequency(const EST_String &s,double c); 291 /** Sets the frequency of named item, modifies {\tt num\_samples} 292 accordingly. This is used when smoothing frequencies. 293 */ 294 void set_frequency(int i,double c); 295 void set_frequency(EST_Litem *i,double c); 296 297 /// Sets the frequency of named item, without modifying {\tt num\_samples}. 298 void override_frequency(const EST_String &s,double c); 299 /// Sets the frequency of named item, without modifying {\tt num\_samples}. 300 void override_frequency(int i,double c); 301 void override_frequency(EST_Litem *i,double c); 302 303 /** Sets the number of samples. Care should be taken on setting this 304 as it will affect how probabilities are calculated. 305 */ set_num_samples(const double c)306 void set_num_samples(const double c) { num_samples = c;} 307 308 friend ostream & operator <<(ostream &s, const EST_DiscreteProbDistribution &p); 309 EST_DiscreteProbDistribution &operator=(const EST_DiscreteProbDistribution &a); 310 }; 311 312 #endif // __EST_SIMPLESTATS_H__ 313