Debian Codegraph @

src/libsphinxbase/lm/lm_trie_quant.c

raw
1 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /* ====================================================================
3 * Copyright (c) 2015 Carnegie Mellon University. All rights
4 * reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * This work was supported in part by funding from the Defense Advanced
19 * Research Projects Agency and the National Science Foundation of the
20 * United States of America, and the CMU Sphinx Speech Consortium.
21 *
22 * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
23 * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
24 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
25 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
26 * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
28 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 *
34 * ====================================================================
35 *
36 */
37
38 #include <math.h>
39
40 #include <sphinxbase/prim_type.h>
41 #include <sphinxbase/ckd_alloc.h>
42 #include <sphinxbase/err.h>
43
44 #include "ngram_model_internal.h"
45 #include "lm_trie_quant.h"
46
47 #define FLOAT_INF (0x7f800000)
48
49 typedef struct bins_s {
50 float *begin;
51 const float *end;
52 } bins_t;
53
54 struct lm_trie_quant_s {
55 bins_t tables[NGRAM_MAX_ORDER - 1][2];
56 bins_t *longest;
57 uint8 *mem;
58 size_t mem_size;
59 uint8 prob_bits;
60 uint8 bo_bits;
61 uint32 prob_mask;
62 uint32 bo_mask;
63 };
64
65 static void
66 bins_create(bins_t * bins, uint8 bits, float *begin)
67 {
68 bins->begin = begin;
69 bins->end = bins->begin + (1ULL << bits);
70 }
71
72 static float *
73 lower_bound(float *first, const float *last, float val)
74 {
75 int count, step;
76 float *it;
77
78 count = last - first;
79 while (count > 0) {
80 it = first;
81 step = count / 2;
82 it += step;
83 if (*it < val) {
84 first = ++it;
85 count -= step + 1;
86 }
87 else {
88 count = step;
89 }
90 }
91 return first;
92 }
93
94 static uint64
95 bins_encode(bins_t * bins, float value)
96 {
97 float *above = lower_bound(bins->begin, bins->end, value);
98 if (above == bins->begin)
99 return 0;
100 if (above == bins->end)
101 return bins->end - bins->begin - 1;
102 return above - bins->begin - (value - *(above - 1) < *above - value);
103 }
104
105 static float
106 bins_decode(bins_t * bins, size_t off)
107 {
108 return bins->begin[off];
109 }
110
111 static size_t
112 quant_size(int order)
113 {
114 int prob_bits = 16;
115 int bo_bits = 16;
116 size_t longest_table = (1U << prob_bits) * sizeof(float);
117 size_t middle_table = (1U << bo_bits) * sizeof(float) + longest_table;
118 /* unigrams are currently not quantized so no need for a table. */
119 return (order - 2) * middle_table + longest_table;
120 }
121
122 lm_trie_quant_t *
123 lm_trie_quant_create(int order)
124 {
125 float *start;
126 int i;
127 lm_trie_quant_t *quant =
128 (lm_trie_quant_t *) ckd_calloc(1, sizeof(*quant));
129 quant->mem_size = quant_size(order);
130 quant->mem =
131 (uint8 *) ckd_calloc(quant->mem_size, sizeof(*quant->mem));
132
133 quant->prob_bits = 16;
134 quant->bo_bits = 16;
135 quant->prob_mask = (1U << quant->prob_bits) - 1;
136 quant->bo_mask = (1U << quant->bo_bits) - 1;
137
138 start = (float *) (quant->mem);
139 for (i = 0; i < order - 2; i++) {
140 bins_create(&quant->tables[i][0], quant->prob_bits, start);
141 start += (1ULL << quant->prob_bits);
142 bins_create(&quant->tables[i][1], quant->bo_bits, start);
143 start += (1ULL << quant->bo_bits);
144 }
145 bins_create(&quant->tables[order - 2][0], quant->prob_bits, start);
146 quant->longest = &quant->tables[order - 2][0];
147 return quant;
148 }
149
150
151 lm_trie_quant_t *
152 lm_trie_quant_read_bin(FILE * fp, int order)
153 {
154 int dummy;
155 lm_trie_quant_t *quant;
156
157 fread(&dummy, sizeof(dummy), 1, fp);
158 quant = lm_trie_quant_create(order);
159 fread(quant->mem, sizeof(*quant->mem), quant->mem_size, fp);
160
161 return quant;
162 }
163
164 void
165 lm_trie_quant_write_bin(lm_trie_quant_t * quant, FILE * fp)
166 {
167 /* Before it was quantization type */
168 int dummy = 1;
169 fwrite(&dummy, sizeof(dummy), 1, fp);
170 fwrite(quant->mem, sizeof(*quant->mem), quant->mem_size, fp);
171 }
172
173 void
174 lm_trie_quant_free(lm_trie_quant_t * quant)
175 {
176 if (quant->mem)
177 ckd_free(quant->mem);
178 ckd_free(quant);
179 }
180
181 uint8
182 lm_trie_quant_msize(lm_trie_quant_t * quant)
183 {
184 return 32;
185 }
186
187 uint8
188 lm_trie_quant_lsize(lm_trie_quant_t * quant)
189 {
190 return 16;
191 }
192
193 static int
194 weights_comparator(const void *a, const void *b)
195 {
196 return (int) (*(float *) a - *(float *) b);
197 }
198
199 static void
200 make_bins(float *values, uint32 values_num, float *centers, uint32 bins)
201 {
202 float *finish, *start;
203 uint32 i;
204
205 qsort(values, values_num, sizeof(*values), &weights_comparator);
206 start = values;
207 for (i = 0; i < bins; i++, centers++, start = finish) {
208 finish = values + (size_t) ((uint64) values_num * (i + 1) / bins);
209 if (finish == start) {
210 /* zero length bucket. */
211 *centers = i ? *(centers - 1) : -FLOAT_INF;
212 }
213 else {
214 float sum = 0.0f;
215 float *ptr;
216 for (ptr = start; ptr != finish; ptr++) {
217 sum += *ptr;
218 }
219 *centers = sum / (float) (finish - start);
220 }
221 }
222 }
223
224 void
225 lm_trie_quant_train(lm_trie_quant_t * quant, int order, uint32 counts,
226 ngram_raw_t * raw_ngrams)
227 {
228 float *probs;
229 float *backoffs;
230 float *centers;
231 uint32 backoff_num;
232 uint32 prob_num;
233 ngram_raw_t *raw_ngrams_end;
234
235 probs = (float *) ckd_calloc(counts, sizeof(*probs));
236 backoffs = (float *) ckd_calloc(counts, sizeof(*backoffs));
237 raw_ngrams_end = raw_ngrams + counts;
238
239 for (backoff_num = 0, prob_num = 0; raw_ngrams != raw_ngrams_end;
240 raw_ngrams++) {
241 probs[prob_num++] = raw_ngrams->prob;
242 backoffs[backoff_num++] = raw_ngrams->backoff;
243 }
244
245 make_bins(probs, prob_num, quant->tables[order - 2][0].begin,
246 1ULL << quant->prob_bits);
247 centers = quant->tables[order - 2][1].begin;
248 make_bins(backoffs, backoff_num, centers, (1ULL << quant->bo_bits));
249 ckd_free(probs);
250 ckd_free(backoffs);
251 }
252
253 void
254 lm_trie_quant_train_prob(lm_trie_quant_t * quant, int order, uint32 counts,
255 ngram_raw_t * raw_ngrams)
256 {
257 float *probs;
258 uint32 prob_num;
259 ngram_raw_t *raw_ngrams_end;
260
261 probs = (float *) ckd_calloc(counts, sizeof(*probs));
262 raw_ngrams_end = raw_ngrams + counts;
263
264 for (prob_num = 0; raw_ngrams != raw_ngrams_end; raw_ngrams++) {
265 probs[prob_num++] = raw_ngrams->prob;
266 }
267
268 make_bins(probs, prob_num, quant->tables[order - 2][0].begin,
269 1ULL << quant->prob_bits);
270 ckd_free(probs);
271 }
272
273 void
274 lm_trie_quant_mwrite(lm_trie_quant_t * quant, bitarr_address_t address,
275 int order_minus_2, float prob, float backoff)
276 {
277 bitarr_write_int57(address, quant->prob_bits + quant->bo_bits,
278 (uint64) ((bins_encode
279 (&quant->tables[order_minus_2][0],
280 prob) << quant->
281 bo_bits) | bins_encode(&quant->
282 tables
283 [order_minus_2]
284 [1],
285 backoff)));
286 }
287
288 void
289 lm_trie_quant_lwrite(lm_trie_quant_t * quant, bitarr_address_t address,
290 float prob)
291 {
292 bitarr_write_int25(address, quant->prob_bits,
293 (uint32) bins_encode(quant->longest, prob));
294 }
295
296 float
297 lm_trie_quant_mboread(lm_trie_quant_t * quant, bitarr_address_t address,
298 int order_minus_2)
299 {
300 return bins_decode(&quant->tables[order_minus_2][1],
301 bitarr_read_int25(address, quant->bo_bits,
302 quant->bo_mask));
303 }
304
305 float
306 lm_trie_quant_mpread(lm_trie_quant_t * quant, bitarr_address_t address,
307 int order_minus_2)
308 {
309 address.offset += quant->bo_bits;
310 return bins_decode(&quant->tables[order_minus_2][0],
311 bitarr_read_int25(address, quant->prob_bits,
312 quant->prob_mask));
313 }
314
315 float
316 lm_trie_quant_lpread(lm_trie_quant_t * quant, bitarr_address_t address)
317 {
318 return bins_decode(quant->longest,
319 bitarr_read_int25(address, quant->prob_bits,
320 quant->prob_mask));
321 }