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     assert(index < G_N_ELEMENTS(content_table));
  88     const content_table_item_t & item = content_table[index];
  89
  90     if (CHEWING_ZERO_TONE == m_tone) {
  91         return g_strdup(item.m_pinyin_str);
  92     } else {
  93         return g_strdup_printf("%s%d", item.m_pinyin_str, m_tone);
  94     }
  95 }
  96
  97 gchar * ChewingKey::get_chewing_string() {
  98     assert(m_tone < CHEWING_NUMBER_OF_TONES);
  99     gint index = get_table_index();
 100     assert(index < G_N_ELEMENTS(content_table));
 101     const content_table_item_t & item = content_table[index];
 102
 103     if (CHEWING_ZERO_TONE == m_tone) {
 104         return g_strdup(item.m_chewing_str);
 105     } else {
 106         return g_strdup_printf("%s%s", item.m_chewing_str,
 107                                chewing_tone_table[m_tone]);
 108     }
 109 }
 110
 111
 112 /* Pinyin Parsers */
 113
 114 /* internal information for pinyin parsers. */
 115 struct parse_value_t{
 116     ChewingKey m_key;
 117     ChewingKeyRest m_key_rest;
 118     gint16 m_num_keys;
 119     gint16 m_parsed_len;
 120     gint16 m_last_step;
 121
 122     /* constructor */
 123 public:
 124     parse_value_t(){
 125         m_num_keys = 0;
 126         m_parsed_len = 0;
 127         m_last_step = -1;
 128     }
 129 };
 130
 131 const guint16 max_full_pinyin_length   = 7;  /* include tone. */
 132
 133 const guint16 max_double_pinyin_length = 3;  /* include tone. */
 134
 135 const guint16 max_chewing_length       = 4;  /* include tone. */
 136
 137 static bool compare_pinyin_less_than(const pinyin_index_item_t & lhs,
 138                                      const pinyin_index_item_t & rhs){
 139     return 0 > strcmp(lhs.m_pinyin_input, rhs.m_pinyin_input);
 140 }
 141
 142 static inline bool search_pinyin_index(pinyin_option_t options,
 143                                        const char * pinyin,
 144                                        ChewingKey & key){
 145     pinyin_index_item_t item;
 146     memset(&item, 0, sizeof(item));
 147     item.m_pinyin_input = pinyin;
 148
 149     std_lite::pair<const pinyin_index_item_t *,
 150                    const pinyin_index_item_t *> range;
 151     range = std_lite::equal_range
 152         (pinyin_index, pinyin_index + G_N_ELEMENTS(pinyin_index),
 153          item, compare_pinyin_less_than);
 154
 155     guint16 range_len = range.second - range.first;
 156     assert(range_len <= 1);
 157     if (range_len == 1) {
 158         const pinyin_index_item_t * index = range.first;
 159
 160         if (!check_pinyin_options(options, index))
 161             return false;
 162
 163         key = content_table[index->m_table_index].m_chewing_key;
 164         assert(key.get_table_index() == index->m_table_index);
 165         return true;
 166     }
 167
 168     return false;
 169 }
 170
 171 static bool compare_chewing_less_than(const chewing_index_item_t & lhs,
 172                                       const chewing_index_item_t & rhs){
 173     return 0 > strcmp(lhs.m_chewing_input, rhs.m_chewing_input);
 174 }
 175
 176 static inline bool search_chewing_index(pinyin_option_t options,
 177                                         const char * chewing,
 178                                         ChewingKey & key){
 179     chewing_index_item_t item;
 180     memset(&item, 0, sizeof(item));
 181     item.m_chewing_input = chewing;
 182
 183     std_lite::pair<const chewing_index_item_t *,
 184                    const chewing_index_item_t *> range;
 185     range = std_lite::equal_range
 186         (chewing_index, chewing_index + G_N_ELEMENTS(chewing_index),
 187          item, compare_chewing_less_than);
 188
 189     guint16 range_len = range.second - range.first;
 190     assert (range_len <= 1);
 191
 192     if (range_len == 1) {
 193         const chewing_index_item_t * index = range.first;
 194
 195         if (!check_chewing_options(options, index))
 196             return false;
 197
 198         key = content_table[index->m_table_index].m_chewing_key;
 199         assert(key.get_table_index() == index->m_table_index);
 200         return true;
 201     }
 202
 203     return false;
 204 }
 205
 206 /* Full Pinyin Parser */
 207 FullPinyinParser2::FullPinyinParser2 (){
 208     m_parse_steps = g_array_new(TRUE, FALSE, sizeof(parse_value_t));
 209 }
 210
 211
 212 bool FullPinyinParser2::parse_one_key (pinyin_option_t options,
 213                                        ChewingKey & key,
 214                                        const char * pinyin, int len) const {
 215     /* "'" are not accepted in parse_one_key. */
 216     gchar * input = g_strndup(pinyin, len);
 217     assert(NULL == strchr(input, '\''));
 218
 219     guint16 tone = CHEWING_ZERO_TONE; guint16 tone_pos = 0;
 220     guint16 parsed_len = len;
 221     key = ChewingKey();
 222
 223     if (options & USE_TONE) {
 224         /* find the tone in the last character. */
 225         char chr = input[parsed_len - 1];
 226         if ( '0' < chr && chr <= '5' ) {
 227             tone = chr - '0';
 228             parsed_len --;
 229             tone_pos = parsed_len;
 230         }
 231     }
 232
 233     /* parse pinyin core staff here. */
 234
 235     /* Note: optimize here? */
 236     input[parsed_len] = '\0';
 237     if (!search_pinyin_index(options, input, key)) {
 238         g_free(input);
 239         return false;
 240     }
 241
 242     if (options & USE_TONE) {
 243         /* post processing tone. */
 244         if ( parsed_len == tone_pos ) {
 245             if (tone != CHEWING_ZERO_TONE) {
 246                 key.m_tone = tone;
 247                 parsed_len ++;
 248             }
 249         }
 250     }
 251
 252     g_free(input);
 253     return parsed_len == len;
 254 }
 255
 256
 257 int FullPinyinParser2::parse (pinyin_option_t options, ChewingKeyVector & keys,
 258                               ChewingKeyRestVector & key_rests,
 259                               const char *str, int len) const {
 260     int i;
 261     /* clear arrays. */
 262     g_array_set_size(keys, 0);
 263     g_array_set_size(key_rests, 0);
 264
 265     /* init m_parse_steps, and prepare dynamic programming. */
 266     int step_len = len + 1;
 267     g_array_set_size(m_parse_steps, 0);
 268     parse_value_t value;
 269     for (i = 0; i < step_len; ++i) {
 270         g_array_append_val(m_parse_steps, value);
 271     }
 272
 273     size_t next_sep = 0;
 274     gchar * input = g_strndup(str, len);
 275     parse_value_t * curstep = NULL, * nextstep = NULL;
 276
 277     for (i = 0; i < len; ++i) {
 278         if (input[i] == '\'') {
 279             curstep = &g_array_index(m_parse_steps, parse_value_t, i);
 280             nextstep = &g_array_index(m_parse_steps, parse_value_t, i + 1);
 281
 282             /* propagate current step into next step. */
 283             nextstep->m_key = ChewingKey();
 284             nextstep->m_key_rest = ChewingKeyRest();
 285             nextstep->m_num_keys = curstep->m_num_keys;
 286             nextstep->m_parsed_len = curstep->m_parsed_len + 1;
 287             nextstep->m_last_step = i;
 288             next_sep = 0;
 289             continue;
 290         }
 291
 292         /* forward to next "'" */
 293         if ( 0 == next_sep ) {
 294             int k;
 295             for (k = i;  k < len; ++k) {
 296                 if (input[k] == '\'')
 297                     break;
 298             }
 299             next_sep = k;
 300         }
 301
 302 #if 0
 303         /* Heuristic Method:
 304          *   do maximum forward match first. */
 305         for (size_t pos = i; pos < next_sep; ++pos) {
 306             curstep = &g_array_index(m_parse_steps, parse_value_t, pos);
 307             size_t try_len = std_lite::min
 308                 (pos + max_full_pinyin_length, next_sep);
 309             for (size_t n = try_len; n > pos; --n) {
 310                 nextstep = &g_array_index(m_parse_steps, parse_value_t, n);
 311
 312                 /* gen next step */
 313                 const char * onepinyin = input + pos;
 314                 gint16 onepinyinlen = n - pos;
 315                 value = parse_value_t();
 316
 317                 ChewingKey key; ChewingKeyRest rest;
 318                 bool parsed = parse_one_key
 319                     (options, key, onepinyin, onepinyinlen);
 320                 rest.m_raw_begin = pos; rest.m_raw_end = n;
 321
 322                 if (!parsed)
 323                     continue;
 324
 325                 //printf("onepinyin:%s len:%d\n", onepinyin, onepinyinlen);
 326                 value.m_key = key; value.m_key_rest = rest;
 327                 value.m_num_keys = curstep->m_num_keys + 1;
 328                 value.m_parsed_len = curstep->m_parsed_len + onepinyinlen;
 329                 value.m_last_step = pos;
 330
 331                 /* save next step */
 332                 if (-1 == nextstep->m_last_step)
 333                     *nextstep = value;
 334                 if (value.m_parsed_len > nextstep->m_parsed_len)
 335                     *nextstep = value;
 336                 if (value.m_parsed_len == nextstep->m_parsed_len &&
 337                     value.m_num_keys < nextstep->m_num_keys)
 338                     *nextstep = value;
 339
 340                 /* maximum forward, set pos to n in next iteration. */
 341                 pos = n - 1;
 342                 break;
 343             }
 344         }
 345 #endif
 346
 347         /* dynamic programming here. */
 348         /* for (size_t m = i; m < next_sep; ++m) */
 349         {
 350             size_t m = i;
 351             curstep = &g_array_index(m_parse_steps, parse_value_t, m);
 352             size_t try_len = std_lite::min
 353                 (m + max_full_pinyin_length, next_sep);
 354             for (size_t n = m + 1; n < try_len + 1; ++n) {
 355                 nextstep = &g_array_index(m_parse_steps, parse_value_t, n);
 356
 357                 /* gen next step */
 358                 const char * onepinyin = input + m;
 359                 gint16 onepinyinlen = n - m;
 360                 value = parse_value_t();
 361
 362                 ChewingKey key; ChewingKeyRest rest;
 363                 bool parsed = parse_one_key
 364                     (options, key, onepinyin, onepinyinlen);
 365                 rest.m_raw_begin = m; rest.m_raw_end = n;
 366                 if (!parsed)
 367                     continue;
 368
 369                 //printf("onepinyin:%s len:%d\n", onepinyin, onepinyinlen);
 370
 371                 value.m_key = key; value.m_key_rest = rest;
 372                 value.m_num_keys = curstep->m_num_keys + 1;
 373                 value.m_parsed_len = curstep->m_parsed_len + onepinyinlen;
 374                 value.m_last_step = m;
 375
 376                 /* save next step */
 377                 /* no previous result */
 378                 if (-1 == nextstep->m_last_step)
 379                     *nextstep = value;
 380                 /* prefer the longest pinyin */
 381                 if (value.m_parsed_len > nextstep->m_parsed_len)
 382                     *nextstep = value;
 383                 /* prefer the shortest keys with the same pinyin length */
 384                 if (value.m_parsed_len == nextstep->m_parsed_len &&
 385                     value.m_num_keys < nextstep->m_num_keys)
 386                     *nextstep = value;
 387
 388                 /* handle with the same pinyin length and the number of keys */
 389                 if (value.m_parsed_len == nextstep->m_parsed_len &&
 390                     value.m_num_keys == nextstep->m_num_keys) {
 391
 392 #if 0
 393                     /* prefer the complete pinyin with shengmu
 394                      * over without shengmu,
 395                      * ex: "kaneiji" -> "ka'nei'ji".
 396                      */
 397                     if ((value.m_key.m_initial != CHEWING_ZERO_INITIAL &&
 398                          !(value.m_key.m_middle == CHEWING_ZERO_MIDDLE &&
 399                            value.m_key.m_final == CHEWING_ZERO_FINAL)) &&
 400                         nextstep->m_key.m_initial == CHEWING_ZERO_INITIAL)
 401                         *nextstep = value;
 402
 403                     /* prefer the complete pinyin 'er'
 404                      * over the in-complete pinyin 'r',
 405                      * ex: "xierqi" -> "xi'er'qi."
 406                      */
 407                     if ((value.m_key.m_initial == CHEWING_ZERO_INITIAL &&
 408                         value.m_key.m_middle == CHEWING_ZERO_MIDDLE &&
 409                         value.m_key.m_final == CHEWING_ER) &&
 410                         (nextstep->m_key.m_initial == CHEWING_R &&
 411                          nextstep->m_key.m_middle == CHEWING_ZERO_MIDDLE &&
 412                          nextstep->m_key.m_final == CHEWING_ZERO_FINAL))
 413                         *nextstep = value;
 414 #endif
 415
 416                     /* prefer the 'a' at the end of clause,
 417                      * ex: "zheyanga$" -> "zhe'yang'a$".
 418                      */
 419                     if (value.m_parsed_len == len &&
 420                         (nextstep->m_key.m_initial != CHEWING_ZERO_INITIAL &&
 421                          nextstep->m_key.m_final == CHEWING_A) &&
 422                         (value.m_key.m_initial == CHEWING_ZERO_INITIAL &&
 423                          value.m_key.m_middle == CHEWING_ZERO_MIDDLE &&
 424                          value.m_key.m_final == CHEWING_A))
 425                         *nextstep = value;
 426                 }
 427             }
 428         }
 429     }
 430
 431     /* final step for back tracing. */
 432     gint16 parsed_len = final_step(step_len, keys, key_rests);
 433
 434     /* post processing for re-split table. */
 435     if (options & USE_RESPLIT_TABLE) {
 436         post_process2(options, keys, key_rests, str, len);
 437     }
 438
 439     g_free(input);
 440     return parsed_len;
 441 }
 442
 443 int FullPinyinParser2::final_step(size_t step_len, ChewingKeyVector & keys,
 444                                   ChewingKeyRestVector & key_rests) const{
 445     int i;
 446     gint16 parsed_len = 0;
 447     parse_value_t * curstep = NULL;
 448
 449     /* find longest match, which starts from the beginning of input. */
 450     for (i = step_len - 1; i >= 0; --i) {
 451         curstep = &g_array_index(m_parse_steps, parse_value_t, i);
 452         if (i == curstep->m_parsed_len)
 453             break;
 454     }
 455     /* prepare saving. */
 456     parsed_len = curstep->m_parsed_len;
 457     gint16 num_keys = curstep->m_num_keys;
 458     g_array_set_size(keys, num_keys);
 459     g_array_set_size(key_rests, num_keys);
 460
 461     /* save the match. */
 462     while (curstep->m_last_step != -1) {
 463         gint16 pos = curstep->m_num_keys - 1;
 464
 465         /* skip "'" */
 466         if (0 != curstep->m_key.get_table_index()) {
 467             ChewingKey * key = &g_array_index(keys, ChewingKey, pos);
 468             ChewingKeyRest * rest = &g_array_index
 469                 (key_rests, ChewingKeyRest, pos);
 470             *key = curstep->m_key; *rest = curstep->m_key_rest;
 471         }
 472
 473         /* back ward */
 474         curstep = &g_array_index(m_parse_steps, parse_value_t,
 475                                  curstep->m_last_step);
 476     }
 477     return parsed_len;
 478 }
 479
 480 bool FullPinyinParser2::post_process2(pinyin_option_t options,
 481                                       ChewingKeyVector & keys,
 482                                       ChewingKeyRestVector & key_rests,
 483                                       const char * str,
 484                                       int len) const {
 485     int i;
 486     assert(keys->len == key_rests->len);
 487     gint num_keys = keys->len;
 488
 489     ChewingKey * cur_key = NULL, * next_key = NULL;
 490     ChewingKeyRest * cur_rest = NULL, * next_rest = NULL;
 491     guint16 next_tone = CHEWING_ZERO_TONE;
 492
 493     for (i = 0; i < num_keys - 1; ++i) {
 494         cur_rest = &g_array_index(key_rests, ChewingKeyRest, i);
 495         next_rest = &g_array_index(key_rests, ChewingKeyRest, i + 1);
 496
 497         /* some "'" here */
 498         if (cur_rest->m_raw_end != next_rest->m_raw_begin)
 499             continue;
 500
 501         cur_key = &g_array_index(keys, ChewingKey, i);
 502         next_key = &g_array_index(keys, ChewingKey, i + 1);
 503
 504         /* some tone here */
 505         if (CHEWING_ZERO_TONE != cur_key->m_tone)
 506             continue;
 507
 508         /* back up tone */
 509         if (options & USE_TONE) {
 510             next_tone = next_key->m_tone;
 511             if (CHEWING_ZERO_TONE != next_tone) {
 512                 next_key->m_tone = CHEWING_ZERO_TONE;
 513                 next_rest->m_raw_end --;
 514             }
 515         }
 516
 517         /* lookup re-split table */
 518         size_t k;
 519         const resplit_table_item_t * item = NULL;
 520
 521         item = retrieve_resplit_item_by_original_pinyins
 522             (options, cur_key, cur_rest, next_key, next_rest,
 523              str, len);
 524
 525         if (item) {
 526             /* no ops */
 527             if (item->m_orig_freq >= item->m_new_freq)
 528                 continue;
 529
 530             /* do re-split */
 531             const char * onepinyin = str + cur_rest->m_raw_begin;
 532             size_t len = strlen(item->m_new_keys[0]);
 533
 534             assert(parse_one_key(options, *cur_key, onepinyin, len));
 535             cur_rest->m_raw_end = cur_rest->m_raw_begin + len;
 536
 537             next_rest->m_raw_begin = cur_rest->m_raw_end;
 538             onepinyin = str + next_rest->m_raw_begin;
 539             len = strlen(item->m_new_keys[1]);
 540
 541             assert(parse_one_key(options, *next_key, onepinyin, len));
 542         }
 543
 544         /* restore tones */
 545         if (options & USE_TONE) {
 546             if (CHEWING_ZERO_TONE != next_tone) {
 547                 next_key->m_tone = next_tone;
 548                 next_rest->m_raw_end ++;
 549             }
 550         }
 551     }
 552
 553     return true;
 554 }
 555
 556 const divided_table_item_t * FullPinyinParser2::retrieve_divided_item
 557 (pinyin_option_t options, ChewingKey * key, ChewingKeyRest * rest,
 558  const char * str, int len) const {
 559
 560     /* lookup divided table */
 561     size_t k;
 562     const divided_table_item_t * item = NULL;
 563     for (k = 0; k < G_N_ELEMENTS(divided_table); ++k) {
 564         item = divided_table + k;
 565
 566         const char * onepinyin = str + rest->m_raw_begin;
 567         size_t len = strlen(item->m_orig_key);
 568
 569         if (rest->length() != len)
 570             continue;
 571
 572         if (0 == strncmp(onepinyin, item->m_orig_key, len))
 573             break;
 574     }
 575
 576     /* found the match */
 577     if (k < G_N_ELEMENTS(divided_table)) {
 578         /* do divided */
 579         item = divided_table + k;
 580         return item;
 581     }
 582
 583     return NULL;
 584 }
 585
 586
 587 const resplit_table_item_t * FullPinyinParser2::retrieve_resplit_item_by_original_pinyins
 588 (pinyin_option_t options,
 589  ChewingKey * cur_key, ChewingKeyRest * cur_rest,
 590  ChewingKey * next_key, ChewingKeyRest * next_rest,
 591  const char * str, int len) const{
 592     /* lookup re-split table */
 593     size_t k;
 594     const resplit_table_item_t * item = NULL;
 595
 596     for (k = 0; k < G_N_ELEMENTS(resplit_table); ++k) {
 597         item = resplit_table + k;
 598
 599         const char * onepinyin = str + cur_rest->m_raw_begin;
 600         size_t len = strlen(item->m_orig_keys[0]);
 601
 602         if (cur_rest->length() != len)
 603             continue;
 604
 605         if (0 != strncmp(onepinyin, item->m_orig_keys[0], len))
 606             continue;
 607
 608         onepinyin = str + next_rest->m_raw_begin;
 609         len = strlen(item->m_orig_keys[1]);
 610
 611         if (next_rest->length() != len)
 612             continue;
 613
 614         if (0 == strncmp(onepinyin, item->m_orig_keys[1], len))
 615             break;
 616     }
 617
 618     /* found the match */
 619     if (k < G_N_ELEMENTS(resplit_table)) {
 620         item = resplit_table + k;
 621         return item;
 622     }
 623
 624     return NULL;
 625 }
 626
 627 const resplit_table_item_t * FullPinyinParser2::retrieve_resplit_item_by_resplit_pinyins
 628 (pinyin_option_t options,
 629  ChewingKey * cur_key, ChewingKeyRest * cur_rest,
 630  ChewingKey * next_key, ChewingKeyRest * next_rest,
 631  const char * str, int len) const {
 632     /* lookup divide table */
 633     size_t k;
 634     const resplit_table_item_t * item = NULL;
 635
 636     for (k = 0; k < G_N_ELEMENTS(resplit_table); ++k) {
 637         item = resplit_table + k;
 638
 639         const char * onepinyin = str + cur_rest->m_raw_begin;
 640         size_t len = strlen(item->m_orig_keys[0]);
 641
 642         if (cur_rest->length() != len)
 643             continue;
 644
 645         if (0 != strncmp(onepinyin, item->m_orig_keys[0], len))
 646             continue;
 647
 648         onepinyin = str + next_rest->m_raw_begin;
 649         len = strlen(item->m_orig_keys[1]);
 650
 651         if (next_rest->length() != len)
 652             continue;
 653
 654         if (0 == strncmp(onepinyin, item->m_orig_keys[1], len))
 655             break;
 656     }
 657
 658     /* found the match */
 659     if (k < G_N_ELEMENTS(resplit_table)) {
 660         item = resplit_table + k;
 661         return item;
 662     }
 663
 664     return NULL;
 665 }
 666
 667 #define IS_KEY(x)   (('a' <= x && x <= 'z') || x == ';')
 668
 669 bool DoublePinyinParser2::parse_one_key(pinyin_option_t options,
 670                                         ChewingKey & key,
 671                                         const char *str, int len) const {
 672     options &= ~(PINYIN_CORRECT_ALL|PINYIN_AMB_ALL);
 673
 674     if (1 == len) {
 675         if (!(options & PINYIN_INCOMPLETE))
 676             return false;
 677
 678         char ch = str[0];
 679         if (!IS_KEY(ch))
 680             return false;
 681
 682         int charid = ch == ';' ? 26 : ch - 'a';
 683         const char * sheng = m_shengmu_table[charid].m_shengmu;
 684         if (NULL == sheng || strcmp(sheng, "'") == 0)
 685             return false;
 686
 687         if (search_pinyin_index(options, sheng, key)) {
 688             return true;
 689         } else {
 690             return false;
 691         }
 692     }
 693
 694     ChewingTone tone = CHEWING_ZERO_TONE;
 695     options &= ~(PINYIN_INCOMPLETE|CHEWING_INCOMPLETE);
 696
 697     /* parse tone */
 698     if (3 == len) {
 699         if (!(options & USE_TONE))
 700             return false;
 701         char ch = str[2];
 702         if (!('0' < ch && ch <= '5'))
 703             return false;
 704         tone = (ChewingTone) (ch - '0');
 705     }
 706
 707     if (2 == len || 3 == len) {
 708         /* parse shengmu here. */
 709         char ch = str[0];
 710         if (!IS_KEY(ch))
 711             return false;
 712
 713         int charid = ch == ';' ? 26 : ch - 'a';
 714         const char * sheng = m_shengmu_table[charid].m_shengmu;
 715         if (NULL == sheng)
 716             return false;
 717         if (strcmp(sheng, "'") == 0)
 718             sheng = "";
 719
 720         /* parse yunmu here. */
 721         ch = str[1];
 722         if (!IS_KEY(ch))
 723             return false;
 724
 725         charid = ch == ';' ? 26 : ch - 'a';
 726         /* first yunmu */
 727         const char * yun = m_yunmu_table[charid].m_yunmus[0];
 728         if (NULL == yun)
 729             return false;
 730
 731         gchar * pinyin = g_strdup_printf("%s%s", sheng, yun);
 732         if (search_pinyin_index(options, pinyin, key)) {
 733             key.m_tone = tone;
 734             g_free(pinyin);
 735             return true;
 736         }
 737         g_free(pinyin);
 738
 739         /* second yunmu */
 740         yun = m_yunmu_table[charid].m_yunmus[1];
 741         if (NULL == yun)
 742             return false;
 743
 744         pinyin = g_strdup_printf("%s%s", sheng, yun);
 745         if (search_pinyin_index(options, pinyin, key)) {
 746             key.m_tone = tone;
 747             g_free(pinyin);
 748             return true;
 749         }
 750         g_free(pinyin);
 751
 752     }
 753
 754     return false;
 755 }
 756
 757
 758 /* only 'a'-'z' and ';' are accepted here. */
 759 int DoublePinyinParser2::parse(pinyin_option_t options, ChewingKeyVector & keys,
 760                                ChewingKeyRestVector & key_rests,
 761                                const char *str, int len) const {
 762     g_array_set_size(keys, 0);
 763     g_array_set_size(key_rests, 0);
 764
 765     int maximum_len = 0; int i;
 766     /* probe the longest possible double pinyin string. */
 767     for (i = 0; i < len; ++i) {
 768         const char ch = str[i];
 769         if (!(IS_KEY(ch) || ('0' < ch && ch <= '5')))
 770             break;
 771     }
 772     maximum_len = i;
 773
 774     /* maximum forward match for double pinyin. */
 775     int parsed_len = 0;
 776     while (parsed_len < maximum_len) {
 777         const char * cur_str = str + parsed_len;
 778         i = std_lite::min(maximum_len - parsed_len,
 779                           (int)max_double_pinyin_length);
 780
 781         ChewingKey key; ChewingKeyRest key_rest;
 782         for (; i > 0; --i) {
 783             bool success = parse_one_key(options, key, cur_str, i);
 784             if (success)
 785                 break;
 786         }
 787
 788         if (0 == i)        /* no more possible double pinyins. */
 789             break;
 790
 791         key_rest.m_raw_begin = parsed_len; key_rest.m_raw_end = parsed_len + i;
 792         parsed_len += i;
 793
 794         /* save the pinyin */
 795         g_array_append_val(keys, key);
 796         g_array_append_val(key_rests, key_rest);
 797     }
 798
 799     return parsed_len;
 800 }
 801
 802 #undef IS_KEY
 803
 804 bool DoublePinyinParser2::set_scheme(DoublePinyinScheme scheme) {
 805
 806     switch (scheme) {
 807     case DOUBLE_PINYIN_ZRM:
 808         m_shengmu_table = double_pinyin_zrm_sheng;
 809         m_yunmu_table   = double_pinyin_zrm_yun;
 810         return true;
 811     case DOUBLE_PINYIN_MS:
 812         m_shengmu_table = double_pinyin_mspy_sheng;
 813         m_yunmu_table   = double_pinyin_mspy_yun;
 814         return true;
 815     case DOUBLE_PINYIN_ZIGUANG:
 816         m_shengmu_table = double_pinyin_zgpy_sheng;
 817         m_yunmu_table   = double_pinyin_zgpy_yun;
 818         return true;
 819     case DOUBLE_PINYIN_ABC:
 820         m_shengmu_table = double_pinyin_abc_sheng;
 821         m_yunmu_table   = double_pinyin_abc_yun;
 822         return true;
 823     case DOUBLE_PINYIN_PYJJ:
 824         m_shengmu_table = double_pinyin_pyjj_sheng;
 825         m_yunmu_table   = double_pinyin_pyjj_yun;
 826         return true;
 827     case DOUBLE_PINYIN_XHE:
 828         m_shengmu_table = double_pinyin_xhe_sheng;
 829         m_yunmu_table   = double_pinyin_xhe_yun;
 830         return true;
 831     case DOUBLE_PINYIN_CUSTOMIZED:
 832         assert(FALSE);
 833     };
 834
 835     return false; /* no such scheme. */
 836 }
 837
 838 /* the chewing string must be freed with g_free. */
 839 static bool search_chewing_symbols(const chewing_symbol_item_t * symbol_table,
 840                                    const char key, const char ** chewing) {
 841     *chewing = NULL;
 842     /* just iterate the table, as we only have < 50 items. */
 843     while (symbol_table->m_input != '\0') {
 844         if (symbol_table->m_input == key) {
 845             *chewing = symbol_table->m_chewing;
 846             return true;
 847         }
 848         symbol_table ++;
 849     }
 850     return false;
 851 }
 852
 853 static bool search_chewing_tones(const chewing_tone_item_t * tone_table,
 854                                  const char key, char * tone) {
 855     *tone = CHEWING_ZERO_TONE;
 856     /* just iterate the table, as we only have < 10 items. */
 857     while (tone_table->m_input != '\0') {
 858         if (tone_table->m_input == key) {
 859             *tone = tone_table->m_tone;
 860             return true;
 861         }
 862         tone_table ++;
 863     }
 864     return false;
 865 }
 866
 867
 868 bool ChewingParser2::parse_one_key(pinyin_option_t options,
 869                                    ChewingKey & key,
 870                                    const char *str, int len) const {
 871     options &= ~(PINYIN_CORRECT_ALL|PINYIN_AMB_ALL);
 872     char tone = CHEWING_ZERO_TONE;
 873
 874     int symbols_len = len;
 875     /* probe whether the last key is tone key in str. */
 876     if (options & USE_TONE) {
 877         char ch = str[len - 1];
 878         /* remove tone from input */
 879         if (search_chewing_tones(m_tone_table, ch, &tone))
 880             symbols_len --;
 881     }
 882
 883     int i;
 884     gchar * chewing = NULL; const char * onechar = NULL;
 885
 886     /* probe the possible chewing map in the rest of str. */
 887     for (i = 0; i < symbols_len; ++i) {
 888         if (!search_chewing_symbols(m_symbol_table, str[i], &onechar)) {
 889             g_free(chewing);
 890             return false;
 891         }
 892
 893         if (!chewing) {
 894             chewing = g_strdup(onechar);
 895         } else {
 896             gchar * tmp = chewing;
 897             chewing = g_strconcat(chewing, onechar, NULL);
 898             g_free(tmp);
 899         }
 900     }
 901
 902     /* search the chewing in the chewing index table. */
 903     if (chewing && search_chewing_index(options, chewing, key)) {
 904         /* save back tone if available. */
 905         key.m_tone = tone;
 906         g_free(chewing);
 907         return true;
 908     }
 909
 910     g_free(chewing);
 911     return false;
 912 }
 913
 914
 915 /* only characters in chewing keyboard scheme are accepted here. */
 916 int ChewingParser2::parse(pinyin_option_t options, ChewingKeyVector & keys,
 917                           ChewingKeyRestVector & key_rests,
 918                           const char *str, int len) const {
 919     g_array_set_size(keys, 0);
 920     g_array_set_size(key_rests, 0);
 921
 922     int maximum_len = 0; int i;
 923     /* probe the longest possible chewing string. */
 924     for (i = 0; i < len; ++i) {
 925         if (!in_chewing_scheme(options, str[i], NULL))
 926             break;
 927     }
 928     maximum_len = i;
 929
 930     /* maximum forward match for chewing. */
 931     int parsed_len = 0;
 932     while (parsed_len < maximum_len) {
 933         const char * cur_str = str + parsed_len;
 934         i = std_lite::min(maximum_len - parsed_len,
 935                           (int)max_chewing_length);
 936
 937         ChewingKey key; ChewingKeyRest key_rest;
 938         for (; i > 0; --i) {
 939             bool success = parse_one_key(options, key, cur_str, i);
 940             if (success)
 941                 break;
 942         }
 943
 944         if (0 == i)        /* no more possible chewings. */
 945             break;
 946
 947         key_rest.m_raw_begin = parsed_len; key_rest.m_raw_end = parsed_len + i;
 948         parsed_len += i;
 949
 950         /* save the pinyin. */
 951         g_array_append_val(keys, key);
 952         g_array_append_val(key_rests, key_rest);
 953     }
 954
 955     return parsed_len;
 956 }
 957
 958
 959 bool ChewingParser2::set_scheme(ChewingScheme scheme) {
 960     switch(scheme) {
 961     case CHEWING_STANDARD:
 962         m_symbol_table = chewing_standard_symbols;
 963         m_tone_table   = chewing_standard_tones;
 964         return true;
 965     case CHEWING_IBM:
 966         m_symbol_table = chewing_ibm_symbols;
 967         m_tone_table   = chewing_ibm_tones;
 968         return true;
 969     case CHEWING_GINYIEH:
 970         m_symbol_table = chewing_ginyieh_symbols;
 971         m_tone_table   = chewing_ginyieh_tones;
 972         return true;
 973     case CHEWING_ETEN:
 974         m_symbol_table = chewing_eten_symbols;
 975         m_tone_table   = chewing_eten_tones;
 976         return true;
 977     }
 978
 979     return false;
 980 }
 981
 982
 983 bool ChewingParser2::in_chewing_scheme(pinyin_option_t options,
 984                                        const char key, const char ** symbol)
 985  const {
 986     const gchar * chewing = NULL;
 987     char tone = CHEWING_ZERO_TONE;
 988
 989     if (search_chewing_symbols(m_symbol_table, key, &chewing)) {
 990         if (symbol)
 991             *symbol = chewing;
 992         return true;
 993     }
 994
 995     if (!(options & USE_TONE))
 996         return false;
 997
 998     if (search_chewing_tones(m_tone_table, key, &tone)) {
 999         if (symbol)
1000             *symbol = chewing_tone_table[tone];
1001         return true;
1002     }
1003
1004     return false;
1005 }