libsent/src/ngram/ngram_read_arpa.c

Go to the documentation of this file.

/*
 * Copyright (c) 1991-2007 Kawahara Lab., Kyoto University
 * Copyright (c) 2000-2005 Shikano Lab., Nara Institute of Science and Technology
 * Copyright (c) 2005-2007 Julius project team, Nagoya Institute of Technology
 * All rights reserved
 */

/* $Id: ngram_read_arpa.c,v 1.1.1.1 2007/09/28 02:50:56 sumomo Exp $ */

/* words should be alphabetically sorted */

#include <sent/stddefs.h>
#include <sent/ngram2.h>

static char buf[800];                   
static char pbuf[800];                  


static int
get_total_info(FILE *fp, int num[])
{
  char *p;
  int n;
  int maxn;
  int entry_num;

  maxn = 0;
  while (getl(buf, sizeof(buf), fp) != NULL && buf[0] != '\\') {
    if (strnmatch(buf, "ngram", 5)) { /* n-gram num */
      p = strtok(buf, "=");
      n = p[strlen(p)-1] - '0';
      if (n > MAX_N) {
        jlog("Error: too long N-gram (N=%d)\n", n);
        jlog("Error: current maximum length of N-gram is set to %d\n", MAX_N);
        jlog("Error: you can expand the limit by setting MAX_N in \"sent/ngram.h\"\n");
        return -1;
      }
      p = strtok(NULL, "=");
      entry_num = atoi(p);
      /* ignore empty entry */
      if (entry_num == 0) {
        jlog("Warning: empty %d-gram, skipped\n", n);
      } else {
        num[n-1] = entry_num;
        if (maxn < n) maxn = n;
      }
    }
  }

  return(maxn);
}

static boolean
set_unigram(FILE *fp, NGRAM_INFO *ndata)
{
  WORD_ID nid;
  int resid;
  LOGPROB prob, bo_wt;
  char *name, *p;
  boolean ok_p = TRUE;
  NGRAM_TUPLE_INFO *t;

  t = &(ndata->d[0]);

  /* malloc name area */
  ndata->wname = (char **)mymalloc(sizeof(char *) * ndata->max_word_num);

  /* malloc data area */
  //t->bgn_upper = t->bgn_lower = t->bgn = t->num = NULL;
  t->bgn_upper = NULL;
  t->bgn_lower = NULL;
  t->bgn = NULL;
  t->num = NULL;
  t->bgnlistlen = 0;
  t->nnid2wid = NULL;
  t->prob = (LOGPROB *)mymalloc(sizeof(LOGPROB) * t->totalnum);
  t->bo_wt = (LOGPROB *)mymalloc(sizeof(LOGPROB) * t->totalnum);
  t->context_num = t->totalnum;
  t->nnid2ctid_upper = NULL;
  t->nnid2ctid_lower = NULL;

  nid = 0;
  
  while (getl(buf, sizeof(buf), fp) != NULL && buf[0] != '\\') {
    if ((p = strtok(buf, DELM)) == NULL) {
      jlog("Error: ngram_read_arpa: LR 1-gram: failed to parse, corrupted or invalid data?\n");
      return FALSE;
    }
    prob = (LOGPROB)atof(p);
    if ((p = strtok(NULL, DELM)) == NULL) {
      jlog("Error: ngram_read_arpa: LR 1-gram: failed to parse, corrupted or invalid data?\n");
      return FALSE;
    }
    name = strcpy((char *)mymalloc(strlen(p)+1), p);
    if ((p = strtok(NULL, DELM)) == NULL) {
      jlog("Error: ngram_read_arpa: LR 1-gram: failed to parse, corrupted or invalid data?\n");
      return FALSE;
    }
    bo_wt = (LOGPROB)atof(p);

    /* register word entry name */
    ndata->wname[nid] = name;

    /* add entry name to index tree */
    if (ndata->root == NULL) {
      ndata->root = ptree_make_root_node(nid);
    } else {
      resid = ptree_search_data(name, ndata->root);
      if (resid != -1 && strmatch(name, ndata->wname[resid])) { /* already exist */
        jlog("Error: ngram_read_arpa: duplicate word entry \"%s\" at #%d and #%d in 1-gram\n", name, resid, nid);
        ok_p = FALSE;
        continue;
      } else {
        ptree_add_entry(name, nid, ndata->wname[resid], &(ndata->root));
      }
    }

    if (nid >= ndata->max_word_num) {
      jlog("Error: ngram_read_arpa: num of 1-gram is bigger than header value (%d)\n", ndata->max_word_num);
      return FALSE;
    }

    /* register entry info */
    t->prob[nid] = prob;
    t->bo_wt[nid] = bo_wt;
  
    nid++;
  }

  if (nid != t->totalnum) {
    jlog("Error: ngram_read_arpa: num of 1-gram (%d) not equal to header value (%d)\n", nid, t->totalnum);
    return FALSE;
  }

  if (ok_p == TRUE) {
    jlog("Stat: ngram_read_arpa: read %d 1-gram entries\n", nid);
  }
  
  return ok_p;
}

/* read-in 1-gram (RL) --- only add back-off weight */
static boolean
add_unigram(FILE *fp, NGRAM_INFO *ndata)
{
  WORD_ID read_word_num;
  WORD_ID nid;
  LOGPROB prob, bo_wt;
  char *name, *p;
  boolean ok_p = TRUE;
  boolean mismatched = FALSE;

  ndata->bo_wt_1 = (LOGPROB *)mymalloc(sizeof(LOGPROB) * ndata->max_word_num);

  read_word_num = 0;
  while (getl(buf, sizeof(buf), fp) != NULL && buf[0] != '\\') {
    if ((p = strtok(buf, DELM)) == NULL) {
      jlog("Error: ngram_read_arpa: RL 1-gram: failed to parse, corrupted or invalid data?\n");
      return FALSE;
    }
    prob = atof(p);
    if ((p = strtok(NULL, DELM)) == NULL) {
      jlog("Error: ngram_read_arpa: RL 1-gram: failed to parse, corrupted or invalid data?\n");
      return FALSE;
    }
    name = strcpy((char *)mymalloc(strlen(p)+1), p);
    if ((p = strtok(NULL, DELM)) == NULL) {
      jlog("Error: ngram_read_arpa: RL 1-gram: failed to parse, corrupted or invalid data?\n");
      return FALSE;
    }
    bo_wt = (LOGPROB)atof(p);
  
    /* add bo_wt_rl to existing 1-gram entry */
    nid = ngram_lookup_word(ndata, name);
    if (nid == WORD_INVALID) {
      if (mismatched == FALSE) {
        jlog("Error: ngram_read_arpa: vocabulary mismatch between LR n-gram and RL n-gram\n");
        mismatched = TRUE;
      }
      jlog("Error: ngram_read_arpa: \"%s\" does not appears in LR n-gram\n", name);
      ok_p = FALSE;
    } else {
      ndata->bo_wt_1[nid] = bo_wt;
    }
  
    read_word_num++;
    if (read_word_num > ndata->max_word_num) {
      jlog("Error: ngram_read_arpa: vocabulary size of RL n-gram is bigger than header value (%d)\n", ndata->max_word_num);
      return FALSE;
    }
    free(name);
  }
  if (ok_p == TRUE) {
    jlog("Stat: ngram_read_arpa: read %d 1-gram entries\n", read_word_num);
  }

  return ok_p;
}

static boolean
add_bigram(FILE *fp, NGRAM_INFO *ndata)
{
  WORD_ID w[2], wtmp;
  LOGPROB prob;
  int bi_count = 0;
  NNID n2;
  boolean ok_p = TRUE;
  char *s;

  ndata->p_2 = (LOGPROB *)mymalloc(sizeof(LOGPROB)*ndata->d[1].totalnum);

  while (getl(buf, sizeof(buf), fp) != NULL && buf[0] != '\\') {
    strcpy(pbuf, buf);
    if ( ++bi_count % 100000 == 0) {
      jlog("Stat: ngram_read_arpa: 2-gram read %d (%d%%)\n", bi_count, bi_count * 100 / ndata->d[1].totalnum);
    }
    if ((s = strtok(buf, DELM)) == NULL) {
      jlog("Error: ngram_read_arpa: 2-gram: failed to parse, corrupted or invalid data?\n");
      return FALSE;
    }
    prob = (LOGPROB)atof(s);
    if ((s = strtok(NULL, DELM)) == NULL) {
      jlog("Error: ngram_read_arpa: 2-gram: failed to parse, corrupted or invalid data?\n");
      return FALSE;
    }
    w[0] = ngram_lookup_word(ndata, s);
    if (w[1] == WORD_INVALID) {
      jlog("Error: ngram_read_arpa: 2-gram #%d: \"%s\": \"%s\" not exist in 1-gram\n", n2+1, pbuf, s);
      ok_p = FALSE;
      continue;
    }
    if ((s = strtok(NULL, DELM)) == NULL) {
      jlog("Error: ngram_read_arpa: 2-gram: failed to parse, corrupted or invalid data?\n");
      return FALSE;
    }
    w[1] = ngram_lookup_word(ndata, s);
    if (w[0] == WORD_INVALID) {
      jlog("Error: ngram_read_arpa: 2-gram #%d: \"%s\": \"%s\" not exist in 1-gram\n", n2+1, pbuf, s);
      ok_p = FALSE;
      continue;
    }
    if (ndata->dir == DIR_RL) {
      /* word order should be reversed */
      wtmp = w[0];
      w[0] = w[1];
      w[1] = wtmp;
    }
    n2 = search_ngram(ndata, 2, w);
    if (n2 == NNID_INVALID) {
      jlog("Warning: ngram_read_arpa: 2-gram #%d: \"%s\": (%s,%s) not exist in LR 2-gram (ignored)\n", n2+1, pbuf, ndata->wname[w[0]], ndata->wname[w[1]]);
    } else {
      ndata->p_2[n2] = prob;
    }
  }

  if (ok_p == TRUE) {
    jlog("Stat: ngram_read_arpa: 2-gram read %d end\n", bi_count);
  }

  return ok_p;
}
    
static boolean
set_ngram(FILE *fp, NGRAM_INFO *ndata, int n)
{
  NNID i;
  WORD_ID w[MAX_N];
  WORD_ID w_last[MAX_N];
  LOGPROB p, bowt;
  NNID nnid;
  NNID cid, cid_last;
  boolean ok_p = TRUE;
  char *s;
  NGRAM_TUPLE_INFO *t;
  NGRAM_TUPLE_INFO *tprev;
  NNID ntmp;

  if (n < 2) {
    jlog("Error: ngram_read_arpa: unable to process 1-gram\n");
    return FALSE;
  }

  t = &(ndata->d[n-1]);
  tprev = &(ndata->d[n-2]);

  /* initialize pointer storage to access from (N-1)-gram */
  t->bgnlistlen = tprev->context_num;
  if (t->is24bit) {
    t->bgn_upper = (NNID_UPPER *)mymalloc(sizeof(NNID_UPPER) * t->bgnlistlen);
    t->bgn_lower = (NNID_LOWER *)mymalloc(sizeof(NNID_LOWER) * t->bgnlistlen);
    for(i = 0; i < t->bgnlistlen; i++) {    
      t->bgn_upper[i] = NNID_INVALID_UPPER;
      t->bgn_lower[i] = 0;
    }
  } else {
    t->bgn = (NNID *)mymalloc(sizeof(NNID) * t->bgnlistlen);
    for(i = 0;i < t->bgnlistlen; i++) {
      t->bgn[i] = NNID_INVALID;
    }
  }
  t->num = (WORD_ID *)mymalloc(sizeof(WORD_ID) * t->bgnlistlen);
  for(i = 0; i < t->bgnlistlen; i++) {
    t->num[i] = 0;
  }

  /* allocate data area */
  t->nnid2wid = (WORD_ID *)mymalloc(sizeof(WORD_ID) * t->totalnum);
  t->prob = (LOGPROB *)mymalloc(sizeof(LOGPROB) * t->totalnum);
  t->bo_wt = NULL;
  t->nnid2ctid_upper = NULL;
  t->nnid2ctid_lower = NULL;

  nnid = 0;
  cid = cid_last = NNID_INVALID;
  for(i=0;i<n;i++) w_last[i] = WORD_INVALID;

  /* read in 2-gram */
  for (;;) {
    if (getl(buf, sizeof(buf), fp) == NULL || buf[0] == '\\') break;
    strcpy(pbuf, buf);
    if ( nnid % 100000 == 0) {
      jlog("Stat: ngram_read_arpa: %d-gram read %d (%d%%)\n", n, nnid, nnid * 100 / t->totalnum);
    }

    /* 2-gram probability */
    if ((s = strtok(buf, DELM)) == NULL) {
      jlog("Error: ngram_read_arpa: %d-gram: failed to parse, corrupted or invalid data?\n", n);
      return FALSE;
    }
    p = (LOGPROB)atof(s);
    /* read in context word and lookup the ID */
    for(i=0;i<n;i++) {
      if ((s = strtok(NULL, DELM)) == NULL) {
        jlog("Error: ngram_read_arpa: %d-gram: failed to parse, corrupted or invalid data?\n", n);
        return FALSE;
      }
      if ((w[i] = ngram_lookup_word(ndata, s)) == WORD_INVALID) {
        jlog("Error: ngram_read_arpa: %d-gram #%d: \"%s\": \"%s\" not exist in %d-gram\n", n, nnid+1, pbuf, s, n);
        ok_p = FALSE;
        break;
      }
      /* increment nnid_bgn and nnid_num if context word changed */
    }
    if (i < n) continue;        /* error out */

    /* detect context entry change at this line */
    for(i=0;i<n-1;i++) {
      if (w[i] != w_last[i]) break;
    }
    if (i < n-1) {              /* context changed here */
      /* find new entry point */
      cid = search_ngram(ndata, n-1, w);
      if (cid == NNID_INVALID) {        /* no context */
        //jlog("Warning: ngram_read_arpa: %d-gram #%d: \"%s\": context (%s,%s) not exist in %d-gram (ignored)\n", n, nnid+1, pbuf, ndata->wname[w_m], ndata->wname[w_r], n-1);
        jlog("Warning: ngram_read_arpa: %d-gram #%d: \"%s\": context (",
             n, nnid+1, pbuf);
        for(i=0;i<n-1;i++) {
          jlog(" %s", ndata->wname[w[i]]);
        }
        jlog(") not exist in %d-gram (ignored)\n", n-1);
        ok_p = FALSE;
        continue;
      }
      if (cid_last != NNID_INVALID) {
        /* close last entry */
        if (t->is24bit) {
          ntmp = ((NNID)(t->bgn_upper[cid_last]) << 16) + (NNID)(t->bgn_lower[cid_last]);
        } else {
          ntmp = t->bgn[cid_last];
        }
        t->num[cid_last] = nnid - ntmp;
      }
      /* the next context word should be an new entry */
      if (t->is24bit) {
        if (t->bgn_upper[cid] != NNID_INVALID_UPPER) {
          jlog("Error: ngram_read_arpa: %d-gram #%d: \"%s\": word order is not the same as 1-gram\n", n, nnid+1, pbuf);
          return FALSE;
        }
        ntmp = nnid & 0xffff;
        t->bgn_lower[cid] = ntmp;
        ntmp = nnid >> 16;
        t->bgn_upper[cid] = ntmp;
      } else {
        if (t->bgn[cid] != NNID_INVALID) {
          jlog("Error: ngram_read_arpa: %d-gram #%d: \"%s\": word order is not the same as 1-gram\n", n, nnid+1, pbuf);
          return FALSE;
        }
        t->bgn[cid] = nnid;
      }

      cid_last = cid;
      w_last[n-1] = WORD_INVALID;
    }

    /* store the probabilities of the target word */
    if (w[n-1] == w_last[n-1]) {
      jlog("Error: ngram_read_arpa: %d-gram #%d: \"%s\": duplicated entry\n", n, nnid+1, pbuf);
      ok_p = FALSE;
      continue;
    } else if (w_last[n-1] != WORD_INVALID && w[n-1] < w_last[n-1]) {
      jlog("Error: ngram_read_arpa: %d-gram #%d: \"%s\": word order is not the same as 1-gram\n", n, nnid+1, pbuf);
      return FALSE;
    }

    /* if the 2-gram has back-off entries, store them here */
    if ((s = strtok(NULL, DELM)) != NULL) {
      bowt = (LOGPROB) atof(s);
      if (t->bo_wt == NULL) {
        t->bo_wt = (LOGPROB *)mymalloc(sizeof(LOGPROB) * t->totalnum);
      }
      t->bo_wt[nnid] = bowt;
    }

    /* store the entry info */
    t->nnid2wid[nnid] = w[n-1];
    t->prob[nnid] = p;

    nnid++;
    for(i=0;i<n;i++) w_last[i] = w[i];

    /* check total num */
    if (nnid > t->totalnum) {
      jlog("Error: ngram_read_arpa: %d-gram: read num (%d) not match the header value (%d)\n", n, nnid, t->totalnum);
      return FALSE;
    }
  }
  
  /* set the last entry */
  if (t->is24bit) {
    ntmp = ((NNID)(t->bgn_upper[cid_last]) << 16) + (NNID)(t->bgn_lower[cid_last]);
  } else {
    ntmp = t->bgn[cid_last];
  }
  t->num[cid_last] = nnid - ntmp;

  if (t->bo_wt != NULL) t->context_num = t->totalnum;

  if (ok_p == TRUE) {
    jlog("Stat: ngram_read_arpa: %d-gram read %d end\n", n, nnid);
  }

  return ok_p;
}

boolean
ngram_read_arpa(FILE *fp, NGRAM_INFO *ndata, boolean addition)
{
  int i, n;
  int num[MAX_N];

  /* source file is not a binary N-gram */
  ndata->from_bin = FALSE;
  ndata->bigram_index_reversed = FALSE;

  /* read until `\data\' found */
  while (getl(buf, sizeof(buf), fp) != NULL && strncmp(buf,"\\data\\",6) != 0);


  if (addition) {
    /* reading additional forward 2-gram for the 1st pass */
    /* read n-gram total info */
    n = get_total_info(fp, num);
    if (n == -1) {              /* error */
      return FALSE;
    }

    /* check N limit */
    if (n < 2) {
      jlog("Error: forward N-gram for pass1 is does not contain 2-gram\n");
      return FALSE;
    }
    if (n > 2) {
      jlog("Warning: forward N-gram for pass1 contains %d-gram, only 2-gram will be used\n", n);
    }

    /* check if the numbers are the same with already read n-gram */
    for(i=0;i<2;i++) {
      if (ndata->d[i].totalnum != num[i]) {
        jlog("Warning: ngram_read_arpa: %d-gram total num differ between forward N-gram and backward N-gram, may cause some error\n", n+1);
      }
    }
    /* read additional 1-gram data */
    if (!strnmatch(buf,"\\1-grams",8)) {
      jlog("Error: ngram_read_arpa: 1-gram not found for additional LR 2-gram\n");
      return FALSE;
    }
    jlog("Stat: ngram_read_arpa: reading 1-gram part...\n");
    if (add_unigram(fp, ndata) == FALSE) return FALSE;
    /* read 2-gram data */
    if (!strnmatch(buf,"\\2-grams", 8)) {
      jlog("Error: ngram_read_arpa: 2-gram not found for additional LR 2-gram\n");
      return FALSE;
    }
    jlog("Stat: ngram_read_arpa: reading 2-gram part...\n");
    if (add_bigram(fp, ndata) == FALSE) return FALSE;


    /* ignore the rest */
    if (strnmatch(buf,"\\3-grams", 8)) {
      jlog("Warning: forward n-gram contains more than 3-gram, ignored\n");
    }

  } else {
    /* read n-gram total info */
    n = get_total_info(fp, num);
    if (n == -1) {              /* error */
      return FALSE;
    }
    jlog("Stat: ngram_read_arpa: this is %d-gram file\n", n);
    for(i=0;i<n;i++) {
      ndata->d[i].totalnum = num[i];
    }
    
    /* set word num */
    if (ndata->d[0].totalnum > MAX_WORD_NUM) {
      jlog("Error: ngram_read_arpa: N-gram vocabulary size exceeds the limit (%d)\n", MAX_WORD_NUM);
      return FALSE;
    }
    ndata->max_word_num = ndata->d[0].totalnum;
    
    /* check if each N-gram allows 24bit and back-off compaction mode */
    /* for fast access, 1-gram and 2-gram always use non-compaction mode */
    for(i=0;i<n;i++) {
      if (i < 2) {              /* not use for 1-gram and 2-gram */
        ndata->d[i].is24bit = FALSE;
      } else {
        /* for 3-gram and later 24 bit mode is preferred,
           but should be disabled if number of entries is over 2^24 */
        if (ndata->d[i].totalnum >= NNIDMAX) {
          jlog("Warning: ngram_read_arpa: more than 24bit %d-gram tuples, use 32bit index\n", NNIDMAX, n+1);
          ndata->d[i].is24bit = FALSE;
        } else {
          ndata->d[i].is24bit = TRUE;
        }
      }
    }
    /* disable ct_compaction flag while reading ARPA data */
    for(i=0;i<n;i++) {
      ndata->d[i].ct_compaction = FALSE;
    }
    
    /* read 1-gram data */
    if (!strnmatch(buf,"\\1-grams",8)) {
      jlog("Error: ngram_read_arpa: data format error: 1-gram not found\n");
      return FALSE;
    }
    jlog("Stat: ngram_read_arpa: reading 1-gram part...\n");
    if (set_unigram(fp, ndata) == FALSE) return FALSE;
    
    i = 2;
    while(i <= n) {
      /* read n-gram data in turn */
      sprintf(pbuf, "\\%d-grams", i);
      if (!strnmatch(buf, pbuf, 8)) {
        jlog("Error: ngram_read_arpa: data format error: %d-gram not found\n", i);
        return FALSE;
      }
      jlog("Stat: ngram_read_arpa: reading %d-gram part...\n", i);
      if (set_ngram(fp, ndata, i) == FALSE) return FALSE;
      i++;
    }
    /* finished reading file */
    if (!strnmatch(buf, "\\end", 4)) {
      jlog("Error: ngram_read_arpa: data format error: end marker \"\\end\" not found\n");
      return FALSE;
    }

    ndata->n = n;

    for(i=1;i<n;i++) {
      if (ndata->d[i].bo_wt != NULL) {
        /* perform back-off compaction */
        if (ngram_compact_context(ndata, i+1) == FALSE) return FALSE;
        ndata->d[i].ct_compaction = TRUE;
      }
    }
    
    /* set unknown (=OOV) word id */
    set_unknown_id(ndata);
    
  }
    
#ifdef CLASS_NGRAM
  /* skip in-class word entries (they should be in word dictionary) */
  if (getl(buf, sizeof(buf), fp) != NULL) {
    if (strnmatch(buf, "\\class", 6)) {
      jlog("Stat: ngram_read_arpa: skipping in-class word entries...\n");
    }
  }
#endif

  bi_prob_func_set(ndata);

  return TRUE;
}

---