src/lexicon/pytrie_gen.cpp

   1 #ifdef HAVE_CONFIG_H
   2 #include "config.h"
   3 #endif
   4
   5 #ifdef HAVE_ASSERT_H
   6 #include <assert.h>
   7 #endif
   8
   9 #ifdef HAVE_ICONV_H
  10 #include <iconv.h>
  11 #endif
  12
  13 #include <algorithm>
  14
  15 #include "pytrie_gen.h"
  16 #include "pinyin_data.h"
  17 #include "trie_writer.h"
  18
  19 static const char*
  20 skipSpace(const char* p)
  21 {
  22     while (*p == ' ' || *p == '\t' || *p == '\n' || *p == '\r')
  23         ++p;
  24     return p;
  25 }
  26
  27 static const char*
  28 skipNonSpace(const char* p)
  29 {
  30     while (*p != '\0' && *p != ' ' && *p != '\t' && *p != '\n' && *p != '\r')
  31         ++p;
  32     return p;
  33 }
  34
  35 static void
  36 insertWordId(CPinyinTrieMaker::CWordSet& idset, CPinyinTrieMaker::TWordId id)
  37 {
  38     CPinyinTrieMaker::CWordSet::const_iterator it = idset.find(id);
  39     if (it == idset.end())
  40         idset.insert(id);
  41     else {
  42         const CPinyinTrieMaker::TWordId& a = *it;
  43         if ((a.anony.m_bHide &&
  44              !id.anony.m_bHide) ||
  45             (a.anony.m_bHide == id.anony.m_bHide && a.anony.m_cost >
  46              id.anony.m_cost)) {
  47             idset.erase(it);
  48             idset.insert(id);
  49         }
  50     }
  51 }
  52
  53 struct TSyllableInfo {
  54     std::string m_py;
  55     int m_cost;
  56
  57     TSyllableInfo(const char* py = NULL, int cost = 0) : m_py(py), m_cost(cost)
  58     {
  59     }
  60     bool
  61     operator<(const TSyllableInfo& b) const
  62     {
  63         return m_py < b.m_py;
  64     }
  65 };
  66
  67 #ifdef HAVE_ICONV_H
  68 bool
  69 isCorrectConverted(const char* utf8, iconv_t ic, iconv_t ric)
  70 {
  71     static char gbstr[256];
  72     static char utstr[256];
  73
  74     TIConvSrcPtr src = (TIConvSrcPtr)utf8;
  75     size_t srclen = strlen((char*)src) + 1;
  76     char* dst = (char*)gbstr;
  77     size_t dstlen = 256;
  78     size_t res = iconv(ic, &src, &srclen, &dst, &dstlen);
  79
  80     if (res != size_t(-1) && srclen == 0) {
  81         // do revert convertion and compare them
  82         src = (TIConvSrcPtr)gbstr;
  83         srclen = strlen((char*)src) + 1;
  84         dst = (char*)utstr;
  85         dstlen = 256;
  86         res = iconv(ric, &src, &srclen, &dst, &dstlen);
  87         if (res != size_t(-1) && srclen == 0)
  88             return(strcmp(utf8, utstr) == 0);
  89     }
  90     return false;
  91 }
  92
  93 //return: bit 0x1: contains some gbk out of gb2312, bit 0x2: contains some gb18030 outof gbk
  94 unsigned
  95 getPureGBEncoding(const char* utf8str)
  96 {
  97     static iconv_t ic_gb = iconv_open("GB2312", "UTF-8");
  98     static iconv_t ic_gbk = iconv_open("GBK", "UTF-8");
  99     static iconv_t ric_gb = iconv_open("UTF-8", "GB2312");
 100     static iconv_t ric_gbk = iconv_open("UTF-8", "GBK");
 101
 102     unsigned ret = 0;
 103
 104     if (!isCorrectConverted(utf8str, ic_gb, ric_gb)) {
 105         ret = 1; // at least it is contains some GBK char
 106         if (!isCorrectConverted(utf8str, ic_gbk, ric_gbk))
 107             ret = 3;  //contains some GB18030-only char
 108
 109         #ifdef DEBUG
 110         fprintf(stderr, "==> GB category of (%s) is (0x%x)\n ", utf8str, ret);
 111         fflush(stderr);
 112         #endif
 113     }
 114     return ret;
 115 }
 116 #else // !HAVE_ICONV_H
 117 unsigned
 118 getPureGBEncoding(const char* utf8str)
 119 {
 120     // FIXME
 121     return 0x3;
 122 }
 123 #endif // HAVE_ICONV_H
 124
 125 bool
 126 parseLine(char* buf,
 127           char* word_buf,
 128           unsigned& id,
 129           std::set<TSyllableInfo>& pyset)
 130 {
 131     pyset.clear();
 132
 133     /* ignore the empty lines and comment lines */
 134     if (*buf == '\n' || *buf == '#')
 135         return 0;
 136
 137     char* p = (char*)skipSpace(buf);
 138     char* t = (char*)skipNonSpace(p);
 139     while (p < t) *word_buf++ = *p++;
 140     *word_buf = 0;
 141
 142     p = (char*)skipSpace(p);
 143     t = (char*)skipNonSpace(p);
 144     if (*t)
 145         *t++ = 0;
 146     id = atoi(p);
 147     p = (char*)skipSpace(t);
 148     while (*p) {
 149         const char* s = p;
 150         t = (char*)skipNonSpace(p);
 151         if (*t)
 152             *t++ = 0;
 153         while ((*p >= 'a' && *p <= 'z') || (*p == '\''))
 154             ++p;
 155         if ((p > s) && ((*p == 0) || (*p == ':'))) {
 156             int cost = 0;
 157             if (*p == ':') {
 158                 *p++ = 0;
 159                 cost = -log2(atof(p)/100);
 160             }
 161             pyset.insert(TSyllableInfo(s, cost));
 162         }
 163         p = (char*)skipSpace(t);
 164     }
 165     return pyset.size() > 0;
 166 }
 167
 168
 169 CPinyinTrieMaker::CPinyinTrieMaker()
 170 {
 171     m_RootNode.m_bExpanded = true;
 172 }
 173 /**********************************************************
 174     lexicon文件格式：
 175         以行为单位的文本文件。行中是空格或TAB(1个或多个)分
 176         隔开的字段。 第一个字段为词，第二个字段是word id。
 177         后面的字段中，如果一个字段仅仅由小写字母和'构成，
 178         则认为该字段是该词的一个拼音。行长最大4095;
 179 **********************************************************/
 180
 181 bool
 182 CPinyinTrieMaker::constructFromLexicon(const char* fileName)
 183 {
 184     static char buf[4096];
 185     static char word_buf[2048];
 186
 187     unsigned id;
 188     bool suc = true;
 189     std::set<TSyllableInfo> pyset;
 190     FILE *fp = fopen(fileName, "r");
 191     if (!fp) return false;
 192     printf("Adding pinyin and corresponding words..."); fflush(stdout);
 193     while (fgets(buf, sizeof(buf), fp) != NULL) {
 194         if (!parseLine(buf, word_buf, id, pyset)) {
 195             if (word_buf[0] != L'<' && word_buf[0] != 0) {
 196                 if (m_Lexicon.size() < id + 1) m_Lexicon.resize(id + 1);
 197                 m_Lexicon[id] = std::string(word_buf);
 198             }
 199             continue;
 200         }
 201         unsigned gbcategory = getPureGBEncoding(word_buf);
 202
 203         std::set<TSyllableInfo>::const_iterator its = pyset.begin();
 204         std::set<TSyllableInfo>::const_iterator ite = pyset.end();
 205         for (; its != ite; ++its) {
 206             const char *pystr = its->m_py.c_str();
 207             if (m_Lexicon.size() < id + 1) m_Lexicon.resize(id + 1);
 208             m_Lexicon[id] = std::string(word_buf);
 209
 210             CPinyinTrieMaker::TWordId wid(id, its->m_cost, false, gbcategory);
 211             suc = insertFullPinyinPair(pystr, wid) && suc;
 212         }
 213     }
 214     fclose(fp);
 215
 216     printf("\n    %zd primitive nodes", TNode::m_AllNodes.size());  fflush(stdout);
 217
 218     threadNonCompletePinyin();
 219     printf("\n    %zd total nodes", TNode::m_AllNodes.size());  fflush(stdout);
 220
 221     std::string pyPrefix = "";
 222     printf("\n");  fflush(stdout);
 223
 224     return suc;
 225 }
 226
 227 CPinyinTrieMaker::CNodeList CPinyinTrieMaker::TNode::m_AllNodes;
 228 CPinyinTrieMaker::TNode::TNode()
 229     : m_bExpanded(false), m_bFullSyllableTransfer(false)
 230 {
 231     m_AllNodes.push_back(this);
 232 }
 233
 234 bool
 235 CPinyinTrieMaker::PNodeSet::operator<(const PNodeSet& another) const
 236 {
 237     CNodeSet::const_iterator t1 = m_pns->begin();
 238     CNodeSet::const_iterator t2 = m_pns->end();
 239     CNodeSet::const_iterator a1 = another.m_pns->begin();
 240     CNodeSet::const_iterator a2 = another.m_pns->end();
 241     for (; t1 != t2 && a1 != a2; ++t1, ++a1) {
 242         if (*t1 < *a1) return true;
 243         if (*t1 > *a1) return false;
 244     }
 245     return(a1 != a2);
 246 }
 247
 248 bool
 249 CPinyinTrieMaker::PNodeSet::operator==(const PNodeSet& another) const
 250 {
 251     CNodeSet::const_iterator t1 = m_pns->begin();
 252     CNodeSet::const_iterator t2 = m_pns->end();
 253     CNodeSet::const_iterator a1 = another.m_pns->begin();
 254     CNodeSet::const_iterator a2 = another.m_pns->end();
 255     for (; t1 != t2 && a1 != a2; ++t1, ++a1) {
 256         if (*t1 != *a1) return false;
 257     }
 258     return(a1 == a2 && t1 != t2);
 259 }
 260
 261 static void
 262 parseFullPinyin(const char *pinyin, std::vector<TSyllable> &ret)
 263 {
 264     char *buf = strdup(pinyin);
 265     char *p = buf, *q = buf;
 266     ret.clear();
 267
 268     while (*p) {
 269         if (*p == '\'') {
 270             *p = '\0';
 271             unsigned s = CPinyinData::encodeSyllable(q);
 272             if (s)
 273                 ret.push_back(TSyllable(s));
 274             else
 275                 printf("\nWarning! unrecognized syllable %s", q);
 276             q = p + 1;
 277         }
 278         p++;
 279     }
 280
 281     if (*q) {
 282         unsigned s = CPinyinData::encodeSyllable(q);
 283         if (s)
 284             ret.push_back(TSyllable(s));
 285         else
 286             printf("\nWarning! unrecognized syllable %s", q);
 287     }
 288
 289     free(buf);
 290 }
 291
 292 CPinyinTrieMaker::TNode*
 293 CPinyinTrieMaker::insertTransfer(TNode* pnode, unsigned s)
 294 {
 295     CTrans::const_iterator itt = pnode->m_Trans.find(s);
 296     CTrans::const_iterator ite = pnode->m_Trans.end();
 297     if (itt == ite) {
 298         TNode *p = new TNode();
 299         p->m_bFullSyllableTransfer = true;
 300         p->m_bExpanded = true;
 301         pnode->m_Trans[s] = p;
 302         return p;
 303     }
 304     return itt->second;
 305 }
 306
 307 bool
 308 CPinyinTrieMaker::insertFullPinyinPair(const char* pinyin, TWordId wid)
 309 {
 310     TNode *pnode = &m_RootNode;
 311     std::vector<TSyllable> syllables;
 312     parseFullPinyin(pinyin, syllables);
 313
 314     if (syllables.empty())
 315         return true;
 316
 317     std::vector<TSyllable>::const_iterator it = syllables.begin();
 318     std::vector<TSyllable>::const_iterator ite = syllables.end();
 319
 320     for (; it != ite; ++it)
 321         pnode = insertTransfer(pnode, *it);
 322
 323     insertWordId(pnode->m_WordIdSet, wid);
 324     return true;
 325 }
 326
 327 CPinyinTrieMaker::TNode*
 328 CPinyinTrieMaker::addCombinedTransfers(TNode *pnode,
 329                                        unsigned s,
 330                                        const CNodeSet& nodes)
 331 {
 332     assert(!nodes.empty());
 333
 334     TNode *p = NULL;
 335     if (nodes.size() == 1) {
 336         p = *(nodes.begin());
 337     } else {
 338         p = new TNode();
 339         p->m_cmbNodes = nodes;
 340         m_StateMap[&p->m_cmbNodes] = p;
 341
 342         CNodeSet::const_iterator it = nodes.begin();
 343         CNodeSet::const_iterator ite = nodes.end();
 344         for (; it != ite; ++it) {
 345             CWordSet::const_iterator wit  = (*it)->m_WordIdSet.begin();
 346             CWordSet::const_iterator wite = (*it)->m_WordIdSet.end();
 347
 348             for (; wit != wite; ++wit) {
 349                 CWordSet::iterator tmp = p->m_WordIdSet.find (*wit);
 350
 351                 if (tmp == p->m_WordIdSet.end()) {
 352                     p->m_WordIdSet.insert (*wit);
 353                 } else if (tmp->anony.m_cost > wit->anony.m_cost) {
 354                     p->m_WordIdSet.erase (tmp);
 355                     p->m_WordIdSet.insert (*wit);
 356                 }
 357             }
 358         }
 359     }
 360
 361     pnode->m_Trans[s] = p;
 362     return p;
 363 }
 364
 365 void
 366 CPinyinTrieMaker::combineInitialTrans(TNode *pnode)
 367 {
 368     std::map<unsigned, CNodeSet> combTrans;
 369
 370     CTrans::const_iterator itTrans = pnode->m_Trans.begin();
 371     CTrans::const_iterator itTransLast = pnode->m_Trans.end();
 372     for (; itTrans != itTransLast; ++itTrans) {
 373         TSyllable s = (TSyllable)itTrans->first;
 374         if (s.initial) {
 375             s.final = s.tone = 0;
 376             combTrans[s].insert(itTrans->second);
 377         }
 378     }
 379
 380     std::map<unsigned, CNodeSet>::const_iterator itCombTrans = combTrans.begin();
 381     for (; itCombTrans != combTrans.end(); ++itCombTrans)
 382         addCombinedTransfers(pnode, itCombTrans->first, itCombTrans->second);
 383 }
 384
 385 void
 386 CPinyinTrieMaker::expandCombinedNode(TNode *pnode)
 387 {
 388     assert(pnode->m_cmbNodes.size() >= 1);
 389
 390     std::map<unsigned, CNodeSet> combTrans;
 391     CNodeSet::const_iterator itNode = pnode->m_cmbNodes.begin();
 392     CNodeSet::const_iterator itNodeLast = pnode->m_cmbNodes.end();
 393     for (; itNode != itNodeLast; ++itNode) {
 394         CTrans::const_iterator itTrans = (*itNode)->m_Trans.begin();
 395         CTrans::const_iterator itTransLast = (*itNode)->m_Trans.end();
 396         for (; itTrans != itTransLast; ++itTrans)
 397             combTrans[itTrans->first].insert(itTrans->second);
 398     }
 399
 400     std::map<unsigned, CNodeSet>::const_iterator itCombTrans = combTrans.begin();
 401     for (; itCombTrans != combTrans.end(); ++itCombTrans) {
 402         TNode* p = NULL;
 403         unsigned s = itCombTrans->first;
 404         CNodeSet nodes = itCombTrans->second;
 405
 406         CStateMap::const_iterator itStateMap = m_StateMap.find(&nodes);
 407         if (itStateMap != m_StateMap.end())
 408             p = itStateMap->second;
 409         else
 410             p = addCombinedTransfers(pnode, s, nodes);
 411
 412         pnode->m_Trans[s] = p;
 413     }
 414
 415     pnode->m_bExpanded = true;
 416 }
 417
 418 bool
 419 CPinyinTrieMaker::threadNonCompletePinyin(void)
 420 {
 421     CNodeList::const_iterator itNode = TNode::m_AllNodes.begin();
 422     for (; itNode != TNode::m_AllNodes.end(); ++itNode) {
 423         TNode* pnode = *itNode;
 424         if (pnode->m_bExpanded)
 425             combineInitialTrans(pnode);
 426         else
 427             expandCombinedNode(pnode);
 428     }
 429     return true;
 430 }
 431
 432 bool
 433 CPinyinTrieMaker::write(const char* fileName, CWordEvaluator* psrt,
 434                         bool revert_endian)
 435 {
 436     bool suc = false;
 437     FILE* fp = fopen(fileName, "wb");
 438     if (fp != NULL) {
 439         suc = write(fp, psrt, revert_endian);
 440         fclose(fp);
 441     }
 442     return suc;
 443 }
 444
 445 bool
 446 CPinyinTrieMaker::write(FILE *fp, CWordEvaluator* psrt, bool revert_endian)
 447 {
 448     bool suc = true;
 449     static TWCHAR wbuf[1024];
 450
 451     std::map<TNode*, unsigned int> nodeOffsetMap;
 452
 453     unsigned int nWord = m_Lexicon.size();
 454     unsigned int nNode = TNode::m_AllNodes.size();
 455     unsigned int lexiconOffset;
 456     unsigned int offset = sizeof(unsigned int) * 3;
 457
 458     CNodeList::const_iterator itNode = TNode::m_AllNodes.begin();
 459     CNodeList::const_iterator itNodeLast = TNode::m_AllNodes.end();
 460     for (; itNode != itNodeLast; ++itNode) {
 461         nodeOffsetMap[*itNode] = offset;
 462         offset += CPinyinTrie::TNode::size_for((*itNode)->m_Trans.size(),
 463                                                (*itNode)->m_WordIdSet.size());
 464     }
 465     lexiconOffset = offset;
 466     CLexicon::const_iterator itWordStr = m_Lexicon.begin();
 467     CLexicon::const_iterator itWordStrLast = m_Lexicon.end();
 468     for (; itWordStr != itWordStrLast; ++itWordStr) {
 469         MBSTOWCS(wbuf, itWordStr->c_str(), 1024);
 470         int sz = WCSLEN(wbuf);
 471         offset += (sz + 1) * sizeof(TWCHAR);
 472     }
 473
 474     Writer f(fp, revert_endian);
 475
 476     suc = f.write(nWord);
 477     suc = f.write(nNode);
 478     suc = f.write(lexiconOffset);
 479
 480     itNode = TNode::m_AllNodes.begin();
 481     itNodeLast = TNode::m_AllNodes.end();
 482
 483     for (; itNode != itNodeLast && suc; ++itNode) {
 484         CPinyinTrie::TNode outNode;
 485         TNode *pnode = *itNode;
 486
 487         outNode.m_nTransfer = pnode->m_Trans.size();
 488         outNode.m_nWordId = pnode->m_WordIdSet.size();
 489         outNode.m_bFullSyllableTransfer = pnode->m_bFullSyllableTransfer;
 490         outNode.m_csLevel = 0;
 491
 492         CWordSet::const_iterator itId = pnode->m_WordIdSet.begin();
 493         CWordSet::const_iterator itIdLast = pnode->m_WordIdSet.end();
 494         for (; itId != itIdLast && outNode.m_csLevel < 3; ++itId) {
 495             if (outNode.m_csLevel < itId->anony.m_csLevel)
 496                 outNode.m_csLevel = itId->anony.m_csLevel;
 497         }
 498
 499         suc = f.write(outNode);
 500
 501         CTrans::const_iterator itTrans = pnode->m_Trans.begin();
 502         CTrans::const_iterator itTransLast = pnode->m_Trans.end();
 503         for (; itTrans != itTransLast && suc; ++itTrans) {
 504             CPinyinTrie::TTransUnit tru;
 505             tru.m_Syllable = itTrans->first;
 506             tru.m_Offset = nodeOffsetMap[itTrans->second];
 507             assert(tru.m_Offset != 0 && tru.m_Offset < lexiconOffset);
 508             suc = f.write(tru);
 509         }
 510
 511         CWordVec vec;
 512         itId = pnode->m_WordIdSet.begin();
 513         itIdLast = pnode->m_WordIdSet.end();
 514         for (; itId != itIdLast; ++itId)
 515             vec.push_back(TWordInfo(*itId, psrt->getCost(*itId) + itId->anony.m_cost,
 516                                     psrt->isSeen(*itId)));
 517         std::make_heap(vec.begin(), vec.end());
 518         std::sort_heap(vec.begin(), vec.end());
 519
 520         CWordVec::const_iterator itv = vec.begin();
 521         CWordVec::const_iterator itve = vec.end();
 522         for (; itv != itve && suc; ++itv) {
 523             CPinyinTrie::TWordIdInfo wi;
 524             wi.m_id = itv->m_id.anony.m_id;
 525             assert(wi.m_id < nWord);
 526             wi.m_csLevel = itv->m_id.anony.m_csLevel;
 527             wi.m_bSeen = ((itv->m_bSeen) ? (1) : (0));
 528             wi.m_cost = itv->m_id.anony.m_cost;
 529             suc = f.write(wi);
 530         }
 531     }
 532
 533     itWordStr = m_Lexicon.begin();
 534     itWordStrLast = m_Lexicon.end();
 535     for (; itWordStr != itWordStrLast && suc; ++itWordStr) {
 536         MBSTOWCS(wbuf, itWordStr->c_str(), 1024);
 537         int sz = WCSLEN(wbuf);
 538         suc = f.write(wbuf, (sz + 1));
 539     }
 540     return suc;
 541 }