pico/lib/picoklex.c

/*
 * Copyright (C) 2008-2009 SVOX AG, Baslerstr. 30, 8048 Zuerich, Switzerland
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/**
 * @file picoklex.c
 *
 * Copyright (C) 2008-2009 SVOX AG, Baslerstr. 30, 8048 Zuerich, Switzerland
 * All rights reserved.
 *
 * History:
 * - 2009-04-20 -- initial version
 *
 */
#include "picoos.h"
#include "picodbg.h"
#include "picodata.h"
#include "picoknow.h"
#include "picoklex.h"

#ifdef __cplusplus
extern "C" {
#endif
#if 0
}
#endif

/* ************************************************************/
/* lexicon */
/* ************************************************************/

/**
 * @addtogroup picolex
 *
  overview:
  - lex consists of optional searchindex and a non-empty list of lexblocks
  - lexblocks are fixed size, at the start of a block there is also the
    start of an entry
  - using the searchindex a unambiguous lexblock can be determined which
    contains the entry (or there is no entry)
  - one lex entry has POS GRAPH PHON, all mandatory, but
    - PHON can be empty string -> no pronunciation in the resulting TTS output
    - PHON can be :G2P -> use G2P later to add pronunciation
  - (POS,GRAPH) is a uniq key (only one entry allowed)
  - (GRAPH) is almost a uniq key (2-4 entries with the same GRAPH, and
    differing POS and differing PHON possible)
    - for one graph we can have two or three solutions from the lex
       which all need to be passed on the the next PU
    - in this case GRAPH, POS, and PHON all must be available in lex

  sizing:
    - 3 bytes entry index -> 16MB addressable
    - 2 bytes searchindex nr -> 64K blocks possible
    - 5 bytes per searchindex entry
      - 3 bytes for graph-prefix
      - 2 bytes blockadr in searchindex -> 64K blocks possible
    - lexblock size 512B:
      - 32M possible
      - with ~20 bytes per entry
        -> max. average of ~26 entries to be searched per lookup
    - overhead of ~10 bytes per block to sync with
      block boundaries
    - examples:
      - 500KB lex -> 1000 blocks,
        1000 entries in searchindex, ~25.6K lex-entries,
        - ~5KB searchindex
           ~10KB overhead for block sync
      - 100KB lex -> 200 blocks,
        200 entries in searchindex, ~5.1K lex-entries,
        - ~1KB searchindex
           ~2KB overhead for block sync

  pil-file: lexicon knowledge base in binary form

    lex-kb = content

    content = searchindex {lexblock}1:NRBLOCKS2

    lexblock = {lexentry}1:        (lexblock size is fixed 512Bytes)

    searchindex = NRBLOCKS2 {GRAPH1 GRAPH1 GRAPH1 LEXBLOCKIND2}=NRBLOCKS2

    lexentry = LENGRAPH1 {GRAPH1}=LENGRAPH1-1
               LENPOSPHON1 POS1 {PHON1}=LENPOSPHON1-2

    - special cases:
      - PHON is empty string (no pronunciation in the resulting TTS output):
        lexentry = LENGRAPH1 {GRAPH1}=LENGRAPH1-1  2 POS1
      - PHON can be :G2P -> use G2P later to add pronunciation:
        lexentry = LENGRAPH1 {GRAPH1}=LENGRAPH1-1  3 POS1 <reserved-phon-val=5>
    - multi-byte values always little endian
*/


/* ************************************************************/
/* lexicon data defines */
/* may not be changed with current implementation */
/* ************************************************************/

/* nr bytes of nrblocks info */
#define PICOKLEX_LEX_NRBLOCKS_SIZE 2

/* search index entry: - nr graphs
                       - nr bytes of block index
                       - nr bytes per entry, NRGRAPHS*INDSIZE */
#define PICOKLEX_LEX_SIE_NRGRAPHS  3
#define PICOKLEX_LEX_SIE_INDSIZE   2
#define PICOKLEX_LEX_SIE_SIZE      5

/* nr of bytes per lexblock */
#define PICOKLEX_LEXBLOCK_SIZE   512


/* reserved values in klex to indicate :G2P needed for a lexentry */
#define PICOKLEX_NEEDS_G2P   5


/* ************************************************************/
/* lexicon type and loading */
/* ************************************************************/

/** object       : LexKnowledgeBase
 *  shortcut     : klex
 *  derived from : picoknow_KnowledgeBase
 */

typedef struct klex_subobj *klex_SubObj;

typedef struct klex_subobj
{
    picoos_uint16 nrblocks; /* nr lexblocks = nr eles in searchind */
    picoos_uint8 *searchind;
    picoos_uint8 *lexblocks;
} klex_subobj_t;


static pico_status_t klexInitialize(register picoknow_KnowledgeBase this,
                                    picoos_Common common)
{
    picoos_uint32 curpos = 0;
    klex_subobj_t *klex;

    PICODBG_DEBUG(("start"));

    /* check whether (this->size != 0) done before calling this function */

    if (NULL == this || NULL == this->subObj) {
        return picoos_emRaiseException(common->em, PICO_EXC_KB_MISSING,
                                       NULL, NULL);
    }
    klex = (klex_subobj_t *) this->subObj;

    if (PICO_OK == picoos_read_mem_pi_uint16(this->base, &curpos,
                                             &(klex->nrblocks))) {
        if (klex->nrblocks > 0) {
            PICODBG_DEBUG(("nr blocks: %i, curpos: %i", klex->nrblocks,curpos));
            klex->searchind = this->base + curpos;
        } else {
            klex->searchind = NULL;
        }
        klex->lexblocks = this->base + PICOKLEX_LEX_NRBLOCKS_SIZE +
                             (klex->nrblocks * (PICOKLEX_LEX_SIE_SIZE));
        return PICO_OK;
    } else {
        return picoos_emRaiseException(common->em, PICO_EXC_FILE_CORRUPT,
                                       NULL, NULL);
    }
}


static pico_status_t klexSubObjDeallocate(register picoknow_KnowledgeBase this,
                                          picoos_MemoryManager mm)
{
    if (NULL != this) {
        picoos_deallocate(mm, (void *) &this->subObj);
    }
    return PICO_OK;
}


/* we don't offer a specialized constructor for a LexKnowledgeBase but
 * instead a "specializer" of an allready existing generic
 * picoknow_KnowledgeBase */

pico_status_t picoklex_specializeLexKnowledgeBase(picoknow_KnowledgeBase this,
                                                  picoos_Common common)
{
    if (NULL == this) {
        return picoos_emRaiseException(common->em, PICO_EXC_KB_MISSING,
                                       NULL, NULL);
    }
    if (this->size > 0) {
        this->subDeallocate = klexSubObjDeallocate;
        this->subObj = picoos_allocate(common->mm, sizeof(klex_subobj_t));
        if (NULL == this->subObj) {
            return picoos_emRaiseException(common->em, PICO_EXC_OUT_OF_MEM,
                                           NULL, NULL);
        }
        return klexInitialize(this, common);
    } else {
        /* some dummy klex */
        return PICO_OK;
    }
}

/* for now we don't need to do anything special for the main lex */
/*
pico_status_t picoklex_specializeMainLexKnowledgeBase(
        picoknow_KnowledgeBase this,
        picoos_Common common)
{
    return picoklex_specializeLexKnowledgeBase(this,common);
}
*/


/* ************************************************************/
/* lexicon getLex */
/* ************************************************************/

picoklex_Lex picoklex_getLex(picoknow_KnowledgeBase this)
{
    if (NULL == this) {
        return NULL;
    } else {
        return (picoklex_Lex) this->subObj;
    }
}


/* ************************************************************/
/* functions on searchindex */
/* ************************************************************/


static picoos_uint32 klex_getSearchIndexVal(const klex_SubObj this,
                                            picoos_uint16 index)
{
    picoos_uint32 pos, val;
    pos = index * PICOKLEX_LEX_SIE_SIZE;
    val = this->searchind[pos];
    val = (val << 8) + this->searchind[pos + 1];
    val = (val << 8) + this->searchind[pos + 2];
    return val;
}


/* Determine first lexblock containing entries for specified
   grapheme. */

static picoos_uint16 klex_getLexblockNr(const klex_SubObj this,
                                        const picoos_uint8 *graphsi) {
    /* graphsi is of len PICOKLEX_LEX_SI_NGRAPHS */
    picoos_int32 low, mid, high;
    picoos_uint32 searchval, indval;

    /* PICOKLEX_LEX_SIE_NRGRAPHS */

    /* convert graph-prefix to number with 'lexicographic' ordering */
    searchval = graphsi[0];
    searchval = (searchval << 8) + graphsi[1];
    searchval = (searchval << 8) + graphsi[2];

    low = 0;
    high = this->nrblocks;

    /* do binary search */
    while (low < high) {
        mid = (low + high) / 2;
        indval = klex_getSearchIndexVal(this, mid);
        if (indval < searchval) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    PICODBG_ASSERT(high == low);
    /* low points to the first entry greater than or equal to searchval */

    if (low < this->nrblocks) {
        indval = klex_getSearchIndexVal(this, low);
        if (indval > searchval) {
            low--;
            /* if there are identical elements in the search index we have
               to move to the first one */
            if (low > 0) {
                indval = klex_getSearchIndexVal(this, low);
                while (indval == klex_getSearchIndexVal(this, low-1)) {
                    low--;
                }
            }
        }
    } else {
        low = this->nrblocks - 1;
    }

#if defined(PICO_DEBUG)
    {
        picoos_uint32 pos = low * PICOKLEX_LEX_SIE_SIZE;
        PICODBG_DEBUG(("binary search result is %c%c%c (%d)",
                       this->searchind[pos], this->searchind[pos + 1],
                       this->searchind[pos + 2], low));
    }
#endif

    return (picoos_uint16) low;
}


/* Determine number of adjacent lexblocks containing entries for
   the same grapheme search prefix (identified by search index). */

static picoos_uint16 klex_getLexblockRange(const klex_SubObj this,
                                           picoos_uint16 index)
{
    picoos_uint16 count;
    picoos_uint32 sval1, sval2;

    sval1 = klex_getSearchIndexVal(this, index);

#if defined(PICO_DEBUG)
    /* 'index' must point to first lexblock of its kind */
    if (index > 0) {
        sval2 = klex_getSearchIndexVal(this, index - 1);
        PICODBG_ASSERT(sval1 != sval2);
    }
#endif

    index++;
    sval2 = klex_getSearchIndexVal(this, index);

    count = 1;
    while (sval1 == sval2) {
        count++;
        index++;
        sval2 = klex_getSearchIndexVal(this, index);
    }

    return count;
}


/* ************************************************************/
/* functions on single lexblock */
/* ************************************************************/

static picoos_int8 klex_lexMatch(picoos_uint8 *lexentry,
                                 const picoos_uint8 *graph,
                                 const picoos_uint16 graphlen) {
    picoos_uint8 i;
    picoos_uint8 lexlen;
    picoos_uint8 *lexgraph;

    lexlen = lexentry[0] - 1;
    lexgraph = &(lexentry[1]);
    for (i=0; (i<graphlen) && (i<lexlen); i++) {
        PICODBG_TRACE(("%d|%d  graph|lex: %c|%c", graphlen, lexlen,
                       graph[i], lexgraph[i]));
        if (lexgraph[i] < graph[i]) {
            return -1;
        } else if (lexgraph[i] > graph[i]) {
            return 1;
        }
    }
    if (graphlen == lexlen) {
        return 0;
    } else if (lexlen < graphlen) {
        return -1;
    } else {
        return 1;
    }
}


static void klex_setLexResult(const picoos_uint8 *lexentry,
                              const picoos_uint32 lexpos,
                              picoklex_lexl_result_t *lexres) {
    picoos_uint8 i;

    /* check if :G2P */
    if ((2 < (lexentry[lexentry[0]])) && ((lexentry[lexentry[0] + 2]) == PICOKLEX_NEEDS_G2P)) {
        /* set pos */
        lexres->posind[0] = lexentry[lexentry[0] + 1];
        /* set rest */
        lexres->phonfound = FALSE;
        lexres->posindlen = 1;
        lexres->nrres = 1;
        PICODBG_DEBUG(("result %d :G2P", lexres->nrres));
    } else {
        i = lexres->nrres * (PICOKLEX_POSIND_SIZE);
        lexres->posindlen += PICOKLEX_POSIND_SIZE;
        lexres->phonfound = TRUE;
        /* set pos */
        lexres->posind[i++] = lexentry[lexentry[0] + 1];
        /* set ind, PICOKLEX_IND_SIZE */
        lexres->posind[i++] = 0x000000ff & (lexpos);
        lexres->posind[i++] = 0x000000ff & (lexpos >>  8);
        lexres->posind[i]   = 0x000000ff & (lexpos >> 16);
        lexres->nrres++;
        PICODBG_DEBUG(("result %d", lexres->nrres));
    }
}


static void klex_lexblockLookup(klex_SubObj this,
                                const picoos_uint32 lexposStart,
                                const picoos_uint32 lexposEnd,
                                const picoos_uint8 *graph,
                                const picoos_uint16 graphlen,
                                picoklex_lexl_result_t *lexres) {
    picoos_uint32 lexpos;
    picoos_int8 rv;

    lexres->nrres = 0;

    lexpos = lexposStart;
    rv = -1;
    while ((rv < 0) && (lexpos < lexposEnd)) {

        rv = klex_lexMatch(&(this->lexblocks[lexpos]), graph, graphlen);

        if (rv == 0) { /* found */
            klex_setLexResult(&(this->lexblocks[lexpos]), lexpos, lexres);
            if (lexres->phonfound) {
                /* look for more results, up to MAX_NRRES, don't even
                   check if more results would be available */
                while ((lexres->nrres < PICOKLEX_MAX_NRRES) &&
                       (lexpos < lexposEnd)) {
                    lexpos += this->lexblocks[lexpos];
                    lexpos += this->lexblocks[lexpos];
                    /* if there are no more entries in this block, advance
                       to next block by skipping all zeros */
                    while ((this->lexblocks[lexpos] == 0) &&
                           (lexpos < lexposEnd)) {
                        lexpos++;
                    }
                    if (lexpos < lexposEnd) {
                        if (klex_lexMatch(&(this->lexblocks[lexpos]), graph,
                                          graphlen) == 0) {
                            klex_setLexResult(&(this->lexblocks[lexpos]),
                                              lexpos, lexres);
                        } else {
                            /* no more results, quit loop */
                            lexpos = lexposEnd;
                        }
                    }
                }
            } else {
                /* :G2P mark */
            }
        } else if (rv < 0) {
            /* not found, goto next entry */
            lexpos += this->lexblocks[lexpos];
            lexpos += this->lexblocks[lexpos];
            /* if there are no more entries in this block, advance
               to next block by skipping all zeros */
            while ((this->lexblocks[lexpos] == 0) && (lexpos < lexposEnd)) {
                lexpos++;
            }
        } else {
            /* rv > 0, not found, won't show up later in block */
        }
    }
}


/* ************************************************************/
/* lexicon lookup functions */
/* ************************************************************/

picoos_uint8 picoklex_lexLookup(const picoklex_Lex this,
                                const picoos_uint8 *graph,
                                const picoos_uint16 graphlen,
                                picoklex_lexl_result_t *lexres) {
    picoos_uint16 lbnr, lbc;
    picoos_uint32 lexposStart, lexposEnd;
    picoos_uint8 i;
    picoos_uint8 tgraph[PICOKLEX_LEX_SIE_NRGRAPHS];
    klex_SubObj klex = (klex_SubObj) this;

    if (NULL == klex) {
        PICODBG_ERROR(("no lexicon loaded"));
        /* no exception here needed, already checked at initialization */
        return FALSE;
    }

    lexres->nrres = 0;
    lexres->posindlen = 0;
    lexres->phonfound = FALSE;

    for (i = 0; i<PICOKLEX_LEX_SIE_NRGRAPHS; i++) {
        if (i < graphlen) {
            tgraph[i] = graph[i];
        } else {
            tgraph[i] = '\0';
        }
    }
    PICODBG_DEBUG(("tgraph: %c%c%c", tgraph[0],tgraph[1],tgraph[2]));

    if ((klex->nrblocks) == 0) {
        /* no searchindex, no lexblock */
        PICODBG_WARN(("no searchindex, no lexblock"));
        return FALSE;
    } else {
        lbnr = klex_getLexblockNr(klex, tgraph);
        PICODBG_ASSERT(lbnr < klex->nrblocks);
        lbc = klex_getLexblockRange(klex, lbnr);
        PICODBG_ASSERT((lbc >= 1) && (lbc <= klex->nrblocks));
    }
    PICODBG_DEBUG(("lexblock nr: %d (#%d)", lbnr, lbc));

    lexposStart = lbnr * PICOKLEX_LEXBLOCK_SIZE;
    lexposEnd = lexposStart + lbc * PICOKLEX_LEXBLOCK_SIZE;

    PICODBG_DEBUG(("lookup start, lexpos range %d..%d", lexposStart,lexposEnd));
    klex_lexblockLookup(klex, lexposStart, lexposEnd, graph, graphlen, lexres);
    PICODBG_DEBUG(("lookup done, %d found", lexres->nrres));

    return (lexres->nrres > 0);
}


picoos_uint8 picoklex_lexIndLookup(const picoklex_Lex this,
                                   const picoos_uint8 *ind,
                                   const picoos_uint8 indlen,
                                   picoos_uint8 *pos,
                                   picoos_uint8 **phon,
                                   picoos_uint8 *phonlen) {
    picoos_uint32 pentry;
    klex_SubObj klex = (klex_SubObj) this;

    /* check indlen */
    if (indlen != PICOKLEX_IND_SIZE) {
        return FALSE;
    }

    /* PICOKLEX_IND_SIZE */
    pentry = 0x000000ff & (ind[0]);
    pentry |= ((picoos_uint32)(ind[1]) <<  8);
    pentry |= ((picoos_uint32)(ind[2]) << 16);

    /* check ind if it is within lexblocks byte stream, if not, return FALSE */
    if (pentry >= ((picoos_uint32)klex->nrblocks * PICOKLEX_LEXBLOCK_SIZE)) {
        return FALSE;
    }

    pentry += (klex->lexblocks[pentry]);
    *phonlen = (klex->lexblocks[pentry++]) - 2;
    *pos = klex->lexblocks[pentry++];
    *phon = &(klex->lexblocks[pentry]);

    PICODBG_DEBUG(("pentry: %d, phonlen: %d", pentry, *phonlen));
    return TRUE;
}

#ifdef __cplusplus
}
#endif


/* end */