src/storage/pinyin_parser2.cpp

   1 /*
   2  *  libpinyin
   3  *  Library to deal with pinyin.
   4  *
   5  *  Copyright (C) 2011 Peng Wu <alexepico@gmail.com>
   6  *
   7  *  This program is free software; you can redistribute it and/or modify
   8  *  it under the terms of the GNU General Public License as published by
   9  *  the Free Software Foundation; either version 2 of the License, or
  10  *  (at your option) any later version.
  11  *
  12  *  This program is distributed in the hope that it will be useful,
  13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  15  *  GNU General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU General Public License
  18  *  along with this program; if not, write to the Free Software
  19  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  20  */
  21
  22
  23 #include "pinyin_parser2.h"
  24 #include <ctype.h>
  25 #include <assert.h>
  26 #include <stdio.h>
  27 #include <string.h>
  28 #include "stl_lite.h"
  29 #include "pinyin_phrase2.h"
  30 #include "pinyin_custom2.h"
  31 #include "chewing_key.h"
  32 #include "pinyin_parser_table.h"
  33 #include "double_pinyin_table.h"
  34 #include "chewing_table.h"
  35
  36
  37 using namespace pinyin;
  38
  39 static bool check_pinyin_options(pinyin_option_t options, const pinyin_index_item_t * item) {
  40     guint32 flags = item->m_flags;
  41     assert (flags & IS_PINYIN);
  42
  43     /* handle incomplete pinyin. */
  44     if (flags & PINYIN_INCOMPLETE) {
  45         if (!(options & PINYIN_INCOMPLETE))
  46             return false;
  47     }
  48
  49     /* handle correct pinyin, currently only one flag per item. */
  50     flags &= PINYIN_CORRECT_ALL;
  51     options &= PINYIN_CORRECT_ALL;
  52
  53     if (flags) {
  54         if ((flags & options) != flags)
  55             return false;
  56     }
  57
  58     return true;
  59 }
  60
  61 static bool check_chewing_options(pinyin_option_t options, const chewing_index_item_t * item) {
  62     guint32 flags = item->m_flags;
  63     assert (flags & IS_CHEWING);
  64
  65     /* handle incomplete chewing. */
  66     if (flags & CHEWING_INCOMPLETE) {
  67         if (!(options & CHEWING_INCOMPLETE))
  68             return false;
  69     }
  70
  71     return true;
  72 }
  73
  74
  75 gint ChewingKey::get_table_index() {
  76     assert(m_initial <  CHEWING_NUMBER_OF_INITIALS);
  77     assert(m_middle < CHEWING_NUMBER_OF_MIDDLES);
  78     assert(m_final < CHEWING_NUMBER_OF_FINALS);
  79
  80     gint index = chewing_key_table[(m_initial * CHEWING_NUMBER_OF_MIDDLES + m_middle) * CHEWING_NUMBER_OF_FINALS + m_final];
  81     return index == -1 ? 0 : index;
  82 }
  83
  84 gchar * ChewingKey::get_pinyin_string() {
  85     assert(m_tone < CHEWING_NUMBER_OF_TONES);
  86     gint index = get_table_index();
  87     const content_table_item_t & item = content_table[index];
  88
  89     if (CHEWING_ZERO_TONE == m_tone) {
  90         return g_strdup(item.m_pinyin_str);
  91     } else {
  92         return g_strdup_printf("%s%d", item.m_pinyin_str, m_tone);
  93     }
  94 }
  95
  96 gchar * ChewingKey::get_chewing_string() {
  97     assert(m_tone < CHEWING_NUMBER_OF_TONES);
  98     gint index = get_table_index();
  99     const content_table_item_t & item = content_table[index];
 100
 101     if (CHEWING_ZERO_TONE == m_tone) {
 102         return g_strdup(item.m_chewing_str);
 103     } else {
 104         return g_strdup_printf("%s%s", item.m_chewing_str,
 105                                chewing_tone_table[m_tone]);
 106     }
 107 }
 108
 109
 110 /* methods for Chewing Keys to access pinyin parser table. */
 111 const char * ChewingKeyRest::get_pinyin_string(){
 112     if (m_table_index == 0)
 113         return NULL;
 114
 115     /* check end boundary. */
 116     assert(m_table_index < G_N_ELEMENTS(content_table));
 117     return content_table[m_table_index].m_pinyin_str;
 118 }
 119
 120 const char * ChewingKeyRest::get_chewing_string(){
 121     if (m_table_index == 0)
 122         return NULL;
 123
 124     /* check end boundary. */
 125     assert(m_table_index < G_N_ELEMENTS(content_table));
 126     return content_table[m_table_index].m_chewing_str;
 127 }
 128
 129
 130 /* Pinyin Parsers */
 131
 132 /* internal information for pinyin parsers. */
 133 struct parse_value_t{
 134     ChewingKey m_key;
 135     ChewingKeyRest m_key_rest;
 136     gint16 m_num_keys;
 137     gint16 m_parsed_len;
 138     gint16 m_last_step;
 139
 140     /* constructor */
 141 public:
 142     parse_value_t(){
 143         m_num_keys = 0;
 144         m_parsed_len = 0;
 145         m_last_step = -1;
 146     }
 147 };
 148
 149 const guint16 max_full_pinyin_length   = 7;  /* include tone. */
 150
 151 const guint16 max_double_pinyin_length = 3;  /* include tone. */
 152
 153 const guint16 max_chewing_length       = 4;  /* include tone. */
 154
 155 static bool compare_pinyin_less_than(const pinyin_index_item_t & lhs,
 156                                      const pinyin_index_item_t & rhs){
 157     return 0 > strcmp(lhs.m_pinyin_input, rhs.m_pinyin_input);
 158 }
 159
 160 static inline bool search_pinyin_index(pinyin_option_t options, const char * pinyin,
 161                                        ChewingKey & key,
 162                                        ChewingKeyRest & key_rest){
 163     pinyin_index_item_t item;
 164     memset(&item, 0, sizeof(item));
 165     item.m_pinyin_input = pinyin;
 166
 167     std_lite::pair<const pinyin_index_item_t *,
 168                    const pinyin_index_item_t *> range;
 169     range = std_lite::equal_range
 170         (pinyin_index, pinyin_index + G_N_ELEMENTS(pinyin_index),
 171          item, compare_pinyin_less_than);
 172
 173     guint16 range_len = range.second - range.first;
 174     assert(range_len <= 1);
 175     if (range_len == 1) {
 176         const pinyin_index_item_t * index = range.first;
 177
 178         if (!check_pinyin_options(options, index))
 179             return false;
 180
 181         key_rest.m_table_index = index->m_table_index;
 182         key = content_table[key_rest.m_table_index].m_chewing_key;
 183         return true;
 184     }
 185
 186     return false;
 187 }
 188
 189 static bool compare_chewing_less_than(const chewing_index_item_t & lhs,
 190                                       const chewing_index_item_t & rhs){
 191     return 0 > strcmp(lhs.m_chewing_input, rhs.m_chewing_input);
 192 }
 193
 194 static inline bool search_chewing_index(pinyin_option_t options, const char * chewing,
 195                                         ChewingKey & key,
 196                                         ChewingKeyRest & key_rest){
 197     chewing_index_item_t item;
 198     memset(&item, 0, sizeof(item));
 199     item.m_chewing_input = chewing;
 200
 201     std_lite::pair<const chewing_index_item_t *,
 202                    const chewing_index_item_t *> range;
 203     range = std_lite::equal_range
 204         (chewing_index, chewing_index + G_N_ELEMENTS(chewing_index),
 205          item, compare_chewing_less_than);
 206
 207     guint16 range_len = range.second - range.first;
 208     assert (range_len <= 1);
 209
 210     if (range_len == 1) {
 211         const chewing_index_item_t * index = range.first;
 212
 213         if (!check_chewing_options(options, index))
 214             return false;
 215
 216         key_rest.m_table_index = index->m_table_index;
 217         key = content_table[key_rest.m_table_index].m_chewing_key;
 218         return true;
 219     }
 220
 221     return false;
 222 }
 223
 224 /* Full Pinyin Parser */
 225 FullPinyinParser2::FullPinyinParser2 (){
 226     m_parse_steps = g_array_new(TRUE, FALSE, sizeof(parse_value_t));
 227 }
 228
 229
 230 bool FullPinyinParser2::parse_one_key (pinyin_option_t options, ChewingKey & key,
 231                                        ChewingKeyRest & key_rest,
 232                                        const char * pinyin, int len) const {
 233     /* "'" are not accepted in parse_one_key. */
 234     gchar * input = g_strndup(pinyin, len);
 235     assert(NULL == strchr(input, '\''));
 236
 237     guint16 tone = CHEWING_ZERO_TONE; guint16 tone_pos = 0;
 238     guint16 parsed_len = len;
 239     key = ChewingKey(); key_rest = ChewingKeyRest();
 240
 241     if (options & USE_TONE) {
 242         /* find the tone in the last character. */
 243         char chr = input[parsed_len - 1];
 244         if ( '0' < chr && chr <= '5' ) {
 245             tone = chr - '0';
 246             parsed_len --;
 247             tone_pos = parsed_len;
 248         }
 249     }
 250
 251     /* parse pinyin core staff here. */
 252
 253     /* Note: optimize here? */
 254     input[parsed_len] = '\0';
 255     if (!search_pinyin_index(options, input, key, key_rest)) {
 256         g_free(input);
 257         return false;
 258     }
 259
 260     if (options & USE_TONE) {
 261         /* post processing tone. */
 262         if ( parsed_len == tone_pos ) {
 263             if (tone != CHEWING_ZERO_TONE) {
 264                 key.m_tone = tone;
 265                 parsed_len ++;
 266             }
 267         }
 268     }
 269
 270     key_rest.m_raw_begin = 0; key_rest.m_raw_end = parsed_len;
 271     g_free(input);
 272     return parsed_len == len;
 273 }
 274
 275
 276 int FullPinyinParser2::parse (pinyin_option_t options, ChewingKeyVector & keys,
 277                               ChewingKeyRestVector & key_rests,
 278                               const char *str, int len) const {
 279     int i;
 280     /* clear arrays. */
 281     g_array_set_size(keys, 0);
 282     g_array_set_size(key_rests, 0);
 283
 284     /* init m_parse_steps, and prepare dynamic programming. */
 285     int step_len = len + 1;
 286     g_array_set_size(m_parse_steps, 0);
 287     parse_value_t value;
 288     for (i = 0; i < step_len; ++i) {
 289         g_array_append_val(m_parse_steps, value);
 290     }
 291
 292     size_t next_sep = 0;
 293     gchar * input = g_strndup(str, len);
 294     parse_value_t * curstep = NULL, * nextstep = NULL;
 295
 296     for (i = 0; i < len; ++i) {
 297         if (input[i] == '\'') {
 298             curstep = &g_array_index(m_parse_steps, parse_value_t, i);
 299             nextstep = &g_array_index(m_parse_steps, parse_value_t, i + 1);
 300
 301             /* propagate current step into next step. */
 302             nextstep->m_key = ChewingKey();
 303             nextstep->m_key_rest = ChewingKeyRest();
 304             nextstep->m_num_keys = curstep->m_num_keys;
 305             nextstep->m_parsed_len = curstep->m_parsed_len + 1;
 306             nextstep->m_last_step = i;
 307             next_sep = 0;
 308             continue;
 309         }
 310
 311         /* forward to next "'" */
 312         if ( 0 == next_sep ) {
 313             int k;
 314             for (k = i;  k < len; ++k) {
 315                 if (input[k] == '\'')
 316                     break;
 317             }
 318             next_sep = k;
 319         }
 320
 321         /* Heuristic Method:
 322          *   do maximum forward match first. */
 323         for (size_t pos = i; pos < next_sep; ++pos) {
 324             curstep = &g_array_index(m_parse_steps, parse_value_t, pos);
 325             size_t try_len = std_lite::min
 326                 (pos + max_full_pinyin_length, next_sep);
 327             for (size_t n = try_len; n > pos; --n) {
 328                 nextstep = &g_array_index(m_parse_steps, parse_value_t, n);
 329
 330                 /* gen next step */
 331                 const char * onepinyin = input + pos;
 332                 gint16 onepinyinlen = n - pos;
 333                 value = parse_value_t();
 334
 335                 ChewingKey key; ChewingKeyRest rest;
 336                 bool parsed = parse_one_key
 337                     (options, key, rest, onepinyin, onepinyinlen);
 338                 rest.m_raw_begin = pos; rest.m_raw_end = n;
 339
 340                 if (!parsed)
 341                     continue;
 342
 343                 //printf("onepinyin:%s len:%d\n", onepinyin, onepinyinlen);
 344                 value.m_key = key; value.m_key_rest = rest;
 345                 value.m_num_keys = curstep->m_num_keys + 1;
 346                 value.m_parsed_len = curstep->m_parsed_len + onepinyinlen;
 347                 value.m_last_step = pos;
 348
 349                 /* save next step */
 350                 if (-1 == nextstep->m_last_step)
 351                     *nextstep = value;
 352                 if (value.m_parsed_len > nextstep->m_parsed_len)
 353                     *nextstep = value;
 354                 if (value.m_parsed_len == nextstep->m_parsed_len &&
 355                     value.m_num_keys < nextstep->m_num_keys)
 356                     *nextstep = value;
 357
 358                 /* maximum forward, set pos to n in next iteration. */
 359                 pos = n - 1;
 360                 break;
 361             }
 362         }
 363
 364         /* dynamic programming here. */
 365         for (size_t m = i; m < next_sep; ++m) {
 366             curstep = &g_array_index(m_parse_steps, parse_value_t, m);
 367             size_t try_len = std_lite::min
 368                 (m + max_full_pinyin_length, next_sep);
 369             for (size_t n = m + 1; n < try_len + 1; ++n) {
 370                 nextstep = &g_array_index(m_parse_steps, parse_value_t, n);
 371
 372                 /* gen next step */
 373                 const char * onepinyin = input + m;
 374                 gint16 onepinyinlen = n - m;
 375                 value = parse_value_t();
 376
 377                 ChewingKey key; ChewingKeyRest rest;
 378                 bool parsed = parse_one_key
 379                     (options, key, rest, onepinyin, onepinyinlen);
 380                 rest.m_raw_begin = m; rest.m_raw_end = n;
 381                 if (!parsed)
 382                     continue;
 383
 384                 //printf("onepinyin:%s len:%d\n", onepinyin, onepinyinlen);
 385
 386                 value.m_key = key; value.m_key_rest = rest;
 387                 value.m_num_keys = curstep->m_num_keys + 1;
 388                 value.m_parsed_len = curstep->m_parsed_len + onepinyinlen;
 389                 value.m_last_step = m;
 390
 391                 /* save next step */
 392                 if (-1 == nextstep->m_last_step)
 393                     *nextstep = value;
 394                 if (value.m_parsed_len > nextstep->m_parsed_len)
 395                     *nextstep = value;
 396                 if (value.m_parsed_len == nextstep->m_parsed_len &&
 397                     value.m_num_keys < nextstep->m_num_keys)
 398                     *nextstep = value;
 399             }
 400         }
 401     }
 402
 403     /* final step for back tracing. */
 404     gint16 parsed_len = final_step(step_len, keys, key_rests);
 405
 406     /* post processing for re-split table. */
 407     if (options & USE_RESPLIT_TABLE) {
 408         post_process(options, keys, key_rests);
 409     }
 410
 411     g_free(input);
 412     return parsed_len;
 413 }
 414
 415 int FullPinyinParser2::final_step(size_t step_len, ChewingKeyVector & keys,
 416                                   ChewingKeyRestVector & key_rests) const{
 417     int i;
 418     gint16 parsed_len = 0;
 419     parse_value_t * curstep = NULL;
 420
 421     /* find longest match, which starts from the beginning of input. */
 422     for (i = step_len - 1; i >= 0; --i) {
 423         curstep = &g_array_index(m_parse_steps, parse_value_t, i);
 424         if (i == curstep->m_parsed_len)
 425             break;
 426     }
 427     /* prepare saving. */
 428     parsed_len = curstep->m_parsed_len;
 429     gint16 num_keys = curstep->m_num_keys;
 430     g_array_set_size(keys, num_keys);
 431     g_array_set_size(key_rests, num_keys);
 432
 433     /* save the match. */
 434     while (curstep->m_last_step != -1) {
 435         gint16 pos = curstep->m_num_keys - 1;
 436
 437         /* skip "'" */
 438         if (0 != curstep->m_key_rest.m_table_index) {
 439             ChewingKey * key = &g_array_index(keys, ChewingKey, pos);
 440             ChewingKeyRest * rest = &g_array_index
 441                 (key_rests, ChewingKeyRest, pos);
 442             *key = curstep->m_key; *rest = curstep->m_key_rest;
 443         }
 444
 445         /* back ward */
 446         curstep = &g_array_index(m_parse_steps, parse_value_t,
 447                                  curstep->m_last_step);
 448     }
 449     return parsed_len;
 450 }
 451
 452
 453 bool FullPinyinParser2::post_process(pinyin_option_t options,
 454                                      ChewingKeyVector & keys,
 455                                      ChewingKeyRestVector & key_rests) const {
 456     int i;
 457     assert(keys->len == key_rests->len);
 458     gint16 num_keys = keys->len;
 459
 460     ChewingKey * cur_key = NULL, * next_key = NULL;
 461     ChewingKeyRest * cur_rest = NULL, * next_rest = NULL;
 462     guint16 cur_tone = CHEWING_ZERO_TONE, next_tone = CHEWING_ZERO_TONE;
 463
 464     for (i = 0; i < num_keys - 1; ++i) {
 465         cur_rest = &g_array_index(key_rests, ChewingKeyRest, i);
 466         next_rest = &g_array_index(key_rests, ChewingKeyRest, i + 1);
 467
 468         /* some "'" here */
 469         if (cur_rest->m_raw_end != next_rest->m_raw_begin)
 470             continue;
 471
 472         cur_key = &g_array_index(keys, ChewingKey, i);
 473         next_key = &g_array_index(keys, ChewingKey, i + 1);
 474
 475         if (options & USE_TONE) {
 476             cur_tone = cur_key->m_tone;
 477             next_tone = next_key->m_tone;
 478             cur_key->m_tone = next_key->m_tone = CHEWING_ZERO_TONE;
 479         }
 480
 481         /* lookup re-split table */
 482         size_t k;
 483         const resplit_table_item_t * item = NULL;
 484         for (k = 0; k < G_N_ELEMENTS(resplit_table); ++k) {
 485             item = resplit_table + k;
 486             /* no ops */
 487             if (item->m_orig_freq >= item->m_new_freq)
 488                 continue;
 489
 490             /* use pinyin_exact_compare2 here. */
 491             if (0 == pinyin_exact_compare2(item->m_orig_keys,
 492                                            cur_key, 2))
 493                 break;
 494
 495         }
 496
 497         /* find the match */
 498         if (k < G_N_ELEMENTS(resplit_table)) {
 499             /* do re-split */
 500             item = resplit_table + k;
 501             *cur_key = item->m_new_keys[0];
 502             *next_key = item->m_new_keys[1];
 503             /* assumes only moved one char in gen_all_resplit script. */
 504             cur_rest->m_raw_end --;
 505             next_rest->m_raw_begin --;
 506         }
 507
 508         /* save back tones */
 509         if (options & USE_TONE) {
 510             cur_key->m_tone = cur_tone;
 511             next_key->m_tone = next_tone;
 512         }
 513     }
 514
 515     return true;
 516 }
 517
 518 #define IS_KEY(x)   (('a' <= x && x <= 'z') || x == ';')
 519
 520 bool DoublePinyinParser2::parse_one_key(pinyin_option_t options, ChewingKey & key,
 521                                         ChewingKeyRest & key_rest,
 522                                         const char *str, int len) const {
 523
 524     if (1 == len) {
 525         if (!(options & PINYIN_INCOMPLETE))
 526             return false;
 527
 528         char ch = str[0];
 529         if (!IS_KEY(ch))
 530             return false;
 531
 532         int charid = ch == ';' ? 26 : ch - 'a';
 533         const char * sheng = m_shengmu_table[charid].m_shengmu;
 534         if (NULL == sheng || strcmp(sheng, "'") == 0)
 535             return false;
 536
 537         if (search_pinyin_index(options, sheng, key, key_rest)) {
 538             key_rest.m_raw_begin = 0; key_rest.m_raw_end = len;
 539             return true;
 540         } else {
 541             return false;
 542         }
 543     }
 544
 545     ChewingTone tone = CHEWING_ZERO_TONE;
 546     options &= ~(PINYIN_CORRECT_ALL|PINYIN_AMB_ALL);
 547
 548     /* parse tone */
 549     if (3 == len) {
 550         if (!(options & USE_TONE))
 551             return false;
 552         char ch = str[2];
 553         if (!('0' < ch && ch <= '5'))
 554             return false;
 555         tone = (ChewingTone) (ch - '0');
 556     }
 557
 558     if (2 == len || 3 == len) {
 559         /* parse shengmu here. */
 560         char ch = str[0];
 561         if (!IS_KEY(ch))
 562             return false;
 563
 564         int charid = ch == ';' ? 26 : ch - 'a';
 565         const char * sheng = m_shengmu_table[charid].m_shengmu;
 566         if (NULL == sheng)
 567             return false;
 568         if (strcmp(sheng, "'") == 0)
 569             sheng = "";
 570
 571         /* parse yunmu here. */
 572         ch = str[1];
 573         if (!IS_KEY(ch))
 574             return false;
 575
 576         charid = ch == ';' ? 26 : ch - 'a';
 577         /* first yunmu */
 578         const char * yun = m_yunmu_table[charid].m_yunmus[0];
 579         gchar * pinyin = g_strdup_printf("%s%s", sheng, yun);
 580         if (search_pinyin_index(options, pinyin, key, key_rest)) {
 581             key_rest.m_raw_begin = 0; key_rest.m_raw_end = len;
 582             key.m_tone = tone;
 583             g_free(pinyin);
 584             return true;
 585         }
 586         g_free(pinyin);
 587
 588         /* second yunmu */
 589         yun = m_yunmu_table[charid].m_yunmus[1];
 590         pinyin = g_strdup_printf("%s%s", sheng, yun);
 591         if (search_pinyin_index(options, pinyin, key, key_rest)) {
 592             key_rest.m_raw_begin = 0; key_rest.m_raw_end = len;
 593             key.m_tone = tone;
 594             g_free(pinyin);
 595             return true;
 596         }
 597         g_free(pinyin);
 598
 599     }
 600
 601     return false;
 602 }
 603
 604
 605 /* only 'a'-'z' and ';' are accepted here. */
 606 int DoublePinyinParser2::parse(pinyin_option_t options, ChewingKeyVector & keys,
 607                                ChewingKeyRestVector & key_rests,
 608                                const char *str, int len) const {
 609     g_array_set_size(keys, 0);
 610     g_array_set_size(key_rests, 0);
 611
 612     int maximum_len = 0; int i;
 613     /* probe the longest possible double pinyin string. */
 614     for (i = 0; i < len; ++i) {
 615         const char ch = str[i];
 616         if (!(IS_KEY(ch) || ('0' < ch && ch <= '5')))
 617             break;
 618     }
 619     maximum_len = i;
 620
 621     /* maximum forward match for double pinyin. */
 622     int parsed_len = 0;
 623     while (parsed_len < maximum_len) {
 624         const char * cur_str = str + parsed_len;
 625         i = std_lite::min(maximum_len - parsed_len,
 626                           (int)max_double_pinyin_length);
 627
 628         ChewingKey key; ChewingKeyRest key_rest;
 629         for (; i > 0; --i) {
 630             bool success = parse_one_key(options, key, key_rest, cur_str, i);
 631             if (success)
 632                 break;
 633         }
 634
 635         if (0 == i)        /* no more possible double pinyins. */
 636             break;
 637
 638         key_rest.m_raw_begin = parsed_len; key_rest.m_raw_end = parsed_len + i;
 639         parsed_len += i;
 640
 641         /* save the pinyin */
 642         g_array_append_val(keys, key);
 643         g_array_append_val(key_rests, key_rest);
 644     }
 645
 646     return parsed_len;
 647 }
 648
 649 #undef IS_KEY
 650
 651 bool DoublePinyinParser2::set_scheme(DoublePinyinScheme scheme) {
 652
 653     switch (scheme) {
 654     case DOUBLE_PINYIN_ZRM:
 655         m_shengmu_table = double_pinyin_zrm_sheng;
 656         m_yunmu_table   = double_pinyin_zrm_yun;
 657         return true;
 658     case DOUBLE_PINYIN_MS:
 659         m_shengmu_table = double_pinyin_mspy_sheng;
 660         m_yunmu_table   = double_pinyin_mspy_yun;
 661         return true;
 662     case DOUBLE_PINYIN_ZIGUANG:
 663         m_shengmu_table = double_pinyin_zgpy_sheng;
 664         m_yunmu_table   = double_pinyin_zgpy_yun;
 665         return true;
 666     case DOUBLE_PINYIN_ABC:
 667         m_shengmu_table = double_pinyin_abc_sheng;
 668         m_yunmu_table   = double_pinyin_abc_yun;
 669         return true;
 670     case DOUBLE_PINYIN_PYJJ:
 671         m_shengmu_table = double_pinyin_pyjj_sheng;
 672         m_yunmu_table   = double_pinyin_pyjj_yun;
 673         return true;
 674     case DOUBLE_PINYIN_XHE:
 675         m_shengmu_table = double_pinyin_xhe_sheng;
 676         m_yunmu_table   = double_pinyin_xhe_yun;
 677         return true;
 678     case DOUBLE_PINYIN_CUSTOMIZED:
 679         assert(FALSE);
 680     };
 681
 682     return false; /* no such scheme. */
 683 }
 684
 685 /* the chewing string must be freed with g_free. */
 686 static bool search_chewing_symbols(const chewing_symbol_item_t * symbol_table,
 687                                    const char key, char ** chewing) {
 688     *chewing = NULL;
 689     /* just iterate the table, as we only have < 50 items. */
 690     while (symbol_table->m_input != '\0') {
 691         if (symbol_table->m_input == key) {
 692             *chewing = g_strdup(symbol_table->m_chewing);
 693             return true;
 694         }
 695         symbol_table ++;
 696     }
 697     return false;
 698 }
 699
 700 static bool search_chewing_tones(const chewing_tone_item_t * tone_table,
 701                                  const char key, char * tone) {
 702     *tone = CHEWING_ZERO_TONE;
 703     /* just iterate the table, as we only have < 10 items. */
 704     while (tone_table->m_input != '\0') {
 705         if (tone_table->m_input == key) {
 706             *tone = tone_table->m_tone;
 707             return true;
 708         }
 709         tone_table ++;
 710     }
 711     return false;
 712 }
 713
 714
 715 bool ChewingParser2::parse_one_key(pinyin_option_t options, ChewingKey & key, ChewingKeyRest & key_rest, const char *str, int len) const {
 716     char tone = CHEWING_ZERO_TONE;
 717
 718     int symbols_len = len;
 719     /* probe whether the last key is tone key in str. */
 720     if (options & USE_TONE) {
 721         char ch = str[len - 1];
 722         /* remove tone from input */
 723         if (search_chewing_tones(m_tone_table, ch, &tone))
 724             symbols_len --;
 725     }
 726
 727     int i;
 728     gchar * chewing = NULL, * onechar = NULL;
 729
 730     /* probe the possible chewing map in the rest of str. */
 731     for (i = 0; i < symbols_len; ++i) {
 732         if (!search_chewing_symbols(m_symbol_table, str[i], &onechar)) {
 733             g_free(onechar);
 734             g_free(chewing);
 735             return false;
 736         }
 737
 738         if (!chewing) {
 739             chewing = g_strdup(onechar);
 740         } else {
 741             gchar * tmp = chewing;
 742             chewing = g_strconcat(chewing, onechar, NULL);
 743             g_free(tmp);
 744         }
 745         g_free(onechar);
 746     }
 747
 748     /* search the chewing in the chewing index table. */
 749     if (search_chewing_index(options, chewing, key, key_rest)) {
 750         key_rest.m_raw_begin = 0; key_rest.m_raw_end = len;
 751         /* save back tone if available. */
 752         key.m_tone = tone;
 753         g_free(chewing);
 754         return true;
 755     }
 756
 757     g_free(chewing);
 758     return false;
 759 }
 760
 761
 762 /* only characters in chewing keyboard scheme are accepted here. */
 763 int ChewingParser2::parse(pinyin_option_t options, ChewingKeyVector & keys,
 764                           ChewingKeyRestVector & key_rests,
 765                           const char *str, int len) const {
 766     g_array_set_size(keys, 0);
 767     g_array_set_size(key_rests, 0);
 768
 769     int maximum_len = 0; int i;
 770     /* probe the longest possible chewing string. */
 771     for (i = 0; i < len; ++i) {
 772         if (!in_chewing_scheme(str[i]))
 773             break;
 774     }
 775     maximum_len = i;
 776
 777     /* maximum forward match for chewing. */
 778     int parsed_len = 0;
 779     while (parsed_len < maximum_len) {
 780         const char * cur_str = str + parsed_len;
 781         i = std_lite::min(maximum_len - parsed_len,
 782                           (int)max_chewing_length);
 783
 784         ChewingKey key; ChewingKeyRest key_rest;
 785         for (; i > 0; --i) {
 786             bool success = parse_one_key(options, key, key_rest, cur_str, i);
 787             if (success)
 788                 break;
 789         }
 790
 791         if (0 == i)        /* no more possible chewings. */
 792             break;
 793
 794         key_rest.m_raw_begin = parsed_len; key_rest.m_raw_end = parsed_len + i;
 795         parsed_len += i;
 796
 797         /* save the pinyin. */
 798         g_array_append_val(keys, key);
 799         g_array_append_val(key_rests, key_rest);
 800     }
 801
 802     return parsed_len;
 803 }
 804
 805
 806 bool ChewingParser2::set_scheme(ChewingScheme scheme) {
 807     switch(scheme) {
 808     case CHEWING_STANDARD:
 809         m_symbol_table = chewing_standard_symbols;
 810         m_tone_table   = chewing_standard_tones;
 811         return true;
 812     case CHEWING_IBM:
 813         m_symbol_table = chewing_ibm_symbols;
 814         m_tone_table   = chewing_ibm_tones;
 815         return true;
 816     case CHEWING_GINYIEH:
 817         m_symbol_table = chewing_ginyieh_symbols;
 818         m_tone_table   = chewing_ginyieh_tones;
 819         return true;
 820     case CHEWING_ETEN:
 821         m_symbol_table = chewing_eten_symbols;
 822         m_tone_table   = chewing_eten_tones;
 823         return true;
 824     }
 825
 826     return false;
 827 }
 828
 829
 830 bool ChewingParser2::in_chewing_scheme(const char key) const {
 831     gchar * chewing = NULL;
 832     char tone = CHEWING_ZERO_TONE;
 833
 834     bool retval = search_chewing_symbols(m_symbol_table, key, &chewing) ||
 835         search_chewing_tones(m_tone_table, key, &tone);
 836     g_free(chewing);
 837
 838     return retval;
 839 }