ime/src/lattice_states.h

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright (c) 2007 Sun Microsystems, Inc. All Rights Reserved.
 *
 * The contents of this file are subject to the terms of either the GNU Lesser
 * General Public License Version 2.1 only ("LGPL") or the Common Development and
 * Distribution License ("CDDL")(collectively, the "License"). You may not use this
 * file except in compliance with the License. You can obtain a copy of the CDDL at
 * http://www.opensource.org/licenses/cddl1.php and a copy of the LGPLv2.1 at
 * http://www.opensource.org/licenses/lgpl-license.php. See the License for the
 * specific language governing permissions and limitations under the License. When
 * distributing the software, include this License Header Notice in each file and
 * include the full text of the License in the License file as well as the
 * following notice:
 *
 * NOTICE PURSUANT TO SECTION 9 OF THE COMMON DEVELOPMENT AND DISTRIBUTION LICENSE
 * (CDDL)
 * For Covered Software in this distribution, this License shall be governed by the
 * laws of the State of California (excluding conflict-of-law provisions).
 * Any litigation relating to this License shall be subject to the jurisdiction of
 * the Federal Courts of the Northern District of California and the state courts
 * of the State of California, with venue lying in Santa Clara County, California.
 *
 * Contributor(s):
 *
 * If you wish your version of this file to be governed by only the CDDL or only
 * the LGPL Version 2.1, indicate your decision by adding "[Contributor]" elects to
 * include this software in this distribution under the [CDDL or LGPL Version 2.1]
 * license." If you don't indicate a single choice of license, a recipient has the
 * option to distribute your version of this file under either the CDDL or the LGPL
 * Version 2.1, or to extend the choice of license to its licensees as provided
 * above. However, if you add LGPL Version 2.1 code and therefore, elected the LGPL
 * Version 2 license, then the option applies only if the new code is made subject
 * to such option by the copyright holder.
 */

#ifndef SUNPY_LATTICE_STATES_H
#define SUNPY_LATTICE_STATES_H

#include "portability.h"

#include "imi_context.h"

/**
 * CStateKey represent the history. In real implementation, it's a
 * node pointer to a state in the language model. But to save the
 * language model size, the state node in language model do not
 * thread the back-off pointer. Now, we just use the Word Id for
 * the node in the language model. Later we should abstract the
 * StateNode from language model implemetation to replace this
 * definition.
 */
typedef CThreadSlm::TState          CStateKey;

/**
 * A WordKey could represent a word. Define this use the unsigned int
 * directly. Because in the future, we may adopt word class, such as
 * Digital Word Class.
 */
typedef unsigned                    CWordKey;

/**
 * This class is used to record lexicon state (pinyin trie nodes)
 * just before a bone. From the bone, it could see when arriving
 * it, how many valid Pinyin Trie Node still could be used to search
 * more words further, and what bone is its starting bone.
 */
struct CLexiconState {
public:
    /**
     * The bone where m_pPYNode starts
     */
    CSkeletonIter                   m_BoneStart;

    /**
     * PinYin trie node, from which we could get its corresponding
     * words (if it contains some), and search further for longer
     * words.
     */
    const CPinyinTrie::TNode       *m_pPYNode;

    /**
     * If is not a PINYIN state, we should use the m_WordId directly.
     */
    bool                            m_bPinyin;

    /**
     * the word id for normal string, like english string, punc, etc.
     */
    unsigned int                    m_WordId;

public:
    CLexiconState(const CLexiconState& b)
        : m_BoneStart(b.m_BoneStart), m_pPYNode(b.m_pPYNode),
          m_bPinyin(b.m_bPinyin), m_WordId(b.m_WordId) { }

    CLexiconState(CSkeletonIter boneStart = CSkeletonIter(),
                  const CPinyinTrie::TNode *pynptr = NULL)
        : m_BoneStart(boneStart), m_pPYNode(pynptr),
          m_bPinyin(true), m_WordId(0) { }

    CLexiconState(CSkeletonIter boneStart, unsigned int wid)
        : m_BoneStart(boneStart), m_pPYNode(NULL),
          m_bPinyin(false), m_WordId(wid) { }
};

/**
 * A list of Lexicon State. Every state may from different
 * starting position. Later, when Fuzzy PinYin are added,
 * more than one state may comes from one starting bone.
 */
typedef std::vector<CLexiconState>    CLexiconStates;


/**
 * The basic static unit used in the lattice searching
 */
struct TLatticeState {
public:

    /**
     * The score from the beginning of the sentence to here
     * pr(w1)*pr(w2|w1)*... or its log format
     */
    TSentenceScore                  m_Score;

    /**
     * The bone right after this lattice node.
     */
    CSkeletonIter                   m_BoneAfter;

    /**
     * The history key
     */
    CStateKey                       m_State;

    /**
     * prevState --- word ---> thisState
     * BackTraceNode record the best prevState that make thisState
     * best score.
     */
    TLatticeState                  *m_pBackTraceNode;

    /**
     * BackTraceWordId record the best word's id that make thisState
     * best score
     */
    CWordKey                        m_BackTraceWordId;

    /** for debug printing... */
    void
    print(std::string& prefix);

public:
    /**
     * Default constructor
     */
    #ifdef _USE_RAW_PROBABILITY
    TLatticeState(double score = -1.0,
    #else
    TLatticeState(double score = 0.0,
    #endif
                  CSkeletonIter bone=CSkeletonIter(),
                  TLatticeState* btNodePtr = NULL,
                  CStateKey sk= CStateKey(),
                  CWordKey wk = CWordKey())
        : m_Score(score), m_BoneAfter(bone), m_State(sk),
          m_pBackTraceNode(btNodePtr), m_BackTraceWordId(wk) { }

};

typedef std::vector<TLatticeState>  CLatticeStateVec;


/**
 * All lattice node before a single bone. This class provide beam pruning
 * while push_back, which means at most the best MAX states are reserved,
 * ie, weak state will may be discard while new better state are inserted,
 * and the number MAX is arrived.
 */
class CLatticeStates {
private:
    static const unsigned beam_width = 32;

public:
    /** just use the CLatticeStateVec's iterator */
    typedef CLatticeStateVec::iterator        iterator;

    /** just use the CLatticeStateVec's iterator */
    typedef CLatticeStateVec::const_iterator  const_iterator;

public:
    void
    clear();

    void
    push_back(const TLatticeState& node);

    //@{
    /** return the first iterator of m_Vec. */
    size_t
    size()
        { return m_Vec.size(); }

    iterator
    begin()
        { return m_Vec.begin(); }

    /** return the first iterator of m_Vec. */
    const_iterator
    begin() const
        { return m_Vec.begin(); }
    //@}


    //@{
    /** return the last iterator of m_Vec. */
    iterator
    end()
        { return m_Vec.end(); }

    /** return the last iterator of m_Vec. */
    const_iterator
    end() const
        { return m_Vec.end(); }
    //@}


protected:
    void
    bubbleUp(int idxInHeap);

    void
    ironDown(int idxInHeap);

protected:
    std::vector<TLatticeState>      m_Vec;
    std::vector<int>                m_VecIdxInHeap;
    std::map<CStateKey, int>        m_Map;
    std::vector<int>                m_Heap;
};


/**
 * Bone Inner Data is used to construct the search lattice. Logically,
 * each bone just like the time fram as in the speech recoginition.
 * Many information when searching arrived right before the bone are needed.
 *    - The Pinyin Trie States start from previous bones, and not terminated
 *      yet. From these states, we could look further to find longer words.
 *    - All Lattice State (which is already after beam-pruning). They are
 *      basic units of the Lattice.
 * Any other information also needed to help the interaction with user:
 *    - Best word start righ from the bone. A best word in the best
 *      sentence is an edge of the best path.
 *    - Best word type.
 *       -# Whether there is a best word start right before the bone? Best
 *          words are not overlaped and many bones may contains no best word.
 *       -# Whether the best word is user-selected. Some best word is user
 *          selected, and may be really diffirent with what we found according
 *          to Language Model.
 */
class CBoneInnerData {
public:
    /** values used by m_BWType to reflect the m_BestWord status */
    enum {
        NoBestWordStartHere, /**< best word not start here. m_bestWod invalid.*/
        BestWordStartHere, /**< m_BestWord is valid, but not user selected.*/
        UserSelectedBestWord /**< m_BestWord is the user selected best word.*/
    };

    /**
     * The best word start from here. A best word in the best sentence is
     * an edge of the best path.
     */
    CCandidate                      m_BestWord;

    /**
     * m_BWType reflects the m_BestWord status:
     *    -# Is there a best word start here?
     *    -# Whether or not it is user selected?
     */
    int                             m_BWType;

    /**
     * Lexicon status list just before this bone.
     */
    CLexiconStates                  m_LexiconStates;

    /**
     * Lattice status list just before this bone.
     */
    CLatticeStates                  m_LatticeNodes;

public:
    CBoneInnerData()
        : m_BestWord(), m_BWType(NoBestWordStartHere),
          m_LexiconStates(), m_LatticeNodes() { }
    /**
     * clear LatticeNodes and LexiconStates,
     * set the BWType to NoBestWordStartHere.
     */
    void
    clear()
        {
            m_BWType = NoBestWordStartHere;
            m_LatticeNodes.clear();
            m_LexiconStates.clear();
        }

    void
    print(std::string& prefix);
};


#endif