src/lexicon/pytrie.h

   1 // -*- mode: c++ -*-
   2 #ifndef __SUNPINYIN_PYTRIE_H__
   3 #define __SUNPINYIN_PYTRIE_H__
   4
   5 #ifdef HAVE_CONFIG_H
   6 #include <config.h>
   7 #endif
   8
   9 #include "../portability.h"
  10 #include "pinyin/syllable.h"
  11 #include <map>
  12
  13 #define WORD_ID_WIDTH       24
  14
  15 class CPinyinTrie {
  16 public:
  17     friend class CPinyinTrieMaker;
  18
  19     struct TTransUnit {
  20         TSyllable m_Syllable;
  21         unsigned m_Offset;
  22     };
  23
  24     struct TWordIdInfo {
  25     #ifdef WORDS_BIGENDIAN
  26         unsigned m_bSeen    : 1;
  27         unsigned m_cost     : 5;
  28         unsigned m_csLevel  : 2;
  29         unsigned m_id       : WORD_ID_WIDTH;
  30     #else
  31         unsigned m_id       : WORD_ID_WIDTH;
  32         unsigned m_csLevel  : 2;
  33         unsigned m_cost     : 5;
  34         unsigned m_bSeen    : 1;
  35     #endif
  36
  37         TWordIdInfo() { memset(this, 0, sizeof(TWordIdInfo)); }
  38
  39         TWordIdInfo(unsigned id,
  40                     unsigned len = 0,
  41                     unsigned seen = 0,
  42                     unsigned cost = 0,
  43                     unsigned cslvl = 0)
  44             : m_id(id), m_csLevel(cslvl), m_cost(cost), m_bSeen(seen) { }
  45
  46         operator unsigned int() const { return m_id; }
  47     };
  48
  49     struct TNode {
  50     #ifdef WORDS_BIGENDIAN
  51         unsigned m_other      : 5;
  52         unsigned m_bFullSyllableTransfer : 1;
  53         unsigned m_csLevel    : 2;
  54         unsigned m_nTransfer  : 12;
  55         unsigned m_nWordId    : 12;
  56     #else
  57         unsigned m_nWordId    : 12;
  58         unsigned m_nTransfer  : 12;
  59         unsigned m_csLevel    : 2;
  60         unsigned m_bFullSyllableTransfer : 1;
  61         unsigned m_other      : 5;
  62     #endif
  63
  64         static unsigned int size_for(unsigned int nTransfer,
  65                                      unsigned int nWordId)                    {
  66             return sizeof(TNode) + sizeof(TTransUnit) * nTransfer +
  67                    sizeof(TWordIdInfo) * nWordId;
  68         }
  69
  70         TNode()
  71         { *((unsigned *) this) = 0; }
  72
  73         bool hasPinyinChild(void) const
  74         { return(m_nTransfer > 1); }
  75
  76         const TTransUnit*getTrans() const
  77         { return (TTransUnit *) (this + 1); }
  78
  79         const TWordIdInfo*getWordIdPtr() const
  80         { return (TWordIdInfo *) (((char *) (this +
  81                                              1)) + sizeof(TTransUnit) *
  82                                   m_nTransfer); }
  83
  84         unsigned int transfer(unsigned s) const {
  85             unsigned int b = 0, e = m_nTransfer;
  86             const TTransUnit* ptrans = getTrans();
  87             while (b < e) {
  88                 int m = b + (e - b) / 2;
  89                 if (ptrans[m].m_Syllable == s)
  90                     return ptrans[m].m_Offset;
  91                 if (ptrans[m].m_Syllable < s)
  92                     b = m + 1;
  93                 else
  94                     e = m;
  95             }
  96             return 0;
  97         }
  98     };
  99
 100 public:
 101     CPinyinTrie() : m_Size(0), m_mem(NULL), m_words(NULL) { }
 102
 103     ~CPinyinTrie()
 104     { free(); }
 105
 106     bool
 107     load(const char* fileName);
 108
 109     void
 110     free(void);
 111
 112     bool
 113     isValid(const TNode* pnode, bool allowNonComplete, unsigned csLevel = 0);
 114
 115     unsigned int getRootOffset() const
 116     { return 3 * sizeof(unsigned int); }
 117
 118     const TNode*getRootNode() const
 119     { return (TNode *) (m_mem + getRootOffset()); }
 120
 121     const TNode*nodeFromOffset(unsigned int offset) const
 122     { return (offset < getRootOffset()) ? NULL : ((TNode *) (m_mem + offset)); }
 123
 124     unsigned int getWordCount(void) const
 125     { return *(unsigned int *) m_mem; }
 126
 127     unsigned int getNodeCount(void) const
 128     { return *(unsigned int *) (m_mem + sizeof(unsigned int)); }
 129
 130     unsigned int getStringOffset(void) const
 131     { return *(unsigned int *) (m_mem + 2 * sizeof(unsigned int)); }
 132
 133     inline const TNode*transfer(const TNode* pnode, unsigned s) const
 134     { return nodeFromOffset(pnode->transfer(s)); }
 135
 136     inline const TNode*transfer(unsigned s) const
 137     { return transfer(getRootNode(), s); }
 138
 139     unsigned int
 140     getSymbolId(const TWCHAR* wstr);
 141
 142     unsigned int
 143     getSymbolId(const wstring & wstr);
 144
 145     const TWCHAR*operator[](unsigned int idx) const
 146     { return m_words[idx]; }
 147
 148     int
 149     lengthAt(unsigned int idx) const;
 150
 151     void
 152     print(FILE *fp) const;
 153
 154 protected:
 155     unsigned int m_Size;
 156     char                  *m_mem;
 157     TWCHAR               **m_words;
 158
 159     std::map<wstring, unsigned>  m_SymbolMap;
 160
 161     void
 162     print(const TNode* pRoot, std::string& prefix, FILE *fp) const;
 163 };
 164
 165 #endif /* __SUNPINYIN_PYTRIE_H__*/