EST_lattice_io.cc

Go to the documentation of this file.

/*************************************************************************/
/*                                                                       */
/*                Centre for Speech Technology Research                  */
/*                     University of Edinburgh, UK                       */
/*                      Copyright (c) 1995,1996                          */
/*                        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 :  Simon King                               */
/*                    Date   :  November 1996                            */
/*-----------------------------------------------------------------------*/
/*           Lattice/Finite State Network i/o functions                  */
/*                                                                       */
/*=======================================================================*/

#include <fstream>
#include <cstdlib>
#include "EST_lattice.h"
#include "EST_types.h"
#include "EST_Token.h"
#include "EST_StringTrie.h"

using namespace std;

bool save(Lattice &lattice, EST_String filename)
{
    ostream *outf;
    EST_Litem *n_ptr, *a_ptr;
    int acount=0,ncount=0;
    int i,from,to;
    Lattice::symbol_t *symbol;
    EST_String word;

    if (filename == "-")
    outf = &cout;
    else
    outf = new ofstream(filename);
    
    if (!(*outf))
    {
    cerr << "lattice save: can't open lattice output file \"" 
        << filename << "\"" << endl;
    return false;
    }

    // count
    for (n_ptr = lattice.nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
    ncount++;
    for (a_ptr = lattice.nodes(n_ptr)->arcs_out.head();
         a_ptr != 0; a_ptr = a_ptr->next())
        acount++;
    }

    // size line (duh!)
    *outf << "# " << "Generated by Edinburgh Speech Tools" << endl << "#" << endl;
    *outf << "# Header" << endl;
    *outf << "VERSION=1.1" << endl << "#" << endl;
    *outf << "# Size line" << endl;
    *outf << "N=" << ncount << " L=" << acount << endl;
    *outf << "#" << endl;


    // to do : for HTK name nodes, not arcs
    // since all arcs in have same label

    // nodes
    for(i=0;i<=1;i++){

    if(i==0)
        *outf << "# Nodes" << endl;
    else
        *outf << "# Arcs" << endl;

    acount=0;

    for (n_ptr = lattice.nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
        
        from=lattice.node_index(lattice.nodes(n_ptr));
        
        if(i==0){
        *outf << "I=" << from << endl;
        
        }else
        for (a_ptr = lattice.nodes(n_ptr)->arcs_out.head();
             a_ptr != 0; a_ptr = a_ptr->next()){

            to = lattice.node_index(lattice.nodes(n_ptr)->arcs_out(a_ptr)->to);
            
            symbol = lattice.alphabet_index_to_symbol(lattice.nodes(n_ptr)->arcs_out(a_ptr)->label);

            if(lattice.nodes(n_ptr)->arcs_out(a_ptr)->label == lattice.e_move_symbol_index){
            *outf << "J=" << acount++ << " S=" << from << " E=" << to 
                  << " W=!NULL" << endl;

            }else{
            *outf << "J=" << acount++ << " S=" << from << " E=" << to 
                  << " l=" << lattice.qmap_index_to_value(symbol->qmap_index)
                  << " W=" << lattice.nmap_index_to_name(symbol->nmap_index)
                  << endl;
            }
        }
    }
    }
    
    return true;
}

bool
load(Lattice &lattice,EST_String filename)
{

    EST_String name, next_token, str;
    EST_TokenStream ts;
    EST_Token t;
    int i,j;
    // temporary storage
    struct arc_t{
    int start;
    int end;
    float logprob;
    EST_String word;
    };

    arc_t *temp_arcs = NULL;
    int arcindex=0;
    int nodeindex=0;

    // nodes can have labels too - but this is not yet supported
    
    

    if (((filename == "-") ? ts.open(cin) : ts.open(filename)) != 0)
    {
    cerr << "Can't open lattice input file " << filename << endl;
    return false;
    }

    // read file into a arrays, make alphabet, then make lattice

    // find 'size' line

    int numnodes=0;
    int numarcs=0;

    int narcs=-1;
    int nnodes=-1;
    int nodenum=-1;
    int arcnum=-1;
    int startnode=-1;
    int endnode=-1;
    float logprob = 0.0;
    EST_String word="";

    while(!ts.eof())
    {

    str = ts.get().string();

    if(!str.contains("="))
        continue;

    EST_String left=str.before("=");
    EST_String right=str.after("=");

    if(left == "N")
        nnodes=atoi(right);
    else if(left == "L")
        narcs=atoi(right);
    else if(left == "I")
        nodenum=atoi(right);
    else if(left == "J")
        arcnum=atoi(right); 
    else if(left == "S")
        startnode=atoi(right);
    else if(left == "E")
        endnode=atoi(right);
    else if(left == "l")
        logprob=atof(right);
    else if(left == "W")
        word=right;


    if(ts.eoln()){

        // do something

        if( (narcs>0) && (nnodes>0) ){
        // it's the size line
        if(temp_arcs != NULL){
            cerr << "Error in lattice file : 2 size lines found"
             << " : line " << ts.linenum() << endl;
            ts.close();
            return false;
        }else{
            numarcs=narcs;
            numnodes=nnodes;
            temp_arcs = new arc_t[numarcs];
            cerr << "size : " << numnodes << " " << numarcs << endl;
        }
        
        }else if(nodenum>=0){
                
        if(arcnum>0){
            cerr << "Error in lattice file at line "
             << ts.linenum() << endl;
            ts.close();
            return false;
        }

        if(nodenum>=numnodes){
            cerr << "Error in lattice file at line "
             << ts.linenum() 
             << " : node index (" << nodenum << ") out of range"
             << endl;
            ts.close();
            return false;
        }

        nodeindex++;

        }else if(arcnum>=0){
        if(nodenum>0){
            cerr << "Error in lattice file at line "
             << ts.linenum() << endl;
            ts.close();
            return false;
        }
        
        if(arcnum>=numarcs){
            cerr << "Error in lattice file at line "
             << ts.linenum() 
             << " : arc index (" << arcnum << ") out of range"
             << endl;
            ts.close();
            return false;
        }

        if((startnode<0) || (startnode>=numnodes)){
            cerr << "Error in lattice file at line " << ts.linenum()
             << endl
             << " arc starts at out of range node " 
             << startnode << endl;
            return false;
        }

        if((endnode<0) || (endnode>=numnodes)){
            cerr << "Error in lattice file at line " << ts.linenum()
             << endl
             << " arc ends at out of range node " 
             << endnode << endl;
            return false;
        }

        // make arc
        temp_arcs[arcindex].start = startnode;
        temp_arcs[arcindex].end = endnode;
        temp_arcs[arcindex].logprob = logprob;
        temp_arcs[arcindex].word = word;
        arcindex++;
                
        }

        narcs=-1;
        nnodes=-1;
        nodenum=-1;
        arcnum=-1;
        startnode=-1;
        endnode=-1;
        logprob=-1;
        word="";
        
    }

    }

    if(arcindex != numarcs){
    cerr << "Error in lattice file at line "
         << "found " << arcindex << " arcs, but expected " 
         << numarcs << endl;
    return false;
    }

    if(nodeindex != numnodes){
    cerr << "Error in lattice file at line "
         << "found " << nodeindex << " nodes, but expected " 
         << numnodes << endl;
    return false;
    }


    // make nmap
    EST_StringTrie seen_before;
    EST_StrList list_nmap;
    
    for(i=0;i<numarcs;i++){

    if(seen_before.lookup(temp_arcs[i].word) != (void *)(1)){
        seen_before.add(temp_arcs[i].word,(void *)(1));
        list_nmap.append(temp_arcs[i].word);
    }
    }
    qsort(list_nmap);
    
    //cerr << "here is the list nmap" << list_nmap << endl;

    i=0;
    EST_Litem *l_ptr;
    bool flag;
    for(l_ptr=list_nmap.head();l_ptr != 0; l_ptr=l_ptr->next())
    i++;

    // transfer to array
    lattice.nmap.resize(i);
    i=0;
    for(l_ptr=list_nmap.head();l_ptr != 0; l_ptr=l_ptr->next())
    lattice.nmap[i++] = list_nmap(l_ptr);

    list_nmap.clear();
    cerr << "Built nmap with " << i << " entries" << endl;


    // make qmap
    // should be a separate fn

    EST_TList<float> list_qmap;

    float error_margin = 1.0e-02; // temporary hack

    for(i=0;i<numarcs;i++){
        
        flag = false;
        for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
        if(fabs(list_qmap(l_ptr) - temp_arcs[i].logprob) <= error_margin){
            flag = true;
            break;
        }

        if(!flag)
        list_qmap.append(temp_arcs[i].logprob);
        
    }
    
    // special zero (within error_margin) entry, if not already there
    flag = false;
    for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
    if(fabs(list_qmap(l_ptr)) <= error_margin){
        flag = true;
        break;
    }
    
    if(!flag)
    list_qmap.append(0);
    
    qsort(list_qmap);
    
    i=0;
    for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
    i++;
    
    // transfer to array
    lattice.qmap.resize(i);
    i=0;
    for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
    lattice.qmap[i++] = list_qmap(l_ptr);

    list_qmap.clear();
    cerr << "Built qmap with " << i << " entries" << endl;


    // make alphabet
   
    // temporary list
    bool **used; // index nmap,qmap
    int nl = lattice.nmap.n();
    int ql = lattice.qmap.n();
    used = new bool*[nl];
    for(i=0;i<nl;i++)
    used[i] = new bool[ql];

    for(i=0;i<nl;i++)
    for(j=0;j<ql;j++)
        used[i][j] = false;

    // get all combinations of word and log probability actually used
    for(i=0;i<numarcs;i++){

    //cerr << "arc " << i << " " << temp_arcs[i].logprob
    //<< " " << temp_arcs[i].word << endl;

    used[lattice.nmap_name_to_index(temp_arcs[i].word)][lattice.qmap_value_to_index(temp_arcs[i].logprob)] = true;
    }

    int count = 0;
    for(i=0;i<nl;i++)
    for(j=0;j<ql;j++)
        if(used[i][j])
        count++;

    lattice.alphabet.resize(count);
    count=0;
    Lattice::symbol_t *sym;
    // ordered this way so already sorted, first by q then by n
    for(j=0;j<ql;j++)
    for(i=0;i<nl;i++)
        if(used[i][j]){
        sym = new Lattice::symbol_t;
        sym->nmap_index=i;
        sym->qmap_index=j;
        lattice.alphabet[count++] = *sym;

        }

    cerr << "Alphabet has " << count << " symbols " << endl;

    // make lattice itself

    // nodes
    for(i=0;i<numnodes;i++){
    Lattice::Node *new_node;
    new_node = new Lattice::Node;
    lattice.nodes.append(new_node);

    }

    // arcs
    EST_Litem *n_ptr;
    for(j=0;j<numarcs;j++){
    
    // find from and to nodes by counting down node list

    // from node

    for (n_ptr =lattice. nodes.head(),count=0; 
         count<temp_arcs[j].start;
         n_ptr = n_ptr->next(),count++){

        if(n_ptr == NULL){
        cerr << "Couldn't find 'from' node ";
        for (i=0;i<lattice.alphabet.length();i++)
           delete &(lattice.alphabet[i]);
        delete[] used;
        return false;
        }
    }
    Lattice::Node *from_node = lattice.nodes(n_ptr);

    // double check
    if(from_node == NULL){
        cerr << "Couldn't find from node, index " 
         << temp_arcs[j].start << endl;
        return false;
    }


    for (n_ptr = lattice.nodes.head(),count=0; 
         count<temp_arcs[j].end;
         n_ptr = n_ptr->next(),count++){

        if(n_ptr == NULL){
        cerr << "Couldn't find 'to' node ";
        return false;
        }
    }
    Lattice::Node *to_node = lattice.nodes(n_ptr);

    // double check
    if(to_node == NULL){
        cerr << "Couldn't find to node, index " 
         << temp_arcs[j].end << endl;
        return false;
    }


    int word_index = lattice.nmap_name_to_index(temp_arcs[j].word);

    // get arc symbol
    int symbol = lattice.alphabet_index_lookup(word_index,
                       lattice.qmap_value_to_index(temp_arcs[j].logprob));
    if(symbol < 0){
        cerr << "Couldn't lookup symbol in alphabet !" << endl;
        return false;
    }
    
    Lattice::Arc *new_arc = new Lattice::Arc;
    new_arc->label = symbol;
    new_arc->to = to_node;

    if(to_node->name.head() == NULL)
        to_node->name.append(word_index); // only name of first arc in .. !

    from_node->arcs_out.append(new_arc);
    
    }

    // find final nodes
    for (n_ptr = lattice.nodes.head(),count=0; 
     n_ptr!= NULL;
     n_ptr = n_ptr->next()){

    if(lattice.nodes(n_ptr)->arcs_out.head() == NULL){
        lattice.final_nodes.append(lattice.nodes(n_ptr));
        count++;
    }
    }

    cerr << "found " << count << " final nodes" << endl;



    cerr << "Lattice loaded !" << endl;

    delete [] used;
    delete [] temp_arcs;

    return true;
}