latticeoptimizer.java

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

     * Given two edges from equivalent nodes to a single nodes,
     * replace with one edge from one node with incomming edges
     * that are a union of the incomming edges of the old two nodes.
     *
     *  A --> B --> C
     *  X --> B' --/
     *
     *  where B and B' are equivalent.
     *
     *  is replaced with
     *
     *  A --> B" --> C
     *  X --/
     *
     *  where B" is the merge of B and B'
     *
     *  Note that equivalent nodes must have the same outgoing edges.
     *  For example
     *
     *  A --> X
     *    \
     *     \
     *      \
     *  A' --> B
     *
     *  A and A' would not be equivalent because the outgoing edges
     *  are different
     */
    protected void optimizeBackward() {
        //System.err.println("*** Optimizing backward ***");

        boolean moreChanges = true;
        while (moreChanges) {
            moreChanges = false;
            // search for a node that can be optimized
            // note that we use getCopyOfNodes to avoid concurrent changes to nodes
            for (Iterator i = lattice.getCopyOfNodes().iterator(); i.hasNext();) {
                Node n = (Node) i.next();

                // we are iterating down a list of node before optimization
                // previous iterations may have removed nodes from the list
                // therefore we have to check that the node stiff exists
                if (lattice.hasNode(n)) {
                    moreChanges |= optimizeNodeBackward(n);
                }
            }
        }
    }

    /**
     * Look for 2 entering edges from equivalent nodes.  Replace the edges
     * with one edge to one new node that is a merge of the equivalent nodes
     * Nodes are equivalent if they have equivalent to edges, and the same 
     * label. Merged nodes have a union of entering and leaving edges
     *
     * @param n
     * @return true if Node n required opimizing backwards
     */
    protected boolean optimizeNodeBackward(Node n) {
        Vector enteringEdges = new Vector(n.getEnteringEdges());
        for (int j = 0; j < enteringEdges.size(); j++) {
            Edge e = (Edge) enteringEdges.elementAt(j);
            for (int k = j + 1; k < n.getEnteringEdges().size(); k++) {
                Edge e2 = (Edge) enteringEdges.elementAt(k);

                /*
                 * If these are not the same edge, and they point to
                 * equivalent nodes, we have a hit, return true
                 */
                assert e != e2;
                if (equivalentNodesBackward(e.getFromNode(),
                                            e2.getFromNode())) {
                    mergeNodesAndEdgesBackward(n, e, e2);
                    return true;
                }
            }
        }
        /*
         * return false if we did not get a hit
         */
        return false;
    }

    /**
     * nodes are equivalent backward if they have "to" edges to the same nodes,
     * and have equivalent labels (Token, start/end times)
     *
     * @param n1
     * @param n2
     * @return true if n1 and n2 are "equivalent backwards"
     */
    protected boolean equivalentNodesBackward(Node n1, Node n2) {

        assert lattice.hasNode(n1);
        assert lattice.hasNode(n2);

        // do the labels match?
        if (!equivalentNodeLabels(n1, n2)) return false;

        // if they have different number of "to" edges they are not equivalent
        // or if there is a "to" edge with no match then the nodes are not equiv
        return n1.hasEquivalentLeavingEdges(n2);
    }

    /**
     * Is the contents of these Node equivalent?
     *
     * @param n1
     * @param n2
     * @return true if n1 and n2 have "equivalent labels"
     */
    protected boolean equivalentNodeLabels(Node n1, Node n2) {
        return (n1.getWord().equals(n2.getWord()) &&
                (n1.getBeginTime() == n2.getBeginTime() &&
                 n1.getEndTime() == n2.getEndTime()));
    }

    /**
     * given edges e1 and e2 to node n from nodes n1 and n2
     *
     * merge e1 and e2, that is, merge the scores of e1 and e2
     * create n' that is a merge of n1 and n2
     * add n'
     * add edge e' from n' to n
     *
     * remove n1 and n2 and all associated edges
     *
     * @param n
     * @param e1
     * @param e2
     */
    protected void mergeNodesAndEdgesBackward(Node n, Edge e1, Edge e2) {
        assert lattice.hasNode(n);
        assert lattice.hasEdge(e1);
        assert lattice.hasEdge(e2);

        assert e1.getToNode() == n;
        assert e2.getToNode() == n;

        Node n1 = e1.getFromNode();
        Node n2 = e2.getFromNode();

        assert n1.hasEquivalentLeavingEdges(n2);
        assert n1.getWord().equals(n2.getWord());

        // merge the scores of e1 and e2 into e1
        e1.setAcousticScore(mergeAcousticScores(e1.getAcousticScore(),
                                                e2.getAcousticScore()));
        e1.setLMScore(mergeLanguageScores(e1.getLMScore(),
                                          e2.getLMScore()));

        // add n2's "from" edges to n1
        for (Iterator i = n2.getEnteringEdges().iterator(); i.hasNext();) {
            Edge e = (Edge) i.next();
            e2 = n1.getEdgeFromNode( e.getFromNode() );
            if ( e2 == null ) {
                lattice.addEdge(e.getFromNode(), n1,
                                e.getAcousticScore(), e.getLMScore());
            } else {
                // if we got here then n1 and n2 had edges from the same node
                // choose the edge with best score
                e2.setAcousticScore
                    (mergeAcousticScores(e.getAcousticScore(),
                                         e2.getAcousticScore()));
                e2.setLMScore(mergeLanguageScores(e.getLMScore(),
                                                  e2.getLMScore()));
            }
        }

        // remove n2 and all associated edges
        lattice.removeNodeAndEdges(n2);
    }

    /**
     * Remove all Nodes that have no Edges to them (but not <s>)
     */
    protected void removeHangingNodes() {
        for (Iterator i = lattice.getCopyOfNodes().iterator(); i.hasNext();) {
            Node n = (Node) i.next();
            if (lattice.hasNode(n)) {
                if (n == lattice.getInitialNode()) {

                } else if (n == lattice.getTerminalNode()) {

                } else {
                    if (n.getLeavingEdges().size() == 0
                        || n.getEnteringEdges().size() == 0) {
                        lattice.removeNodeAndEdges(n);
                        removeHangingNodes();
                        return;
                    }
                }
            }
        }
    }

    /**
     * Provides a single method to merge acoustic scores, so that changes
     * to how acoustic score are merged can be made at one point only.
     *
     * @param score1 the first acoustic score
     * @param score2 the second acoustic score
     *
     * @return the merged acoustic score
     */
    private double mergeAcousticScores(double score1, double score2) {
        // return lattice.getLogMath().addAsLinear(score1, score2);
        return Math.max(score1, score2);
    }

    /**
     * Provides a single method to merge language scores, so that changes
     * to how language score are merged can be made at one point only.
     *
     * @param score1 the first language score
     * @param score2 the second language score
     *
     * @return the merged language score
     */
    private double mergeLanguageScores(double score1, double score2) {
        // return lattice.getLogMath().addAsLinear(score1, score2);
        return Math.max(score1, score2);
    }

    /**
     * Self test for LatticeOptimizer
     *
     * @param args
     */
    public static void main(String[] args) {
        Lattice lattice = new Lattice(args[0]);

        LatticeOptimizer optimizer = new LatticeOptimizer(lattice);

        optimizer.optimize();

        lattice.dump(args[1]);
    }
}