ngrams_raw.c
/* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
/* ====================================================================
* Copyright (c) 2015 Carnegie Mellon University. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* This work was supported in part by funding from the Defense Advanced
* Research Projects Agency and the National Science Foundation of the
* United States of America, and the CMU Sphinx Speech Consortium.
*
* THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
* ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
* NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* ====================================================================
*
*/
#include <string.h>
#include <sphinxbase/err.h>
#include <sphinxbase/pio.h>
#include <sphinxbase/strfuncs.h>
#include <sphinxbase/ckd_alloc.h>
#include <sphinxbase/byteorder.h>
#include "ngram_model_internal.h"
#include "ngrams_raw.h"
int
ngram_ord_comparator(const void *a_raw, const void *b_raw)
{
ngram_raw_t *a = (ngram_raw_t *) a_raw;
ngram_raw_t *b = (ngram_raw_t *) b_raw;
int a_w_ptr = 0;
int b_w_ptr = 0;
while (a_w_ptr < a->order && b_w_ptr < b->order) {
if (a->words[a_w_ptr] == b->words[b_w_ptr]) {
a_w_ptr++;
b_w_ptr++;
continue;
}
if (a->words[a_w_ptr] < b->words[b_w_ptr])
return -1;
else
return 1;
}
return a->order - b->order;
}
static int
read_ngram_instance(lineiter_t ** li, hash_table_t * wid,
logmath_t * lmath, int order, int order_max,
ngram_raw_t * raw_ngram)
{
int n;
int words_expected;
int i;
char *wptr[NGRAM_MAX_ORDER + 1];
uint32 *word_out;
if (*li)
*li = lineiter_next(*li);
if (*li == NULL) {
E_ERROR("Unexpected end of ARPA file. Failed to read %d-gram\n",
order);
return -1;
}
words_expected = order + 1;
if ((n =
str2words((*li)->buf, wptr,
NGRAM_MAX_ORDER + 1)) < words_expected) {
E_ERROR("Format error; %d-gram ignored: %s\n", order, (*li)->buf);
return -1;
}
raw_ngram->order = order;
if (order == order_max) {
raw_ngram->prob = atof_c(wptr[0]);
if (raw_ngram->prob > 0) {
E_WARN("%d-gram '%s' has positive probability\n", order, wptr[1]);
raw_ngram->prob = 0.0f;
}
raw_ngram->prob =
logmath_log10_to_log_float(lmath, raw_ngram->prob);
}
else {
float weight, backoff;
weight = atof_c(wptr[0]);
if (weight > 0) {
E_WARN("%d-gram '%s' has positive probability\n", order, wptr[1]);
raw_ngram->prob = 0.0f;
}
else {
raw_ngram->prob =
logmath_log10_to_log_float(lmath, weight);
}
if (n == order + 1) {
raw_ngram->backoff = 0.0f;
}
else {
backoff = atof_c(wptr[order + 1]);
raw_ngram->backoff =
logmath_log10_to_log_float(lmath, backoff);
}
}
raw_ngram->words =
(uint32 *) ckd_calloc(order, sizeof(*raw_ngram->words));
for (word_out = raw_ngram->words + order - 1, i = 1;
word_out >= raw_ngram->words; --word_out, i++) {
hash_table_lookup_int32(wid, wptr[i], (int32 *) word_out);
}
return 0;
}
static int
ngrams_raw_read_order(ngram_raw_t ** raw_ngrams, lineiter_t ** li,
hash_table_t * wid, logmath_t * lmath, uint32 count,
int order, int order_max)
{
char expected_header[20];
uint32 i;
sprintf(expected_header, "\\%d-grams:", order);
while (*li && strcmp((*li)->buf, expected_header) != 0) {
*li = lineiter_next(*li);
}
if (*li == NULL) {
E_ERROR("Failed to find '%s', language model file truncated\n", expected_header);
return -1;
}
*raw_ngrams = (ngram_raw_t *) ckd_calloc(count, sizeof(ngram_raw_t));
for (i = 0; i < count; i++) {
if (read_ngram_instance(li, wid, lmath, order, order_max,
&((*raw_ngrams)[i])) < 0)
break;
}
qsort(*raw_ngrams, count, sizeof(ngram_raw_t), &ngram_ord_comparator);
return 0;
}
ngram_raw_t **
ngrams_raw_read_arpa(lineiter_t ** li, logmath_t * lmath, uint32 * counts,
int order, hash_table_t * wid)
{
ngram_raw_t **raw_ngrams;
int order_it;
raw_ngrams =
(ngram_raw_t **) ckd_calloc(order - 1, sizeof(*raw_ngrams));
for (order_it = 2; order_it <= order; order_it++) {
if (ngrams_raw_read_order(&raw_ngrams[order_it - 2], li, wid, lmath,
counts[order_it - 1], order_it, order) < 0)
break;
}
/* Check if we found ARPA end-mark */
if (*li == NULL) {
E_ERROR("ARPA file ends without end-mark\n");
ngrams_raw_free(raw_ngrams, counts, order);
return NULL;
} else {
*li = lineiter_next(*li);
if (strcmp((*li)->buf, "\\end\\") != 0) {
E_WARN
("Finished reading ARPA file. Expecting end mark but found '%s'\n",
(*li)->buf);
}
}
return raw_ngrams;
}
static void
read_dmp_weight_array(FILE * fp, logmath_t * lmath, uint8 do_swap,
int32 counts, ngram_raw_t * raw_ngrams,
int weight_idx)
{
int32 i, k;
dmp_weight_t *tmp_weight_arr;
fread(&k, sizeof(k), 1, fp);
if (do_swap)
SWAP_INT32(&k);
tmp_weight_arr =
(dmp_weight_t *) ckd_calloc(k, sizeof(*tmp_weight_arr));
fread(tmp_weight_arr, sizeof(*tmp_weight_arr), k, fp);
for (i = 0; i < k; i++) {
if (do_swap)
SWAP_INT32(&tmp_weight_arr[i].l);
/* Convert values to log. */
tmp_weight_arr[i].f =
logmath_log10_to_log_float(lmath, tmp_weight_arr[i].f);
}
/* replace indexes with real probs in raw bigrams */
for (i = 0; i < counts; i++) {
if (weight_idx == 0) {
raw_ngrams[i].prob =
tmp_weight_arr[(int) raw_ngrams[i].prob].f;
} else {
raw_ngrams[i].backoff =
tmp_weight_arr[(int) raw_ngrams[i].backoff].f;
}
}
ckd_free(tmp_weight_arr);
}
#define BIGRAM_SEGMENT_SIZE 9
ngram_raw_t **
ngrams_raw_read_dmp(FILE * fp, logmath_t * lmath, uint32 * counts,
int order, uint32 * unigram_next, uint8 do_swap)
{
uint32 j, ngram_idx;
uint16 *bigrams_next;
ngram_raw_t **raw_ngrams =
(ngram_raw_t **) ckd_calloc(order - 1, sizeof(*raw_ngrams));
/* read bigrams */
raw_ngrams[0] =
(ngram_raw_t *) ckd_calloc((size_t) (counts[1] + 1),
sizeof(*raw_ngrams[0]));
bigrams_next =
(uint16 *) ckd_calloc((size_t) (counts[1] + 1),
sizeof(*bigrams_next));
ngram_idx = 1;
for (j = 0; j <= (int32) counts[1]; j++) {
uint16 wid, prob_idx, bo_idx;
ngram_raw_t *raw_ngram = &raw_ngrams[0][j];
fread(&wid, sizeof(wid), 1, fp);
if (do_swap)
SWAP_INT16(&wid);
raw_ngram->order = 2;
while (ngram_idx < counts[0] && j == unigram_next[ngram_idx]) {
ngram_idx++;
}
if (j != counts[1]) {
raw_ngram->words =
(uint32 *) ckd_calloc(2, sizeof(*raw_ngram->words));
raw_ngram->words[0] = (uint32) wid;
raw_ngram->words[1] = (uint32) ngram_idx - 1;
}
fread(&prob_idx, sizeof(prob_idx), 1, fp);
fread(&bo_idx, sizeof(bo_idx), 1, fp);
fread(&bigrams_next[j], sizeof(bigrams_next[j]), 1, fp);
if (do_swap) {
SWAP_INT16(&prob_idx);
SWAP_INT16(&bo_idx);
SWAP_INT16(&bigrams_next[j]);
}
if (j != counts[1]) {
raw_ngram->prob = prob_idx + 0.5f; /* keep index in float. ugly but avoiding using extra memory */
raw_ngram->backoff = bo_idx + 0.5f;
}
}
if (ngram_idx < counts[0]) {
E_ERROR("Corrupted model, not enough unigrams %d %d\n", ngram_idx, counts[0]);
ckd_free(bigrams_next);
ngrams_raw_free(raw_ngrams, counts, order);
return NULL;
}
/* read trigrams */
if (order > 2) {
raw_ngrams[1] =
(ngram_raw_t *) ckd_calloc((size_t) counts[2],
sizeof(*raw_ngrams[1]));
for (j = 0; j < (int32) counts[2]; j++) {
uint16 wid, prob_idx;
ngram_raw_t *raw_ngram = &raw_ngrams[1][j];
fread(&wid, sizeof(wid), 1, fp);
fread(&prob_idx, sizeof(prob_idx), 1, fp);
if (do_swap) {
SWAP_INT16(&wid);
SWAP_INT16(&prob_idx);
}
raw_ngram->order = 3;
raw_ngram->words =
(uint32 *) ckd_calloc(3, sizeof(*raw_ngram->words));
raw_ngram->words[0] = (uint32) wid;
raw_ngram->prob = prob_idx + 0.5f; /* keep index in float. ugly but avoiding using extra memory */
}
}
/* read prob2 */
read_dmp_weight_array(fp, lmath, do_swap, (int32) counts[1],
raw_ngrams[0], 0);
/* read bo2 */
if (order > 2) {
int32 k;
int32 *tseg_base;
read_dmp_weight_array(fp, lmath, do_swap, (int32) counts[1],
raw_ngrams[0], 1);
/* read prob3 */
read_dmp_weight_array(fp, lmath, do_swap, (int32) counts[2],
raw_ngrams[1], 0);
/* Read tseg_base size and tseg_base to fill trigram's first words */
fread(&k, sizeof(k), 1, fp);
if (do_swap)
SWAP_INT32(&k);
tseg_base = (int32 *) ckd_calloc(k, sizeof(int32));
fread(tseg_base, sizeof(int32), k, fp);
if (do_swap) {
for (j = 0; j < (uint32) k; j++) {
SWAP_INT32(&tseg_base[j]);
}
}
ngram_idx = 0;
for (j = 1; j <= counts[1]; j++) {
uint32 next_ngram_idx =
(uint32) (tseg_base[j >> BIGRAM_SEGMENT_SIZE] +
bigrams_next[j]);
while (ngram_idx < next_ngram_idx) {
raw_ngrams[1][ngram_idx].words[1] =
raw_ngrams[0][j - 1].words[0];
raw_ngrams[1][ngram_idx].words[2] =
raw_ngrams[0][j - 1].words[1];
ngram_idx++;
}
}
ckd_free(tseg_base);
if (ngram_idx < counts[2]) {
E_ERROR("Corrupted model, some trigrams have no corresponding bigram\n");
ckd_free(bigrams_next);
ngrams_raw_free(raw_ngrams, counts, order);
return NULL;
}
}
ckd_free(bigrams_next);
/* sort raw ngrams for reverse trie */
qsort(raw_ngrams[0], (size_t) counts[1], sizeof(*raw_ngrams[0]),
&ngram_ord_comparator);
if (order > 2) {
qsort(raw_ngrams[1], (size_t) counts[2], sizeof(*raw_ngrams[1]),
&ngram_ord_comparator);
}
return raw_ngrams;
}
void
ngrams_raw_free(ngram_raw_t ** raw_ngrams, uint32 * counts, int order)
{
uint32 num;
int order_it;
for (order_it = 0; order_it < order - 1; order_it++) {
for (num = 0; num < counts[order_it + 1]; num++) {
ckd_free(raw_ngrams[order_it][num].words);
}
ckd_free(raw_ngrams[order_it]);
}
ckd_free(raw_ngrams);
}
ckd_alloc.h
Sphinx's memory allocation/deallocation routines.
ckd_free
SPHINXBASE_EXPORT void ckd_free(void *ptr)
Test and free a 1-D array.
Definition ckd_alloc.c:244
ckd_calloc
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
Definition ckd_alloc.h:248
err.h
Implementation of logging routines.
E_ERROR
#define E_ERROR(...)
Print error message to error log.
Definition err.h:104
E_WARN
#define E_WARN(...)
Print warning message to error log.
Definition err.h:109
hash_table_lookup_int32
SPHINXBASE_EXPORT int32 hash_table_lookup_int32(hash_table_t *h, const char *key, int32 *val)
Look up a 32-bit integer value in a hash table.
Definition hash_table.c:322
logmath_log10_to_log_float
SPHINXBASE_EXPORT float logmath_log10_to_log_float(logmath_t *lmath, float64 log_p)
Convert base 10 log (in floating point) to float log in base B.
Definition logmath.c:480
logmath_t
struct logmath_s logmath_t
Integer log math computation class.
Definition logmath.h:108
pio.h
file IO related operations.
lineiter_next
SPHINXBASE_EXPORT lineiter_t * lineiter_next(lineiter_t *li)
Move to the next line in the file.
Definition pio.c:347
strfuncs.h
Miscellaneous useful string functions.
str2words
SPHINXBASE_EXPORT int32 str2words(char *line, char **wptr, int32 n_wptr)
Convert a line to an array of "words", based on whitespace separators.
Definition strfuncs.c:123
atof_c
SPHINXBASE_EXPORT double atof_c(char const *str)
Locale independent version of atof().
Definition strfuncs.c:55
lineiter_t
Line iterator for files.
Definition pio.h:177
dmp_weight_t
Definition ngrams_raw.h:54