wfst_transduce.cc

/*************************************************************************/
/*                                                                       */
/*                Centre for Speech Technology Research                  */
/*                     University of Edinburgh, UK                       */
/*                         Copyright (c) 1997                            */
/*                        All Rights Reserved.                           */
/*                                                                       */
/*  Permission is hereby granted, free of charge, to use and distribute  */
/*  this software and its documentation without restriction, including   */
/*  without limitation the rights to use, copy, modify, merge, publish,  */
/*  distribute, sublicense, and/or sell copies of this work, and to      */
/*  permit persons to whom this work is furnished to do so, subject to   */
/*  the following conditions:                                            */
/*   1. The code must retain the above copyright notice, this list of    */
/*      conditions and the following disclaimer.                         */
/*   2. Any modifications must be clearly marked as such.                */
/*   3. Original authors' names are not deleted.                         */
/*   4. The authors' names are not used to endorse or promote products   */
/*      derived from this software without specific prior written        */
/*      permission.                                                      */
/*                                                                       */
/*  THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK        */
/*  DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING      */
/*  ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT   */
/*  SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE     */
/*  FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES    */
/*  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN   */
/*  AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,          */
/*  ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF       */
/*  THIS SOFTWARE.                                                       */
/*                                                                       */
/*************************************************************************/
/*                     Author :  Alan W Black                            */
/*                     Date   :  December 1997                           */
/*-----------------------------------------------------------------------*/
/*                                                                       */
/* Transduction using a WFST                                             */
/*                                                                       */
/*=======================================================================*/
#include <iostream>
#include "EST_WFST.h"

/** An internal class in transduction of WFSTs holding intermediate
    state information.
*/
class wfst_tstate {
  public:
    int state;
    EST_IList outs;
    float score;
};

ostream &operator << (ostream &s, const wfst_tstate &state)
{
  (void)state;
  return s << "<<wfst_tstate>>";
}

Declare_TList(wfst_tstate)

#if defined(INSTANTIATE_TEMPLATES)
#include "../base_class/EST_TList.cc"

Instantiate_TList(wfst_tstate)

#endif

typedef EST_TList<wfst_tstate> wfst_tstate_list;

static void add_transduce_mstate(const EST_WFST &wfst,
                 const wfst_tstate &cs,
                 wfst_translist &tranlist,
                 wfst_tstate_list &ns);

int transduce(const EST_WFST &wfst,const EST_StrList &in,EST_StrList &out)
{
    // Map names to internal ints before transduction
    EST_Litem *p;
    EST_IList in_i,out_i;
    int r;

    for (p=in.head(); p != 0; p=p->next())
    in_i.append(wfst.in_symbol(in(p)));

    r = transduce(wfst,in_i,out_i);

    for (p=out_i.head(); p != 0; p=p->next())
    out.append(wfst.out_symbol(out_i(p)));

    return r;
}

int transduce(const EST_WFST &wfst,const EST_IList &in,EST_IList &out)
{
    // Transduce input stream to an output stream
    EST_Litem *i,*cs;
    int r=FALSE;
    wfst_tstate_list *current_ms = new wfst_tstate_list;
    wfst_tstate start_state;
    wfst_translist ss_eps_trans;

    start_state.state = wfst.start_state();
    start_state.score = 0;
    current_ms->append(start_state);
    // Add any epsilon accessible states
    wfst.transduce(wfst.start_state(),wfst.in_epsilon(),ss_eps_trans);
    add_transduce_mstate(wfst,start_state,ss_eps_trans,*current_ms);

    for (i=in.head(); i != 0; i=i->next())
    {
    wfst_tstate_list *ns = new wfst_tstate_list;

    for (cs=current_ms->head(); cs != 0; cs=cs->next())
    {   // For each state in current update list of new states
        wfst_translist translist;
        wfst.transduce((*current_ms)(cs).state,in(i),translist);
        add_transduce_mstate(wfst,(*current_ms)(cs),translist,*ns);
    }
    // Using pointers to avoid having to copy the state list
    delete current_ms; 
    current_ms = ns;  

    if (current_ms->length() == 0)
        break;  // give up, no transition possible
    }
    // current_ms will contain the list of possible transitions
    if (current_ms->length() > 1)
    cerr << "WFST: found " << current_ms->length() << " transductions" <<
        endl;
    // should find "best" but we'll find longest at present
    // Choose the longest (should be based on score)
    for (cs = current_ms->head(); cs != 0; cs=cs->next())
    {
    if ((wfst.final((*current_ms)(cs).state)) &&
        ((*current_ms)(cs).outs.length() > out.length()))
    {
        r = TRUE;
        out = (*current_ms)(cs).outs;
    }
    }
    delete current_ms;
    return r;
}

static void add_transduce_mstate(const EST_WFST &wfst,
                 const wfst_tstate &cs,
                 wfst_translist &translist,
                 wfst_tstate_list &ns)
{
    // For each possible transduction of in from cs.state in WFST
    // add it to ns.
    // This should really only add states if they are not already there
    // but you really need stae plus recognized path to get all 
    // transductions so a tree structure would be better.
    EST_Litem *t;

    // Add new states to ns if not already there
    for (t=translist.head(); t != 0; t=t->next())
    {
    // Declare a new one and put it on the end of the list
    // before we fill its values, this saves a copy
    wfst_tstate tts;
    ns.append(tts); 
    wfst_tstate &ts = ns.last();
    
    ts.state = translist(t)->state();
    // the combination is probably WFST dependant
    ts.score = translist(t)->weight()+cs.score;
    // copying the outs up to now (pity)
    ts.outs = cs.outs;
    ts.outs.append(translist(t)->out_symbol());
    
    // Also any potential epsilon transitions for this new state
    wfst_translist etranslist;
    wfst.transduce(ts.state,wfst.in_epsilon(),etranslist);
    add_transduce_mstate(wfst,ts,etranslist,ns);
    }
}

int recognize(const EST_WFST &wfst,const EST_StrList &in,int quiet)
{
    // Map names to internal ints before recognition
    EST_Litem *p;
    EST_IList in_i,out_i;
    int i,o;
    int r;
    
    for (p=in.head(); p != 0; p=p->next())
    {
    if (in(p).contains("/"))
    {
        i = wfst.in_symbol(in(p).before("/"));
        o = wfst.out_symbol(in(p).after("/"));
    }
    else
    {
        i = wfst.in_symbol(in(p));
        o = wfst.out_symbol(in(p));
    }
    in_i.append(i);
    out_i.append(o);
    }
    
    r = recognize(wfst,in_i,out_i,quiet);
    
    return r;
}

int recognize(const EST_WFST &wfst,const EST_IList &in, 
          const EST_IList &out, int quiet)
{
    int state = wfst.start_state();
    EST_Litem *p,*q;
    int nstate;
    
    for (p=in.head(),q=out.head();
     ((p != 0) && (q != 0));
     p=p->next(),q=q->next())
    {
    nstate = wfst.transition(state,in(p),out(q));
    if (!quiet)
        printf("state %d %s/%s -> %d\n",state,
           (const char *)wfst.in_symbol(in(p)),
           (const char *)wfst.out_symbol(out(q)),
           nstate);
    state = nstate;
    if (state == WFST_ERROR_STATE)
        return FALSE;
    }
    
    if (p != q)
    {  
    cerr << "wfst recognize: in/out tapes of different lengths"
        << endl;
    return FALSE;
    }
    
    if (wfst.final(state))
    return TRUE;
    else 
    return FALSE;
}

int recognize_for_perplexity(const EST_WFST &wfst,
                 const EST_StrList &in,
                 int quiet,
                 float &count,
                 float &sumlogp)
{
    // Map names to internal ints before recognition
    EST_Litem *p;
    EST_IList in_i,out_i;
    int i,o;
    int r;
    
    for (p=in.head(); p != 0; p=p->next())
    {
    if (in(p).contains("/"))
    {
        i = wfst.in_symbol(in(p).before("/"));
        o = wfst.out_symbol(in(p).after("/"));
    }
    else
    {
        i = wfst.in_symbol(in(p));
        o = wfst.out_symbol(in(p));
    }
    in_i.append(i);
    out_i.append(o);
    }
    
    r = recognize_for_perplexity(wfst,in_i,out_i,quiet,count,sumlogp);
    
    return r;
}

int recognize_for_perplexity(const EST_WFST &wfst,
                 const EST_IList &in, 
                 const EST_IList &out, 
                 int quiet,
                 float &count,
                 float &sumlogp)
{
    int state = wfst.start_state();
    EST_Litem *p,*q;
    int nstate;
    float prob;
    count = 0;
    sumlogp = 0;
    
    for (p=in.head(),q=out.head();
     ((p != 0) && (q != 0));
     p=p->next(),q=q->next())
    {
    nstate = wfst.transition(state,in(p),out(q),prob);
    count++;
    if (prob > 0)
        sumlogp += log(prob);
    else
        sumlogp += -100;  // bad hack
    if (!quiet)
        printf("state %d %s/%s -> %d\n",state,
           (const char *)wfst.in_symbol(in(p)),
           (const char *)wfst.out_symbol(out(q)),
           nstate);
    state = nstate;
    if (state == WFST_ERROR_STATE)
        return FALSE;
    }
    
    if (p != q)
    {  
    cerr << "wfst recognize: in/out tapes of different lengths"
        << endl;
    return FALSE;
    }
    
    if (wfst.final(state))
    return TRUE;
    else 
    return FALSE;
}