packages/inputmethods/PinyinIME/jni/share/spellingtable.cpp

   1 /*
   2  * Copyright (C) 2009 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <assert.h>
  18 #include <stdlib.h>
  19 #include <stdio.h>
  20 #include <string.h>
  21 #include <math.h>
  22 #include "../include/spellingtable.h"
  23
  24 namespace ime_pinyin {
  25
  26 #ifdef ___BUILD_MODEL___
  27
  28 const char SpellingTable::
  29     kNotSupportList[kNotSupportNum][kMaxSpellingSize + 1] = {"HM", "HNG", "NG"};
  30
  31 // "" is the biggest, so that all empty strings will be moved to the end
  32 // _eb mean empty is biggest
  33 int compare_raw_spl_eb(const void* p1, const void* p2) {
  34   if ('\0' == (static_cast<const RawSpelling*>(p1))->str[0])
  35     return 1;
  36
  37   if ('\0' == (static_cast<const RawSpelling*>(p2))->str[0])
  38     return -1;
  39
  40   return strcmp((static_cast<const RawSpelling*>(p1))->str,
  41                 (static_cast<const RawSpelling*>(p2))->str);
  42 }
  43
  44 size_t get_odd_next(size_t value) {
  45   size_t v_next = value;
  46   while (true) {
  47     size_t v_next_sqrt = (size_t)sqrt(v_next);
  48
  49     bool is_odd = true;
  50     for (size_t v_dv = 2; v_dv < v_next_sqrt + 1; v_dv++) {
  51       if (v_next % v_dv == 0) {
  52         is_odd = false;
  53         break;
  54       }
  55     }
  56
  57     if (is_odd)
  58       return v_next;
  59
  60     v_next++;
  61   }
  62
  63   // never reach here
  64   return 0;
  65 }
  66
  67 SpellingTable::SpellingTable() {
  68   need_score_ = false;
  69   raw_spellings_ = NULL;
  70   spelling_buf_ = NULL;
  71   spelling_num_ = 0;
  72   total_freq_ = 0;
  73   frozen_ = true;
  74 }
  75
  76 SpellingTable::~SpellingTable() {
  77   free_resource();
  78 }
  79
  80 size_t SpellingTable::get_hash_pos(const char* spelling_str) {
  81   size_t hash_pos = 0;
  82   for (size_t pos = 0; pos < spelling_size_; pos++) {
  83     if ('\0' == spelling_str[pos])
  84       break;
  85     hash_pos += (size_t)spelling_str[pos];
  86   }
  87
  88   hash_pos = hash_pos % spelling_max_num_;
  89   return hash_pos;
  90 }
  91
  92 size_t SpellingTable::hash_pos_next(size_t hash_pos) {
  93   hash_pos += 123;
  94   hash_pos = hash_pos % spelling_max_num_;
  95   return hash_pos;
  96 }
  97
  98 void SpellingTable::free_resource() {
  99   if (NULL != raw_spellings_)
 100     delete [] raw_spellings_;
 101   raw_spellings_ = NULL;
 102
 103   if (NULL != spelling_buf_)
 104     delete [] spelling_buf_;
 105   spelling_buf_ = NULL;
 106 }
 107
 108 bool SpellingTable::init_table(size_t pure_spl_size, size_t spl_max_num,
 109                                bool need_score) {
 110   if (pure_spl_size == 0 || spl_max_num ==0)
 111     return false;
 112
 113   need_score_ = need_score;
 114
 115   free_resource();
 116
 117   spelling_size_ = pure_spl_size + 1;
 118   if (need_score)
 119     spelling_size_ += 1;
 120   spelling_max_num_ = get_odd_next(spl_max_num);
 121   spelling_num_ = 0;
 122
 123   raw_spellings_ = new RawSpelling[spelling_max_num_];
 124   spelling_buf_ = new char[spelling_max_num_ * (spelling_size_)];
 125   if (NULL == raw_spellings_ || NULL == spelling_buf_) {
 126     free_resource();
 127     return false;
 128   }
 129
 130   memset(raw_spellings_, 0, spelling_max_num_ * sizeof(RawSpelling));
 131   memset(spelling_buf_, 0, spelling_max_num_ * (spelling_size_));
 132   frozen_ = false;
 133   total_freq_ = 0;
 134   return true;
 135 }
 136
 137 bool SpellingTable::put_spelling(const char* spelling_str, double freq) {
 138   if (frozen_ || NULL == spelling_str)
 139     return false;
 140
 141   for (size_t pos = 0; pos < kNotSupportNum; pos++) {
 142     if (strcmp(spelling_str, kNotSupportList[pos]) == 0) {
 143       return false;
 144     }
 145   }
 146
 147   total_freq_ += freq;
 148
 149   size_t hash_pos = get_hash_pos(spelling_str);
 150
 151   raw_spellings_[hash_pos].str[spelling_size_ - 1] = '\0';
 152
 153   if (strncmp(raw_spellings_[hash_pos].str, spelling_str,
 154               spelling_size_ - 1) == 0) {
 155     raw_spellings_[hash_pos].freq += freq;
 156     return true;
 157   }
 158
 159   size_t hash_pos_ori = hash_pos;
 160
 161   while (true) {
 162     if (strncmp(raw_spellings_[hash_pos].str,
 163                 spelling_str, spelling_size_ - 1) == 0) {
 164       raw_spellings_[hash_pos].freq += freq;
 165       return true;
 166     }
 167
 168     if ('\0' == raw_spellings_[hash_pos].str[0]) {
 169       raw_spellings_[hash_pos].freq += freq;
 170       strncpy(raw_spellings_[hash_pos].str, spelling_str, spelling_size_ - 1);
 171       raw_spellings_[hash_pos].str[spelling_size_ - 1] = '\0';
 172       spelling_num_++;
 173       return true;
 174     }
 175
 176     hash_pos = hash_pos_next(hash_pos);
 177     if (hash_pos_ori == hash_pos)
 178       return false;
 179   }
 180
 181   // never reach here
 182   return false;
 183 }
 184
 185 bool SpellingTable::contain(const char* spelling_str) {
 186   if (NULL == spelling_str || NULL == spelling_buf_ || frozen_)
 187     return false;
 188
 189   size_t hash_pos = get_hash_pos(spelling_str);
 190
 191   if ('\0' == raw_spellings_[hash_pos].str[0])
 192     return false;
 193
 194   if (strncmp(raw_spellings_[hash_pos].str, spelling_str, spelling_size_ - 1)
 195       == 0)
 196     return true;
 197
 198   size_t hash_pos_ori = hash_pos;
 199
 200   while (true) {
 201     hash_pos = hash_pos_next(hash_pos);
 202     if (hash_pos_ori == hash_pos)
 203       return false;
 204
 205     if ('\0' == raw_spellings_[hash_pos].str[0])
 206       return false;
 207
 208     if (strncmp(raw_spellings_[hash_pos].str, spelling_str, spelling_size_ - 1)
 209         == 0)
 210       return true;
 211   }
 212
 213   // never reach here
 214   return false;
 215 }
 216
 217 const char* SpellingTable::arrange(size_t *item_size, size_t *spl_num) {
 218   if (NULL == raw_spellings_ || NULL == spelling_buf_ ||
 219       NULL == item_size || NULL == spl_num)
 220     return NULL;
 221
 222   qsort(raw_spellings_, spelling_max_num_, sizeof(RawSpelling),
 223         compare_raw_spl_eb);
 224
 225   // After sorting, only the first spelling_num_ items are valid.
 226   // Copy them to the destination buffer.
 227   for (size_t pos = 0; pos < spelling_num_; pos++) {
 228     strncpy(spelling_buf_ + pos * spelling_size_, raw_spellings_[pos].str,
 229             spelling_size_);
 230   }
 231
 232   if (need_score_) {
 233     if (kPrintDebug0)
 234       printf("------------Spelling Possiblities--------------\n");
 235
 236     double max_score = 0;
 237     double min_score = 0;
 238
 239     // After sorting, only the first spelling_num_ items are valid.
 240     for (size_t pos = 0; pos < spelling_num_; pos++) {
 241       raw_spellings_[pos].freq /= total_freq_;
 242       if (need_score_) {
 243         if (0 == pos) {
 244           max_score = raw_spellings_[0].freq;
 245           min_score = max_score;
 246         } else {
 247           if (raw_spellings_[pos].freq > max_score)
 248             max_score = raw_spellings_[pos].freq;
 249           if (raw_spellings_[pos].freq < min_score)
 250             min_score = raw_spellings_[pos].freq;
 251         }
 252       }
 253     }
 254
 255     if (kPrintDebug0)
 256       printf("-----max psb: %f, min psb: %f\n", max_score, min_score);
 257
 258     max_score = log(max_score);
 259     min_score = log(min_score);
 260
 261     if (kPrintDebug0)
 262       printf("-----max log value: %f, min log value: %f\n",
 263              max_score, min_score);
 264
 265     // The absolute value of min_score is bigger than that of max_score because
 266     // both of them are negative after log function.
 267     score_amplifier_ = 1.0 * 255 / min_score;
 268
 269     double average_score = 0;
 270     for (size_t pos = 0; pos < spelling_num_; pos++) {
 271       double score = log(raw_spellings_[pos].freq) * score_amplifier_;
 272       assert(score >= 0);
 273
 274       average_score += score;
 275
 276       // Because of calculation precision issue, score might be a little bigger
 277       // than 255 after being amplified.
 278       if (score > 255)
 279         score = 255;
 280       char *this_spl_buf = spelling_buf_ + pos * spelling_size_;
 281       this_spl_buf[spelling_size_ - 1] =
 282           static_cast<char>((unsigned char)score);
 283
 284       if (kPrintDebug0) {
 285         printf("---pos:%d, %s, psb:%d\n", pos, this_spl_buf,
 286                (unsigned char)this_spl_buf[spelling_size_ -1]);
 287       }
 288     }
 289     average_score /= spelling_num_;
 290     assert(average_score <= 255);
 291     average_score_ = static_cast<uint8>(average_score);
 292
 293     if (kPrintDebug0)
 294       printf("\n----Score Amplifier: %f, Average Score: %d\n", score_amplifier_,
 295              average_score_);
 296   }
 297
 298   *item_size = spelling_size_;
 299   *spl_num = spelling_num_;
 300   frozen_ = true;
 301   return spelling_buf_;
 302 }
 303
 304 float SpellingTable::get_score_amplifier() {
 305   return static_cast<float>(score_amplifier_);
 306 }
 307
 308 unsigned char SpellingTable::get_average_score() {
 309   return average_score_;
 310 }
 311
 312 #endif  // ___BUILD_MODEL___
 313 }  // namespace ime_pinyin