sausagemaker.java

来自「It is the Speech recognition software. 」· Java 代码 · 共 620 行 · 第 1/2 页

    /**
     * Return the total probability mass of the subcluster of nodes of the given
     * cluster that all have the given word as their word.
     * 
     * @param cluster the cluster to subcluster from
     * @param word the word to subcluster by
     * @return the log probability mass of the subcluster formed by the word
     */
    protected double wordSubClusterProbability(List cluster, String word) {
        return clusterProbability(makeWordSubCluster(cluster,word));
    }
    
    /**
     * Calculate the sum of posteriors in this cluster.
     * 
     * @param cluster the cluster to sum over
     * @return the probability sum
     */
    protected double clusterProbability(List cluster) {
        float p = LogMath.getLogZero();
        Iterator i = cluster.iterator();
        while (i.hasNext()) {
            p = lattice.getLogMath().addAsLinear(p,(float)((Node)i.next()).getPosterior());
        }
        return p;
    }
    
    /**
     * Form a subcluster by extracting all nodes corresponding to a given word.
     * 
     * @param cluster the parent cluster
     * @param word the word to cluster by
     * @return the subcluster.
     */
    protected List makeWordSubCluster(List cluster, String word) {
        Vector sub = new Vector();
        Iterator i = cluster.iterator();
        while (i.hasNext()) {
            Node n = (Node)i.next();
            if (n.getWord().getSpelling().equals(word)) {
                sub.add(n);
            }
        }
        return sub;
    }
    
    /**
     * Calculate the distance between two clusters
     * 
     * @param cluster1 the first cluster
     * @param cluster2 the second cluster
     * @return the inter cluster similarity, or Double.NEGATIVE_INFINITY if 
     *         these clusters should never be clustered together.
     */
    protected double interClusterDistance(List cluster1, List cluster2) {
        if (areClustersInRelation(cluster1,cluster2)) {
            return Double.NEGATIVE_INFINITY;
        }
        float totalSim = LogMath.getLogZero();
        float wordPairCount = (float)0.0;
        HashSet wordsSeen1 = new HashSet();
        
        Iterator i1 = cluster1.iterator();
        while (i1.hasNext()) {
            Node node1 = (Node)i1.next();
            String word1 = node1.getWord().getSpelling();
            if (wordsSeen1.contains(word1)) {
                continue;
            }
            wordsSeen1.add(word1);
            HashSet wordsSeen2 = new HashSet();
            Iterator i2 = cluster2.iterator();
            while (i2.hasNext()) {
                Node node2 = (Node)i2.next();
                String word2 = node2.getWord().getSpelling();
                if (wordsSeen2.contains(word2)) {
                    continue;
                }
                wordsSeen2.add(word2);
                float sim = (float)computePhoneticSimilarity(node1,node2);
                sim = lattice.getLogMath().linearToLog(sim);
                sim += wordSubClusterProbability(cluster1,word1);
                sim += wordSubClusterProbability(cluster2,word2);
                totalSim = lattice.getLogMath().addAsLinear(totalSim,sim);
                wordPairCount++;
            }
        }                        
        return totalSim - lattice.getLogMath().logToLinear(wordPairCount);
    }
    
    /**
     * Check whether these to clusters stand in a relation to each other.
     * Two clusters are related if a member of one is an ancestor of a member
     * of the other cluster.
     * 
     * @param cluster1 the first cluster
     * @param cluster2 the second cluster
     * @return true if the clusters are related
     */
    protected boolean areClustersInRelation(List cluster1, List cluster2) {
        Iterator i = cluster1.iterator();
        while (i.hasNext()) {
            Iterator j = cluster2.iterator();
            Node n1 = (Node)i.next();
            while (j.hasNext()) {
                if (n1.hasAncestralRelationship((Node)j.next())) {
                    return true;
                }
            }
        }
        return false;
    }
    
    /**
     * Calculate the distance between two clusters, forcing them to have the same
     * words in them, and to not be related to each other.
     * 
     * @param cluster1 the first cluster
     * @param cluster2 the second cluster
     * @return The intra cluster distance, or Double.NEGATIVE_INFINITY if the clusters
     *         should never be clustered together.
     */
    protected double intraClusterDistance(List cluster1, List cluster2) {
        double maxSim = Double.NEGATIVE_INFINITY;
        Iterator i1 = cluster1.iterator();
        while (i1.hasNext()) {
            Node node1 = (Node)i1.next();
            Iterator i2 = cluster2.iterator();
            while (i2.hasNext()) {
                Node node2 = (Node)i2.next();
                if (!node1.getWord().getSpelling().equals(node2.getWord().getSpelling())) {
                    return Double.NEGATIVE_INFINITY;
                }
                if (node1.hasAncestralRelationship(node2)) {
                    return Double.NEGATIVE_INFINITY;
                }
                double overlap = 0.0;
                if (node1.getBeginTime() <= node2.getBeginTime() &&
                        node1.getEndTime() >= node2.getBeginTime()) {
                    overlap = node1.getEndTime() - node2.getBeginTime();
                    if (node1.getEndTime() > node2.getEndTime()) {
                        overlap -= node2.getEndTime() - node1.getEndTime(); 
                    }
                } else if(node2.getBeginTime() <= node1.getBeginTime() &&
                        node2.getEndTime() >= node1.getBeginTime()) {
                    overlap = node2.getEndTime() - node1.getBeginTime();                    
                    if (node2.getEndTime() > node1.getEndTime()) {
                        overlap -= node1.getEndTime() - node2.getEndTime(); 
                    }
                }
                if (overlap > 0.0) {
                    overlap = lattice.getLogMath().logToLinear((float)overlap);
                    overlap += node1.getPosterior() + node2.getPosterior();
                    if (overlap > maxSim) {
                        maxSim = overlap;
                    }
                }
            }
        }        
        return maxSim;
    }
    
    /**
     * print out a cluster for debugging
     * 
     * @param cluster
     */
    protected void printCluster(List cluster) {
        ListIterator j = cluster.listIterator();
        while (j.hasNext()) {
            System.out.print(" " + j.next());                
        }
	System.out.println();
    }
    
    /**
     * print out a list of clusters for debugging
     * 
     * @param clusters
     */
    protected void printClusters(List clusters) {
        ListIterator i = clusters.listIterator();
        while (i.hasNext()) {
            System.out.print("----cluster " + i.nextIndex() + " : ");
            printCluster((List)i.next());
        }
        System.out.println("----");
    }
    
    /**
     * Perform the intra word clustering stage of the algorithm
     * 
     * @param clusters the current list of clusters
     */
    protected void intraWordCluster(List clusters) {
        while (intraWordClusterStep(clusters));
    }
    
    /**
     * Perform a step of the intra word clustering stage
     * 
     * @param clusters the current list of clusters
     * @return did two clusters get merged?
     */
    protected boolean intraWordClusterStep(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 = intraClusterDistance(c1,c2);
                if (sim > maxSim) {
                    maxSim = sim;
                    toBeMerged1 = c1;
                    toBeMerged2 = c2;
                }
            }
        }
        if (toBeMerged1 != null) {
            clusters.remove(toBeMerged2);
            toBeMerged1.addAll(toBeMerged2);
            return true;
        }
        return false;
    }
    
    /**
     * Turn the lattice contained in this sausage maker into a sausage object.
     * 
     * @return the sausage producing by collapsing the lattice.
     */
    public Sausage makeSausage() {

        Vector clusters = new Vector(lattice.getNodes().size());
        Collection nodes = lattice.nodes.values();
        Iterator i = nodes.iterator();
        while(i.hasNext()) {
            Vector bucket = new Vector(1);
            bucket.add(i.next());
            clusters.add(bucket);
        }
        intraWordCluster(clusters);
        interWordCluster(clusters);

        clusters = topologicalSort(clusters);

        Sausage sausage = new Sausage(clusters.size());
        ListIterator c1 = clusters.listIterator();
        while (c1.hasNext()) {
            HashSet seenWords = new HashSet();
            int index = c1.nextIndex();
            List cluster = ((List)c1.next());
            Iterator c2 = cluster.iterator();
            while (c2.hasNext()) {
                Node node = (Node)c2.next();
                Word word = node.getWord();
                if (seenWords.contains(word.getSpelling())) {
                    continue;
                }
                seenWords.add(word.getSpelling());
                SimpleWordResult swr = new SimpleWordResult
                    (node,
                     wordSubClusterProbability(cluster,word.getSpelling()),
                     lattice.getLogMath());
                sausage.addWordHypothesis(index,swr);
            }
        }
        sausage.fillInBlanks(lattice.getLogMath());
        return sausage;
    }
    
    /**
     * @see edu.cmu.sphinx.result.ConfidenceScorer#score(edu.cmu.sphinx.result.Result)
     */
    public ConfidenceResult score(Result result) {
        lattice = new Lattice(result);
        LatticeOptimizer lop = new LatticeOptimizer(lattice);
        lop.optimize();
        lattice.computeNodePosteriors(languageWeight);
        return makeSausage();
    }

    /**
     * Topologically sort the clusters. Note that this is a brunt force
     * sort by removing the min cluster from the list of clusters,
     * since Collections.sort() does not work in all cases.
     *
     * @param clusters the list of clusters to be topologically sorted
     *
     * @return a topologically sorted list of clusters
     */
    private Vector topologicalSort(Vector clusters) {
        Comparator comparator = new ClusterComparator();
        Vector sorted = new Vector(clusters.size());
        while (clusters.size() > 0) {
            List cluster = (List) Collections.min(clusters, comparator);
            clusters.remove(cluster);
            sorted.add(cluster);
        }
        return sorted;
    }
}