src/slm/tslmpack/arpa_slm.cpp

   1 /*
   2  * Copyright (c) 2009 Kov Chai <tchaikov@gmail.com>
   3  *
   4  * The contents of this file are subject to the terms of either the GNU Lesser
   5  * General Public License Version 2.1 only ("LGPL") or the Common Development and
   6  * Distribution License ("CDDL")(collectively, the "License"). You may not use this
   7  * file except in compliance with the License. You can obtain a copy of the CDDL at
   8  * http://www.opensource.org/licenses/cddl1.php and a copy of the LGPLv2.1 at
   9  * http://www.opensource.org/licenses/lgpl-license.php. See the License for the
  10  * specific language governing permissions and limitations under the License. When
  11  * distributing the software, include this License Header Notice in each file and
  12  * include the full text of the License in the License file as well as the
  13  * following notice:
  14  *
  15  * NOTICE PURSUANT TO SECTION 9 OF THE COMMON DEVELOPMENT AND DISTRIBUTION LICENSE
  16  * (CDDL)
  17  * For Covered Software in this distribution, this License shall be governed by the
  18  * laws of the State of California (excluding conflict-of-law provisions).
  19  * Any litigation relating to this License shall be subject to the jurisdiction of
  20  * the Federal Courts of the Northern District of California and the state courts
  21  * of the State of California, with venue lying in Santa Clara County, California.
  22  *
  23  * Contributor(s):
  24  *
  25  * If you wish your version of this file to be governed by only the CDDL or only
  26  * the LGPL Version 2.1, indicate your decision by adding "[Contributor]" elects to
  27  * include this software in this distribution under the [CDDL or LGPL Version 2.1]
  28  * license." If you don't indicate a single choice of license, a recipient has the
  29  * option to distribute your version of this file under either the CDDL or the LGPL
  30  * Version 2.1, or to extend the choice of license to its licensees as provided
  31  * above. However, if you add LGPL Version 2.1 code and therefore, elected the LGPL
  32  * Version 2 license, then the option applies only if the new code is made subject
  33  * to such option by the copyright holder.
  34  */
  35 #include <string>
  36 #include <iostream>
  37 #include <fstream>
  38 #include <algorithm>
  39 #include "arpa_slm.h"
  40
  41 using namespace std;
  42
  43 /**
  44  * the GNU extension is not always available, so we invent another wheel.
  45  */
  46 size_t
  47 getline(char *buf, size_t n, FILE* stream)
  48 {
  49     char* p;
  50     char* end = buf + n;
  51     for (p = buf; p != end; ++p) {
  52         int c = fgetc(stream);
  53         if (c == '\n' || c == EOF)
  54             break;
  55         *p = c;
  56         --n;
  57     }
  58     if (p != end)
  59         *p = 0;
  60     else
  61         *(p - 1) = 0;
  62     return p - buf;
  63 }
  64
  65 char*
  66 getwords(char* buf, char** next)
  67 {
  68     char* word = buf;
  69     char* delim = strstr(buf, "  ");
  70     if (delim == NULL) {
  71         cerr << "Unknown format in: " << buf << "." << endl;
  72         exit(2);
  73     }
  74     *delim = '\0';
  75     *next = delim + 2;
  76     return word;
  77 }
  78
  79 unsigned
  80 get_wid(const char* word, const TLexicon& lexicon)
  81 {
  82     TLexicon::const_iterator lexi = lexicon.find(word);
  83     unsigned wid;
  84     if (lexi != lexicon.end()) {
  85         wid = lexi->second;
  86     } else {
  87         cerr << "Error:\"" << word << "\" not found in lexicon." << endl;
  88         wid = 0;
  89     }
  90     return wid;
  91 }
  92
  93 int
  94 CArpaSlm::TLeaf::load_words(char* buf, const TLexicon& lexicon)
  95 {
  96     int nword = 0;
  97     char* word, *end;
  98     for (word = end = buf; *end != 0; ++end) {
  99         if (*end == ' ') {
 100             assert(nword < N_GRAM);
 101             *end = 0;
 102             hw[nword++] = get_wid(word, lexicon);
 103             word = end + 1;
 104         }
 105     }
 106     if (buf != end) {
 107         wid = hw[nword++] = get_wid(word, lexicon);
 108     }
 109     return nword;
 110 }
 111
 112 void
 113 CArpaSlm::TLeaf::load(istream& is, const TLexicon& lexicon)
 114 {
 115     char buf[1024];
 116     is.getline(buf, sizeof(buf));
 117     char* next = 0;
 118     char* words = getwords(buf, &next);
 119     load_words(words, lexicon);
 120     sscanf(next, "%f (%1u, %u)",
 121            &pr, &bol, &bon);
 122 }
 123
 124 void
 125 CArpaSlm::TNode::load(istream& is, const TLexicon& lexicon)
 126 {
 127     char buf[1024];
 128     is.getline(buf, sizeof(buf));
 129     char* next = 0;
 130     char* words = getwords(buf, &next);
 131     load_words(words, lexicon);
 132     sscanf(next, "%f %f (%1u, %u)",
 133            &pr, &bow, &bol, &bon);
 134 }
 135
 136 void
 137 CArpaSlm::TNode::load_level0(istream& is)
 138 {
 139     hw[0] = 0;
 140     char buf[1024];
 141     is.getline(buf, sizeof(buf));
 142     sscanf(buf, "%f %f (%1u, %u)",
 143            &pr, &bow, &bol, &bon);
 144     wid = 0;
 145 }
 146
 147 void
 148 CArpaSlm::load(const char* filename, const TLexicon& lexicon)
 149 {
 150     printf("Loading ARPA slm..."); fflush(stdout);
 151     ifstream file(filename);
 152     char buf[1024];
 153     for (int i = 0; i <= N_GRAM; ++i) {
 154         unsigned lvl;
 155         int size;
 156         file.getline(buf, sizeof(buf));
 157         if (!file) {
 158             cerr << "Failed to read from" << filename << endl;
 159             exit(1);
 160         }
 161         sscanf(buf, "\\%d-gram\\%d%*[\n]", &lvl, &size);
 162         assert(lvl <= N_GRAM);
 163         if (lvl == 0) {
 164             TNode node0;
 165             node0.load_level0(file);
 166             m_levels[0].push_back(node0);
 167         } else if (lvl < m_N) {
 168             m_levels[lvl].reserve(size);
 169             for (int i = 0; i < size; ++i) {
 170                 TNode node;
 171                 node.load(file, lexicon);
 172                 m_levels[lvl].push_back(node);
 173             }
 174         } else {
 175             // leaf nodes
 176             m_lastLevel.reserve(size);
 177             for (int i = 0; i < size; ++i) {
 178                 TLeaf leaf;
 179                 leaf.load(file, lexicon);
 180                 m_lastLevel.push_back(leaf);
 181             }
 182         }
 183     }
 184 }
 185
 186 template <class NodeT>
 187 struct CompareNode {
 188     const unsigned m_lvl;
 189     CompareNode(unsigned lvl) : m_lvl(lvl)
 190     {
 191     }
 192     /**
 193      * @return true if strictly less, false otherwise
 194      */
 195     bool
 196     operator ()(const NodeT& node, const TSIMWordId hw[N_GRAM])
 197     {
 198         for (unsigned i = 0; i < m_lvl; ++i) {
 199             if (node.hw[i] < hw[i])
 200                 return true;
 201             if (node.hw[i] > hw[i])
 202                 return false;
 203         }
 204         // node.hw[:lvl] is the same as hw[:]
 205         return false;
 206     }
 207 };
 208
 209 void
 210 CArpaSlm::threading()
 211 {
 212     {
 213         TNode& node = m_levels[0][0];
 214         node.ch = 0;
 215     }
 216     for (unsigned lvl = 1; lvl < m_N; ++lvl) {
 217         TNodeLevel& level = m_levels[lvl];
 218         unsigned last_child = 0;
 219         for (TNodeLevel::iterator node = level.begin();
 220              node != level.end();
 221              ++node) {
 222             node->ch = last_child = find_1st_child(lvl, *node, last_child);
 223         }
 224     }
 225 }
 226
 227 unsigned
 228 CArpaSlm::find_1st_child(unsigned lvl, const TNode& node, int last_child)
 229 {
 230     assert(lvl < m_N);
 231     if (lvl == m_N - 1) {
 232         TLeafLevel::iterator found = lower_bound(
 233             m_lastLevel.begin(), m_lastLevel.end(), node.hw,
 234             CompareNode<TLeaf>(lvl));
 235         return distance(m_lastLevel.begin(), found);
 236     } else {
 237         const TNodeLevel& level = m_levels[lvl + 1];
 238         TNodeLevel::const_iterator found = lower_bound(level.begin(), level.end(
 239                                                            ), node.hw,
 240                                                        CompareNode<TNode>(lvl));
 241         return distance(level.begin(), found);
 242     }
 243 }