← Back to branch summary

~ubuntu-branches/ubuntu/trusty/sunpinyin/trusty-proposed

« back to all changes in this revision

Viewing changes to src/ime-core/lattice_states.h

  • Committer: Package Import Robot
  • Author(s): YunQiang Su
  • Date: 2012-03-30 15:31:55 UTC
  • mfrom: (1.1.2)
  • Revision ID: package-import@ubuntu.com-20120330153155-ep92npxp3mucniyt
Tags: 2.0.3+git20120222-1
* Team upload: git snapshot 20120222.
   - fix breaks if LDFLAGS in environment contains
       multiple words (Closese #646001).
   - rm patches merged to upstream:
       append-os-environ-toenv.patch
       fix-ftbfs-on-sh.patch
       remove-10-candidate-words-limitation.patch
   - refresh disable-lm-dict-compile.patch.
* Bump stardard version to 3.9.3: no modify needed.
* add libsunpinyin3-dbg and python-sunpinyin packages.
* debian/compat to 9, multiarch it.
* rewrite debian/rules with dh 7 format.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/ime-core/lattice_states.h
1
1
/*
2
2
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3
 
 * 
 
3
 *
4
4
 * Copyright (c) 2007 Sun Microsystems, Inc. All Rights Reserved.
5
 
 * 
 
5
 *
6
6
 * The contents of this file are subject to the terms of either the GNU Lesser
7
7
 * General Public License Version 2.1 only ("LGPL") or the Common Development and
8
8
 * Distribution License ("CDDL")(collectively, the "License"). You may not use this
9
9
 * file except in compliance with the License. You can obtain a copy of the CDDL at
10
10
 * http://www.opensource.org/licenses/cddl1.php and a copy of the LGPLv2.1 at
11
 
 * http://www.opensource.org/licenses/lgpl-license.php. See the License for the 
 
11
 * http://www.opensource.org/licenses/lgpl-license.php. See the License for the
12
12
 * specific language governing permissions and limitations under the License. When
13
13
 * distributing the software, include this License Header Notice in each file and
14
14
 * include the full text of the License in the License file as well as the
15
15
 * following notice:
16
 
 * 
 
16
 *
17
17
 * NOTICE PURSUANT TO SECTION 9 OF THE COMMON DEVELOPMENT AND DISTRIBUTION LICENSE
18
18
 * (CDDL)
19
19
 * For Covered Software in this distribution, this License shall be governed by the
21
21
 * Any litigation relating to this License shall be subject to the jurisdiction of
22
22
 * the Federal Courts of the Northern District of California and the state courts
23
23
 * of the State of California, with venue lying in Santa Clara County, California.
24
 
 * 
 
24
 *
25
25
 * Contributor(s):
26
 
 * 
 
26
 *
27
27
 * If you wish your version of this file to be governed by only the CDDL or only
28
28
 * the LGPL Version 2.1, indicate your decision by adding "[Contributor]" elects to
29
29
 * include this software in this distribution under the [CDDL or LGPL Version 2.1]
32
32
 * Version 2.1, or to extend the choice of license to its licensees as provided
33
33
 * above. However, if you add LGPL Version 2.1 code and therefore, elected the LGPL
34
34
 * Version 2 license, then the option applies only if the new code is made subject
35
 
 * to such option by the copyright holder. 
 
35
 * to such option by the copyright holder.
36
36
 */
37
37
 
38
38
#ifndef SUNPY_LATTICE_STATES_H
55
55
 * StateNode from language model implemetation to replace this
56
56
 * definition.
57
57
 */
58
 
typedef CThreadSlm::TState          CSlmState;
 
58
typedef CThreadSlm::TState CSlmState;
59
59
 
60
60
/**
61
61
 * A WordKey could represent a word. Define this use the unsigned int
62
62
 * directly. Because in the future, we may adopt word class, such as
63
63
 * Digital Word Class.
64
64
 */
65
 
typedef unsigned                    CWordId;
 
65
typedef unsigned CWordId;
66
66
 
67
67
/**
68
68
 * This class is used to record lexicon state (pinyin trie nodes)
74
74
    typedef std::vector<CPinyinTrie::TWordIdInfo> TWordIdInfoVec;
75
75
 
76
76
    const CPinyinTrie::TNode   *m_pPYNode;
77
 
    TWordIdInfoVec              m_words;
78
 
    CSyllables                  m_syls;         // accumulated syllables, may contain fuzzy syllables
79
 
    std::vector<unsigned>       m_seg_path;     // accumulated segments,  may contain fuzzy segments
80
 
    unsigned                    m_start                 :16;
81
 
    unsigned                    m_num_of_inner_fuzzies  :14;
82
 
    bool                        m_bFuzzy                :1;
83
 
    bool                        m_bPinyin               :1;
84
 
 
85
 
    TLexiconState (unsigned start, const CPinyinTrie::TNode *pnode, CSyllables& syls, std::vector<unsigned>& seg_path, bool fuzzy=false):
86
 
        m_start(start), m_pPYNode(pnode), m_syls(syls), m_seg_path(seg_path), m_bPinyin(true), m_bFuzzy(fuzzy), m_num_of_inner_fuzzies(0) {}
87
 
 
88
 
    TLexiconState (unsigned start, TWordIdInfoVec &words, CSyllables &syls, std::vector<unsigned>& seg_path, bool fuzzy=false):
89
 
        m_start(start), m_pPYNode(NULL), m_words(words), m_syls(syls), m_seg_path(seg_path), m_bPinyin(true), m_bFuzzy(fuzzy), m_num_of_inner_fuzzies(0) {}
90
 
 
91
 
    TLexiconState (unsigned start, unsigned wid):
92
 
        m_start(start), m_pPYNode(NULL), m_bPinyin(false)
93
 
        {
94
 
            m_words.push_back(wid);
95
 
            m_seg_path.push_back (start);
96
 
            m_seg_path.push_back (start+1);
97
 
        }
98
 
 
99
 
    const CPinyinTrie::TWordIdInfo *getWords (unsigned &num);
100
 
    void print (std::string prefix) const;
 
77
    TWordIdInfoVec m_words;
 
78
    // accumulated syllables, may contain fuzzy syllables
 
79
    CSyllables m_syls;
 
80
    // accumulated segments,  may contain fuzzy segments
 
81
    std::vector<unsigned> m_seg_path;
 
82
 
 
83
    unsigned m_start                 : 16;
 
84
    unsigned m_num_of_inner_fuzzies  : 14;
 
85
    bool m_bFuzzy                : 1;
 
86
    bool m_bPinyin               : 1;
 
87
 
 
88
    TLexiconState (unsigned start,
 
89
                   const CPinyinTrie::TNode *pnode,
 
90
                   CSyllables& syls,
 
91
                   std::vector<unsigned>& seg_path,
 
92
                   bool fuzzy = false)
 
93
    : m_pPYNode(pnode), m_syls(syls), m_seg_path(seg_path), m_start(start),
 
94
        m_num_of_inner_fuzzies(0), m_bFuzzy(fuzzy), m_bPinyin(true) {}
 
95
 
 
96
    TLexiconState (unsigned start,
 
97
                   TWordIdInfoVec &words,
 
98
                   CSyllables &syls,
 
99
                   std::vector<unsigned>& seg_path,
 
100
                   bool fuzzy = false)
 
101
    : m_pPYNode(NULL), m_words(words), m_syls(syls), m_seg_path(seg_path),
 
102
        m_start(start), m_num_of_inner_fuzzies(0), m_bFuzzy(fuzzy),
 
103
        m_bPinyin(true) {}
 
104
 
 
105
    TLexiconState (unsigned start, unsigned wid)
 
106
    : m_pPYNode(NULL), m_start(start), m_bPinyin(false) {
 
107
        m_words.push_back(wid);
 
108
        m_seg_path.push_back(start);
 
109
        m_seg_path.push_back(start + 1);
 
110
    }
 
111
 
 
112
    const CPinyinTrie::TWordIdInfo *getWords(unsigned &num);
 
113
    void print(std::string prefix) const;
101
114
};
102
115
 
103
116
/**
112
125
 * The basic static unit used in the lattice searching
113
126
 */
114
127
struct TLatticeState {
115
 
    TSentenceScore      m_score;
116
 
    unsigned            m_frIdx;
117
 
    TLexiconState      *m_pLexiconState;
118
 
    TLatticeState      *m_pBackTraceNode;
119
 
    CSlmState           m_slmState;
120
 
    CWordId             m_backTraceWordId;
121
 
    
 
128
    TSentenceScore m_score;
 
129
    unsigned m_frIdx;
 
130
    TLexiconState* m_pLexiconState;
 
131
    TLatticeState* m_pBackTraceNode;
 
132
    CSlmState m_slmState;
 
133
    CWordId m_backTraceWordId;
 
134
 
122
135
    TLatticeState(double score = -1.0,
123
 
                  unsigned frIdx=0,
 
136
                  unsigned frIdx = 0,
124
137
                  TLexiconState* lxstPtr = NULL,
125
138
                  TLatticeState* btNodePtr = NULL,
126
 
                  CSlmState sk= CSlmState(),
 
139
                  CSlmState sk = CSlmState(),
127
140
                  CWordId wk = CWordId())
128
 
        : m_score(score), m_frIdx(frIdx), m_pBackTraceNode(btNodePtr),
129
 
          m_pLexiconState(lxstPtr), m_slmState(sk), m_backTraceWordId(wk) {}
 
141
    : m_score(score), m_frIdx(frIdx), m_pLexiconState(lxstPtr),
 
142
        m_pBackTraceNode(btNodePtr), m_slmState(sk), m_backTraceWordId(wk) {}
130
143
 
131
144
    /** for debug printing... */
132
 
    void
133
 
    print(std::string prefix) const;
 
145
    void print(std::string prefix) const;
 
146
 
 
147
    bool operator<(const TLatticeState& rhs) const {
 
148
        return m_score < rhs.m_score;
 
149
    }
 
150
 
 
151
    bool operator==(const TLatticeState& rhs) const {
 
152
        return m_score == rhs.m_score;
 
153
    }
 
154
 
 
155
    bool operator>(const TLatticeState& rhs) const {
 
156
        return !((*this) < rhs || (*this) == rhs);
 
157
    }
134
158
};
135
159
 
136
160
typedef std::vector<TLatticeState>  CLatticeStateVec;
137
161
 
138
162
/**
 
163
 * A container that keeps the top K elements.
 
164
 */
 
165
class CTopLatticeStates {
 
166
    std::vector<TLatticeState> m_heap;
 
167
    size_t m_threshold;
 
168
public:
 
169
    CTopLatticeStates(size_t threshold) : m_threshold(threshold) {}
 
170
 
 
171
    bool push(const TLatticeState& state);
 
172
    void pop();
 
173
 
 
174
    const TLatticeState& top() const { return m_heap[0]; }
 
175
 
 
176
    size_t size() const { return m_heap.size(); }
 
177
 
 
178
    typedef std::vector<TLatticeState>::iterator iterator;
 
179
 
 
180
    iterator begin() { return m_heap.begin(); }
 
181
    iterator end() { return m_heap.end(); }
 
182
};
 
183
 
 
184
/**
139
185
 * All lattice node on a lattice frame. This class provide beam pruning
140
186
 * while push_back, which means at most the best MAX states are reserved,
141
187
 * ie, weak state will may be discard while new better state are inserted,
143
189
 */
144
190
class CLatticeStates {
145
191
private:
146
 
    static const unsigned beam_width = 32;
147
 
 
148
 
public:
149
 
    /** just use the CLatticeStateVec's iterator */
150
 
    typedef CLatticeStateVec::iterator        iterator;
151
 
 
152
 
    /** just use the CLatticeStateVec's iterator */
153
 
    typedef CLatticeStateVec::const_iterator  const_iterator;
154
 
 
155
 
    typedef CLatticeStateVec::reference       reference;
156
 
    typedef CLatticeStateVec::const_reference const_reference;
157
 
    typedef CLatticeStateVec::size_type       size_type;
158
 
 
159
 
public:
160
 
    void
161
 
    clear();
162
 
 
163
 
    void
164
 
    push_back(const TLatticeState& node);
165
 
 
166
 
    //@{
167
 
    /** return the first iterator of m_vec. */
168
 
    size_t
169
 
    size()
170
 
        { return m_vec.size(); }
171
 
 
172
 
    iterator
173
 
    begin()
174
 
        { return m_vec.begin(); }
175
 
 
176
 
    /** return the first iterator of m_vec. */
177
 
    const_iterator
178
 
    begin() const
179
 
        { return m_vec.begin(); }
180
 
    //@}
181
 
 
182
 
 
183
 
    //@{
184
 
    /** return the last iterator of m_vec. */
185
 
    iterator
186
 
    end()
187
 
        { return m_vec.end(); }
188
 
 
189
 
    /** return the last iterator of m_vec. */
190
 
    const_iterator
191
 
    end() const
192
 
        { return m_vec.end(); }
193
 
    //@}
194
 
 
195
 
    reference
196
 
    operator[] (size_type index)
197
 
        {return m_vec[index];}
198
 
 
199
 
    const_reference
200
 
    operator[] (size_type index) const
201
 
        {return m_vec[index];}
202
 
 
203
 
protected:
204
 
    void
205
 
    bubbleUp(int idxInHeap);
206
 
 
207
 
    void
208
 
    ironDown(int idxInHeap);
209
 
 
210
 
protected:
211
 
    std::vector<TLatticeState>      m_vec;
212
 
    std::vector<int>                m_vecIdxInHeap;
213
 
    std::map<CSlmState, int>        m_map;
214
 
    std::vector<int>                m_heap;
 
192
    static const unsigned beam_width;
 
193
    static const TSentenceScore filter_ratio_l1;
 
194
    static const TSentenceScore filter_ratio_l2;
 
195
    static const TSentenceScore filter_threshold_exp;
 
196
 
 
197
public:
 
198
    CLatticeStates() : m_size(0), m_maxBest(2) {}
 
199
 
 
200
    void setMaxBest(size_t maxBest) { m_maxBest = maxBest; }
 
201
 
 
202
    void clear();
 
203
    void add(const TLatticeState& state);
 
204
 
 
205
    std::vector<TLatticeState> getSortedResult();
 
206
    std::vector<TLatticeState> getFilteredResult();
 
207
 
 
208
    typedef std::map<CSlmState, CTopLatticeStates> state_map;
 
209
    class iterator {
 
210
        friend class CLatticeStates;
 
211
        state_map::iterator m_mainIt;
 
212
        state_map::iterator m_mainEnd;
 
213
        CTopLatticeStates::iterator m_childIt;
 
214
public:
 
215
        iterator(state_map::iterator mit, state_map::iterator mend,
 
216
                 CTopLatticeStates::iterator cit)
 
217
            : m_mainIt(mit), m_mainEnd(mend), m_childIt(cit) {}
 
218
 
 
219
        iterator() {}
 
220
 
 
221
        void operator++();
 
222
        bool operator!=(const CLatticeStates::iterator& rhs);
 
223
        TLatticeState& operator*();
 
224
        TLatticeState* operator->();
 
225
    };
 
226
 
 
227
    iterator begin();
 
228
    iterator end();
 
229
private:
 
230
    void _pushScoreHeap(TSentenceScore score, CSlmState slmState);
 
231
    void _popScoreHeap();
 
232
    void _refreshHeapIdx(int heapIdx);
 
233
    void _adjustUp(int node);
 
234
    void _adjustDown(int node);
 
235
 
 
236
private:
 
237
    state_map m_stateMap;
 
238
    size_t m_size;
 
239
    size_t m_maxBest;
 
240
 
 
241
    std::map<CSlmState, int>                           m_heapIdx;
 
242
    std::vector<std::pair<TSentenceScore, CSlmState> > m_scoreHeap;
215
243
};
216
244
 
217
245
#endif