← Back to branch summary

~ubuntu-branches/ubuntu/raring/sunpinyin/raring

« back to all changes in this revision

Viewing changes to src/slm/slmprune/slmprune.cpp

  • Committer: Package Import Robot
  • Author(s): YunQiang Su
  • Date: 2012-03-30 15:31:55 UTC
  • mfrom: (1.1.3) (1.2.7 sid)
  • Revision ID: package-import@ubuntu.com-20120330153155-qgls77sogzgtg9zp
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/slm/slmprune/slmprune.cpp
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
#ifdef HAVE_CONFIG_H
61
61
#endif
62
62
 
63
63
public:
64
 
    TNodeInfo(double distance=0.0, int pos=0, bool children=0) : d(distance)
65
 
    { idx = pos; child = (children==0)?0:1; }
66
 
 
67
 
    bool operator< (const TNodeInfo& r) const
68
 
    { return ((child ^ r.child) == 0)?(d < r.d):(child == 0); }
69
 
 
70
 
    bool operator==(const TNodeInfo& r) const
71
 
    { return (child == r.child && d == r.d); }
 
64
    TNodeInfo(double distance = 0.0, int pos = 0, bool children =
 
65
                  0) : d(distance)
 
66
    {
 
67
        idx = pos; child = (children == 0) ? 0 : 1;
 
68
    }
 
69
 
 
70
    bool
 
71
    operator<(const TNodeInfo& r) const
 
72
    {
 
73
        return ((child ^ r.child) == 0) ? (d < r.d) : (child == 0);
 
74
    }
 
75
 
 
76
    bool
 
77
    operator==(const TNodeInfo& r) const
 
78
    {
 
79
        return(child == r.child && d == r.d);
 
80
    }
72
81
};
73
82
 
74
83
class CSlmPruner : public CSIMSlm {
75
84
public:
76
85
    CSlmPruner() : CSIMSlm(), cut(NULL)
77
 
    { }
 
86
    {
 
87
    }
78
88
 
79
89
    ~CSlmPruner()
80
 
    { if (cut) delete [] cut; }
 
90
    {
 
91
        if (cut) delete [] cut;
 
92
    }
81
93
 
82
94
    void SetCut(int* nCut);
83
95
    void SetReserve(int* nReserve);
95
107
    double cache_PA, cache_PB;
96
108
};
97
109
 
98
 
void CSlmPruner::Prune()
 
110
void
 
111
CSlmPruner::Prune()
99
112
{
100
113
    printf("Erasing items using Entropy distance"); fflush(stdout);
101
 
    for (int lvl=N; lvl>0; --lvl)
 
114
    for (int lvl = N; lvl > 0; --lvl)
102
115
        PruneLevel(lvl);
103
116
    printf("\n"); fflush(stdout);
104
117
    CalcBOW();
105
118
}
106
 
void CSlmPruner::Write(const char* filename)
 
119
void
 
120
CSlmPruner::Write(const char* filename)
107
121
{
108
122
    FILE* out = fopen(filename, "wb");
109
123
    fwrite(&N, sizeof(N), 1, out);
110
124
    fwrite(&bUseLogPr, sizeof(bUseLogPr), 1, out);
111
 
    fwrite(sz, sizeof(int), N+1, out);
112
 
    for (int i=0; i<N; ++i) {
 
125
    fwrite(sz, sizeof(int), N + 1, out);
 
126
    for (int i = 0; i < N; ++i) {
113
127
        fwrite(level[i], sizeof(TNode), sz[i], out);
114
128
    }
115
129
    fwrite(level[N], sizeof(TLeaf), sz[N], out);
116
130
    fclose(out);
117
131
}
118
132
 
119
 
void CSlmPruner::SetReserve(int* nReserve)
 
133
void
 
134
CSlmPruner::SetReserve(int* nReserve)
120
135
{
121
 
    cut = new int [N+1];
 
136
    cut = new int [N + 1];
122
137
    cut[0] = 0;
123
 
    for (int lvl=1; lvl<=N; ++lvl) {
 
138
    for (int lvl = 1; lvl <= N; ++lvl) {
124
139
        cut[lvl] = sz[lvl] - 1 - nReserve[lvl];
125
140
        if (cut[lvl] < 0) cut[lvl] = 0;
126
141
    }
127
142
}
128
143
 
129
 
void CSlmPruner::SetCut(int* nCut)
 
144
void
 
145
CSlmPruner::SetCut(int* nCut)
130
146
{
131
 
    cut = new int [N+1];
 
147
    cut = new int [N + 1];
132
148
    cut[0] = 0;
133
 
    for (int lvl=1; lvl<=N; ++lvl)
 
149
    for (int lvl = 1; lvl <= N; ++lvl)
134
150
        cut[lvl] = nCut[lvl];
135
151
}
136
152
 
137
153
template <class chIterator>
138
 
int CutLevel(CSIMSlm::TNode* pfirst, CSIMSlm::TNode* plast, chIterator chfirst, chIterator chlast, bool bUseLogPr)
 
154
int
 
155
CutLevel(CSIMSlm::TNode* pfirst,
 
156
         CSIMSlm::TNode* plast,
 
157
         chIterator chfirst,
 
158
         chIterator chlast,
 
159
         bool bUseLogPr)
139
160
{
140
 
   int idxfirst, idxchk;
141
 
   chIterator chchk = chfirst;
142
 
   for (idxfirst=idxchk=0; chchk != chlast; ++chchk, ++idxchk) {
 
161
    int idxfirst, idxchk;
 
162
    chIterator chchk = chfirst;
 
163
    for (idxfirst = idxchk = 0; chchk != chlast; ++chchk, ++idxchk) {
143
164
        //cut item whoese pr == 1.0; and not psuedo tail
144
 
        if (chchk->pr != ((bUseLogPr)?0.0:1.0) || (chchk+1) == chlast) {
 
165
        if (chchk->pr != ((bUseLogPr) ? 0.0 : 1.0) || (chchk + 1) == chlast) {
145
166
            if (idxfirst < idxchk) *chfirst = *chchk;
146
167
            while (pfirst != plast && pfirst->child <= idxchk)
147
168
                pfirst++->child = idxfirst;
152
173
    return idxfirst;
153
174
}
154
175
 
155
 
void CSlmPruner::PruneLevel(int lvl)
 
176
void
 
177
CSlmPruner::PruneLevel(int lvl)
156
178
{
157
179
    cache_level = cache_idx = -1;
158
180
 
159
181
    if (cut[lvl] <= 0) {
160
 
        printf("\n  Level %d (%d items), no need to cut as your command!", lvl, sz[lvl]-1); fflush(stdout);
 
182
        printf("\n  Level %d (%d items), no need to cut as your command!",
 
183
               lvl,
 
184
               sz[lvl] - 1); fflush(stdout);
161
185
        return;
162
186
    }
163
187
 
164
 
    printf("\n  Level %d (%d items), allocating...", lvl, sz[lvl]-1); fflush(stdout);
 
188
    printf("\n  Level %d (%d items), allocating...", lvl, sz[lvl] - 1); fflush(
 
189
        stdout);
165
190
 
166
191
    int n = sz[lvl] - 1; //do not count last psuedo tail
167
 
    if (cut[lvl] >= n) cut[lvl] = n-1;
 
192
    if (cut[lvl] >= n) cut[lvl] = n - 1;
168
193
    TNodeInfo* pbuf = new TNodeInfo[n];
169
194
    TSIMWordId hw[16]; // it should be lvl+1, yet some compiler do not support it
170
195
    int idx[16];       // it should be lvl+1, yet some compiler do not support it
171
196
 
172
197
    printf(", Calculating..."); fflush(stdout);
173
 
    for (int i=0; i <=lvl; ++i)
 
198
    for (int i = 0; i <= lvl; ++i)
174
199
        idx[i] = 0;
175
200
    while (idx[lvl] < n) {
176
201
        if (lvl == N) {
177
 
            hw[lvl] = (((TLeaf*)level[lvl])+idx[lvl])->id;
 
202
            hw[lvl] = (((TLeaf*)level[lvl]) + idx[lvl])->id;
178
203
        } else {
179
 
            hw[lvl] = (((TNode*)level[lvl])+idx[lvl])->id;
 
204
            hw[lvl] = (((TNode*)level[lvl]) + idx[lvl])->id;
180
205
        }
181
 
        for (int j=lvl-1; j >= 0; --j) {
182
 
            TNode* pnode = ((TNode*)level[j])+idx[j];
183
 
            for (; (pnode+1)->child <= idx[j+1]; ++pnode, ++idx[j])
 
206
        for (int j = lvl - 1; j >= 0; --j) {
 
207
            TNode* pnode = ((TNode*)level[j]) + idx[j];
 
208
            for (; (pnode + 1)->child <= idx[j + 1]; ++pnode, ++idx[j])
184
209
                ;
185
210
            hw[j] = pnode->id;
186
211
        }
187
212
        bool has_child = false;
188
213
        if (lvl != N) {
189
214
            TNode* pn = ((TNode*)level[lvl]) + idx[lvl];
190
 
            if ((pn+1)->child > pn->child)
 
215
            if ((pn + 1)->child > pn->child)
191
216
                has_child = true;
192
217
        }
193
 
        pbuf[idx[lvl]].child = (has_child)?1:0;
 
218
        pbuf[idx[lvl]].child = (has_child) ? 1 : 0;
194
219
        pbuf[idx[lvl]].idx = idx[lvl];
195
220
        if (!has_child)
196
221
            pbuf[idx[lvl]].d = CalcDistance(lvl, idx, hw);
197
222
        ++idx[lvl];
198
223
    }
199
224
    printf(", sorting...");
200
 
    std::make_heap(pbuf, pbuf+n);
201
 
    std::sort_heap(pbuf, pbuf+n);
 
225
    std::make_heap(pbuf, pbuf + n);
 
226
    std::sort_heap(pbuf, pbuf + n);
202
227
 
203
228
    int k = 0;
204
229
    // because pr in model can not be 1.0, so we use this to mark a item to be prune
205
 
    for (TNodeInfo* pinfo = pbuf; k < cut[lvl] && pinfo->child == 0; ++k, ++pinfo) {
 
230
    for (TNodeInfo* pinfo = pbuf;
 
231
         k < cut[lvl] && pinfo->child == 0;
 
232
         ++k, ++pinfo) {
206
233
        if (lvl == N) {
207
234
            if (bUseLogPr)
208
 
                (((TLeaf*)level[lvl]) + pinfo->idx)->pr = 0.0; // -log(1.0)
 
235
                (((TLeaf*)level[lvl]) + pinfo->idx)->pr = 0.0;  // -log(1.0)
209
236
            else
210
237
                (((TLeaf*)level[lvl]) + pinfo->idx)->pr = 1.0;
211
238
        } else {
212
239
            if (bUseLogPr)
213
 
                (((TNode*)level[lvl]) + pinfo->idx)->pr = 0.0; // -log(1.0)
 
240
                (((TNode*)level[lvl]) + pinfo->idx)->pr = 0.0;  // -log(1.0)
214
241
            else
215
 
                (((TNode*)level[lvl]) + pinfo->idx)->pr = 1.0; // -log(1.0)
 
242
                (((TNode*)level[lvl]) + pinfo->idx)->pr = 1.0;  // -log(1.0)
216
243
        }
217
244
    }
218
245
    printf("(cut %d items), build parent ptr...", k); fflush(stdout);
219
246
    if (lvl == N) {
220
 
        k = CutLevel((TNode*)level[lvl-1], ((TNode*)level[lvl-1])+sz[lvl-1], (TLeaf*)level[lvl], ((TLeaf*)level[lvl])+sz[lvl], bUseLogPr);
 
247
        k =
 
248
            CutLevel((TNode*)level[lvl - 1],
 
249
                     ((TNode*)level[lvl - 1]) + sz[lvl - 1],
 
250
                     (TLeaf*)level[lvl],
 
251
                     ((TLeaf*)level[lvl]) + sz[lvl],
 
252
                     bUseLogPr);
221
253
    } else {
222
 
        k = CutLevel((TNode*)level[lvl-1], ((TNode*)level[lvl-1])+sz[lvl-1], (TNode*)level[lvl], ((TNode*)level[lvl])+sz[lvl], bUseLogPr);
 
254
        k =
 
255
            CutLevel((TNode*)level[lvl - 1],
 
256
                     ((TNode*)level[lvl - 1]) + sz[lvl - 1],
 
257
                     (TNode*)level[lvl],
 
258
                     ((TNode*)level[lvl]) + sz[lvl],
 
259
                     bUseLogPr);
223
260
    }
224
261
    sz[lvl] = k; //k is new size
225
262
    printf("done!");
228
265
}
229
266
 
230
267
template<class chIterator>
231
 
double CalcNodeBow(CSlmPruner* pruner, int lvl, TSIMWordId words[], chIterator chh, chIterator cht, bool bUseLogPr)
 
268
double
 
269
CalcNodeBow(CSlmPruner* pruner,
 
270
            int lvl,
 
271
            TSIMWordId words[],
 
272
            chIterator chh,
 
273
            chIterator cht,
 
274
            bool bUseLogPr)
232
275
{
233
 
    double sumnext = 0.0, sum=0.0;
 
276
    double sumnext = 0.0, sum = 0.0;
234
277
    if (chh == cht)
235
278
        return 1.0;
236
279
    for (; chh < cht; ++chh) {
238
281
            sumnext += exp(-double(chh->pr));
239
282
        else
240
283
            sumnext += double(chh->pr);
241
 
        words[lvl+1] = chh->id;
242
 
        sum += pruner->getPr(lvl, words+2);
 
284
        words[lvl + 1] = chh->id;
 
285
        sum += pruner->getPr(lvl, words + 2);
243
286
    }
244
287
    assert(sumnext >= 0.0 && sumnext < 1.0);
245
288
    assert(sum >= 0.0 && sum < 1.0);
246
 
    return (1.0-sumnext)/(1.0-sum);
 
289
    return (1.0 - sumnext) / (1.0 - sum);
247
290
}
248
291
 
249
 
void CSlmPruner::CalcBOW()
 
292
void
 
293
CSlmPruner::CalcBOW()
250
294
{
251
295
    printf("\nUpdating back-off weight"); fflush(stdout);
252
 
    for (int lvl=0; lvl < N; ++lvl) {
 
296
    for (int lvl = 0; lvl < N; ++lvl) {
253
297
        printf("\n    Level %d...", lvl); fflush(stdout);
254
298
        TNode* base[16]; //it should be lvl+1, yet some compiler do not support it
255
299
        int idx[16];     //it should be lvl+1, yet some compiler do not support it
256
 
        for (int i=0; i <= lvl; ++i) {
 
300
        for (int i = 0; i <= lvl; ++i) {
257
301
            base[i] = (TNode*)level[i];
258
302
            idx[i] = 0;
259
303
        }
260
304
        TSIMWordId words[17];   //it should be lvl+2, yet some compiler do not support it
261
 
        for (int lsz = sz[lvl]-1; idx[lvl] < lsz; ++idx[lvl]) {
 
305
        for (int lsz = sz[lvl] - 1; idx[lvl] < lsz; ++idx[lvl]) {
262
306
            words[lvl] = base[lvl][idx[lvl]].id;
263
 
            for (int k=lvl-1; k >= 0; --k) {
264
 
                while (base[k][idx[k]+1].child <= idx[k+1])
 
307
            for (int k = lvl - 1; k >= 0; --k) {
 
308
                while (base[k][idx[k] + 1].child <= idx[k + 1])
265
309
                    ++idx[k];
266
310
                words[k] = base[k][idx[k]].id;
267
311
            }
268
312
            TNode & node = base[lvl][idx[lvl]];
269
 
            TNode & nodenext = *((&node)+1);
 
313
            TNode & nodenext = *((&node) + 1);
270
314
 
271
315
            double bow = 1.0;
272
 
            if (lvl == N-1) {
273
 
                TLeaf* ch = (TLeaf*)level[lvl+1];
274
 
                bow = CalcNodeBow(this, lvl, words, &(ch[node.child]), &(ch[nodenext.child]), bUseLogPr);
 
316
            if (lvl == N - 1) {
 
317
                TLeaf* ch = (TLeaf*)level[lvl + 1];
 
318
                bow =
 
319
                    CalcNodeBow(this, lvl, words, &(ch[node.child]),
 
320
                                &(ch[nodenext.child]), bUseLogPr);
275
321
            } else {
276
 
                TNode* ch = (TNode*)level[lvl+1];
277
 
                bow = CalcNodeBow(this, lvl, words, &(ch[node.child]), &(ch[nodenext.child]), bUseLogPr);
 
322
                TNode* ch = (TNode*)level[lvl + 1];
 
323
                bow =
 
324
                    CalcNodeBow(this, lvl, words, &(ch[node.child]),
 
325
                                &(ch[nodenext.child]), bUseLogPr);
278
326
            }
279
327
            if (bUseLogPr)
280
328
                node.bow = PR_TYPE(-log(bow));
285
333
    printf("\n"); fflush(stdout);
286
334
}
287
335
 
288
 
double CSlmPruner::CalcDistance(int lvl, int* idx, TSIMWordId* hw)
 
336
double
 
337
CSlmPruner::CalcDistance(int lvl, int* idx, TSIMWordId* hw)
289
338
{
290
339
    double PA, PB, PHW, PH_W, PH, BOW, _BOW, pr, p_r;
291
340
    TSIMWordId w = hw[lvl];
292
341
 
293
 
    PH=1.0;
294
 
    TNode* parent = ((TNode*)level[lvl-1])+idx[lvl-1];
 
342
    PH = 1.0;
 
343
    TNode* parent = ((TNode*)level[lvl - 1]) + idx[lvl - 1];
295
344
    if (bUseLogPr)
296
345
        BOW = exp(-double(parent->bow));  //Fix original bug to use the BOW directly
297
346
    else
298
347
        BOW = double(parent->bow);
299
348
 
300
 
    for (int i=1; i < lvl; ++i)
301
 
        PH *= getPr(i, hw+1+(lvl-i));
302
 
    assert(PH <= 1.0 && PH >0.0);
 
349
    for (int i = 1; i < lvl; ++i)
 
350
        PH *= getPr(i, hw + 1 + (lvl - i));
 
351
    assert(PH <= 1.0 && PH > 0.0);
303
352
 
304
353
    if (lvl == N) {
305
354
        if (bUseLogPr)
306
 
            PHW = exp(-((((TLeaf*)level[lvl])+idx[lvl])->pr));
 
355
            PHW = exp(-((((TLeaf*)level[lvl]) + idx[lvl])->pr));
307
356
        else
308
 
            PHW = ((((TLeaf*)level[lvl])+idx[lvl])->pr);
309
 
        assert(w == (((TLeaf*)level[lvl])+idx[lvl])->id);
 
357
            PHW = ((((TLeaf*)level[lvl]) + idx[lvl])->pr);
 
358
        assert(w == (((TLeaf*)level[lvl]) + idx[lvl])->id);
310
359
    } else {
311
360
        if (bUseLogPr)
312
 
            PHW = exp(-((((TNode*)level[lvl])+idx[lvl])->pr));
 
361
            PHW = exp(-((((TNode*)level[lvl]) + idx[lvl])->pr));
313
362
        else
314
 
            PHW = ((((TNode*)level[lvl])+idx[lvl])->pr);
315
 
        assert(w == (((TNode*)level[lvl])+idx[lvl])->id);
316
 
 
 
363
            PHW = ((((TNode*)level[lvl]) + idx[lvl])->pr);
 
364
        assert(w == (((TNode*)level[lvl]) + idx[lvl])->id);
317
365
    }
318
 
    PH_W = getPr(lvl-1, hw+2);
 
366
    PH_W = getPr(lvl - 1, hw + 2);
319
367
    assert(PHW > 0.0 && PHW < 1.0);
320
368
    assert(PH_W > 0.0 && PH_W < 1.0);
321
369
 
322
 
    if (cache_level != lvl-1 || cache_idx != idx[lvl-1]) {
323
 
        cache_level = lvl-1;
324
 
        cache_idx = idx[lvl-1];
 
370
    if (cache_level != lvl - 1 || cache_idx != idx[lvl - 1]) {
 
371
        cache_level = lvl - 1;
 
372
        cache_idx = idx[lvl - 1];
325
373
        cache_PA = cache_PB = 1.0;
326
 
        for (int h=parent->child, t = (parent+1)->child; h<t; ++h) {
 
374
        for (int h = parent->child, t = (parent + 1)->child; h < t; ++h) {
327
375
            TSIMWordId id;
328
376
            if (lvl == N) {
329
377
                if (bUseLogPr)
330
 
                    pr = exp(-((((TLeaf*)level[lvl])+h)->pr));
 
378
                    pr = exp(-((((TLeaf*)level[lvl]) + h)->pr));
331
379
                else
332
 
                    pr = ((((TLeaf*)level[lvl])+h)->pr);
333
 
                id = (((TLeaf*)level[lvl])+h)->id;
334
 
 
 
380
                    pr = ((((TLeaf*)level[lvl]) + h)->pr);
 
381
                id = (((TLeaf*)level[lvl]) + h)->id;
335
382
            } else {
336
383
                if (bUseLogPr)
337
 
                    pr = exp(-((((TNode*)level[lvl])+h)->pr));
 
384
                    pr = exp(-((((TNode*)level[lvl]) + h)->pr));
338
385
                else
339
 
                    pr = ((((TNode*)level[lvl])+h)->pr);
340
 
                id = (((TNode*)level[lvl])+h)->id;
341
 
 
 
386
                    pr = ((((TNode*)level[lvl]) + h)->pr);
 
387
                id = (((TNode*)level[lvl]) + h)->id;
342
388
            }
343
389
            assert(pr > 0.0 && pr < 1.0);
344
390
            cache_PA -= pr;
345
391
 
346
392
            hw[lvl] = id;
347
 
            p_r = getPr(lvl-1, hw+2);  // Fix bug from pr = getPr(lvl-1, hw+1)
 
393
            p_r = getPr(lvl - 1, hw + 2);  // Fix bug from pr = getPr(lvl-1, hw+1)
348
394
            assert(p_r > 0.0 && p_r < 1.0);
349
395
            cache_PB -= p_r;
350
396
        }
351
397
        assert(cache_PA > -0.01 && cache_PB > -0.01);
352
398
        if (cache_PA < 0.00001 || cache_PB < 0.00001) {
353
 
            printf("\n precision problem on %d gram:", lvl-1);
354
 
            for (int i=1; i < lvl; ++i) printf("%d ", idx[i]);
 
399
            printf("\n precision problem on %d gram:", lvl - 1);
 
400
            for (int i = 1; i < lvl; ++i) printf("%d ", idx[i]);
355
401
            printf("   ");
356
402
            if (cache_PA < 0.00001) {
357
403
                printf("{1.0 - sigma p(w|h)} ==> 0.00001");
366
412
    PA = cache_PA;
367
413
    PB = cache_PB;
368
414
 
369
 
    _BOW = (PA+PHW) / (PB+PH_W); // Fix bug from "(1.0-PA+PHW)/(1.0-PB+PH_W);"
 
415
    _BOW = (PA + PHW) / (PB + PH_W); // Fix bug from "(1.0-PA+PHW)/(1.0-PB+PH_W);"
370
416
 
371
417
    assert(BOW > 0.0);
372
418
    assert(_BOW > 0.0);
373
 
    assert(PA+PHW < 1.01);     // %1 error rate
374
 
    assert(PB+PH_W < 1.01);    // %1 error rate
 
419
    assert(PA + PHW < 1.01);     // %1 error rate
 
420
    assert(PB + PH_W < 1.01);    // %1 error rate
375
421
 
376
 
    /* 
 
422
    /*
377
423
     * PH = P(h), PHW = P(w|h), PH_W = P(w|h'), _BOW = bow'(h) (the new bow)
378
424
     * BOW = bow(h) (the original bow), PA = sum_{w_i:C(w_i,h)=0} P(w_i|h),
379
425
     * PB = sum_{w_i:C(w_i,h)=0} P(w_i|h')
380
426
     */
381
 
    return -(PH * (PHW * (log(PH_W)+log(_BOW)-log(PHW)) + PA * (log(_BOW)-log(BOW)) ));
 
427
    return -(PH *
 
428
             (PHW *
 
429
              (log(PH_W) + log(_BOW) - log(PHW)) + PA * (log(_BOW) - log(BOW))));
382
430
}
383
431
 
384
 
void ShowUsage(void)
 
432
void
 
433
ShowUsage(void)
385
434
{
386
435
    printf("Usage:\n");
387
436
    printf("    slmprune input_slm result_slm [R|C] num1 num2...\n");
388
437
    printf("\nDescription:\n");
389
 
    printf("\
 
438
    printf(
 
439
        "\
390
440
      This program uses entropy-based method to prune the size of back-off \n\
391
441
  language model 'input_slm' to a specific size and write to 'result_slm'. \n\
392
442
  the third parameter [R|C] means the following numbers is the number for\n\
405
455
int nCut[32];
406
456
const char* srcfilename, *tgtfilename;
407
457
 
408
 
int main(int argc, char* argv[])
 
458
int
 
459
main(int argc, char* argv[])
409
460
{
410
461
    memset(nCut, 0, sizeof(nCut));
411
462
    if (argc < 5) {
420
471
    pruner.Load(srcfilename);
421
472
    printf("done!\n"); fflush(stdout);
422
473
 
423
 
    for (int i=4; i < argc && i < 100; ++i)
424
 
        nCut[i-3] = atoi(argv[i]);
 
474
    for (int i = 4; i < argc && i < 100; ++i)
 
475
        nCut[i - 3] = atoi(argv[i]);
425
476
 
426
477
    if (bCut)
427
478
        pruner.SetCut(nCut);