src/slm/slm.cpp

   1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
   3  *
   4  * Copyright (c) 2007 Sun Microsystems, Inc. All Rights Reserved.
   5  *
   6  * The contents of this file are subject to the terms of either the GNU Lesser
   7  * General Public License Version 2.1 only ("LGPL") or the Common Development and
   8  * Distribution License ("CDDL")(collectively, the "License"). You may not use this
   9  * file except in compliance with the License. You can obtain a copy of the CDDL at
  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
  12  * specific language governing permissions and limitations under the License. When
  13  * distributing the software, include this License Header Notice in each file and
  14  * include the full text of the License in the License file as well as the
  15  * following notice:
  16  *
  17  * NOTICE PURSUANT TO SECTION 9 OF THE COMMON DEVELOPMENT AND DISTRIBUTION LICENSE
  18  * (CDDL)
  19  * For Covered Software in this distribution, this License shall be governed by the
  20  * laws of the State of California (excluding conflict-of-law provisions).
  21  * Any litigation relating to this License shall be subject to the jurisdiction of
  22  * the Federal Courts of the Northern District of California and the state courts
  23  * of the State of California, with venue lying in Santa Clara County, California.
  24  *
  25  * Contributor(s):
  26  *
  27  * If you wish your version of this file to be governed by only the CDDL or only
  28  * the LGPL Version 2.1, indicate your decision by adding "[Contributor]" elects to
  29  * include this software in this distribution under the [CDDL or LGPL Version 2.1]
  30  * license." If you don't indicate a single choice of license, a recipient has the
  31  * option to distribute your version of this file under either the CDDL or the LGPL
  32  * Version 2.1, or to extend the choice of license to its licensees as provided
  33  * above. However, if you add LGPL Version 2.1 code and therefore, elected the LGPL
  34  * Version 2 license, then the option applies only if the new code is made subject
  35  * to such option by the copyright holder.
  36  */
  37
  38 #include <unistd.h>
  39 #include <fcntl.h>
  40 #include <sys/types.h>
  41 #include <sys/stat.h>
  42 #include <math.h>
  43 #include <errno.h>
  44 #include <string.h>
  45
  46 #include "slm.h"
  47
  48 #ifdef HAVE_SYS_MMAN_H
  49 #include <sys/mman.h>
  50 #elif defined(BEOS_OS)
  51 #include <be/kernel/OS.h>
  52 #endif
  53
  54 bool
  55 CThreadSlm::load(const char* fname, bool MMap)
  56 {
  57     int fd = open(fname, O_RDONLY);
  58     if (fd == -1) {
  59         fprintf(stderr, "open %s: %s\n", fname, strerror(errno));
  60         return false;
  61     }
  62
  63     m_bufSize = lseek(fd, 0, SEEK_END);
  64     lseek(fd, 0, SEEK_SET);
  65
  66     m_bMMap = MMap;
  67     if (m_bMMap) {
  68 #ifdef HAVE_SYS_MMAN_H
  69         void* p = mmap(NULL, m_bufSize, PROT_READ, MAP_SHARED, fd, 0);
  70         if (p == MAP_FAILED) {
  71             close(fd);
  72             return false;
  73         }
  74         m_buf = (char*)p;
  75 #elif defined(BEOS_OS)
  76         char *p = NULL;
  77         area_id area = create_area("tmp", (void**)&p, B_ANY_ADDRESS,
  78                                    (m_bufSize +
  79                                     (B_PAGE_SIZE - 1)) & ~(B_PAGE_SIZE - 1),
  80                                    B_NO_LOCK, B_READ_AREA | B_WRITE_AREA);
  81         if (area < 0) {
  82             close(fd);
  83             return false;
  84         }
  85         m_buf = p;
  86
  87         for (ssize_t len = m_bufSize; len > 0; ) {
  88             ssize_t n = read(fd, p, len);
  89             if (n < 0) break;
  90             p += n;
  91             len -= n;
  92         }
  93 #else // Other OS
  94         #error "No implementation for mmap()"
  95 #endif // HAVE_SYS_MMAN_H
  96     } else {
  97         if ((m_buf = new char[m_bufSize]) == NULL) {
  98             close(fd);
  99             return false;
 100         }
 101         if (read(fd, m_buf, m_bufSize) != m_bufSize) {
 102             perror("read lm");
 103             delete [] m_buf; m_buf = NULL;
 104             close(fd);
 105             return false;
 106         }
 107     }
 108     close(fd);
 109
 110     m_N = *(unsigned*)m_buf;
 111     m_UseLogPr = *(((unsigned*)m_buf) + 1);
 112     m_LevelSizes = ((unsigned*)m_buf) + 2;
 113     m_prTable =
 114         (float*)(m_buf + 2 * sizeof(unsigned) + (m_N + 1) * sizeof(unsigned));
 115     m_bowTable = m_prTable + (1 << BITS_PR);
 116
 117     TNode* pn = (TNode*)(m_bowTable + (1 << BITS_BOW));
 118
 119     //Solaris CC would cause error in runtime if using some thing like
 120     //following even using (void**) conversion. So add PtrVoid definition
 121     //m_Levels = new (void*) [m_N + 1];
 122     m_Levels = new PtrVoid[m_N + 1];
 123
 124     for (size_t lvl = 0; lvl <= m_N; ++lvl) {
 125         m_Levels[lvl] = (void*)pn;
 126         pn += m_LevelSizes[lvl];
 127     }
 128     return true;
 129 }
 130
 131 void
 132 CThreadSlm::free()
 133 {
 134     if (m_Levels) {
 135         delete [] m_Levels;
 136     }
 137     if (m_buf) {
 138         if (m_bMMap) {
 139 #ifdef HAVE_SYS_MMAN_H
 140             munmap(m_buf, m_bufSize);
 141 #elif defined(BEOS_OS)
 142             delete_area(area_for(m_buf));
 143 #else // Other OS
 144             #error "No implementation for munmap()"
 145 #endif // HAVE_SYS_MMAN_H
 146         } else {
 147             delete [] m_buf;
 148         }
 149     }
 150     m_buf = NULL;
 151     m_Levels = NULL;
 152 }
 153
 154 template<class NodeT>
 155 unsigned int
 156 find_id(NodeT* base, unsigned int h, unsigned int t, unsigned int id)
 157 {
 158     unsigned int tail = t;
 159     while (h < t) {
 160         int m = h + (t - h) / 2;
 161         NodeT* pm = base + m;
 162         unsigned int thisId = pm->wid();
 163         if (thisId < id)
 164             h = m + 1;
 165         else if (thisId > id)
 166             t = m;
 167         else
 168             return m;
 169     }
 170     return tail;
 171 }
 172
 173 /**
 174  * return value as the model suggested. The history state must be historified
 175  * or the history's level should be 0. when level == 0 but idx != 0, the
 176  * history is a psuedo unigram state used for this model to combine another
 177  * bigram cache language model
 178  */
 179 double
 180 CThreadSlm::rawTransfer(TState history, unsigned int wid, TState& result)
 181 {
 182     unsigned int lvl = history.getLevel();
 183     unsigned int pos = history.getIdx();
 184
 185     double cost = (m_UseLogPr) ? 0.0 : 1.0;
 186
 187     // NON_Word id must be dealed with special, let it transfer to root
 188     // without any cost
 189     if (ID_NOT_WORD == wid) {
 190         result = 0;
 191         return cost;
 192     }
 193
 194     while (true) {
 195         //for psuedo cache model unigram state
 196         TNode* pn = ((TNode*)m_Levels[lvl]) + ((lvl) ? pos : 0);
 197
 198         unsigned int t = (pn + 1)->ch();
 199
 200         if (lvl < m_N - 1) {
 201             TNode* pBase = (TNode*)m_Levels[lvl + 1];
 202             unsigned int idx = find_id(pBase, pn->ch(), t, wid);
 203             if (idx != t) {
 204                 result.setIdx(idx);
 205                 result.setLevel(lvl + 1);
 206                 double pr = m_prTable[pBase[idx].pr()];
 207                 return (m_UseLogPr) ? (cost + pr) : (cost * pr);
 208             }
 209         } else {
 210             TLeaf* pBase = (TLeaf*)m_Levels[lvl + 1];
 211             unsigned int idx = find_id(pBase, pn->ch(), t, wid);
 212             if (idx != t) {
 213                 result.setIdx(idx);
 214                 result.setLevel(lvl + 1);
 215                 double pr = m_prTable[pBase[idx].pr()];
 216                 return (m_UseLogPr) ? (cost + pr) : (cost * pr);
 217             }
 218         }
 219
 220         if (m_UseLogPr)
 221             cost += m_bowTable[pn->bow()];
 222         else
 223             cost *= m_bowTable[pn->bow()];
 224         if (lvl == 0)
 225             break;
 226         lvl = pn->bol();
 227         pos = pn->bon();
 228     }
 229     result.setLevel(0);
 230     result.setIdx(0);
 231     if (m_UseLogPr)
 232         return cost + m_prTable[((TNode*)m_Levels[0])->pr()];
 233     else
 234         return cost * m_prTable[((TNode*)m_Levels[0])->pr()];
 235 }
 236
 237 double
 238 CThreadSlm::transferNegLog(TState history, unsigned int wid, TState& result)
 239 {
 240     double cost = rawTransfer(history, wid, result);
 241     if (m_UseLogPr)
 242         return cost;
 243     else
 244         return -log(cost);
 245 }
 246
 247 double
 248 CThreadSlm::transfer(TState history, unsigned int wid, TState& result)
 249 {
 250     double cost = rawTransfer(history, wid, result);
 251     if (!m_UseLogPr)
 252         return cost;
 253     else
 254         return exp(-cost);
 255 }
 256
 257 unsigned int
 258 CThreadSlm::lastWordId(TState st)
 259 {
 260     unsigned int lvl = st.getLevel();
 261     if (lvl >= m_N) {
 262         const TLeaf* pn = ((const TLeaf*)m_Levels[m_N]) + st.getIdx();
 263         return pn->wid();
 264     } else if (lvl > 0) {
 265         const TNode *pn = ((const TNode*)m_Levels[st.getLevel()]) + st.getIdx();
 266         return pn->wid();
 267     } else {
 268         unsigned int idx = st.getIdx();
 269         if (idx == 0) {
 270             const TNode *pn = ((const TNode*)m_Levels[st.getLevel()]) +
 271                               st.getIdx();
 272             return pn->wid();
 273         }
 274         return idx; // return the psuedo state word id
 275     }
 276 }
 277
 278 CThreadSlm::TState
 279 CThreadSlm::history_state_of(TState st)
 280 {
 281     if (st.getLevel() >= m_N) {
 282         TLeaf* pl = ((TLeaf*)m_Levels[m_N]) + st.getIdx();
 283         return TState(pl->bol(), pl->bon());
 284     } else {
 285         TNode* pn = ((TNode*)m_Levels[st.getLevel()]) + st.getIdx();
 286         if (pn->ch() == (pn + 1)->ch())
 287             return TState(pn->bol(), pn->bon());
 288         else
 289             return st;
 290     }
 291 }
 292
 293 CThreadSlm::TState&
 294 CThreadSlm::historify(TState& st)
 295 {
 296     if (st.getLevel() >= m_N) {
 297         TLeaf* pl = ((TLeaf*)m_Levels[m_N]) + st.getIdx();
 298         st.setLevel(pl->bol());
 299         st.setIdx(pl->bon());
 300     } else {
 301         TNode* pn = ((TNode*)m_Levels[st.getLevel()]) + st.getIdx();
 302         if (pn->ch() == (pn + 1)->ch()) {
 303             st.setLevel(pn->bol());
 304             st.setIdx(pn->bon());
 305         }
 306     }
 307     return st;
 308 }