wordpruningbreadthfirstsearchmanager.java

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

    /**
     * Gets the initial grammar node from the linguist and creates a
     * GrammarNodeToken
     */
    protected void localStart() {
        SearchGraph searchGraph = linguist.getSearchGraph();
        currentFrameNumber = 0;
        curTokensScored.value = 0;

        skewMap = new HashMap();
        numStateOrder = searchGraph.getNumStateOrder();
        activeListManager.setNumStateOrder(numStateOrder);
        if (buildWordLattice) {
            loserManager = new AlternateHypothesisManager(maxLatticeEdges);
        }

        SearchState state = searchGraph.getInitialState();

        activeList = activeListManager.getEmittingList();
        activeList.add(new Token(state, currentFrameNumber));
        resultList = new LinkedList();

        bestTokenMap = new HashMap();
        growBranches();
        growNonEmittingLists();
        // tokenTracker.setEnabled(false);
        // tokenTracker.startUtterance();
    }

    /**
     * Local cleanup for this search manager
     */
    protected void localStop() {
        // tokenTracker.stopUtterance();
    }

    /**
     * Goes through the active list of tokens and expands each token, finding
     * the set of successor tokens until all the successor tokens are emitting
     * tokens.
     *  
     */
    protected void growBranches() {
        growTimer.start();
        Iterator iterator = activeList.iterator();
        float relativeBeamThreshold = activeList.getBeamThreshold();
        if (logger.isLoggable(Level.FINE)) {
            logger.fine("Frame: " + currentFrameNumber 
                    + " thresh : " + relativeBeamThreshold + " bs "
                    + activeList.getBestScore() + " tok "
                    + activeList.getBestToken());
        }
        while (iterator.hasNext()) {
            Token token = (Token) iterator.next();
            if (token.getScore() >= relativeBeamThreshold && skewPrune(token)) {
                collectSuccessorTokens(token);
            }
        }
        growTimer.stop();

        // activeListManager.dump();
    }


    /**
     * Grows the emitting branches. This version applies a simple acoustic
     * lookahead based upon the rate of change in the current acoustic score.
     */
    protected void growEmittingBranches() {
        if (acousticLookaheadFrames > 0F) {
            growTimer.start();
            float bestScore = -Float.MAX_VALUE;
            for (Iterator i = activeList.iterator(); i.hasNext();) {
                Token t = (Token) i.next();
                float score = t.getScore() + t.getAcousticScore() 
                            * acousticLookaheadFrames;
                if (score > bestScore) {
                    bestScore = score;
                }
                t.setWorkingScore(score);
            }
            float relativeBeamThreshold = bestScore + relativeBeamWidth;

            for (Iterator i = activeList.iterator(); i.hasNext();) {
                Token t = (Token) i.next();
                if (t.getWorkingScore() >= relativeBeamThreshold) {
                    collectSuccessorTokens(t);
                }
            }
            growTimer.stop();
        } else {
            growBranches();
        }
    }



    /**
     * Grow the non-emitting ActiveLists, until the tokens reach an emitting
     * state.
     */
    private void growNonEmittingLists() {
        for (Iterator i = activeListManager.getNonEmittingListIterator(); i
                .hasNext();) {
            activeList = (ActiveList) i.next();
            if (activeList != null) {
                i.remove();
                pruneBranches();
                growBranches();
            }
        }
    }

    /**
     * Calculate the acoustic scores for the active list. The active list
     * should contain only emitting tokens.
     * 
     * @return <code>true</code> if there are more frames to score,
     *         otherwise, false
     *  
     */
    protected boolean scoreTokens() {
        boolean moreTokens;
        Token bestToken = null;
        scoreTimer.start();
        bestToken = (Token) scorer.calculateScores(activeList.getTokens());
        scoreTimer.stop();

        moreTokens = (bestToken != null);
        activeList.setBestToken(bestToken);

        // monitorWords(activeList);
        monitorStates(activeList);
        if (false) {
            System.out.println("BEST " + bestToken);
        }

        curTokensScored.value += activeList.size();
        totalTokensScored.value += activeList.size();

        return moreTokens;

    }

    /**
     * Keeps track of and reports all of the active word histories for the
     * given active list
     * 
     * @param activeList
     *                the activelist to track
     */
    private void monitorWords(ActiveList activeList) {
        WordTracker tracker = new WordTracker(currentFrameNumber);

        for (Iterator i = activeList.iterator(); i.hasNext();) {
            Token t = (Token) i.next();
            tracker.add(t);
        }
        tracker.dump();
    }

    /**
     * Keeps track of and reports statistics about the number of active states
     * 
     * @param activeList
     *                the active list of states
     */
    private void monitorStates(ActiveList activeList) {

        tokenSum += activeList.size();
        tokenCount++;

        if ((tokenCount % 1000) == 0) {
            logger.info("Average Tokens/State: " + (tokenSum / tokenCount));
        }
    }

    /**
     * Removes unpromising branches from the active list
     *  
     */
    protected void pruneBranches() {
        pruneTimer.start();
        activeList = pruner.prune(activeList);
        pruneTimer.stop();
    }

    /**
     * Gets the best token for this state
     * 
     * @param state
     *                the state of interest
     * 
     * @return the best token
     */
    protected Token getBestToken(SearchState state) {
        Object key = getStateKey(state);

        if (!wantTokenStacks) {
            return (Token) bestTokenMap.get(key);
        } else {
            // new way... if the heap for this state isn't full return
            // null, otherwise return the worst scoring token
            TokenHeap th = (TokenHeap) bestTokenMap.get(key);
            Token t;

            if (th == null) {
                return null;
            } else if ((t = th.get(state)) != null) {
                return t;
            } else if (!th.isFull()) {
                return null;
            } else {
                return th.getSmallest();
            }
        }
    }

    /**
     * Sets the best token for a given state
     * 
     * @param token
     *                the best token
     * 
     * @param state
     *                the state
     * 
     */
    protected void setBestToken(Token token, SearchState state) {
        Object key = getStateKey(state);
        if (!wantTokenStacks) {
            bestTokenMap.put(key, token);
        } else {
            TokenHeap th = (TokenHeap) bestTokenMap.get(key);
            if (th == null) {
                th = new TokenHeap(maxTokenHeapSize);
                bestTokenMap.put(key, th);
            }
            th.add(token);
        }
    }

    /**
     * Find the best token to use as a predecessor token given a candidate
     * predecessor. The predecessor is the most recent word token unless
     * keepAllTokens is set, in which case, the predecessor is always the
     * candidate predecessor.
     * 
     * @param token
     *                the token of interest
     * 
     * @return the immediate successor word token
     */
    protected Token getWordPredecessor(Token token) {
        if (keepAllTokens) {
            return token;
        } else {
            float logAcousticScore = 0.0f;
            float logLanguageScore = 0.0f;

            while (token != null && !token.isWord()) {
                logAcousticScore += token.getAcousticScore();
                logLanguageScore += token.getLanguageScore();
                token = token.getPredecessor();
            }
            if (buildWordLattice) {
                return new Token(logAcousticScore, logLanguageScore, token);
            } else {
                return token;
            }
        }
    }

    /**
     * Returns the state key for the given state. If we are using token stacks
     * then the key will be related to the search state and the word history
     * (depending on the type of token stacks), otherwise, the key will simply
     * be the state itself. Currently we are not using token stacks so the
     * state is the key.
     * 
     * @param state
     *                the state to get the key for
     * 
     * @return the key for the given state
     */
    private Object getStateKey(SearchState state) {
        if (!wantTokenStacks) {
            return state;
        } else {
            if (state.isEmitting()) {
                return new SinglePathThroughHMMKey(((HMMSearchState) state));
                // return ((HMMSearchState) state).getHMMState().getHMM();
            } else {
                return state;
            }
        }
    }

    /**
     * Checks that the given two states are in legitimate order.
     */
    private void checkStateOrder(SearchState fromState, SearchState toState) {
        if (fromState.getOrder() == numStateOrder - 1) {
            return;
        }

        if (fromState.getOrder() > toState.getOrder()) {
            throw new Error("IllegalState order: from "
                    + fromState.getClass().getName() + " "
                    + fromState.toPrettyString() 
                    + " order: " + fromState.getOrder() 
                    + " to "
                    + toState.getClass().getName() + " "
                    + toState.toPrettyString()
                    + " order: " + toState.getOrder());
        }
    }

    /**
     * Collects the next set of emitting tokens from a token and accumulates
     * them in the active or result lists
     * 
     * @param token
     *                the token to collect successors from be immediately
     *                expaned are placed. Null if we should always expand all
     *                nodes.
     *  
     */
    protected void collectSuccessorTokens(Token token) {

        // tokenTracker.add(token);
        // tokenTypeTracker.add(token);

        // If this is a final state, add it to the final list

        if (token.isFinal()) {
            resultList.add(getWordPredecessor(token));
            return;
        }

        // if this is a non-emitting token and we've already 
        // visited the same state during this frame, then we
        // are in a grammar loop, so we don't continue to expand.
        // This check only works properly if we have kept all of the
        // tokens (instead of skipping the non-word tokens).
        // Note that certain linguists will never generate grammar loops
        // (lextree linguist for example). For these cases, it is perfectly
        // fine to disable this check by setting keepAllTokens to false

        if (!token.isEmitting() && (keepAllTokens && isVisited(token))) {
            return;
        }

        SearchState state = token.getSearchState();
        SearchStateArc[] arcs = state.getSuccessors();
        Token predecessor = getWordPredecessor(token);

        // For each successor
        // calculate the entry score for the token based upon the
        // predecessor token score and the transition probabilities
        // if the score is better than the best score encountered for
        // the SearchState and frame then create a new token, add
        // it to the lattice and the SearchState.
        // If the token is an emitting token add it to the list,
        // othewise recursively collect the new tokens successors.

        for (int i = 0; i < arcs.length; i++) {
            SearchStateArc arc = arcs[i];
            SearchState nextState = arc.getState();

            if (checkStateOrder) {
                checkStateOrder(state, nextState);
            }

            // We're actually multiplying the variables, but since
            // these come in log(), multiply gets converted to add
            float logEntryScore = token.getScore() + arc.getProbability();

            Token bestToken = getBestToken(nextState);
            boolean firstToken = bestToken == null;

            if (firstToken || bestToken.getScore() < logEntryScore) {
                Token newBestToken = new Token(predecessor, nextState,
                        logEntryScore, arc.getLanguageProbability(), arc
                                .getInsertionProbability(), currentFrameNumber);
                tokensCreated.value++;

                setBestToken(newBestToken, nextState);
                if (firstToken) {
                    activeListAdd(newBestToken);
                } else {
                    if (false) {
                        System.out.println("Replacing " + bestToken + " with "
                                + newBestToken);
                    }
                    activeListReplace(bestToken, newBestToken);
                    if (buildWordLattice && newBestToken.isWord()) {

                        // Move predecessors of bestToken to precede
                        // newBestToken, bestToken will be garbage collected.
                        loserManager.changeSuccessor(newBestToken, bestToken);
                        loserManager.addAlternatePredecessor(newBestToken,
                                bestToken.getPredecessor());
                    }
                }
            } else {
                if (buildWordLattice && nextState instanceof WordSearchState) {
                    if (predecessor != null) {
                        loserManager.addAlternatePredecessor(bestToken,
                                predecessor);
                    }
                }
            }
        }
    }

    /**
     * Determines whether or not we've visited the state associated with this
     * token since the previous frame.
     *
     * @return true if we've visted the search state since the last frame