jni/share/dictbuilder.cpp

/*
 * Copyright (C) 2009 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "../include/dictbuilder.h"
#include "../include/dicttrie.h"
#include "../include/mystdlib.h"
#include "../include/ngram.h"
#include "../include/searchutility.h"
#include "../include/spellingtable.h"
#include "../include/spellingtrie.h"
#include "../include/splparser.h"
#include "../include/utf16reader.h"

namespace ime_pinyin {

#ifdef ___BUILD_MODEL___

static const size_t kReadBufLen = 512;
static const size_t kSplTableHashLen = 2000;

// Compare a SingleCharItem, first by Hanzis, then by spelling ids, then by
// frequencies.
int cmp_scis_hz_splid_freq(const void* p1, const void* p2) {
  const SingleCharItem *s1, *s2;
  s1 = static_cast<const SingleCharItem*>(p1);
  s2 = static_cast<const SingleCharItem*>(p2);

  if (s1->hz < s2->hz)
    return -1;
  if (s1->hz > s2->hz)
    return 1;

  if (s1->splid.half_splid < s2->splid.half_splid)
    return -1;
  if (s1->splid.half_splid > s2->splid.half_splid)
    return 1;

  if (s1->splid.full_splid < s2->splid.full_splid)
    return -1;
  if (s1->splid.full_splid > s2->splid.full_splid)
    return 1;

  if (s1->freq > s2->freq)
    return -1;
  if (s1->freq < s2->freq)
    return 1;
  return 0;
}

int cmp_scis_hz_splid(const void* p1, const void* p2) {
  const SingleCharItem *s1, *s2;
  s1 = static_cast<const SingleCharItem*>(p1);
  s2 = static_cast<const SingleCharItem*>(p2);

  if (s1->hz < s2->hz)
    return -1;
  if (s1->hz > s2->hz)
    return 1;

  if (s1->splid.half_splid < s2->splid.half_splid)
    return -1;
  if (s1->splid.half_splid > s2->splid.half_splid)
    return 1;

  if (s1->splid.full_splid < s2->splid.full_splid)
    return -1;
  if (s1->splid.full_splid > s2->splid.full_splid)
    return 1;

  return 0;
}

int cmp_lemma_entry_hzs(const void* p1, const void* p2) {
  size_t size1 = utf16_strlen(((const LemmaEntry*)p1)->hanzi_str);
  size_t size2 = utf16_strlen(((const LemmaEntry*)p2)->hanzi_str);
  if (size1 < size2)
    return -1;
  else if (size1 > size2)
    return 1;

  return utf16_strcmp(((const LemmaEntry*)p1)->hanzi_str,
                      ((const LemmaEntry*)p2)->hanzi_str);
}

int compare_char16(const void* p1, const void* p2) {
  if (*((const char16*)p1) < *((const char16*)p2))
    return -1;
  if (*((const char16*)p1) > *((const char16*)p2))
    return 1;
  return 0;
}

int compare_py(const void* p1, const void* p2) {
  int ret = utf16_strcmp(((const LemmaEntry*)p1)->spl_idx_arr,
                         ((const LemmaEntry*)p2)->spl_idx_arr);

  if (0 != ret)
    return ret;

  return static_cast<int>(((const LemmaEntry*)p2)->freq) -
         static_cast<int>(((const LemmaEntry*)p1)->freq);
}

// First hanzi, if the same, then Pinyin
int cmp_lemma_entry_hzspys(const void* p1, const void* p2) {
  size_t size1 = utf16_strlen(((const LemmaEntry*)p1)->hanzi_str);
  size_t size2 = utf16_strlen(((const LemmaEntry*)p2)->hanzi_str);
  if (size1 < size2)
    return -1;
  else if (size1 > size2)
    return 1;
  int ret = utf16_strcmp(((const LemmaEntry*)p1)->hanzi_str,
                         ((const LemmaEntry*)p2)->hanzi_str);

  if (0 != ret)
    return ret;

  ret = utf16_strcmp(((const LemmaEntry*)p1)->spl_idx_arr,
                     ((const LemmaEntry*)p2)->spl_idx_arr);
  return ret;
}

int compare_splid2(const void* p1, const void* p2) {
  int ret = utf16_strcmp(((const LemmaEntry*)p1)->spl_idx_arr,
                         ((const LemmaEntry*)p2)->spl_idx_arr);
  return ret;
}

DictBuilder::DictBuilder() {
  lemma_arr_ = NULL;
  lemma_num_ = 0;

  scis_ = NULL;
  scis_num_ = 0;

  lma_nodes_le0_ = NULL;
  lma_nodes_ge1_ = NULL;

  lma_nds_used_num_le0_ = 0;
  lma_nds_used_num_ge1_ = 0;

  homo_idx_buf_ = NULL;
  homo_idx_num_eq1_ = 0;
  homo_idx_num_gt1_ = 0;

  top_lmas_ = NULL;
  top_lmas_num_ = 0;

  spl_table_ = NULL;
  spl_parser_ = NULL;
}

DictBuilder::~DictBuilder() {
  free_resource();
}

bool DictBuilder::alloc_resource(size_t lma_num) {
  if (0 == lma_num)
    return false;

  free_resource();

  lemma_num_ = lma_num;
  lemma_arr_ = new LemmaEntry[lemma_num_];

  top_lmas_num_ = 0;
  top_lmas_ = new LemmaEntry[kTopScoreLemmaNum];

  // New the scis_ buffer to the possible maximum size.
  scis_num_ = lemma_num_ * kMaxLemmaSize;
  scis_ = new SingleCharItem[scis_num_];

  // The root and first level nodes is less than kMaxSpellingNum + 1
  lma_nds_used_num_le0_ = 0;
  lma_nodes_le0_ = new LmaNodeLE0[kMaxSpellingNum + 1];

  // Other nodes is less than lemma_num
  lma_nds_used_num_ge1_ = 0;
  lma_nodes_ge1_ = new LmaNodeGE1[lemma_num_];

  homo_idx_buf_ = new LemmaIdType[lemma_num_];
  spl_table_ = new SpellingTable();
  spl_parser_ = new SpellingParser();

  if (NULL == lemma_arr_ || NULL == top_lmas_ ||
      NULL == scis_ || NULL == spl_table_ ||
      NULL == spl_parser_ || NULL == lma_nodes_le0_ ||
      NULL == lma_nodes_ge1_ || NULL == homo_idx_buf_) {
    free_resource();
    return false;
  }

  memset(lemma_arr_, 0, sizeof(LemmaEntry) * lemma_num_);
  memset(scis_, 0, sizeof(SingleCharItem) * scis_num_);
  memset(lma_nodes_le0_, 0, sizeof(LmaNodeLE0) * (kMaxSpellingNum + 1));
  memset(lma_nodes_ge1_, 0, sizeof(LmaNodeGE1) * lemma_num_);
  memset(homo_idx_buf_, 0, sizeof(LemmaIdType) * lemma_num_);
  spl_table_->init_table(kMaxPinyinSize, kSplTableHashLen, true);

  return true;
}

char16* DictBuilder::read_valid_hanzis(const char *fn_validhzs, size_t *num) {
  if (NULL == fn_validhzs || NULL == num)
    return NULL;

  *num = 0;
  FILE *fp = fopen(fn_validhzs, "rb");
  if (NULL == fp)
    return NULL;

  char16 utf16header;
  if (fread(&utf16header, sizeof(char16), 1, fp) != 1 ||
      0xfeff != utf16header) {
    fclose(fp);
    return NULL;
  }

  fseek(fp, 0, SEEK_END);
  *num = ftell(fp) / sizeof(char16);
  assert(*num >= 1);
  *num -= 1;

  char16 *hzs = new char16[*num];
  if (NULL == hzs) {
    fclose(fp);
    return NULL;
  }

  fseek(fp, 2, SEEK_SET);

  if (fread(hzs, sizeof(char16), *num, fp) != *num) {
    fclose(fp);
    delete [] hzs;
    return NULL;
  }
  fclose(fp);

  myqsort(hzs, *num, sizeof(char16), compare_char16);
  return hzs;
}

bool DictBuilder::hz_in_hanzis_list(const char16 *hzs, size_t hzs_len,
                                    char16 hz) {
  if (NULL == hzs)
    return false;

  char16 *found;
  found = static_cast<char16*>(
      mybsearch(&hz, hzs, hzs_len, sizeof(char16), compare_char16));
  if (NULL == found)
    return false;

  assert(*found == hz);
  return true;
}

// The caller makes sure that the parameters are valid.
bool DictBuilder::str_in_hanzis_list(const char16 *hzs, size_t hzs_len,
                                     const char16 *str, size_t str_len) {
  if (NULL == hzs || NULL == str)
    return false;

  for (size_t pos = 0; pos < str_len; pos++) {
    if (!hz_in_hanzis_list(hzs, hzs_len, str[pos]))
      return false;
  }
  return true;
}

void DictBuilder::get_top_lemmas() {
  top_lmas_num_ = 0;
  if (NULL == lemma_arr_)
    return;

  for (size_t pos = 0; pos < lemma_num_; pos++) {
    if (0 == top_lmas_num_) {
      top_lmas_[0] = lemma_arr_[pos];
      top_lmas_num_ = 1;
      continue;
    }

    if (lemma_arr_[pos].freq > top_lmas_[top_lmas_num_ - 1].freq) {
      if (kTopScoreLemmaNum > top_lmas_num_)
        top_lmas_num_ += 1;

      size_t move_pos;
      for (move_pos = top_lmas_num_ - 1; move_pos > 0; move_pos--) {
        top_lmas_[move_pos] = top_lmas_[move_pos - 1];
        if (0 == move_pos - 1 ||
            (move_pos - 1 > 0 &&
             top_lmas_[move_pos - 2].freq > lemma_arr_[pos].freq)) {
          break;
        }
      }
      assert(move_pos > 0);
      top_lmas_[move_pos - 1] = lemma_arr_[pos];
    } else if (kTopScoreLemmaNum > top_lmas_num_) {
      top_lmas_[top_lmas_num_] = lemma_arr_[pos];
      top_lmas_num_ += 1;
    }
  }

  if (kPrintDebug0) {
    printf("\n------Top Lemmas------------------\n");
    for (size_t pos = 0; pos < top_lmas_num_; pos++) {
      printf("--%d, idx:%06d, score:%.5f\n", pos, top_lmas_[pos].idx_by_hz,
             top_lmas_[pos].freq);
    }
  }
}

void DictBuilder::free_resource() {
  if (NULL != lemma_arr_)
    delete [] lemma_arr_;

  if (NULL != scis_)
    delete [] scis_;

  if (NULL != lma_nodes_le0_)
    delete [] lma_nodes_le0_;

  if (NULL != lma_nodes_ge1_)
    delete [] lma_nodes_ge1_;

  if (NULL != homo_idx_buf_)
    delete [] homo_idx_buf_;

  if (NULL != spl_table_)
    delete spl_table_;

  if (NULL != spl_parser_)
    delete spl_parser_;

  lemma_arr_ = NULL;
  scis_ = NULL;
  lma_nodes_le0_ = NULL;
  lma_nodes_ge1_ = NULL;
  homo_idx_buf_ = NULL;
  spl_table_ = NULL;
  spl_parser_ = NULL;

  lemma_num_ = 0;
  lma_nds_used_num_le0_ = 0;
  lma_nds_used_num_ge1_ = 0;
  homo_idx_num_eq1_ = 0;
  homo_idx_num_gt1_ = 0;
}

size_t DictBuilder::read_raw_dict(const char* fn_raw,
                                  const char *fn_validhzs,
                                  size_t max_item) {
  if (NULL == fn_raw) return 0;

  Utf16Reader utf16_reader;
  if (!utf16_reader.open(fn_raw, kReadBufLen * 10))
    return false;

  char16 read_buf[kReadBufLen];

  // Read the number of lemmas in the file
  size_t lemma_num = 240000;

  // allocate resource required
  if (!alloc_resource(lemma_num)) {
    utf16_reader.close();
  }

  // Read the valid Hanzi list.
  char16 *valid_hzs = NULL;
  size_t valid_hzs_num = 0;
  valid_hzs = read_valid_hanzis(fn_validhzs, &valid_hzs_num);

  // Begin reading the lemma entries
  for (size_t i = 0; i < max_item; i++) {
    // read next entry
    if (!utf16_reader.readline(read_buf, kReadBufLen)) {
      lemma_num = i;
      break;
    }

    size_t token_size;
    char16 *token;
    char16 *to_tokenize = read_buf;

    // Get the Hanzi string
    token = utf16_strtok(to_tokenize, &token_size, &to_tokenize);
    if (NULL == token) {
      free_resource();
      utf16_reader.close();
      return false;
    }

    size_t lemma_size = utf16_strlen(token);

    if (lemma_size > kMaxLemmaSize) {
      i--;
      continue;
    }

    if (lemma_size > 4) {
      i--;
      continue;
    }

    // Copy to the lemma entry
    utf16_strcpy(lemma_arr_[i].hanzi_str, token);

    lemma_arr_[i].hz_str_len = token_size;

    // Get the freq string
    token = utf16_strtok(to_tokenize, &token_size, &to_tokenize);
    if (NULL == token) {
      free_resource();
      utf16_reader.close();
      return false;
    }
    lemma_arr_[i].freq = utf16_atof(token);

    if (lemma_size > 1 && lemma_arr_[i].freq < 60) {
      i--;
      continue;
    }

    // Get GBK mark, if no valid Hanzi list available, all items which contains
    // GBK characters will be discarded. Otherwise, all items which contains
    // characters outside of the valid Hanzi list will be discarded.
    token = utf16_strtok(to_tokenize, &token_size, &to_tokenize);
    assert(NULL != token);
    int gbk_flag = utf16_atoi(token);
    if (NULL == valid_hzs || 0 == valid_hzs_num) {
      if (0 != gbk_flag) {
        i--;
        continue;
      }
    } else {
      if (!str_in_hanzis_list(valid_hzs, valid_hzs_num,
          lemma_arr_[i].hanzi_str, lemma_arr_[i].hz_str_len)) {
        i--;
        continue;
      }
    }

    // Get spelling String
    bool spelling_not_support = false;
    for (size_t hz_pos = 0; hz_pos < (size_t)lemma_arr_[i].hz_str_len;
         hz_pos++) {
      // Get a Pinyin
      token = utf16_strtok(to_tokenize, &token_size, &to_tokenize);
      if (NULL == token) {
        free_resource();
        utf16_reader.close();
        return false;
      }

      assert(utf16_strlen(token) <= kMaxPinyinSize);

      utf16_strcpy_tochar(lemma_arr_[i].pinyin_str[hz_pos], token);

      format_spelling_str(lemma_arr_[i].pinyin_str[hz_pos]);

      // Put the pinyin to the spelling table
      if (!spl_table_->put_spelling(lemma_arr_[i].pinyin_str[hz_pos],
                                    lemma_arr_[i].freq)) {
        spelling_not_support = true;
        break;
      }
    }

    // The whole line must have been parsed fully, otherwise discard this one.
    token = utf16_strtok(to_tokenize, &token_size, &to_tokenize);
    if (spelling_not_support || NULL != token) {
      i--;
      continue;
    }
  }

  delete [] valid_hzs;
  utf16_reader.close();

  printf("read succesfully, lemma num: %d\n", lemma_num);

  return lemma_num;
}

bool DictBuilder::build_dict(const char *fn_raw,
                             const char *fn_validhzs,
                             DictTrie *dict_trie) {
  if (NULL == fn_raw || NULL == dict_trie)
    return false;

  lemma_num_ = read_raw_dict(fn_raw, fn_validhzs, 240000);
  if (0 == lemma_num_)
    return false;

  // Arrange the spelling table, and build a spelling tree
  // The size of an spelling. '\0' is included. If the spelling table is
  // initialized to calculate the spelling scores, the last char in the
  // spelling string will be score, and it is also included in spl_item_size.
  size_t spl_item_size;
  size_t spl_num;
  const char* spl_buf;
  spl_buf = spl_table_->arrange(&spl_item_size, &spl_num);
  if (NULL == spl_buf) {
    free_resource();
    return false;
  }

  SpellingTrie &spl_trie = SpellingTrie::get_instance();

  if (!spl_trie.construct(spl_buf, spl_item_size, spl_num,
                          spl_table_->get_score_amplifier(),
                          spl_table_->get_average_score())) {
    free_resource();
    return false;
  }

  printf("spelling tree construct successfully.\n");

  // Convert the spelling string to idxs
  for (size_t i = 0; i < lemma_num_; i++) {
    for (size_t hz_pos = 0; hz_pos < (size_t)lemma_arr_[i].hz_str_len;
         hz_pos++) {
      uint16 spl_idxs[2];
      uint16 spl_start_pos[3];
      bool is_pre = true;
      int spl_idx_num =
        spl_parser_->splstr_to_idxs(lemma_arr_[i].pinyin_str[hz_pos],
                                    strlen(lemma_arr_[i].pinyin_str[hz_pos]),
                                    spl_idxs, spl_start_pos, 2, is_pre);
      assert(1 == spl_idx_num);

      if (spl_trie.is_half_id(spl_idxs[0])) {
        uint16 num = spl_trie.half_to_full(spl_idxs[0], spl_idxs);
        assert(0 != num);
      }
      lemma_arr_[i].spl_idx_arr[hz_pos] = spl_idxs[0];
    }
  }

  // Sort the lemma items according to the hanzi, and give each unique item a
  // id
  sort_lemmas_by_hz();

  scis_num_ = build_scis();

  // Construct the dict list
  dict_trie->dict_list_ = new DictList();
  bool dl_success = dict_trie->dict_list_->init_list(scis_, scis_num_,
                                                     lemma_arr_, lemma_num_);
  assert(dl_success);

  // Construct the NGram information
  NGram& ngram = NGram::get_instance();
  ngram.build_unigram(lemma_arr_, lemma_num_,
                      lemma_arr_[lemma_num_ - 1].idx_by_hz + 1);

  // sort the lemma items according to the spelling idx string
  myqsort(lemma_arr_, lemma_num_, sizeof(LemmaEntry), compare_py);

  get_top_lemmas();

#ifdef ___DO_STATISTICS___
  stat_init();
#endif

  lma_nds_used_num_le0_ = 1;  // The root node
  bool dt_success = construct_subset(static_cast<void*>(lma_nodes_le0_),
                                     lemma_arr_, 0, lemma_num_, 0);
  if (!dt_success) {
    free_resource();
    return false;
  }

#ifdef ___DO_STATISTICS___
  stat_print();
#endif

  // Move the node data and homo data to the DictTrie
  dict_trie->root_ = new LmaNodeLE0[lma_nds_used_num_le0_];
  dict_trie->nodes_ge1_ = new LmaNodeGE1[lma_nds_used_num_ge1_];
  size_t lma_idx_num = homo_idx_num_eq1_ + homo_idx_num_gt1_ + top_lmas_num_;
  dict_trie->lma_idx_buf_ = new unsigned char[lma_idx_num * kLemmaIdSize];
  assert(NULL != dict_trie->root_);
  assert(NULL != dict_trie->lma_idx_buf_);
  dict_trie->lma_node_num_le0_ = lma_nds_used_num_le0_;
  dict_trie->lma_node_num_ge1_ = lma_nds_used_num_ge1_;
  dict_trie->lma_idx_buf_len_ = lma_idx_num * kLemmaIdSize;
  dict_trie->top_lmas_num_ = top_lmas_num_;

  memcpy(dict_trie->root_, lma_nodes_le0_,
         sizeof(LmaNodeLE0) * lma_nds_used_num_le0_);
  memcpy(dict_trie->nodes_ge1_, lma_nodes_ge1_,
         sizeof(LmaNodeGE1) * lma_nds_used_num_ge1_);

  for (size_t pos = 0; pos < homo_idx_num_eq1_ + homo_idx_num_gt1_; pos++) {
    id_to_charbuf(dict_trie->lma_idx_buf_ + pos * kLemmaIdSize,
                  homo_idx_buf_[pos]);
  }

  for (size_t pos = homo_idx_num_eq1_ + homo_idx_num_gt1_;
       pos < lma_idx_num; pos++) {
    LemmaIdType idx =
        top_lmas_[pos - homo_idx_num_eq1_ - homo_idx_num_gt1_].idx_by_hz;
    id_to_charbuf(dict_trie->lma_idx_buf_ + pos * kLemmaIdSize, idx);
  }

  if (kPrintDebug0) {
    printf("homo_idx_num_eq1_: %d\n", homo_idx_num_eq1_);
    printf("homo_idx_num_gt1_: %d\n", homo_idx_num_gt1_);
    printf("top_lmas_num_: %d\n", top_lmas_num_);
  }

  free_resource();

  if (kPrintDebug0) {
    printf("Building dict succeds\n");
  }
  return dt_success;
}

void DictBuilder::id_to_charbuf(unsigned char *buf, LemmaIdType id) {
  if (NULL == buf) return;
  for (size_t pos = 0; pos < kLemmaIdSize; pos++) {
    (buf)[pos] = (unsigned char)(id >> (pos * 8));
  }
}

void DictBuilder::set_son_offset(LmaNodeGE1 *node, size_t offset) {
  node->son_1st_off_l = static_cast<uint16>(offset);
  node->son_1st_off_h = static_cast<unsigned char>(offset >> 16);
}

void DictBuilder:: set_homo_id_buf_offset(LmaNodeGE1 *node, size_t offset) {
  node->homo_idx_buf_off_l = static_cast<uint16>(offset);
  node->homo_idx_buf_off_h = static_cast<unsigned char>(offset >> 16);

}

// All spelling strings will be converted to upper case, except that
// spellings started with "ZH"/"CH"/"SH" will be converted to
// "Zh"/"Ch"/"Sh"
void DictBuilder::format_spelling_str(char *spl_str) {
  if (NULL == spl_str)
    return;

  uint16 pos = 0;
  while ('\0' != spl_str[pos]) {
    if (spl_str[pos] >= 'a' && spl_str[pos] <= 'z')
      spl_str[pos] = spl_str[pos] - 'a' + 'A';

    if (1 == pos && 'H' == spl_str[pos]) {
      if ('C' == spl_str[0] || 'S' == spl_str[0] || 'Z' == spl_str[0]) {
        spl_str[pos] = 'h';
      }
    }
    pos++;
  }
}

LemmaIdType DictBuilder::sort_lemmas_by_hz() {
  if (NULL == lemma_arr_ || 0 == lemma_num_)
    return 0;

  myqsort(lemma_arr_, lemma_num_, sizeof(LemmaEntry), cmp_lemma_entry_hzs);

  lemma_arr_[0].idx_by_hz = 1;
  LemmaIdType idx_max = 1;
  for (size_t i = 1; i < lemma_num_; i++) {
    if (utf16_strcmp(lemma_arr_[i].hanzi_str, lemma_arr_[i-1].hanzi_str)) {
      idx_max++;
      lemma_arr_[i].idx_by_hz = idx_max;
    } else {
      idx_max++;
      lemma_arr_[i].idx_by_hz = idx_max;
    }
  }
  return idx_max + 1;
}

size_t DictBuilder::build_scis() {
  if (NULL == scis_ || lemma_num_ * kMaxLemmaSize > scis_num_)
    return 0;

  SpellingTrie &spl_trie = SpellingTrie::get_instance();

  // This first one is blank, because id 0 is invalid.
  scis_[0].freq = 0;
  scis_[0].hz = 0;
  scis_[0].splid.full_splid = 0;
  scis_[0].splid.half_splid = 0;
  scis_num_ = 1;

  // Copy the hanzis to the buffer
  for (size_t pos = 0; pos < lemma_num_; pos++) {
    size_t hz_num = lemma_arr_[pos].hz_str_len;
    for (size_t hzpos = 0; hzpos < hz_num; hzpos++) {
      scis_[scis_num_].hz = lemma_arr_[pos].hanzi_str[hzpos];
      scis_[scis_num_].splid.full_splid = lemma_arr_[pos].spl_idx_arr[hzpos];
      scis_[scis_num_].splid.half_splid =
          spl_trie.full_to_half(scis_[scis_num_].splid.full_splid);
      if (1 == hz_num)
        scis_[scis_num_].freq = lemma_arr_[pos].freq;
      else
        scis_[scis_num_].freq = 0.000001;
      scis_num_++;
    }
  }

  myqsort(scis_, scis_num_, sizeof(SingleCharItem), cmp_scis_hz_splid_freq);

  // Remove repeated items
  size_t unique_scis_num = 1;
  for (size_t pos = 1; pos < scis_num_; pos++) {
    if (scis_[pos].hz == scis_[pos - 1].hz &&
        scis_[pos].splid.full_splid == scis_[pos - 1].splid.full_splid)
      continue;
    scis_[unique_scis_num] = scis_[pos];
    scis_[unique_scis_num].splid.half_splid =
        spl_trie.full_to_half(scis_[pos].splid.full_splid);
    unique_scis_num++;
  }

  scis_num_ = unique_scis_num;

  // Update the lemma list.
  for (size_t pos = 0; pos < lemma_num_; pos++) {
    size_t hz_num = lemma_arr_[pos].hz_str_len;
    for (size_t hzpos = 0; hzpos < hz_num; hzpos++) {
      SingleCharItem key;
      key.hz = lemma_arr_[pos].hanzi_str[hzpos];
      key.splid.full_splid = lemma_arr_[pos].spl_idx_arr[hzpos];
      key.splid.half_splid = spl_trie.full_to_half(key.splid.full_splid);

      SingleCharItem *found;
      found = static_cast<SingleCharItem*>(mybsearch(&key, scis_,
                                                     unique_scis_num,
                                                     sizeof(SingleCharItem),
                                                     cmp_scis_hz_splid));

      assert(found);

      lemma_arr_[pos].hanzi_scis_ids[hzpos] =
          static_cast<uint16>(found - scis_);
      lemma_arr_[pos].spl_idx_arr[hzpos] = found->splid.full_splid;
    }
  }

  return scis_num_;
}

bool DictBuilder::construct_subset(void* parent, LemmaEntry* lemma_arr,
                                   size_t item_start, size_t item_end,
                                   size_t level) {
  if (level >= kMaxLemmaSize || item_end <= item_start)
    return false;

  // 1. Scan for how many sons
  size_t parent_son_num = 0;
  // LemmaNode *son_1st = NULL;
  // parent.num_of_son = 0;

  LemmaEntry *lma_last_start = lemma_arr_ + item_start;
  uint16 spl_idx_node = lma_last_start->spl_idx_arr[level];

  // Scan for how many sons to be allocaed
  for (size_t i = item_start + 1; i< item_end; i++) {
    LemmaEntry *lma_current = lemma_arr + i;
    uint16 spl_idx_current = lma_current->spl_idx_arr[level];
    if (spl_idx_current != spl_idx_node) {
      parent_son_num++;
      spl_idx_node = spl_idx_current;
    }
  }
  parent_son_num++;

#ifdef ___DO_STATISTICS___
  // Use to indicate whether all nodes of this layer have no son.
  bool allson_noson = true;

  assert(level < kMaxLemmaSize);
  if (parent_son_num > max_sonbuf_len_[level])
    max_sonbuf_len_[level] = parent_son_num;

  total_son_num_[level] += parent_son_num;
  total_sonbuf_num_[level] += 1;

  if (parent_son_num == 1)
    sonbufs_num1_++;
  else
    sonbufs_numgt1_++;
  total_lma_node_num_ += parent_son_num;
#endif

  // 2. Update the parent's information
  //    Update the parent's son list;
  LmaNodeLE0 *son_1st_le0 = NULL;  // only one of le0 or ge1 is used
  LmaNodeGE1 *son_1st_ge1 = NULL;  // only one of le0 or ge1 is used.
  if (0 == level) {                 // the parent is root
    (static_cast<LmaNodeLE0*>(parent))->son_1st_off =
      lma_nds_used_num_le0_;
    son_1st_le0 = lma_nodes_le0_ + lma_nds_used_num_le0_;
    lma_nds_used_num_le0_ += parent_son_num;

    assert(parent_son_num <= 65535);
    (static_cast<LmaNodeLE0*>(parent))->num_of_son =
      static_cast<uint16>(parent_son_num);
  } else if (1 == level) {  // the parent is a son of root
    (static_cast<LmaNodeLE0*>(parent))->son_1st_off =
      lma_nds_used_num_ge1_;
    son_1st_ge1 = lma_nodes_ge1_ + lma_nds_used_num_ge1_;
    lma_nds_used_num_ge1_ += parent_son_num;

    assert(parent_son_num <= 65535);
    (static_cast<LmaNodeLE0*>(parent))->num_of_son =
      static_cast<uint16>(parent_son_num);
  } else {
    set_son_offset((static_cast<LmaNodeGE1*>(parent)),
                   lma_nds_used_num_ge1_);
    son_1st_ge1 = lma_nodes_ge1_ + lma_nds_used_num_ge1_;
    lma_nds_used_num_ge1_ += parent_son_num;

    assert(parent_son_num <= 255);
    (static_cast<LmaNodeGE1*>(parent))->num_of_son =
      (unsigned char)parent_son_num;
  }

  // 3. Now begin to construct the son one by one
  size_t son_pos = 0;

  lma_last_start = lemma_arr_ + item_start;
  spl_idx_node = lma_last_start->spl_idx_arr[level];

  size_t homo_num = 0;
  if (lma_last_start->spl_idx_arr[level + 1] == 0)
    homo_num = 1;

  size_t item_start_next = item_start;

  for (size_t i = item_start + 1; i < item_end; i++) {
    LemmaEntry* lma_current = lemma_arr_ + i;
    uint16 spl_idx_current = lma_current->spl_idx_arr[level];

    if (spl_idx_current == spl_idx_node) {
      if (lma_current->spl_idx_arr[level + 1] == 0)
        homo_num++;
    } else {
      // Construct a node
      LmaNodeLE0 *node_cur_le0 = NULL;  // only one of them is valid
      LmaNodeGE1 *node_cur_ge1 = NULL;
      if (0 == level) {
        node_cur_le0 = son_1st_le0 + son_pos;
        node_cur_le0->spl_idx = spl_idx_node;
        node_cur_le0->homo_idx_buf_off = homo_idx_num_eq1_ + homo_idx_num_gt1_;
        node_cur_le0->son_1st_off = 0;
        homo_idx_num_eq1_ += homo_num;
      } else {
        node_cur_ge1 = son_1st_ge1 + son_pos;
        node_cur_ge1->spl_idx = spl_idx_node;

        set_homo_id_buf_offset(node_cur_ge1,
                               (homo_idx_num_eq1_ + homo_idx_num_gt1_));
        set_son_offset(node_cur_ge1, 0);
        homo_idx_num_gt1_ += homo_num;
      }

      if (homo_num > 0) {
        LemmaIdType* idx_buf = homo_idx_buf_ + homo_idx_num_eq1_ +
              homo_idx_num_gt1_ - homo_num;
        if (0 == level) {
          assert(homo_num <= 65535);
          node_cur_le0->num_of_homo = static_cast<uint16>(homo_num);
        } else {
          assert(homo_num <= 255);
          node_cur_ge1->num_of_homo = (unsigned char)homo_num;
        }

        for (size_t homo_pos = 0; homo_pos < homo_num; homo_pos++) {
          idx_buf[homo_pos] = lemma_arr_[item_start_next + homo_pos].idx_by_hz;
        }

#ifdef ___DO_STATISTICS___
        if (homo_num > max_homobuf_len_[level])
          max_homobuf_len_[level] = homo_num;

        total_homo_num_[level] += homo_num;
#endif
      }

      if (i - item_start_next > homo_num) {
        void *next_parent;
        if (0 == level)
          next_parent = static_cast<void*>(node_cur_le0);
        else
          next_parent = static_cast<void*>(node_cur_ge1);
        construct_subset(next_parent, lemma_arr,
                         item_start_next + homo_num, i, level + 1);
#ifdef ___DO_STATISTICS___

        total_node_hasson_[level] += 1;
        allson_noson = false;
#endif
      }

      // for the next son
      lma_last_start = lma_current;
      spl_idx_node = spl_idx_current;
      item_start_next = i;
      homo_num = 0;
      if (lma_current->spl_idx_arr[level + 1] == 0)
        homo_num = 1;

      son_pos++;
    }
  }

  // 4. The last one to construct
  LmaNodeLE0 *node_cur_le0 = NULL;  // only one of them is valid
  LmaNodeGE1 *node_cur_ge1 = NULL;
  if (0 == level) {
    node_cur_le0 = son_1st_le0 + son_pos;
    node_cur_le0->spl_idx = spl_idx_node;
    node_cur_le0->homo_idx_buf_off = homo_idx_num_eq1_ + homo_idx_num_gt1_;
    node_cur_le0->son_1st_off = 0;
    homo_idx_num_eq1_ += homo_num;
  } else {
    node_cur_ge1 = son_1st_ge1 + son_pos;
    node_cur_ge1->spl_idx = spl_idx_node;

    set_homo_id_buf_offset(node_cur_ge1,
                           (homo_idx_num_eq1_ + homo_idx_num_gt1_));
    set_son_offset(node_cur_ge1, 0);
    homo_idx_num_gt1_ += homo_num;
  }

  if (homo_num > 0) {
    LemmaIdType* idx_buf = homo_idx_buf_ + homo_idx_num_eq1_ +
          homo_idx_num_gt1_ - homo_num;
    if (0 == level) {
      assert(homo_num <= 65535);
      node_cur_le0->num_of_homo = static_cast<uint16>(homo_num);
    } else {
      assert(homo_num <= 255);
      node_cur_ge1->num_of_homo = (unsigned char)homo_num;
    }

    for (size_t homo_pos = 0; homo_pos < homo_num; homo_pos++) {
      idx_buf[homo_pos] = lemma_arr[item_start_next + homo_pos].idx_by_hz;
    }

#ifdef ___DO_STATISTICS___
    if (homo_num > max_homobuf_len_[level])
      max_homobuf_len_[level] = homo_num;

    total_homo_num_[level] += homo_num;
#endif
  }

  if (item_end - item_start_next > homo_num) {
    void *next_parent;
    if (0 == level)
      next_parent = static_cast<void*>(node_cur_le0);
    else
      next_parent = static_cast<void*>(node_cur_ge1);
    construct_subset(next_parent, lemma_arr,
                     item_start_next + homo_num, item_end, level + 1);
#ifdef ___DO_STATISTICS___

    total_node_hasson_[level] += 1;
    allson_noson = false;
#endif
  }

#ifdef ___DO_STATISTICS___
  if (allson_noson) {
    total_sonbuf_allnoson_[level] += 1;
    total_node_in_sonbuf_allnoson_[level] += parent_son_num;
  }
#endif

  assert(son_pos + 1 == parent_son_num);
  return true;
}

#ifdef ___DO_STATISTICS___
void DictBuilder::stat_init() {
  memset(max_sonbuf_len_, 0, sizeof(size_t) * kMaxLemmaSize);
  memset(max_homobuf_len_, 0, sizeof(size_t) * kMaxLemmaSize);
  memset(total_son_num_, 0, sizeof(size_t) * kMaxLemmaSize);
  memset(total_node_hasson_, 0, sizeof(size_t) * kMaxLemmaSize);
  memset(total_sonbuf_num_, 0, sizeof(size_t) * kMaxLemmaSize);
  memset(total_sonbuf_allnoson_, 0, sizeof(size_t) * kMaxLemmaSize);
  memset(total_node_in_sonbuf_allnoson_, 0, sizeof(size_t) * kMaxLemmaSize);
  memset(total_homo_num_, 0, sizeof(size_t) * kMaxLemmaSize);

  sonbufs_num1_ = 0;
  sonbufs_numgt1_ = 0;
  total_lma_node_num_ = 0;
}

void DictBuilder::stat_print() {
  printf("\n------------STAT INFO-------------\n");
  printf("[root is layer -1]\n");
  printf(".. max_sonbuf_len per layer(from layer 0):\n   ");
  for (size_t i = 0; i < kMaxLemmaSize; i++)
    printf("%d, ", max_sonbuf_len_[i]);
  printf("-, \n");

  printf(".. max_homobuf_len per layer:\n   -, ");
  for (size_t i = 0; i < kMaxLemmaSize; i++)
    printf("%d, ", max_homobuf_len_[i]);
  printf("\n");

  printf(".. total_son_num per layer:\n   ");
  for (size_t i = 0; i < kMaxLemmaSize; i++)
    printf("%d, ", total_son_num_[i]);
  printf("-, \n");

  printf(".. total_node_hasson per layer:\n   1, ");
  for (size_t i = 0; i < kMaxLemmaSize; i++)
    printf("%d, ", total_node_hasson_[i]);
  printf("\n");

  printf(".. total_sonbuf_num per layer:\n   ");
  for (size_t i = 0; i < kMaxLemmaSize; i++)
    printf("%d, ", total_sonbuf_num_[i]);
  printf("-, \n");

  printf(".. total_sonbuf_allnoson per layer:\n   ");
  for (size_t i = 0; i < kMaxLemmaSize; i++)
    printf("%d, ", total_sonbuf_allnoson_[i]);
  printf("-, \n");

  printf(".. total_node_in_sonbuf_allnoson per layer:\n   ");
  for (size_t i = 0; i < kMaxLemmaSize; i++)
    printf("%d, ", total_node_in_sonbuf_allnoson_[i]);
  printf("-, \n");

  printf(".. total_homo_num per layer:\n   0, ");
  for (size_t i = 0; i < kMaxLemmaSize; i++)
    printf("%d, ", total_homo_num_[i]);
  printf("\n");

  printf(".. son buf allocation number with only 1 son: %d\n", sonbufs_num1_);
  printf(".. son buf allocation number with more than 1 son: %d\n",
         sonbufs_numgt1_);
  printf(".. total lemma node number: %d\n", total_lma_node_num_ + 1);
}
#endif  // ___DO_STATISTICS___

#endif  // ___BUILD_MODEL___
}  // namespace ime_pinyin