sausagemaker.java

It is the Speech recognition software. It is platform independent. To execute the source code,

/*
 * Copyright 1999-2004 Carnegie Mellon University.
 * Portions Copyright 2004 Sun Microsystems, Inc.
 * Portions Copyright 2004 Mitsubishi Electric Research Laboratories.
 * All Rights Reserved.  Use is subject to license terms.
 *
 * See the file "license.terms" for information on usage and
 * redistribution of this file, and for a DISCLAIMER OF ALL
 * WARRANTIES.
 *
 *
 * Created on Aug 10, 2004
 */
package edu.cmu.sphinx.result;

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Vector;

import edu.cmu.sphinx.linguist.dictionary.Pronunciation;
import edu.cmu.sphinx.linguist.dictionary.Word;
import edu.cmu.sphinx.util.LogMath;
import edu.cmu.sphinx.util.props.Configurable;
import edu.cmu.sphinx.util.props.PropertyException;
import edu.cmu.sphinx.util.props.PropertySheet;
import edu.cmu.sphinx.util.props.PropertyType;
import edu.cmu.sphinx.util.props.Registry;

class ClusterComparator implements Comparator {
    
    /**
     * Compares to clusters according to their topological relationship. Relies
     * on strong assumptions about the possible constituents of clusters which
     * will only be valid during the sausage creation process.
     * 
     * @param o1 the first cluster (must be a List)
     * @param o2 the second cluster (must be a List)
     */
    public int compare(Object o1, Object o2) {
        List cluster1 = (List) o1;
        List cluster2 = (List) o2;
        Iterator i = cluster1.iterator();
        while (i.hasNext()) {
            Node n1 = (Node)i.next();
            Iterator i2 = cluster2.iterator();
            while (i2.hasNext()) {
                Node n2 = (Node)i2.next();
                if (n1.isAncestorOf(n2)) {
                    return -1;
                } else if (n2.isAncestorOf(n1)) {
                    return 1;
                }
            }
        }
        return 0;
    }
}


/**
 * <p>
 * The SausageMaker takes word lattices as input and turns them into sausages 
 * (Confusion Networks) according to Mangu, Brill and Stolcke, "Finding 
 * Consensus in Speech Recognition: word error minimization and other 
 * applications of confusion networks", Computer Speech and Language, 2000.
 * Note that the <code>getBestHypothesis</code> of the ConfidenceResult
 * object returned by the {@link #score(Result) score} method
 * returns the path where all the words have the highest posterior
 * probability within its corresponding time slot.
 * </p>
 *
 *
 * @author pgorniak
 *
 */
public class SausageMaker implements ConfidenceScorer, Configurable {
    
    /**
     * Sphinx property that defines the language model weight.
     */
    public final static String PROP_LANGUAGE_WEIGHT = "languageWeight";

    /**
     * The default value for the PROP_LANGUAGE_WEIGHT property
     */
    public final static float PROP_LANGUAGE_WEIGHT_DEFAULT  = 1.0f;
    
    private String name;
    private float languageWeight;
    
    protected Lattice lattice;
    
    /**
     * @see edu.cmu.sphinx.util.props.Configurable#register(java.lang.String,
     *      edu.cmu.sphinx.util.props.Registry)
     */
    public void register(String name, Registry registry)
        throws PropertyException {
        this.name = name;
        registry.register(PROP_LANGUAGE_WEIGHT, PropertyType.FLOAT);
    }


    /**
     * @see edu.cmu.sphinx.util.props.Configurable#newProperties(edu.cmu.sphinx.util.props.PropertySheet)
     */
    public void newProperties(PropertySheet ps) throws PropertyException {
        languageWeight = ps.getFloat(PROP_LANGUAGE_WEIGHT,
                                     PROP_LANGUAGE_WEIGHT_DEFAULT);
    }

    /**
     * @see edu.cmu.sphinx.util.props.Configurable#getName()
     */
    public String getName() {
        return name;
    }

    /**
     * Construct an empty sausage maker
     *
     */
    public SausageMaker() {
    }
    
    /**
     * Construct a sausage maker
     *
     * @param l the lattice to construct a sausage from
     */
    public SausageMaker(Lattice l) {
        lattice = l;
    }

    /**
     * Perform the inter word clustering stage of the algorithm
     * 
     * @param clusters the current cluster set
     */
    protected void interWordCluster(List clusters) {
        while(interWordClusterStep(clusters));
    }

    /**
     * Returns true if the two given clusters has time overlaps.
     * Given clusters A and B, they overlap if and only if:
     * the latest begin time of any node in B is before 
     * the earliest end time of any node in A,
     * and the latest begin time of any node in A is before the
     * earliest end time of any node in B.
     *
     * @param cluster1 the first cluster to examine
     * @param cluster2 the second cluster to examine
     *
     * @return true if the clusters has overlap, false if they don't
     */
    private boolean hasOverlap(List cluster1, List cluster2) {
        int latestBeginTime1 = getLatestBeginTime(cluster1);
        int earliestEndTime1 = getEarliestEndTime(cluster1);
        int latestBeginTime2 = getLatestBeginTime(cluster2);
        int earliestEndTime2 = getEarliestEndTime(cluster2);

        if (latestBeginTime1 < earliestEndTime2 &&
            latestBeginTime2 < earliestEndTime1) {
            return true;
        } else if (latestBeginTime2 < earliestEndTime1 &&
                   latestBeginTime1 < earliestEndTime2) {
            return true;
        } else {
            return false;
        }
    }
    
    /**
     * Returns the latest begin time of all nodes in the given cluster.
     *
     * @param cluster the cluster to examine
     *
     * @return the latest begin time
     */
    private int getLatestBeginTime(List cluster) {
        if (cluster.size() == 0) {
            return -1;
        }
        int startTime = 0;
        Iterator i = cluster.iterator();
        while (i.hasNext()) {
            Node n = (Node)i.next();
            if (n.getBeginTime() > startTime) {
                startTime = n.getBeginTime();
            }
        }
        return startTime;
    }

    /**
     * Returns the earliest end time of all nodes in the given cluster.
     *
     * @param cluster the cluster to examine
     *
     * @return the earliest end time
     */
    private int getEarliestEndTime(List cluster) {
        if (cluster.size() == 0) {
            return -1;
        }
        int endTime = Integer.MAX_VALUE;
        Iterator i = cluster.iterator();
        while (i.hasNext()) {
            Node n = (Node)i.next();
            if (n.getEndTime() < endTime) {
                endTime = n.getEndTime();
            }
        }
        return endTime;
    }

    /**
     * Perform one inter word clustering step of the algorithm
     * 
     * @param clusters the current cluster set
     */
    protected boolean interWordClusterStep(List clusters) {
        List toBeMerged1 = null;
        List toBeMerged2 = null;
        double maxSim = Double.NEGATIVE_INFINITY;
        ListIterator i = clusters.listIterator();
        while (i.hasNext()) {
            List c1 = (List)i.next();
            if (!i.hasNext()) {
                break;
            }
            ListIterator j = clusters.listIterator(i.nextIndex());
            while (j.hasNext()) {
                List c2 = (List)j.next();
                double sim = interClusterDistance(c1,c2);
                if (sim > maxSim && hasOverlap(c1,c2)) {
                    maxSim = sim;
                    toBeMerged1 = c1;
                    toBeMerged2 = c2;
                }
            }
        }
        if (toBeMerged1 != null) {
            clusters.remove(toBeMerged2);
            toBeMerged1.addAll(toBeMerged2);
            return true;
        }
        return false;
    }
    
    /**
     * Find the string edit distance between to lists of objects.
     * Objects are compared using .equals()
     * TODO: could be moved to a general utility class
     * 
     * @param p1 the first list 
     * @param p2 the second list
     * @return the string edit distance between the two lists
     */
    protected int stringEditDistance(List p1, List p2) {
        if (p1.size() == 0) {
            return p2.size();
        }
        if (p2.size() == 0) {
            return p1.size();
        }
        int [][] distances = new int[p1.size()][p2.size()];
        distances[0][0] = 0;
        for (int i=0;i<p1.size();i++) {
            distances[i][0] = i;
        }
        for (int j=0;j<p2.size();j++) {
            distances[0][j] = j;
        }
        for (int i=1;i<p1.size();i++) {
            for (int j=1;j<p2.size();j++) {
                int min = Math.min(distances[i-1][j-1]
                                       + (p1.get(i).equals(p2.get(j)) ? 0 : 1),
                                   distances[i-1][j] + 1);
                min = Math.min(min,distances[i][j-1] + 1);
            }            
        }
        return distances[p1.size()-1][p2.size()-1];
    }
    
    /**
     * Compute the phonetic similarity of two lattice nodes, based on the string
     * edit distance between their most likely pronunciations.
     * TODO: maybe move to Node.java?
     * 
     * @param n1 the first node
     * @param n2 the second node
     * @return the phonetic similarity, between 0 and 1
     */
    protected double computePhoneticSimilarity(Node n1, Node n2) {
        Pronunciation p1 = n1.getWord().getMostLikelyPronunciation();
        Pronunciation p2 = n2.getWord().getMostLikelyPronunciation();
        double sim = stringEditDistance(Arrays.asList(p1.getUnits()),
                        Arrays.asList(p2.getUnits()));
        sim /= (double)(p1.getUnits().length + p2.getUnits().length);
        return 1-sim;
    }