lattice.java

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

    /**
     * @return Returns the logMath object used in this lattice.
     */
    public LogMath getLogMath() {
        return logMath;
    }

    /**
     * Sets the LogMath to use.
     *
     * @param logMath the LogMath to use
     */
    public void setLogMath(LogMath logMath) {
        this.logMath = logMath;
    }
    
    /**
     * Dump all paths through this Lattice.  Used for debugging.
     */
    public void dumpAllPaths() {
        for (Iterator i = allPaths().iterator(); i.hasNext();) {
            System.out.println(i.next());
        }
    }

    /**
     * Generate a List of all paths through this Lattice.
     *
     * @return a lists of lists of Nodes
     */
    public List allPaths() {
        return allPathsFrom("", initialNode);
    }

    /**
     * Internal routine used to generate all paths starting at a given node.
     *
     * @param path
     * @param n
     * @return a list of lists of Nodes
     */
    protected List allPathsFrom(String path, Node n) {
        String p = path + " " + n.getWord();
        List l = new LinkedList();
        if (n == terminalNode) {
            l.add(p);
        } else {
            for (Iterator i = n.getLeavingEdges().iterator(); i.hasNext();) {
                Edge e = (Edge) i.next();
                l.addAll(allPathsFrom(p, e.getToNode()));
            }
        }
        return l;
    }
    
    boolean checkConsistency() {
        for (Iterator i = nodes.values().iterator(); i.hasNext();) {
            Node n = (Node) i.next();
            for (Iterator j = n.getEnteringEdges().iterator(); j.hasNext();) {
                Edge e = (Edge) j.next();
                if (!hasEdge(e)) {
                    throw new Error("Lattice has NODE with missing FROM edge: "
                                    + n + "," + e);
                }
            }
            for (Iterator j = n.getLeavingEdges().iterator(); j.hasNext();) {
                Edge e = (Edge) j.next();
                if (!hasEdge(e)) {
                    throw new Error("Lattice has NODE with missing TO edge: " +
                                    n + "," + e);
                }
            }
        }
        for (Iterator i = edges.iterator(); i.hasNext();) {
            Edge e = (Edge) i.next();
            if (!hasNode(e.getFromNode())) {
                throw new Error("Lattice has EDGE with missing FROM node: " +
                                e);
            }
            if (!hasNode(e.getToNode())) {
                throw new Error("Lattice has EDGE with missing TO node: " + e);
            }
            if(!e.getToNode().hasEdgeFromNode(e.getFromNode())) {
                throw new Error("Lattice has EDGE with TO node with no corresponding FROM edge: " + e);
            }
            if(!e.getFromNode().hasEdgeToNode(e.getToNode())) {
                throw new Error("Lattice has EDGE with FROM node with no corresponding TO edge: " + e);
            }
        }
        return true;
    }

    protected void sortHelper(Node n, List sorted, Set visited) {
        if (visited.contains(n)) {
            return;
        }
        visited.add(n);
        if (n == null) {
            throw new Error("Node is null");
        }
        Iterator e = n.getLeavingEdges().iterator();
        while (e.hasNext()) {
            sortHelper(((Edge)e.next()).getToNode(),sorted,visited);
        }
        sorted.add(n);
    }
    
    /**
     * Topologically sort the nodes in this lattice.
     * 
     * @return Topologically sorted list of nodes in this lattice.
     */
    public List sortNodes() {
        Vector sorted = new Vector(nodes.size());
        sortHelper(initialNode,sorted,new HashSet());
        Collections.reverse(sorted);
        return sorted;
    }
    
    
    /**
     * Compute the utterance-level posterior for every node in the lattice, 
     * i.e. the probability that this node occurs on any path through the 
     * lattice. Uses a forward-backward algorithm specific to the nature of
     * non-looping left-to-right lattice structures.
     * 
     * Node posteriors can be retrieved by calling getPosterior() on Node 
     * objects.
     * 
     * @param languageModelWeight the language model weight that was used
     *        in generating the scores in the lattice
     */
    public void computeNodePosteriors(float languageModelWeight) {
        computeNodePosteriors(languageModelWeight, false);
    }


    /**
     * Compute the utterance-level posterior for every node in the lattice, 
     * i.e. the probability that this node occurs on any path through the 
     * lattice. Uses a forward-backward algorithm specific to the nature of
     * non-looping left-to-right lattice structures.
     * 
     * Node posteriors can be retrieved by calling getPosterior() on Node 
     * objects.
     * 
     * @param languageModelWeight the language model weight that was used
     *        in generating the scores in the lattice
     * @param useAcousticScoresOnly use only the acoustic scores to compute
     *               the posteriors, ignore the language weight and scores
     */
    public void computeNodePosteriors(float languageModelWeight,
                                      boolean useAcousticScoresOnly) {      
        //forward
        initialNode.setForwardScore(LogMath.getLogOne());
        List sortedNodes = sortNodes();
        assert sortedNodes.get(0) == initialNode;
        ListIterator n = sortedNodes.listIterator();
        while (n.hasNext()) {            
            Node currentNode = (Node)n.next();
            Collection currentEdges = currentNode.getLeavingEdges();
            for (Iterator i = currentEdges.iterator();i.hasNext();) {
                Edge edge = (Edge)i.next();
                double forwardProb = edge.getFromNode().getForwardScore();
                forwardProb += computeEdgeScore
                    (edge, languageModelWeight, useAcousticScoresOnly);
                edge.getToNode().setForwardScore
                    (logMath.addAsLinear
                     ((float)forwardProb,
                      (float)edge.getToNode().getForwardScore()));
            }
        }
        
        //backward
        terminalNode.setBackwardScore(LogMath.getLogOne());
        assert sortedNodes.get(sortedNodes.size()-1) == terminalNode;
        n = sortedNodes.listIterator(sortedNodes.size()-1);
        while (n.hasPrevious()) {            
            Node currentNode = (Node)n.previous();
            Collection currentEdges = currentNode.getLeavingEdges();
            for (Iterator i = currentEdges.iterator();i.hasNext();) {
                Edge edge = (Edge)i.next();
                double backwardProb = edge.getToNode().getBackwardScore();
                backwardProb += computeEdgeScore
                    (edge, languageModelWeight, useAcousticScoresOnly);
                edge.getFromNode().setBackwardScore
                    (logMath.addAsLinear((float)backwardProb,
                        (float)edge.getFromNode().getBackwardScore()));
            }
        }
        
        //inner
        double normalizationFactor = terminalNode.getForwardScore();
        for(Iterator i=nodes.values().iterator();i.hasNext();) {
            Node node = (Node)i.next();
            node.setPosterior((node.getForwardScore() + 
                               node.getBackwardScore()) - normalizationFactor);
        }
    }


    /**
     * Computes the score of an edge.
     *
     * @param edge the edge which score we want to compute
     * @param languageModelWeight the language model weight to use
     *
     * @return the score of an edge
     */
    private double computeEdgeScore(Edge edge, float languageModelWeight,
                                    boolean useAcousticScoresOnly) {
        if (useAcousticScoresOnly) {
            return edge.getAcousticScore();
        } else {
            return (edge.getAcousticScore() + edge.getLMScore())/languageModelWeight;
        }
    }


    /**
     * Returns true if the given Lattice is equivalent to this Lattice.
     * Two lattices are equivalent if all their nodes and edges are
     * equivalent.
     *
     * @param other the Lattice to compare this Lattice against
     *
     * @return true if the Lattices are equivalent; false otherwise
     */
    public boolean isEquivalent(Lattice other) {
        return checkNodesEquivalent(initialNode, other.getInitialNode());
    }

    
    /**
     * Returns true if the two lattices starting at the given two nodes
     * are equivalent. It recursively checks all the child nodes until
     * these two nodes until there are no more child nodes.
     *
     * @param n1 starting node of the first lattice
     * @param n2 starting node of the second lattice
     *
     * @return true if the two lattices are equivalent
     */
    private boolean checkNodesEquivalent(Node n1, Node n2) {
        assert n1 != null && n2 != null;

        boolean equivalent = n1.isEquivalent(n2);
        if (equivalent) {
            Collection leavingEdges = n1.getCopyOfLeavingEdges();
            Collection leavingEdges2 = n2.getCopyOfLeavingEdges();

            System.out.println("# edges: " + leavingEdges.size() + " " + 
                               leavingEdges2.size());

            for (Iterator i = leavingEdges.iterator(); i.hasNext(); ) {
                
                Edge edge = (Edge) i.next();
                
                /* find an equivalent edge from n2 for this edge */
                Edge e2 = n2.findEquivalentLeavingEdge(edge);
                
                if (e2 == null) {
                    System.out.println
                        ("Equivalent edge not found, lattices not equivalent.");
                    return false;
                } else {
                    if (!leavingEdges2.remove(e2)) {
                        /*
                         * if it cannot be removed, then the leaving edges
                         * are not the same
                         */
                        System.out.println
                            ("Equivalent edge already matched, lattices not equivalent.");
                        return false;
                    } else {
                        /* recursively check the two child nodes */
                        equivalent &= checkNodesEquivalent
                            (edge.getToNode(), e2.getToNode());
                        if (equivalent == false) {
                            return false;
                        }
                    }
                }
            }
            if (leavingEdges2.size() != 0) {
                System.out.println("One lattice has too many edges.");
                return false;
            }
        }
        return equivalent;
    }

     
    /**
     * Self test for Lattices.  Test loading, saving, dynamically creating
     * and optimizing Lattices
     *
     * @param args
     */
    public static void main(String[] args) {

        Lattice lattice = null;

        if (args.length > 0) {
            System.err.println("Loading lattice from " + args[0]);
            lattice = new Lattice(args[0]);
        } else {
            System.err.println("Building test Lattice");

            lattice = new Lattice();

            /*
            1 --> 2 -
            /         \
            0 --> 1 --> 4
            \     \   /
            2 --> 3 -
            */

            Node n0 = lattice.addNode("0", "0", 0, 0);
            Node n1 = lattice.addNode("1", "1", 0, 0);
            Node n1a = lattice.addNode("1a", "1", 0, 0);
            Node n2 = lattice.addNode("2", "2", 0, 0);
            Node n2a = lattice.addNode("2a", "2", 0, 0);
            Node n3 = lattice.addNode("3", "3", 0, 0);
            Node n4 = lattice.addNode("4", "4", 0, 0);

            Edge e01 = lattice.addEdge(n0, n1, -1, 0);
            Edge e01a = lattice.addEdge(n0, n1a, -1, 0);
            Edge e14 = lattice.addEdge(n1, n4, -1, 0);
            Edge e1a2a = lattice.addEdge(n1a, n2a, -1, 0);
            Edge e2a4 = lattice.addEdge(n2a, n4, -1, 0);
            Edge e02 = lattice.addEdge(n0, n2, -1, 0);
            Edge e23 = lattice.addEdge(n2, n3, -1, 0);
            Edge e13 = lattice.addEdge(n1, n3, -1, 0);
            Edge e34 = lattice.addEdge(n3, n4, -1, 0);

            lattice.setInitialNode(n0);
            lattice.setTerminalNode(n4);
        }

        System.err.println("Lattice has " + lattice.getNodes().size() + " nodes and " + lattice.getEdges().size() + " edges");

        System.err.println("Testing Save/Load .LAT file");
        lattice.dump("test.lat");

        lattice.dumpAllPaths();

        LatticeOptimizer lo = new LatticeOptimizer(lattice);
        lo.optimize();

        /*
        2
        /   \
        0 --> 1 --> 4
        \     \   /
        2 -->  3
        */

        lattice.dumpAllPaths();
    }
}