Loading...
Searching...
No Matches
EST_lattice.cc
/*************************************************************************/
/* */
/* 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 */
/* */
/*=======================================================================*/
#include "EST_lattice.h"
#include <fstream>
#include <cstdlib>
Lattice::Lattice()
{
tf=NULL;
}
Lattice::~Lattice()
{
}
Lattice::Node*
Lattice::start_node()
{
if(nodes.head() != NULL )
return nodes(nodes.head());
else{
cerr << "LAttice has no nodes !" << endl;
return NULL;
}
}
#if 0
bool Lattice::build_qmap(Bigram &g, float error_margin)
{
// very crude VQ (not vectors though)
// works best on log bigrams ?
// to do : automatically determine error_margin
int i,j;
EST_Litem *l_ptr;
bool flag;
// first, build a list, then transfer to array
Tlist<float> list_qmap;
qmap_error_margin = error_margin;
for (i = 0; i < g.size(); ++i){
for (j = 0; j < g.size(); ++j){
flag = false;
for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
if(fabs(list_qmap(l_ptr) - g.p(i,j)) <= error_margin){
flag = true;
break;
}
if(!flag)
list_qmap.append(g.p(i,j));
}
}
// 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
qmap.resize(i);
i=0;
for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
qmap(i++) = list_qmap(l_ptr);
list_qmap.clear();
cerr << "Built qmap with " << i << " entries" << endl;
return true;
}
bool
Lattice::build_nmap(Bigram &g)
{
int j;
//name_map_entry_t entry;
EST_Litem *l_ptr;
// first, build a list, then transfer to array
Tlist<EST_String> list_nmap;
// wordlist must not have !ENTER of !EXIT in it
for (j = 0; j < g.size() - 2; ++j){
if(g.words(j) == "!ENTER"){
cerr << "Wordlist contains special word !ENTER" << endl;
return false;
}
if(g.words(j) == "!EXIT"){
cerr << "Wordlist contains special word !EXIT" << endl;
return false;
}
}
// add all words
for (j = 0; j < g.size() - 2; ++j)
list_nmap.append(g.words(j));
// special enter and exit
list_nmap.append("!ENTER");
list_nmap.append("!EXIT");
qsort(list_nmap);
cerr << list_nmap << endl;
j=0;
for(l_ptr=list_nmap.head();l_ptr != 0; l_ptr=l_ptr->next())
j++;
// transfer to array
nmap.resize(j);
j=0;
for(l_ptr=list_nmap.head();l_ptr != 0; l_ptr=l_ptr->next())
nmap(j++) = list_nmap(l_ptr);
list_nmap.clear();
cerr << "Built nmap with " << j << " entries" << endl;
return true;
}
bool
Lattice::construct_alphabet(Bigram &g)
{
int i,j,enteri,exiti,aindex,qindex,nindex,count;
symbol_t *sym;
EST_Litem *a_ptr;
bool flag;
if(!build_qmap(g,1.0e-02) || !build_nmap(g)) // to do : fix
return false;
// temporary list
Tlist<symbol_t*> list_alphabet;
// alphabet consists of all occurring combinations of
// nmap and qmap entries
enteri = g.size() - 2;
exiti = g.size() - 1;
aindex=0;
// order is this way for speed
for (j = 0; j < g.size(); ++j){
cerr << "constructing alphabet " << (int)((float)j*100/(float)g.size()) << "% \r";
if(j == enteri)
nindex = nmap_name_to_index("!ENTER");
else if(j == exiti)
nindex = nmap_name_to_index("!EXIT");
else
nindex = nmap_name_to_index(g.words(j)); // check !!
for (i = 0; i < g.size(); ++i){
qindex = qmap_value_to_index(g.p(i,j));
// have we got sym already ?
flag=false;
for(a_ptr=list_alphabet.tail();a_ptr!=NULL;a_ptr=a_ptr->prev()){
if( (list_alphabet(a_ptr)->nmap_index == nindex) &&
(list_alphabet(a_ptr)->qmap_index == qindex) ){
flag=true;
break;
}
// since words are added in order, stop
// when we get to previous word
if(list_alphabet(a_ptr)->nmap_index != nindex)
break;
}
if(!flag){
sym = new symbol_t;
sym->qmap_index=qindex;
sym->nmap_index=nindex;
list_alphabet.append(sym);
}
}
}
// special ENTER with prob of 1 symbol
nindex = nmap_name_to_index("!ENTER");
qindex = qmap_value_to_index(0); // log prob
flag=false;
for(a_ptr=list_alphabet.tail();a_ptr!=NULL;a_ptr=a_ptr->prev())
if( (list_alphabet(a_ptr)->nmap_index == nindex) &&
(list_alphabet(a_ptr)->qmap_index == qindex) ){
flag=true;
break;
}
if(!flag){
sym = new symbol_t;
sym->qmap_index=qindex;
sym->nmap_index=nindex;
list_alphabet.append(sym);
}
// and special no-label label (e-move)
sym = new symbol_t;
sym->qmap_index=-1;
sym->nmap_index=-1;
list_alphabet.append(sym);
ptr_qsort(list_alphabet);
count=0;
for(a_ptr=list_alphabet.head();a_ptr != NULL; a_ptr=a_ptr->next())
count++;
alphabet.resize(count);
count=0;
for(a_ptr=list_alphabet.head();a_ptr != NULL; a_ptr=a_ptr->next())
alphabet(count++) = *(list_alphabet(a_ptr));
// .. to do - delete syms
list_alphabet.clear();
e_move_symbol_index = alphabet_index_lookup(-1,-1);
cerr << "Alphabet has " << count << " symbols " << endl;
return true;
}
bool
Lattice::construct(Bigram &g)
{
// every word becomes a node, every non-zero transition becomes an arc
// eliminate any transitions into ENTER and out of EXIT
int i,j,k;
EST_Litem *n_ptr,*a_ptr;
Node *n;
Arc *a;
Node *from,*to;
int symbol;
// unfortunate, but fixed in Bigram class
int enteri = g.size() - 2;
int exiti = g.size() - 1;
int from_name,to_name;
// single entry node, no name since no arcs in
// single arc out to node called "!ENTER"
Node *enter_node = new Node;
enter_node->name.append(-1); // no name !
nodes.append(enter_node);
// make nodes - one for every entry in nmap
for(i=0; i<nmap.n(); i++){
n = new Node;
n->name.append(i); // index into nmap
nodes.append(n);
if(nmap(i) == "!ENTER"){ // temporary hack
symbol = alphabet_index_lookup(i,qmap_value_to_index(0)); // for log probs !!!
a = new Arc;
a->label = symbol;
a->to = n;
enter_node->arcs_out.append(a);
}
// keep note of final node
if(nmap(i) == "!EXIT") // temporary hack
final_nodes.append(n);
}
// make arcs
k=0;
for (i = 0; i < g.size(); ++i){
cerr << "building lattice " << (int)((float)i*100/(float)g.size()) << "% \r";
for (j = 0; j < g.size(); ++j){
// ignore any transitions into ENTER or out of EXIT
//if((g.p(i, j) > 0) && - for probs only, can't do for log probs
if((j != enteri) && (i != exiti)){
// find from and to nodes
from=NULL;
to=NULL;
if(i == enteri)
from_name = nmap_name_to_index("!ENTER");
else
from_name = nmap_name_to_index(g.words(i));
if(j == exiti)
to_name = nmap_name_to_index("!EXIT");
else
to_name= nmap_name_to_index(g.words(j));
for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
int name = nodes(n_ptr)->name(nodes(n_ptr)->name.head());
if(name == from_name)
from = nodes(n_ptr);
if(name == to_name)
to = nodes(n_ptr);
}
if(from==NULL){
cerr << "Couldn't find 'from' node " << nmap_index_to_name(from_name) << endl;
return false;
}
if(to==NULL){
cerr << "Couldn't find 'to' node " << nmap_index_to_name(to_name) << endl;
return false;
}
// get arc symbol - speed up this fn !
symbol = alphabet_index_lookup(to_name,qmap_value_to_index(g.p(i,j)));
if(symbol < 0){
cerr << "Couldn't lookup symbol in alphabet !" << endl;
return false;
}
a = new Arc;
a->label = symbol;
a->to = to;
from->arcs_out.append(a);
}
}
}
cerr << " \r";
int c1=0,c2=0,c3=0;
for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
c1++;
for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
c2++;
}
for (n_ptr = final_nodes.head(); n_ptr != 0; n_ptr = n_ptr->next())
c3++;
cerr << "NFA has " << c1
<< " nodes (" << c3 << " final)"
<< " and " << c2 << " arcs" << endl;
return true;
}
#endif
bool Lattice::determinise()
{
// very simple, but potentially time/memory consuming
// make a new lattice whose nodes are all permutations
// of the nodes in the old lattice
// BUT : only make the nodes which are actually required
// (otherwise number of new nodes = 2^(number of old nodes)
// we will call the old lattice NFA and the new one DFA
EST_Litem *n_ptr,*n2_ptr,*a_ptr,*l_ptr;
Node *new_node;
EST_TList<Node*> new_nodes;
EST_TList<Node*> new_final_nodes;
EST_TList<Arc*> new_arcs;
EST_TList<Arc*> arc_list;
EST_TList<int> new_name;
int c,count,current_label,new_arcs_made;
bool is_final;
// first, sort nodes' lists of arcs by label to make
// it easier
cerr << "sorting arc lists" << endl;
sort_arc_lists();
cerr << "making new nodes" << endl;
// - for every node in the NFA, look at the outgoing arcs with
// the same label
// - make a DFA node which is a combination of the NFA nodes
// which are the destinations of those arcs
// there are more DFA nodes made later
// enter node is special case, it has no in-going arcs
// so will not be made in the following loop
// for now, assume one enter node at head of list ... hmmmmm
new_node = new Node;
if(new_node == NULL){
cerr << "Could not allocate any more memory";
return false;
}
new_node->name = nodes(nodes.head())->name;
new_nodes.append(new_node);
for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
for (a_ptr = nodes(n_ptr)->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next()){
current_label = nodes(n_ptr)->arcs_out(a_ptr)->label;
// make list of arc destinations along arcs with this label
is_final=false;
new_name.clear();
new_name = nodes(n_ptr)->arcs_out(a_ptr)->to->name;
if(final(nodes(n_ptr)->arcs_out(a_ptr)->to) )
is_final=true;
while((a_ptr != NULL) &&
(a_ptr->next() != NULL) &&
(nodes(n_ptr)->arcs_out(a_ptr->next())->label == current_label)){
merge_sort_unique(new_name,nodes(n_ptr)->arcs_out(a_ptr->next())->to->name);
if( !is_final && final(nodes(n_ptr)->arcs_out(a_ptr->next())->to) )
is_final=true;
a_ptr=a_ptr->next();
}
// make new node with this name, unless we already have one
bool flag=false;
for (n2_ptr = new_nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next())
if( new_nodes(n2_ptr)->name == new_name ){
flag=true;
break;
}
if(!flag){ // need to make new node
new_node = new Node;
if(new_node == NULL){
cerr << "Could not allocate any more memory";
count=0;
for (n2_ptr = new_nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next())
count++;
cerr << " after making " << count << " nodes" << endl;
return false;
}
new_node->name = new_name;
new_nodes.append(new_node);
if(is_final)
new_final_nodes.append(new_node);
}
} // loop round outgoing arcs for this node
} // loop round NFA nodes
// now, for every node in the DFA, its 'transition function' (i.e. outgoing arcs)
// is the sum of the transition functions of its constituent nodes from
// the NFA
c=0;
new_arcs_made=0;
for (n_ptr = new_nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
c++;
cerr << "Processing node " << c
<< " arcs=" << new_arcs_made << " \r";
// find constituent nodes in NFA (only works if NFA names are single ints !)
arc_list.clear();
for(l_ptr=new_nodes(n_ptr)->name.head(); l_ptr != 0; l_ptr = l_ptr->next()){
for(n2_ptr = nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next()){
if(nodes(n2_ptr)->name(nodes(n2_ptr)->name.head()) ==
new_nodes(n_ptr)->name(l_ptr))
arc_list += nodes(n2_ptr)->arcs_out;
}
}
// now we have a list of all the NFA nodes we can 'get to'
// from this DFA node, sort by label and find the
// DFA node for each label
// or rather, take the arc list from above, and collapse
// all arcs with the same label into one arc to the DFA
// node which is the equivalent of the NFA nodes at the
// end of those arcs
sort_by_label(arc_list);
for(a_ptr=arc_list.head();a_ptr!=NULL;a_ptr=a_ptr->next()){
current_label=arc_list(a_ptr)->label;
//cerr << " label " << current_label;
is_final=false;
EST_TList<int> new_name2;
new_name2 = arc_list(a_ptr)->to->name;
if(final(arc_list(a_ptr)->to) )
is_final=true;
while((a_ptr != NULL) &&
(a_ptr->next() != NULL) &&
(arc_list(a_ptr->next())->label == current_label)){
merge_sort_unique(new_name2,arc_list(a_ptr)->to->name);
if( !is_final && final(arc_list(a_ptr)->to) )
is_final=true;
a_ptr=a_ptr->next();
}
//cerr << " -> " << new_name2;
// find DFA node with that name
bool flag=false;
for (n2_ptr = new_nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next())
if( new_nodes(n2_ptr)->name == new_name2 ){
flag=true;
break;
}
if(!flag){ // failed to make node previously, do it now
new_node = new Node;
if(new_node == NULL){
cerr << "Could not allocate any more memory";
count=0;
for (n2_ptr = new_nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next())
count++;
cerr << " after making " << count << " nodes" << endl;
return false;
}
new_node->name = new_name2;
new_nodes.append(new_node);
link(new_nodes(n_ptr),new_node,current_label);
if(is_final)
new_final_nodes.append(new_node);
}else{
link(new_nodes(n_ptr),new_nodes(n2_ptr),current_label);
}
new_arcs_made++;
}
} // loop round DFA nodes
cerr << endl;
// delete old nodes, and replace with new nodes
for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next())
delete nodes(n_ptr);
nodes.clear();
nodes=new_nodes;
new_nodes.clear();
final_nodes.clear();
final_nodes=new_final_nodes;
new_final_nodes.clear();
int c1=0,c2=0,c3=0;
for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
c1++;
for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
c2++;
}
for (n_ptr = final_nodes.head(); n_ptr != 0; n_ptr = n_ptr->next())
c3++;
cerr << "DFA has " << c1
<< " nodes (" << c3 << " final)"
<< " and " << c2 << " arcs" << endl;
return true;
}
bool
Lattice::link(Node *n1, Node *n2, int label)
{
//if(l==NULL)
//l=&arcs;
// create arc between two nodes
// in direction n1,n2
Arc *new_arc;
if( (n1==NULL) || (n2==NULL) ){
cerr << "Can't link null nodes" << endl;
return false;
}
new_arc = new Arc;
//new_arc->from = n1;
new_arc->to = n2;
new_arc->label = label;
n1->arcs_out.append(new_arc);
//n2->arcs_in.append(new_arc);
//l->append(new_arc);
return true;
}
void
Lattice::sort_arc_lists()
{
EST_Litem *n_ptr;
for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
// can't sort nodes(n_ptr)->arcs_out directly
// since it is a list of pointers
sort_by_label(nodes(n_ptr)->arcs_out);
}
}
void
sort_by_label(EST_TList<Lattice::Arc*> &l){
ptr_qsort(l);
}
bool
Lattice::build_distinguished_state_table(bool ** &dst)
{
int i,j;
EST_Litem *n_ptr,*n2_ptr;
int num_nodes = nodes.length();
// not every element will be used
dst = new bool*[num_nodes];
if(dst==NULL){
cerr << "Not enough memory" << endl;
return false;
}
for(i=0;i<num_nodes;i++){
dst[i] = new bool[num_nodes];
if(dst[i]==NULL){
cerr << "Not enough memory" << endl;
return false;
}
for(j=0;j<num_nodes;j++)
dst[i][j] = false;
}
cerr << "final/non-final scan";
// any final/non-final (or non-final/final) pairs are distinguished immediately
for(i=0,n_ptr=nodes.head();n_ptr->next()!=NULL;n_ptr=n_ptr->next(),i++){
for(j=i+1,n2_ptr=n_ptr->next();n2_ptr!=NULL;n2_ptr=n2_ptr->next(),j++){
if(final(nodes(n_ptr)) && !final(nodes(n2_ptr)))
dst[i][j] = true;
else if(!final(nodes(n_ptr)) && final(nodes(n2_ptr)))
dst[i][j] = true;
}
}
cerr << "\r \r";
// two possible methods, depending on network representation
// for sparse networks, use actual nodes and their lists of arcs
//build_distinguished_state_table_direct(dst);
// for dense networks, use a transition function matrix
// which will be faster but more memory consuming
if(!build_transition_function()){
cerr << "Couldn't build transition function" << endl;
return false;
}
if(!build_distinguished_state_table_from_transition_function(dst)){
cerr << "Couldn't build dst from transition function" << endl;
return false;
}
// delete tf, since it will be wrong for minimised net
for(i=0;i<num_nodes;i++)
delete [] tf[i];
delete [] tf;
tf=NULL;
return true;
}
bool
Lattice::build_distinguished_state_table_direct(bool ** &dst)
{
int i,j,i1,j1,scan_count,this_symbol;
EST_Litem *n_ptr,*n2_ptr,*a_ptr,*s_ptr;
bool flag,flag2;
// carry out repeated scans of the distinguished state table until no more
// cells are set true
flag=true;
scan_count=0;
while(flag){
flag=false;
scan_count++;
for(i=0,n_ptr=nodes.head();n_ptr->next()!=NULL;n_ptr=n_ptr->next(),i++){
for(j=i+1,n2_ptr=n_ptr->next();n2_ptr!=NULL;n2_ptr=n2_ptr->next(),j++){
cerr << "scan " << scan_count << " : " << i << "," << j << " \r";
if(!dst[i][j]){
// go through alphabet, or rather just those symbols
// occurring on the arcs out of this pair of nodes
flag2=true;
s_ptr=nodes(n_ptr)->arcs_out.head();
while(s_ptr != NULL){
if(flag2){ // we are going through symbols on arcs out of 'nodes(n_ptr)'
this_symbol=nodes(n_ptr)->arcs_out(s_ptr)->label;
i1 = node_index(nodes(n_ptr)->arcs_out(s_ptr)->to);
j1=-1;
for(a_ptr=nodes(n2_ptr)->arcs_out.head();
a_ptr!=NULL; a_ptr=a_ptr->next())
if(nodes(n2_ptr)->arcs_out(a_ptr)->label == this_symbol)
j1 = node_index(nodes(n2_ptr)->arcs_out(a_ptr)->to);
}else{ // we are going through symbols on arcs out of 'nodes(n2_ptr)'
this_symbol=nodes(n2_ptr)->arcs_out(s_ptr)->label;
j1 = node_index(nodes(n2_ptr)->arcs_out(s_ptr)->to);
i1=-1;
for(a_ptr=nodes(n_ptr)->arcs_out.head();
a_ptr!=NULL; a_ptr=a_ptr->next())
if(nodes(n_ptr)->arcs_out(a_ptr)->label == this_symbol)
i1 = node_index(nodes(n_ptr)->arcs_out(a_ptr)->to);
}
// States (nodes) are distinguished if, for any symbol, they
// have transitions (arcs) to a pair of distinguished states.
// This includes the case where, for any symbol, one state
// has a transition and the other does not
if( ( (i1>=0) && (j1>=0) && dst[i1][j1]) ||
( (i1>=0) && (j1<0) ) ||
( (j1>=0) && (i1<0) ) )
{
dst[i][j] = true;
flag=true;
break; // out of s_ptr loop
}
s_ptr=s_ptr->next();
if( (s_ptr==NULL) && (flag2) ){ // now go down second list
s_ptr=nodes(n2_ptr)->arcs_out.head();
flag2=false;
}
}
}
}
}
}
return true;
}
bool
Lattice::build_distinguished_state_table_from_transition_function(bool ** &dst)
{
int i,j,i2,j2,k,scan_count;
int num_nodes = nodes.length();
int num_symbols = alphabet.n();
bool flag;
flag=true;
scan_count=0;
while(flag){
flag=false;
scan_count++;
for(i=0;i<num_nodes-1;i++){
cerr << "scan " << scan_count << " : row "
<< i << " \r";
for(j=i+1;j<num_nodes;j++){
if( !dst[i][j] ){
for(k=0;k<num_symbols;k++){
i2 = tf[i][k];
j2 = tf[j][k];
if((i2<0) && (j2>=0)){
dst[i][j] = true;
flag=true;
break;
}else if((j2<0) && (i2>=0)){
dst[i][j] = true;
flag=true;
break;
}else if( (i2>0) && (j2>0) && dst[i2][j2] ){
dst[i][j] = true;
flag=true;
break;
}
}
}
}
}
}
return true;
}
bool
Lattice::minimise()
{
// method, make distinguished state table
// scan all pairs of states (a.k.a. nodes)
int i,j;
EST_Litem *n_ptr,*n2_ptr,*n3_ptr,*a_ptr;
int num_nodes = nodes.length();
bool **dst = NULL; // distinguished state table
bool flag;
if(!build_distinguished_state_table(dst)){
cerr << "Couldn't build distinguished state table" << endl;
return false;
}
int count=0,count2=0;
for(i=0;i<num_nodes-1;i++)
for(j=i+1;j<num_nodes;j++)
if(!dst[i][j])
count++;
else
count2++;
cerr << "There are " << count << " undistinguished pairs of nodes and "
<< count2 << " distinguished pairs" << endl;
// make lists of nodes to be merged
EST_TList<Node *> merge_list;
flag=true;
while(flag){
flag=false;
merge_list.clear();
for(i=0,n_ptr=nodes.head();n_ptr->next()!=NULL;n_ptr=n_ptr->next(),i++){
cerr << "merge, processing row " << i << " \r";
for(j=i+1,n2_ptr=n_ptr->next();n2_ptr!=NULL;n2_ptr=n2_ptr->next(),j++){
if(!dst[i][j]){
// is the merge list empty ?
if(merge_list.head() == NULL){
// put this pair of nodes on merge list
merge_list.append(nodes(n_ptr));
merge_list.append(nodes(n2_ptr));
dst[i][j] = true;
}else{ // merge list already has some items on it
// see if either of this pair of nodes is on the merge list,
// and if so add the other node in the pair
bool add1=false,add2=false;
for(n3_ptr=merge_list.head();n3_ptr!=NULL;n3_ptr=n3_ptr->next()){
if(merge_list(n3_ptr) == nodes(n_ptr))
add2=true;
if(merge_list(n3_ptr) == nodes(n2_ptr))
add1=true;
}
if(add1 && !add2){
merge_list.append(nodes(n_ptr));
dst[i][j] = true;
}else if(add2 && !add1){
merge_list.append(nodes(n2_ptr));
dst[i][j] = true;
}
}
}
}
}
// anything on the merge list ?
if(merge_list.head() != NULL){
// so merge them
count=0;
for(n_ptr=merge_list.head();n_ptr!=NULL;n_ptr=n_ptr->next())
count++;
cerr << "merging " << count << " nodes out of ";
count=0;
for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next())
count++;
cerr << count;
merge_nodes(merge_list);
flag=true;
count=0;
for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next())
count++;
cerr << " leaving " << count << endl;
}
}
int c1=0,c2=0;
for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
c1++;
for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
c2++;
}
cerr << "Minimum state DFA has " << c1
<< " nodes and " << c2 << " arcs " << endl;
merge_arcs();
c1=0,c2=0;
for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
c1++;
for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
c2++;
}
cerr << "Pruned minimum state DFA has " << c1
<< " nodes and " << c2 << " arcs" << endl;
for(i=0;i<num_nodes;i++)
delete [] dst[i];
delete [] dst;
return true;
}
void
Lattice::merge_nodes(EST_TList<Node*> &l)
{
if(l.head() == NULL)
return;
// make a new node with all node labels of old nodes
// and all arcs of old nodes
EST_Litem *n_ptr,*n2_ptr,*a_ptr,*a2_ptr;
Node *new_node;
new_node = new Node;
// to do .. deal with final_nodes list too ....
for(n_ptr=l.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
// get arcs
for(a_ptr=l(n_ptr)->arcs_out.head();a_ptr!=NULL;a_ptr=a_ptr->next())
new_node->arcs_out.append(l(n_ptr)->arcs_out(a_ptr));
// get name
merge_sort_unique(new_node->name,l(n_ptr)->name);
// find arcs into old nodes and make them go into new node
for(n2_ptr=nodes.head();n2_ptr!=NULL;n2_ptr=n2_ptr->next()){
for(a2_ptr=nodes(n2_ptr)->arcs_out.head();a2_ptr!=NULL;a2_ptr=a2_ptr->next()){
if(nodes(n2_ptr)->arcs_out(a2_ptr)->to == l(n_ptr))
nodes(n2_ptr)->arcs_out(a2_ptr)->to = new_node;
}
}
}
// delete old nodes, but not arcs
for(n_ptr=l.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
for(n2_ptr=nodes.head();n2_ptr!=NULL;n2_ptr=n2_ptr->next())
if(nodes(n2_ptr) == l(n_ptr)){
nodes(n2_ptr)->name.clear();
nodes(n2_ptr)->arcs_out.clear();
delete nodes(n2_ptr);
nodes.remove(n2_ptr);
}
}
nodes.append(new_node);
}
void
Lattice::merge_arcs()
{
EST_Litem *n_ptr,*a_ptr,*a2_ptr;
EST_TList<Arc*> merge_list;
int count=0,count2;
// find repeated arcs with the same label between two nodes
for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
count2=0;
for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
count2++;
cerr << "merging arcs from node " << ++count
<< ", before:" << count2;
for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr->next()!=NULL; a_ptr=a_ptr->next()){
merge_list.clear();
for(a2_ptr=a_ptr->next();a2_ptr!=NULL; a2_ptr=a2_ptr->next())
if((nodes(n_ptr)->arcs_out(a_ptr)->label ==
nodes(n_ptr)->arcs_out(a2_ptr)->label) &&
(nodes(n_ptr)->arcs_out(a_ptr)->to ==
nodes(n_ptr)->arcs_out(a2_ptr)->to) ){
delete nodes(n_ptr)->arcs_out(a2_ptr);
a2_ptr=nodes(n_ptr)->arcs_out.remove(a2_ptr);
}
}
count2=0;
for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
count2++;
cerr<< ", after:" << count2 << endl;
}
cerr << " \r" << endl;
}
void
Lattice::prune_arcs(Node *node, EST_TList<Arc*> arcs)
{
int count=0;
EST_Litem *a_ptr;
for(a_ptr=arcs.head(); a_ptr != 0; a_ptr=a_ptr->next() ){
prune_arc(node, arcs(a_ptr));
count++;
}
//cerr << "pruned " << count << " arcs" << endl;
}
void
Lattice::prune_arc(Node *node, Arc *arc)
{
remove_arc_from_nodes_out_list(node,arc);
delete arc;
}
/*
void
Lattice::remove_arc_from_nodes_in_list(Node *n, Arc *a)
{
EST_Litem *a_ptr;
for (a_ptr = n->arcs_in.head(); a_ptr != 0; a_ptr = a_ptr->next())
if(n->arcs_in(a_ptr) == a)
n->arcs_in.remove(a_ptr);
}
*/
void
Lattice::remove_arc_from_nodes_out_list(Node *n, Arc *a)
{
EST_Litem *a_ptr;
for (a_ptr = n->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next())
if(n->arcs_out(a_ptr) == a)
n->arcs_out.remove(a_ptr);
}
/* not used
bool
Lattice::is_enter_node(Node *n)
{
// contains "!ENTER" in its list of names
EST_Litem *l_ptr;
for(l_ptr=n->name.head(); l_ptr != 0; l_ptr=l_ptr->next())
if(n->name(l_ptr) == nmap_name_to_index("!ENTER")) // temporary !!
return true;
return false;
}
*/
/* Superseded now we have list of final nodes
bool
Lattice::is_exit_node(Node *n)
{
EST_Litem *l_ptr;
for(l_ptr=n->name.head(); l_ptr != 0; l_ptr=l_ptr->next())
if(n->name(l_ptr) == nmap_name_to_index("!EXIT")) // temporary !!
return true;
return false;
}
*/
EST_String
Lattice::nmap_index_to_name(int index)
{
if(index < nmap.n())
return nmap(index);
else{
cerr << "Warning : nmap index " << index << " out of range" << endl;
return EST_String("!error!");
}
}
int
Lattice::nmap_name_to_index(const EST_String &name)
{
int i,j,mid;
// binary search
i=0;
j=nmap.n()-1;
while(true){
mid = (i+j)/2;
if(name > nmap(mid))
i = mid;
else if(name < nmap(mid))
j = mid;
else{ // name == nmap(mid)
return mid; // lucky strike
}
if(i==j){
if(name == nmap(i))
return i;
else{
cerr << "Lattice::nmap_name_to_index failed for '"
<< name << "'" << endl;
return -1;
}
}else if(j==i+1){
if(name == nmap(i))
return i;
else if(name == nmap(j))
return j;
else{
cerr << "Lattice::nmap_name_to_index failed for '"
<< name << "'" << endl;
return -1;
}
}
}
return -1;
}
float
Lattice::qmap_index_to_value(int index)
{
if(index < qmap.n())
return qmap(index);
else{
cerr << "Warning : qmap index " << index << " out of range" << endl;
return 1;
}
}
int
Lattice::qmap_value_to_index(float value)
{
int i,j,mid;
// binary search
i=0;
j=qmap.n()-1;
while(true){
mid = (i+j)/2;
if(value > qmap(mid))
i = mid;
else if(value < qmap(mid))
j = mid;
else
return mid; // lucky strike
if(i==j)
return i;
else if(j==i+1){
if( fabs(qmap(i) - value) < fabs(qmap(j) - value) )
return i;
else
return j;
}
}
return 0;
}
int
Lattice::node_index(Node *n)
{
EST_Litem *n_ptr;
for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
if(nodes(n_ptr) == n)
return nodes.index(n_ptr);
}
//cerr << "Lattice::node_index(Node *n) couldn't find index of node " << n->name;
return -1;
}
bool
Lattice::expand()
{
// keep HTK happy - it can't handle multiple arcs into a node
// with different word labels
EST_Litem *n_ptr,*n2_ptr,*a_ptr,*w_ptr;
int word;
EST_TList<int> word_list;
Node *new_node;
Arc *new_arc;
for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
// find all arcs into this node
word_list.clear();
for (n2_ptr = nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next()){
for (a_ptr = nodes(n2_ptr)->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next())
if(nodes(n2_ptr)->arcs_out(a_ptr)->to == nodes(n_ptr)){
if(nodes(n2_ptr)->arcs_out(a_ptr)->label != e_move_symbol_index){
word = alphabet_index_to_symbol(nodes(n2_ptr)->arcs_out(a_ptr)->label)->nmap_index;
word_list.append(word);
sort_unique(word_list);
}
}
}
// if word_list.head() is NULL we should be worried
if((word_list.head() != NULL) && word_list.head()->next() != NULL){
// for each word make a null node, change all offending arcs to point
// to it, and make another link from null node to nodes(n_ptr)
for(w_ptr=word_list.head();w_ptr!=NULL;w_ptr=w_ptr->next()){
// make null node
new_node = new Node;
new_arc = new Arc;
new_arc->label = e_move_symbol_index; // no label
new_arc->to = nodes(n_ptr);
new_node->arcs_out.append(new_arc);
// for every arc into nodes(n_ptr) with this word label, change its arcs
for (n2_ptr = nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next()){
for (a_ptr = nodes(n2_ptr)->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next()){
if(nodes(n2_ptr)->arcs_out(a_ptr)->to == nodes(n_ptr)){
word = alphabet_index_to_symbol(nodes(n2_ptr)->arcs_out(a_ptr)->label)->nmap_index;
if(word == word_list(w_ptr)){
// change the arc
nodes(n2_ptr)->arcs_out(a_ptr)->to = new_node;
}
}
}
}
nodes.append(new_node);
}
}
}
// need to make sure ENTER node has no arcs in - if so add a dummy ENTER node
//Node *enter_node = nodes(nodes.head());
bool flag=false;
for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next()){
flag=true;
break;
}
}
/*
if(flag){
cerr << " fixing ENTER node" << endl;
new_node = new Node;
new_arc = new Arc;
new_arc->label = enter_node->label;
new_arc->to = enter_node;
new_node->arcs_out.append(new_arc);
nodes.append(new_node);
}
*/
// also need to make sure there is only one EXIT node
if(final_nodes.length() > 1){
cerr << " making single EXIT node" << endl;
// make null node
new_node = new Node;
for(n_ptr=final_nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
new_arc = new Arc;
new_arc->label = e_move_symbol_index; // no label
new_arc->to = final_nodes(n_ptr);
final_nodes(n_ptr)->arcs_out.append(new_arc);
}
// empty final node list (nodes themselves remain on nodes list)
final_nodes.clear();
// now a single final node
nodes.append(new_node);
final_nodes.append(new_node);
}
int c1=0,c2=0;
for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
c1++;
for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
c2++;
}
cerr << "HTKified DFA has " << c1
<< " nodes and " << c2 << " arcs" << endl;
return true;
}
bool
Lattice::final(Node *n)
{
EST_Litem *n_ptr;
for (n_ptr = final_nodes.head(); n_ptr != 0; n_ptr = n_ptr->next())
if(final_nodes(n_ptr) == n)
return true;
return false;
}
EST_String Lattice::name_as_string(EST_IList &l)
{
EST_String name;
EST_Litem *l_ptr;
for(l_ptr=l.head();l_ptr!=NULL;l_ptr=l_ptr->next())
name+=nmap_index_to_name(l(l_ptr)) + ",";
return name;
}
int
Lattice::alphabet_index_lookup(int nmap_index, int qmap_index)
{
symbol_t sym;
sym.nmap_index = nmap_index;
sym.qmap_index = qmap_index;
return alphabet_symbol_to_index(&sym);
}
Lattice::symbol_t*
Lattice::alphabet_index_to_symbol(int index)
{
if(index < alphabet.n())
return &(alphabet[index]);
else{
cerr << "Warning : alphabet index " << index << " out of range" << endl;
return NULL;
}
}
int
Lattice::alphabet_symbol_to_index(Lattice::symbol_t *sym)
{
int i,j,mid;
// binary search
i=0;
j=alphabet.n()-1;
while(true){
mid = (i+j)/2;
if(*sym > alphabet(mid))
i = mid;
else if(*sym < alphabet(mid))
j = mid;
else // *sym == alphabet(mid)
return mid; // lucky strike
if(i==j){
if(*sym == alphabet(i))
return i;
else{
cerr << "Lattice::alphabet_symbol_to_index failed for '"
<< *sym << "' 1" << endl;
return -1;
}
}else if(j==i+1){
if(*sym == alphabet(i))
return i;
else if(*sym == alphabet(j))
return j;
else{
cerr << "Lattice::alphabet_symbol_to_index failed for '"
<< *sym << "' 2" << endl;
cerr << i << " " << alphabet(i) << endl;
cerr << j << " " << alphabet(j) << endl;
return -1;
}
}
}
return -1;
}
bool
Lattice::build_transition_function()
{
// different representation of the network , currently only for DFAs
// since for a NFA each tf cell would be a list
int i,j;
EST_Litem *n_ptr,*a_ptr;
int num_nodes = nodes.length();
int num_symbols = alphabet.n();
if(tf != NULL)
cerr << "Warning : discarding existing transition function" << endl;
tf = new int*[num_nodes];
for(i=0;i<num_nodes;i++)
tf[i] = new int[num_symbols];
if(tf == NULL){
cerr << "Not enough memory to build transition function"
<< "(needed " << num_nodes*num_symbols*sizeof(int) << " bytes)" << endl;
return false;
}
for(i=0,n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next(),i++){
cerr << "building transition function " << (int)((float)(i+1)*100/(float)num_nodes) << "% \r";
for(j=0;j<alphabet.n();j++){
tf[i][j]=-1; // means no transition
for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL;a_ptr=a_ptr->next()){
if(j == nodes(n_ptr)->arcs_out(a_ptr)->label){
tf[i][j] = node_index(nodes(n_ptr)->arcs_out(a_ptr)->to);
break;
}
}
}
}
cerr << endl;
return true;
}
bool
Lattice::accepts(EST_TList<symbol_t*> &string)
{
(void) string;
return false;
}
float
Lattice::viterbi_transduce(EST_TList<EST_String> &input,
EST_TList<Arc*> &path,
EST_Litem *current_symbol,
Node *start_node)
{
// finds maximum sum-of-probs path
EST_Litem *a_ptr,*best;
if(start_node == NULL){
start_node = nodes(nodes.head());
current_symbol = input.head();
path.clear();
}
if(current_symbol == NULL){ // consumed all input
if( final(start_node) )
return 0; // log prob 1
else
return -10000000; // hack for now
}
best=NULL;
float max=-10000000; // hack for now
for (a_ptr = start_node->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next()){
if( alphabet_index_to_symbol(start_node->arcs_out(a_ptr)->label)->nmap_index
== nmap_name_to_index(input(current_symbol)) ){
float x = viterbi_transduce(input,
path,
current_symbol->next(),
start_node->arcs_out(a_ptr)->to)
+ qmap_index_to_value(alphabet_index_to_symbol(start_node->arcs_out(a_ptr)->label)->qmap_index);
if(x > max){
max = x;
best = a_ptr;
}
}
}
if(best != NULL)
path.append(start_node->arcs_out(best));
return max;
}
float Lattice::viterbi_transduce(EST_Track &observations,
EST_TList<Arc*> &path,
float &score,
int current_frame,
Node *start_node)
{
// finds maximum sum-of-probs path
EST_Litem *a_ptr,*best;
if(start_node == NULL){
start_node = nodes(nodes.head());
current_frame = 0;
path.clear();
score = 0.0;
}
if(current_frame == observations.num_frames()){ // consumed all input
if( final(start_node) )
return 0; // log prob 1
else
return -10000000; // hack for now
}
if(score < -100000){ // hack !
return -10000000;
}
best=NULL;
float max=-10000000; // hack for now
for (a_ptr = start_node->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next()){
int observation_element =
alphabet_index_to_symbol(start_node->arcs_out(a_ptr)->label)->nmap_index
- 2; // HACK !!@!!!! to skip ENTER/EXIT
float this_observation = observations.a(current_frame,observation_element);
//cerr << "frame " << current_frame << "," << observation_element
//<< " : " << this_observation << endl;
float x = viterbi_transduce(observations,
path,
score,
current_frame+1,
start_node->arcs_out(a_ptr)->to)
+ qmap_index_to_value(alphabet_index_to_symbol(start_node->arcs_out(a_ptr)->label)->qmap_index)
+ this_observation;
if(x > max){
max = x;
best = a_ptr;
}
}
if(best != NULL){
path.append(start_node->arcs_out(best));
int observation_element =
alphabet_index_to_symbol(start_node->arcs_out(best)->label)->nmap_index;
float this_observation = observations.a(current_frame,observation_element);
score += qmap_index_to_value(alphabet_index_to_symbol(start_node->arcs_out(best)->label)->qmap_index) + this_observation;
;
}
cerr << max << endl;
return max;
}
// hack for now (required for SHARED=2)
bool Lattice::symbol_t::operator!=(Lattice::symbol_t const &) const {
return false;
}
EST_String
Definition EST_String.h:70
EST_TList
Definition EST_TList.h:109
EST_TList::clear
void clear(void)
remove all items in list
Definition EST_TList.h:239
EST_TList::append
void append(const T &item)
add item onto end of list
Definition EST_TList.h:191
EST_Track
Definition EST_Track.h:89
EST_Track::a
float & a(int i, int c=0)
Definition EST_Track.cc:1022
EST_Track::num_frames
int num_frames() const
return number of frames in track
Definition EST_Track.h:650
Lattice::Arc
Definition EST_lattice.h:76
Lattice::Node
Definition EST_lattice.h:82
Lattice::symbol_t
Definition EST_lattice.h:65