ngram_model.c
/* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
/* ====================================================================
* Copyright (c) 1999-2007 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.
*
* ====================================================================
*
*/
/*
* \file ngram_model.c N-Gram language models.
*
* Author: David Huggins-Daines, much code taken from sphinx3/src/libs3decoder/liblm
*/
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <string.h>
#include <assert.h>
#include "sphinxbase/ngram_model.h"
#include "sphinxbase/ckd_alloc.h"
#include "sphinxbase/filename.h"
#include "sphinxbase/pio.h"
#include "sphinxbase/err.h"
#include "sphinxbase/logmath.h"
#include "sphinxbase/strfuncs.h"
#include "sphinxbase/case.h"
#include "ngram_model_internal.h"
#include "ngram_model_trie.h"
ngram_file_type_t
ngram_file_name_to_type(const char *file_name)
{
const char *ext;
ext = strrchr(file_name, '.');
if (ext == NULL) {
return NGRAM_INVALID;
}
if (0 == strcmp_nocase(ext, ".gz")) {
while (--ext >= file_name) {
if (*ext == '.')
break;
}
if (ext < file_name) {
return NGRAM_INVALID;
}
}
else if (0 == strcmp_nocase(ext, ".bz2")) {
while (--ext >= file_name) {
if (*ext == '.')
break;
}
if (ext < file_name) {
return NGRAM_INVALID;
}
}
/* We use strncmp because there might be a .gz on the end. */
if (0 == strncmp_nocase(ext, ".ARPA", 5))
return NGRAM_ARPA;
if (0 == strncmp_nocase(ext, ".DMP", 4)
|| 0 == strncmp_nocase(ext, ".BIN", 4))
return NGRAM_BIN;
return NGRAM_INVALID;
}
ngram_file_type_t
ngram_str_to_type(const char *str_name)
{
if (0 == strcmp_nocase(str_name, "arpa"))
return NGRAM_ARPA;
if (0 == strcmp_nocase(str_name, "dmp")
|| 0 == strcmp_nocase(str_name, "bin"))
return NGRAM_BIN;
return NGRAM_INVALID;
}
char const *
ngram_type_to_str(int type)
{
switch (type) {
case NGRAM_ARPA:
return "arpa";
case NGRAM_BIN:
return "dmp/bin";
default:
return NULL;
}
}
ngram_model_t *
ngram_model_read(cmd_ln_t * config,
const char *file_name,
ngram_file_type_t file_type, logmath_t * lmath)
{
ngram_model_t *model = NULL;
switch (file_type) {
case NGRAM_AUTO:{
if ((model =
ngram_model_trie_read_bin(config, file_name,
lmath)) != NULL)
break;
if ((model =
ngram_model_trie_read_arpa(config, file_name,
lmath)) != NULL)
break;
if ((model =
ngram_model_trie_read_dmp(config, file_name,
lmath)) != NULL)
break;
return NULL;
}
case NGRAM_ARPA:
model = ngram_model_trie_read_arpa(config, file_name, lmath);
break;
case NGRAM_BIN:
if ((model =
ngram_model_trie_read_bin(config, file_name, lmath)) != NULL)
break;
if ((model =
ngram_model_trie_read_dmp(config, file_name, lmath)) != NULL)
break;
return NULL;
default:
E_ERROR("language model file type not supported\n");
return NULL;
}
/* Now set weights based on config if present. */
if (config) {
float32 lw = 1.0;
float32 wip = 1.0;
if (cmd_ln_exists_r(config, "-lw"))
lw = cmd_ln_float32_r(config, "-lw");
if (cmd_ln_exists_r(config, "-wip"))
wip = cmd_ln_float32_r(config, "-wip");
ngram_model_apply_weights(model, lw, wip);
}
return model;
}
int
ngram_model_write(ngram_model_t * model, const char *file_name,
ngram_file_type_t file_type)
{
switch (file_type) {
case NGRAM_AUTO:{
file_type = ngram_file_name_to_type(file_name);
/* Default to ARPA (catches .lm and other things) */
if (file_type == NGRAM_INVALID)
file_type = NGRAM_ARPA;
return ngram_model_write(model, file_name, file_type);
}
case NGRAM_ARPA:
return ngram_model_trie_write_arpa(model, file_name);
case NGRAM_BIN:
return ngram_model_trie_write_bin(model, file_name);
default:
E_ERROR("language model file type not supported\n");
return -1;
}
E_ERROR("language model file type not supported\n");
return -1;
}
int32
ngram_model_init(ngram_model_t * base,
ngram_funcs_t * funcs,
logmath_t * lmath, int32 n, int32 n_unigram)
{
base->refcount = 1;
base->funcs = funcs;
base->n = n;
/* If this was previously initialized... */
if (base->n_counts == NULL)
base->n_counts = (uint32 *) ckd_calloc(n, sizeof(*base->n_counts));
/* Don't reset weights if logmath object hasn't changed. */
if (base->lmath != lmath) {
/* Set default values for weights. */
base->lw = 1.0;
base->log_wip = 0; /* i.e. 1.0 */
base->log_zero = logmath_get_zero(lmath);
base->lmath = lmath;
}
/* Allocate or reallocate space for word strings. */
if (base->word_str) {
/* Free all previous word strings if they were allocated. */
if (base->writable) {
int32 i;
for (i = 0; i < base->n_words; ++i) {
ckd_free(base->word_str[i]);
base->word_str[i] = NULL;
}
}
base->word_str =
(char **) ckd_realloc(base->word_str,
n_unigram * sizeof(char *));
}
else {
base->word_str = (char **) ckd_calloc(n_unigram, sizeof(char *));
}
/* NOTE: They are no longer case-insensitive since we are allowing
* other encodings for word strings. Beware. */
if (base->wid)
hash_table_empty(base->wid);
else
base->wid = hash_table_new(n_unigram, FALSE);
base->n_counts[0] = base->n_1g_alloc = base->n_words = n_unigram;
return 0;
}
ngram_model_t *
ngram_model_retain(ngram_model_t * model)
{
++model->refcount;
return model;
}
void
ngram_model_flush(ngram_model_t * model)
{
if (model->funcs && model->funcs->flush)
(*model->funcs->flush) (model);
}
int
ngram_model_free(ngram_model_t * model)
{
int i;
if (model == NULL)
return 0;
if (--model->refcount > 0)
return model->refcount;
if (model->funcs && model->funcs->free)
(*model->funcs->free) (model);
if (model->writable) {
/* Free all words. */
for (i = 0; i < model->n_words; ++i) {
ckd_free(model->word_str[i]);
}
}
else {
/* Free all class words. */
for (i = 0; i < model->n_classes; ++i) {
ngram_class_t *lmclass;
int32 j;
lmclass = model->classes[i];
for (j = 0; j < lmclass->n_words; ++j) {
ckd_free(model->word_str[lmclass->start_wid + j]);
}
for (j = 0; j < lmclass->n_hash; ++j) {
if (lmclass->nword_hash[j].wid != -1) {
ckd_free(model->word_str[lmclass->nword_hash[j].wid]);
}
}
}
}
for (i = 0; i < model->n_classes; ++i) {
ngram_class_free(model->classes[i]);
}
ckd_free(model->classes);
hash_table_free(model->wid);
ckd_free(model->word_str);
ckd_free(model->n_counts);
ckd_free(model);
return 0;
}
int
ngram_model_casefold(ngram_model_t * model, int kase)
{
int writable, i;
hash_table_t *new_wid;
/* Were word strings already allocated? */
writable = model->writable;
/* Either way, we are going to allocate some word strings. */
model->writable = TRUE;
/* And, don't forget, we need to rebuild the word to unigram ID
* mapping. */
new_wid = hash_table_new(model->n_words, FALSE);
for (i = 0; i < model->n_words; ++i) {
char *outstr;
if (writable) {
outstr = model->word_str[i];
}
else {
outstr = ckd_salloc(model->word_str[i]);
}
/* Don't case-fold <tags> or [classes] */
if (outstr[0] == '<' || outstr[0] == '[') {
}
else {
switch (kase) {
case NGRAM_UPPER:
ucase(outstr);
break;
case NGRAM_LOWER:
lcase(outstr);
break;
default:
;
}
}
model->word_str[i] = outstr;
/* Now update the hash table. We might have terrible
* collisions here, so warn about them. */
if (hash_table_enter_int32(new_wid, model->word_str[i], i) != i) {
E_WARN("Duplicate word in dictionary after conversion: %s\n",
model->word_str[i]);
}
}
/* Swap out the hash table. */
hash_table_free(model->wid);
model->wid = new_wid;
return 0;
}
int
ngram_model_apply_weights(ngram_model_t * model, float32 lw, float32 wip)
{
return (*model->funcs->apply_weights) (model, lw, wip);
}
float32
ngram_model_get_weights(ngram_model_t * model, int32 * out_log_wip)
{
if (out_log_wip)
*out_log_wip = model->log_wip;
return model->lw;
}
int32
ngram_ng_score(ngram_model_t * model, int32 wid, int32 * history,
int32 n_hist, int32 * n_used)
{
int32 score, class_weight = 0;
int i;
/* Closed vocabulary, OOV word probability is zero */
if (wid == NGRAM_INVALID_WID)
return model->log_zero;
/* "Declassify" wid and history */
if (NGRAM_IS_CLASSWID(wid)) {
ngram_class_t *lmclass = model->classes[NGRAM_CLASSID(wid)];
class_weight = ngram_class_prob(lmclass, wid);
if (class_weight == 1) /* Meaning, not found in class. */
return model->log_zero;
wid = lmclass->tag_wid;
}
for (i = 0; i < n_hist; ++i) {
if (history[i] != NGRAM_INVALID_WID
&& NGRAM_IS_CLASSWID(history[i]))
history[i] =
model->classes[NGRAM_CLASSID(history[i])]->tag_wid;
}
score = (*model->funcs->score) (model, wid, history, n_hist, n_used);
/* Multiply by unigram in-class weight. */
return score + class_weight;
}
int32
ngram_score(ngram_model_t * model, const char *word, ...)
{
va_list history;
const char *hword;
int32 *histid;
int32 n_hist;
int32 n_used;
int32 prob;
va_start(history, word);
n_hist = 0;
while ((hword = va_arg(history, const char *)) != NULL)
++n_hist;
va_end(history);
histid = ckd_calloc(n_hist, sizeof(*histid));
va_start(history, word);
n_hist = 0;
while ((hword = va_arg(history, const char *)) != NULL) {
histid[n_hist] = ngram_wid(model, hword);
++n_hist;
}
va_end(history);
prob = ngram_ng_score(model, ngram_wid(model, word),
histid, n_hist, &n_used);
ckd_free(histid);
return prob;
}
int32
ngram_tg_score(ngram_model_t * model, int32 w3, int32 w2, int32 w1,
int32 * n_used)
{
int32 hist[2];
hist[0] = w2;
hist[1] = w1;
return ngram_ng_score(model, w3, hist, 2, n_used);
}
int32
ngram_bg_score(ngram_model_t * model, int32 w2, int32 w1, int32 * n_used)
{
return ngram_ng_score(model, w2, &w1, 1, n_used);
}
int32
ngram_ng_prob(ngram_model_t * model, int32 wid, int32 * history,
int32 n_hist, int32 * n_used)
{
int32 prob, class_weight = 0;
int i;
/* Closed vocabulary, OOV word probability is zero */
if (wid == NGRAM_INVALID_WID)
return model->log_zero;
/* "Declassify" wid and history */
if (NGRAM_IS_CLASSWID(wid)) {
ngram_class_t *lmclass = model->classes[NGRAM_CLASSID(wid)];
class_weight = ngram_class_prob(lmclass, wid);
if (class_weight == 1) /* Meaning, not found in class. */
return class_weight;
wid = lmclass->tag_wid;
}
for (i = 0; i < n_hist; ++i) {
if (history[i] != NGRAM_INVALID_WID
&& NGRAM_IS_CLASSWID(history[i]))
history[i] =
model->classes[NGRAM_CLASSID(history[i])]->tag_wid;
}
prob = (*model->funcs->raw_score) (model, wid, history,
n_hist, n_used);
/* Multiply by unigram in-class weight. */
return prob + class_weight;
}
int32
ngram_probv(ngram_model_t * model, const char *word, ...)
{
va_list history;
const char *hword;
int32 *histid;
int32 n_hist;
int32 n_used;
int32 prob;
va_start(history, word);
n_hist = 0;
while ((hword = va_arg(history, const char *)) != NULL)
++n_hist;
va_end(history);
histid = ckd_calloc(n_hist, sizeof(*histid));
va_start(history, word);
n_hist = 0;
while ((hword = va_arg(history, const char *)) != NULL) {
histid[n_hist] = ngram_wid(model, hword);
++n_hist;
}
va_end(history);
prob = ngram_ng_prob(model, ngram_wid(model, word),
histid, n_hist, &n_used);
ckd_free(histid);
return prob;
}
int32
ngram_prob(ngram_model_t * model, const char* const *words, int32 n)
{
int32 *ctx_id;
int32 nused;
int32 prob;
int32 wid;
uint32 i;
ctx_id = (int32 *) ckd_calloc(n - 1, sizeof(*ctx_id));
for (i = 1; i < (uint32) n; ++i)
ctx_id[i - 1] = ngram_wid(model, words[i]);
wid = ngram_wid(model, *words);
prob = ngram_ng_prob(model, wid, ctx_id, n - 1, &nused);
ckd_free(ctx_id);
return prob;
}
int32
ngram_score_to_prob(ngram_model_t * base, int32 score)
{
int32 prob;
/* Undo insertion penalty. */
prob = score - base->log_wip;
/* Undo language weight. */
prob = (int32) (prob / base->lw);
return prob;
}
int32
ngram_unknown_wid(ngram_model_t * model)
{
int32 val;
/* FIXME: This could be memoized for speed if necessary. */
/* Look up <UNK>, if not found return NGRAM_INVALID_WID. */
if (hash_table_lookup_int32(model->wid, "<UNK>", &val) == -1)
return NGRAM_INVALID_WID;
else
return val;
}
int32
ngram_zero(ngram_model_t * model)
{
return model->log_zero;
}
int32
ngram_model_get_size(ngram_model_t * model)
{
if (model != NULL)
return model->n;
return 0;
}
uint32 const *
ngram_model_get_counts(ngram_model_t * model)
{
if (model != NULL)
return model->n_counts;
return NULL;
}
int32
ngram_wid(ngram_model_t * model, const char *word)
{
int32 val;
if (hash_table_lookup_int32(model->wid, word, &val) == -1)
return ngram_unknown_wid(model);
else
return val;
}
const char *
ngram_word(ngram_model_t * model, int32 wid)
{
/* Remove any class tag */
wid = NGRAM_BASEWID(wid);
if (wid >= model->n_words)
return NULL;
return model->word_str[wid];
}
int32
ngram_add_word_internal(ngram_model_t * model,
const char *word, int32 classid)
{
/* Check for hash collisions. */
int32 wid;
if (hash_table_lookup_int32(model->wid, word, &wid) == 0) {
E_WARN("Omit duplicate word '%s'\n", word);
return wid;
}
/* Take the next available word ID */
wid = model->n_words;
if (classid >= 0) {
wid = NGRAM_CLASSWID(wid, classid);
}
/* Reallocate word_str if necessary. */
if (model->n_words >= model->n_1g_alloc) {
model->n_1g_alloc += UG_ALLOC_STEP;
model->word_str = ckd_realloc(model->word_str,
sizeof(*model->word_str) *
model->n_1g_alloc);
}
/* Add the word string in the appropriate manner. */
/* Class words are always dynamically allocated. */
model->word_str[model->n_words] = ckd_salloc(word);
/* Now enter it into the hash table. */
if (hash_table_enter_int32
(model->wid, model->word_str[model->n_words], wid) != wid) {
E_ERROR
("Hash insertion failed for word %s => %p (should not happen)\n",
model->word_str[model->n_words], (void *) (long) (wid));
}
/* Increment number of words. */
++model->n_words;
return wid;
}
int32
ngram_model_add_word(ngram_model_t * model,
const char *word, float32 weight)
{
int32 wid, prob = model->log_zero;
/* If we add word to unwritable model, we need to make it writable */
if (!model->writable) {
E_WARN("Can't add word '%s' to read-only language model. "
"Disable mmap with '-mmap no' to make it writable\n", word);
return -1;
}
wid = ngram_add_word_internal(model, word, -1);
if (wid == NGRAM_INVALID_WID)
return wid;
/* Do what needs to be done to add the word to the unigram. */
if (model->funcs && model->funcs->add_ug)
prob =
(*model->funcs->add_ug) (model, wid,
logmath_log(model->lmath, weight));
if (prob == 0)
return -1;
return wid;
}
ngram_class_t *
ngram_class_new(ngram_model_t * model, int32 tag_wid, int32 start_wid,
glist_t classwords)
{
ngram_class_t *lmclass;
gnode_t *gn;
float32 tprob;
int i;
lmclass = ckd_calloc(1, sizeof(*lmclass));
lmclass->tag_wid = tag_wid;
/* wid_base is the wid (minus class tag) of the first word in the list. */
lmclass->start_wid = start_wid;
lmclass->n_words = glist_count(classwords);
lmclass->prob1 = ckd_calloc(lmclass->n_words, sizeof(*lmclass->prob1));
lmclass->nword_hash = NULL;
lmclass->n_hash = 0;
tprob = 0.0;
for (gn = classwords; gn; gn = gnode_next(gn)) {
tprob += gnode_float32(gn);
}
if (tprob > 1.1 || tprob < 0.9) {
E_INFO("Total class probability is %f, will normalize\n", tprob);
for (gn = classwords; gn; gn = gnode_next(gn)) {
gn->data.fl /= tprob;
}
}
for (i = 0, gn = classwords; gn; ++i, gn = gnode_next(gn)) {
lmclass->prob1[i] = logmath_log(model->lmath, gnode_float32(gn));
}
return lmclass;
}
int32
ngram_class_add_word(ngram_class_t * lmclass, int32 wid, int32 lweight)
{
int32 hash;
if (lmclass->nword_hash == NULL) {
/* Initialize everything in it to -1 */
lmclass->nword_hash =
ckd_malloc(NGRAM_HASH_SIZE * sizeof(*lmclass->nword_hash));
memset(lmclass->nword_hash, 0xff,
NGRAM_HASH_SIZE * sizeof(*lmclass->nword_hash));
lmclass->n_hash = NGRAM_HASH_SIZE;
lmclass->n_hash_inuse = 0;
}
/* Stupidest possible hash function. This will work pretty well
* when this function is called repeatedly with contiguous word
* IDs, though... */
hash = wid & (lmclass->n_hash - 1);
if (lmclass->nword_hash[hash].wid == -1) {
/* Good, no collision. */
lmclass->nword_hash[hash].wid = wid;
lmclass->nword_hash[hash].prob1 = lweight;
++lmclass->n_hash_inuse;
return hash;
}
else {
int32 next;
/* Collision... Find the end of the hash chain. */
while (lmclass->nword_hash[hash].next != -1)
hash = lmclass->nword_hash[hash].next;
assert(hash != -1);
/* Does we has any more bukkit? */
if (lmclass->n_hash_inuse == lmclass->n_hash) {
/* Oh noes! Ok, we makes more. */
lmclass->nword_hash = ckd_realloc(lmclass->nword_hash,
lmclass->n_hash * 2 *
sizeof(*lmclass->
nword_hash));
memset(lmclass->nword_hash + lmclass->n_hash, 0xff,
lmclass->n_hash * sizeof(*lmclass->nword_hash));
/* Just use the next allocated one (easy) */
next = lmclass->n_hash;
lmclass->n_hash *= 2;
}
else {
/* Look for any available bucket. We hope this doesn't happen. */
for (next = 0; next < lmclass->n_hash; ++next)
if (lmclass->nword_hash[next].wid == -1)
break;
/* This should absolutely not happen. */
assert(next != lmclass->n_hash);
}
lmclass->nword_hash[next].wid = wid;
lmclass->nword_hash[next].prob1 = lweight;
lmclass->nword_hash[hash].next = next;
++lmclass->n_hash_inuse;
return next;
}
}
void
ngram_class_free(ngram_class_t * lmclass)
{
ckd_free(lmclass->nword_hash);
ckd_free(lmclass->prob1);
ckd_free(lmclass);
}
int32
ngram_model_add_class_word(ngram_model_t * model,
const char *classname,
const char *word, float32 weight)
{
ngram_class_t *lmclass;
int32 classid, tag_wid, wid, i, scale;
float32 fprob;
/* Find the class corresponding to classname. Linear search
* probably okay here since there won't be very many classes, and
* this doesn't have to be fast. */
tag_wid = ngram_wid(model, classname);
if (tag_wid == NGRAM_INVALID_WID) {
E_ERROR("No such word or class tag: %s\n", classname);
return tag_wid;
}
for (classid = 0; classid < model->n_classes; ++classid) {
if (model->classes[classid]->tag_wid == tag_wid)
break;
}
/* Hmm, no such class. It's probably not a good idea to create one. */
if (classid == model->n_classes) {
E_ERROR
("Word %s is not a class tag (call ngram_model_add_class() first)\n",
classname);
return NGRAM_INVALID_WID;
}
lmclass = model->classes[classid];
/* Add this word to the model's set of words. */
wid = ngram_add_word_internal(model, word, classid);
if (wid == NGRAM_INVALID_WID)
return wid;
/* This is the fixed probability of the new word. */
fprob = weight * 1.0f / (lmclass->n_words + lmclass->n_hash_inuse + 1);
/* Now normalize everything else to fit it in. This is
* accomplished by simply scaling all the other probabilities
* by (1-fprob). */
scale = logmath_log(model->lmath, 1.0 - fprob);
for (i = 0; i < lmclass->n_words; ++i)
lmclass->prob1[i] += scale;
for (i = 0; i < lmclass->n_hash; ++i)
if (lmclass->nword_hash[i].wid != -1)
lmclass->nword_hash[i].prob1 += scale;
/* Now add it to the class hash table. */
return ngram_class_add_word(lmclass, wid,
logmath_log(model->lmath, fprob));
}
int32
ngram_model_add_class(ngram_model_t * model,
const char *classname,
float32 classweight,
char **words, const float32 * weights, int32 n_words)
{
ngram_class_t *lmclass;
glist_t classwords = NULL;
int32 i, start_wid = -1;
int32 classid, tag_wid;
/* Check if classname already exists in model. If not, add it. */
if ((tag_wid =
ngram_wid(model, classname)) == ngram_unknown_wid(model)) {
tag_wid = ngram_model_add_word(model, classname, classweight);
if (tag_wid == NGRAM_INVALID_WID)
return -1;
}
if (model->n_classes == 128) {
E_ERROR("Number of classes cannot exceed 128 (sorry)\n");
return -1;
}
classid = model->n_classes;
for (i = 0; i < n_words; ++i) {
int32 wid;
wid = ngram_add_word_internal(model, words[i], classid);
if (wid == NGRAM_INVALID_WID)
return -1;
if (start_wid == -1)
start_wid = NGRAM_BASEWID(wid);
classwords = glist_add_float32(classwords, weights[i]);
}
classwords = glist_reverse(classwords);
lmclass = ngram_class_new(model, tag_wid, start_wid, classwords);
glist_free(classwords);
if (lmclass == NULL)
return -1;
++model->n_classes;
if (model->classes == NULL)
model->classes = ckd_calloc(1, sizeof(*model->classes));
else
model->classes = ckd_realloc(model->classes,
model->n_classes *
sizeof(*model->classes));
model->classes[classid] = lmclass;
return classid;
}
int32
ngram_class_prob(ngram_class_t * lmclass, int32 wid)
{
int32 base_wid = NGRAM_BASEWID(wid);
if (base_wid < lmclass->start_wid
|| base_wid > lmclass->start_wid + lmclass->n_words) {
int32 hash;
/* Look it up in the hash table. */
hash = wid & (lmclass->n_hash - 1);
while (hash != -1 && lmclass->nword_hash[hash].wid != wid)
hash = lmclass->nword_hash[hash].next;
if (hash == -1)
return 1;
return lmclass->nword_hash[hash].prob1;
}
else {
return lmclass->prob1[base_wid - lmclass->start_wid];
}
}
int32
read_classdef_file(hash_table_t * classes, const char *file_name)
{
FILE *fp;
int32 is_pipe;
int inclass;
int32 rv = -1;
gnode_t *gn;
glist_t classwords = NULL;
glist_t classprobs = NULL;
char *classname = NULL;
if ((fp = fopen_comp(file_name, "r", &is_pipe)) == NULL) {
E_ERROR("File %s not found\n", file_name);
return -1;
}
inclass = FALSE;
while (!feof(fp)) {
char line[512];
char *wptr[2];
int n_words;
if (fgets(line, sizeof(line), fp) == NULL)
break;
n_words = str2words(line, wptr, 2);
if (n_words <= 0)
continue;
if (inclass) {
/* Look for an end of class marker. */
if (n_words == 2 && 0 == strcmp(wptr[0], "END")) {
classdef_t *classdef;
gnode_t *word, *weight;
int32 i;
if (classname == NULL || 0 != strcmp(wptr[1], classname))
goto error_out;
inclass = FALSE;
/* Construct a class from the list of words collected. */
classdef = ckd_calloc(1, sizeof(*classdef));
classwords = glist_reverse(classwords);
classprobs = glist_reverse(classprobs);
classdef->n_words = glist_count(classwords);
classdef->words = ckd_calloc(classdef->n_words,
sizeof(*classdef->words));
classdef->weights = ckd_calloc(classdef->n_words,
sizeof(*classdef->weights));
word = classwords;
weight = classprobs;
for (i = 0; i < classdef->n_words; ++i) {
classdef->words[i] = gnode_ptr(word);
classdef->weights[i] = gnode_float32(weight);
word = gnode_next(word);
weight = gnode_next(weight);
}
/* Add this class to the hash table. */
if (hash_table_enter(classes, classname, classdef) !=
classdef) {
classdef_free(classdef);
goto error_out;
}
/* Reset everything. */
glist_free(classwords);
glist_free(classprobs);
classwords = NULL;
classprobs = NULL;
classname = NULL;
}
else {
float32 fprob;
if (n_words == 2)
fprob = atof_c(wptr[1]);
else
fprob = 1.0f;
/* Add it to the list of words for this class. */
classwords =
glist_add_ptr(classwords, ckd_salloc(wptr[0]));
classprobs = glist_add_float32(classprobs, fprob);
}
}
else {
/* Start a new LM class if the LMCLASS marker is seen */
if (n_words == 2 && 0 == strcmp(wptr[0], "LMCLASS")) {
if (inclass)
goto error_out;
inclass = TRUE;
classname = ckd_salloc(wptr[1]);
}
/* Otherwise, just ignore whatever junk we got */
}
}
rv = 0; /* Success. */
error_out:
/* Free all the stuff we might have allocated. */
fclose_comp(fp, is_pipe);
for (gn = classwords; gn; gn = gnode_next(gn))
ckd_free(gnode_ptr(gn));
glist_free(classwords);
glist_free(classprobs);
ckd_free(classname);
return rv;
}
void
classdef_free(classdef_t * classdef)
{
int32 i;
for (i = 0; i < classdef->n_words; ++i)
ckd_free(classdef->words[i]);
ckd_free(classdef->words);
ckd_free(classdef->weights);
ckd_free(classdef);
}
int32
ngram_model_read_classdef(ngram_model_t * model, const char *file_name)
{
hash_table_t *classes;
glist_t hl = NULL;
gnode_t *gn;
int32 rv = -1;
classes = hash_table_new(0, FALSE);
if (read_classdef_file(classes, file_name) < 0) {
hash_table_free(classes);
return -1;
}
/* Create a new class in the language model for each classdef. */
hl = hash_table_tolist(classes, NULL);
for (gn = hl; gn; gn = gnode_next(gn)) {
hash_entry_t *he = gnode_ptr(gn);
classdef_t *classdef = he->val;
if (ngram_model_add_class(model, he->key, 1.0,
classdef->words,
classdef->weights,
classdef->n_words) < 0)
goto error_out;
}
rv = 0;
error_out:
for (gn = hl; gn; gn = gnode_next(gn)) {
hash_entry_t *he = gnode_ptr(gn);
ckd_free((char *) he->key);
classdef_free(he->val);
}
glist_free(hl);
hash_table_free(classes);
return rv;
}
case.h
Locale-independent implementation of case swapping operation.
ucase
SPHINXBASE_EXPORT void ucase(char *str)
Convert str to all upper case.
lcase
SPHINXBASE_EXPORT void lcase(char *str)
Convert str to all lower case.
strcmp_nocase
SPHINXBASE_EXPORT int32 strcmp_nocase(const char *str1, const char *str2)
(FIXME!
Definition case.c:94
strncmp_nocase
SPHINXBASE_EXPORT int32 strncmp_nocase(const char *str1, const char *str2, size_t len)
Like strcmp_nocase() but with a maximum length.
Definition case.c:119
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_malloc
#define ckd_malloc(sz)
Macro for ckd_malloc.
Definition ckd_alloc.h:253
ckd_calloc
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
Definition ckd_alloc.h:248
ckd_salloc
#define ckd_salloc(ptr)
Macro for ckd_salloc.
Definition ckd_alloc.h:264
ckd_realloc
#define ckd_realloc(ptr, sz)
Macro for ckd_realloc.
Definition ckd_alloc.h:258
cmd_ln_exists_r
SPHINXBASE_EXPORT int cmd_ln_exists_r(cmd_ln_t *cmdln, char const *name)
Re-entrant version of cmd_ln_exists().
Definition cmd_ln.c:929
err.h
Implementation of logging routines.
E_ERROR
#define E_ERROR(...)
Print error message to error log.
Definition err.h:104
E_INFO
#define E_INFO(...)
Print logging information to standard error stream.
Definition err.h:114
E_WARN
#define E_WARN(...)
Print warning message to error log.
Definition err.h:109
filename.h
File names related operation.
gnode_t
struct gnode_s gnode_t
A node in a generic list.
glist_reverse
SPHINXBASE_EXPORT glist_t glist_reverse(glist_t g)
Reverse the order of the given glist.
Definition glist.c:169
glist_free
SPHINXBASE_EXPORT void glist_free(glist_t g)
Free the given generic list; user-defined data contained within is not automatically freed.
Definition glist.c:133
glist_add_float32
SPHINXBASE_EXPORT glist_t glist_add_float32(glist_t g, float32 val)
Create and prepend a new list node containing a single-precision float.
Definition glist.c:110
glist_add_ptr
SPHINXBASE_EXPORT glist_t glist_add_ptr(glist_t g, void *ptr)
Create and prepend a new list node, with the given user-defined data, at the HEAD of the given generi...
Definition glist.c:74
gnode_ptr
#define gnode_ptr(g)
Head of a list of gnodes.
Definition glist.h:109
glist_count
SPHINXBASE_EXPORT int32 glist_count(glist_t g)
Count the number of element in a given link list.
Definition glist.c:145
hash_entry_t
struct hash_entry_s hash_entry_t
A note by ARCHAN at 20050510: Technically what we use is so-called "hash table with buckets" which is...
hash_table_free
SPHINXBASE_EXPORT void hash_table_free(hash_table_t *h)
Free the specified hash table; the caller is responsible for freeing the key strings pointed to by th...
Definition hash_table.c:688
hash_table_enter_int32
#define hash_table_enter_int32(h, k, v)
Add a 32-bit integer value to a hash table.
Definition hash_table.h:228
hash_table_tolist
SPHINXBASE_EXPORT glist_t hash_table_tolist(hash_table_t *h, int32 *count)
Build a glist of valid hash_entry_t pointers from the given hash table.
Definition hash_table.c:616
hash_table_empty
SPHINXBASE_EXPORT void hash_table_empty(hash_table_t *h)
Delete all entries from a hash_table.
Definition hash_table.c:483
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
hash_table_enter
SPHINXBASE_EXPORT void * hash_table_enter(hash_table_t *h, const char *key, void *val)
Try to add a new entry with given key and associated value to hash table h.
Definition hash_table.c:501
hash_table_new
SPHINXBASE_EXPORT hash_table_t * hash_table_new(int32 size, int32 casearg)
Allocate a new hash table for a given expected size.
Definition hash_table.c:158
logmath.h
Fast integer logarithmic addition operations.
logmath_get_zero
SPHINXBASE_EXPORT int logmath_get_zero(logmath_t *lmath)
Get the smallest possible value represented in this base.
Definition logmath.c:374
logmath_t
struct logmath_s logmath_t
Integer log math computation class.
Definition logmath.h:108
logmath_log
SPHINXBASE_EXPORT int logmath_log(logmath_t *lmath, float64 p)
Convert linear floating point number to integer log in base B.
Definition logmath.c:447
ngram_model.h
N-Gram language models.
ngram_model_add_class
SPHINXBASE_EXPORT int32 ngram_model_add_class(ngram_model_t *model, const char *classname, float32 classweight, char **words, const float32 *weights, int32 n_words)
Add a new class to a language model.
Definition ngram_model.c:831
ngram_tg_score
SPHINXBASE_EXPORT int32 ngram_tg_score(ngram_model_t *model, int32 w3, int32 w2, int32 w1, int32 *n_used)
Quick trigram score lookup.
Definition ngram_model.c:438
ngram_unknown_wid
SPHINXBASE_EXPORT int32 ngram_unknown_wid(ngram_model_t *model)
Get the unknown word ID for a language model.
Definition ngram_model.c:550
ngram_ng_prob
SPHINXBASE_EXPORT int32 ngram_ng_prob(ngram_model_t *model, int32 wid, int32 *history, int32 n_hist, int32 *n_used)
Quick "raw" probability lookup for a general N-Gram.
Definition ngram_model.c:454
ngram_word
SPHINXBASE_EXPORT const char * ngram_word(ngram_model_t *model, int32 wid)
Look up word string for numerical word ID.
Definition ngram_model.c:596
ngram_model_add_word
SPHINXBASE_EXPORT int32 ngram_model_add_word(ngram_model_t *model, const char *word, float32 weight)
Add a word (unigram) to the language model.
Definition ngram_model.c:649
ngram_model_add_class_word
SPHINXBASE_EXPORT int32 ngram_model_add_class_word(ngram_model_t *model, const char *classname, const char *word, float32 weight)
Add a word to a class in a language model.
Definition ngram_model.c:779
NGRAM_INVALID_WID
#define NGRAM_INVALID_WID
Impossible word ID.
Definition ngram_model.h:83
NGRAM_INVALID
@ NGRAM_INVALID
Not a valid file type.
Definition ngram_model.h:77
NGRAM_AUTO
@ NGRAM_AUTO
Determine file type automatically.
Definition ngram_model.h:78
NGRAM_BIN
@ NGRAM_BIN
Sphinx .DMP format.
Definition ngram_model.h:80
NGRAM_ARPA
@ NGRAM_ARPA
ARPABO text format (the standard).
Definition ngram_model.h:79
ngram_model_casefold
SPHINXBASE_EXPORT int ngram_model_casefold(ngram_model_t *model, int kase)
Case-fold word strings in an N-Gram model.
Definition ngram_model.c:308
ngram_model_get_weights
SPHINXBASE_EXPORT float32 ngram_model_get_weights(ngram_model_t *model, int32 *out_log_wip)
Get the current weights from a language model.
Definition ngram_model.c:366
ngram_model_get_size
SPHINXBASE_EXPORT int32 ngram_model_get_size(ngram_model_t *model)
Get the order of the N-gram model (i.e.
Definition ngram_model.c:569
ngram_model_apply_weights
SPHINXBASE_EXPORT int ngram_model_apply_weights(ngram_model_t *model, float32 lw, float32 wip)
Apply a language weight, insertion penalty, and unigram weight to a language model.
Definition ngram_model.c:360
ngram_ng_score
SPHINXBASE_EXPORT int32 ngram_ng_score(ngram_model_t *model, int32 wid, int32 *history, int32 n_hist, int32 *n_used)
Quick general N-Gram score lookup.
Definition ngram_model.c:375
ngram_probv
SPHINXBASE_EXPORT int32 ngram_probv(ngram_model_t *model, const char *word,...)
Get the "raw" log-probability for a general N-Gram.
Definition ngram_model.c:486
ngram_model_read
SPHINXBASE_EXPORT ngram_model_t * ngram_model_read(cmd_ln_t *config, const char *file_name, ngram_file_type_t file_type, logmath_t *lmath)
Read an N-Gram model from a file on disk.
Definition ngram_model.c:124
ngram_model_flush
SPHINXBASE_EXPORT void ngram_model_flush(ngram_model_t *lm)
Flush any cached N-Gram information.
Definition ngram_model.c:256
ngram_type_to_str
SPHINXBASE_EXPORT char const * ngram_type_to_str(int type)
Get the canonical name for an N-Gram file type.
Definition ngram_model.c:110
ngram_bg_score
SPHINXBASE_EXPORT int32 ngram_bg_score(ngram_model_t *model, int32 w2, int32 w1, int32 *n_used)
Quick bigram score lookup.
Definition ngram_model.c:448
ngram_prob
SPHINXBASE_EXPORT int32 ngram_prob(ngram_model_t *model, const char *const *words, int32 n)
Get the "raw" log-probability for a general N-Gram.
Definition ngram_model.c:517
ngram_model_read_classdef
SPHINXBASE_EXPORT int32 ngram_model_read_classdef(ngram_model_t *model, const char *file_name)
Read a class definition file and add classes to a language model.
Definition ngram_model.c:1027
ngram_score
SPHINXBASE_EXPORT int32 ngram_score(ngram_model_t *model, const char *word,...)
Get the score (scaled, interpolated log-probability) for a general N-Gram.
Definition ngram_model.c:407
ngram_model_get_counts
SPHINXBASE_EXPORT uint32 const * ngram_model_get_counts(ngram_model_t *model)
Get the counts of the various N-grams in the model.
Definition ngram_model.c:577
ngram_file_type_t
enum ngram_file_type_e ngram_file_type_t
File types for N-Gram files.
ngram_model_write
SPHINXBASE_EXPORT int ngram_model_write(ngram_model_t *model, const char *file_name, ngram_file_type_t format)
Write an N-Gram model to disk.
Definition ngram_model.c:178
ngram_wid
SPHINXBASE_EXPORT int32 ngram_wid(ngram_model_t *model, const char *word)
Look up numerical word ID.
Definition ngram_model.c:585
ngram_file_name_to_type
SPHINXBASE_EXPORT ngram_file_type_t ngram_file_name_to_type(const char *file_name)
Guess the file type for an N-Gram model from the filename.
Definition ngram_model.c:63
ngram_score_to_prob
SPHINXBASE_EXPORT int32 ngram_score_to_prob(ngram_model_t *model, int32 score)
Convert score to "raw" log-probability.
Definition ngram_model.c:537
ngram_class_t
struct ngram_class_s ngram_class_t
Abstract type representing a word class in an N-Gram model.
Definition ngram_model.h:71
ngram_zero
SPHINXBASE_EXPORT int32 ngram_zero(ngram_model_t *model)
Get the "zero" log-probability value for a language model.
Definition ngram_model.c:563
ngram_model_free
SPHINXBASE_EXPORT int ngram_model_free(ngram_model_t *model)
Release memory associated with an N-Gram model.
Definition ngram_model.c:263
ngram_model_retain
SPHINXBASE_EXPORT ngram_model_t * ngram_model_retain(ngram_model_t *model)
Retain ownership of an N-Gram model.
Definition ngram_model.c:249
ngram_model_t
struct ngram_model_s ngram_model_t
Abstract type representing an N-Gram based language model.
Definition ngram_model.h:66
ngram_str_to_type
SPHINXBASE_EXPORT ngram_file_type_t ngram_str_to_type(const char *str_name)
Get the N-Gram file type from a string.
Definition ngram_model.c:99
pio.h
file IO related operations.
fclose_comp
SPHINXBASE_EXPORT void fclose_comp(FILE *fp, int32 ispipe)
Close a file opened using fopen_comp.
Definition pio.c:184
fopen_comp
SPHINXBASE_EXPORT FILE * fopen_comp(const char *file, const char *mode, int32 *ispipe)
Like fopen, but use popen and zcat if it is determined that "file" is compressed (i....
Definition pio.c:107
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
cmd_ln_t
Opaque structure used to hold the results of command-line parsing.
hash_entry_s::val
void * val
Key-length; the key string does not have to be a C-style NULL terminated string; it can have arbitrar...
Definition hash_table.h:155
ngram_class_s::ngram_hash_s::prob1
int32 prob1
Probability for this word.
Definition ngram_model_internal.h:91
ngram_class_s::ngram_hash_s::next
int32 next
Index of next bucket (or -1 for no collision).
Definition ngram_model_internal.h:92
ngram_class_s::ngram_hash_s::wid
int32 wid
Word ID of this bucket.
Definition ngram_model_internal.h:90
ngram_class_s::start_wid
int32 start_wid
Starting base word ID for this class' words.
Definition ngram_model_internal.h:83
ngram_class_s::prob1
int32 * prob1
Probability table for base words.
Definition ngram_model_internal.h:85
ngram_class_s::n_hash_inuse
int32 n_hash_inuse
Number of words in nword_hash.
Definition ngram_model_internal.h:95
ngram_class_s::n_hash
int32 n_hash
Number of buckets in nword_hash (power of 2).
Definition ngram_model_internal.h:94
ngram_class_s::tag_wid
int32 tag_wid
Base word ID for this class tag.
Definition ngram_model_internal.h:82
ngram_class_s::n_words
int32 n_words
Number of base words for this class.
Definition ngram_model_internal.h:84
ngram_funcs_s::raw_score
int32(* raw_score)(ngram_model_t *model, int32 wid, int32 *history, int32 n_hist, int32 *n_used)
Implementation-specific function for querying raw language model probability.
Definition ngram_model_internal.h:129
ngram_funcs_s::score
int32(* score)(ngram_model_t *model, int32 wid, int32 *history, int32 n_hist, int32 *n_used)
Implementation-specific function for querying language model score.
Definition ngram_model_internal.h:122
ngram_funcs_s::free
void(* free)(ngram_model_t *model)
Implementation-specific function for freeing an ngram_model_t.
Definition ngram_model_internal.h:114
ngram_funcs_s::apply_weights
int(* apply_weights)(ngram_model_t *model, float32 lw, float32 wip)
Implementation-specific function for applying language model weights.
Definition ngram_model_internal.h:118
ngram_funcs_s::add_ug
int32(* add_ug)(ngram_model_t *model, int32 wid, int32 lweight)
Implementation-specific function for adding unigrams.
Definition ngram_model_internal.h:143
ngram_funcs_s::flush
void(* flush)(ngram_model_t *model)
Implementation-specific function for purging N-Gram cache.
Definition ngram_model_internal.h:148
ngram_model_s::lmath
logmath_t * lmath
Log-math object.
Definition ngram_model_internal.h:67
ngram_model_s::classes
struct ngram_class_s ** classes
Word class definitions.
Definition ngram_model_internal.h:74
ngram_model_s::refcount
int refcount
Reference count.
Definition ngram_model_internal.h:56
ngram_model_s::n
uint8 n
This is an n-gram model (1, 2, 3, ...).
Definition ngram_model_internal.h:62
ngram_model_s::log_wip
int32 log_wip
Log of word insertion penalty.
Definition ngram_model_internal.h:69
ngram_model_s::n_1g_alloc
int32 n_1g_alloc
Number of allocated word strings (for new word addition).
Definition ngram_model_internal.h:58
ngram_model_s::log_zero
int32 log_zero
Zero probability, cached here for quick lookup.
Definition ngram_model_internal.h:70
ngram_model_s::n_counts
uint32 * n_counts
Counts for 1, 2, 3, ... grams.
Definition ngram_model_internal.h:57
ngram_model_s::n_words
int32 n_words
Number of actual word strings (NOT the same as the number of unigrams, due to class words).
Definition ngram_model_internal.h:59
ngram_model_s::wid
hash_table_t * wid
Mapping of unigram names to word IDs.
Definition ngram_model_internal.h:72
ngram_model_s::lw
float32 lw
Language model scaling factor.
Definition ngram_model_internal.h:68
ngram_model_s::writable
uint8 writable
Are word strings writable?
Definition ngram_model_internal.h:64
ngram_model_s::funcs
struct ngram_funcs_s * funcs
Implementation-specific methods.
Definition ngram_model_internal.h:75
ngram_model_s::n_classes
uint8 n_classes
Number of classes (maximum 128).
Definition ngram_model_internal.h:63
ngram_model_s::word_str
char ** word_str
Unigram names.
Definition ngram_model_internal.h:71