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 <ctype.h>
  24 #include <assert.h>
  25 #include <string.h>
  26 #include "stl_lite.h"
  27 #include "pinyin_parser2.h"
  28 #include "pinyin_phrase2.h"
  29 #include "pinyin_custom2.h"
  30 #include "chewing_key.h"
  31 #include "pinyin_parser_table.h"
  32 #include "double_pinyin_table.h"
  33 #include "chewing_table.h"
  34
  35
  36 using namespace pinyin;
  37
  38 static bool check_pinyin_options(guint32 options, const pinyin_index_item_t * item) {
  39     guint32 flags = item->m_flags;
  40     assert (flags & IS_PINYIN);
  41
  42     /* handle incomplete pinyin. */
  43     if (flags & PINYIN_INCOMPLETE) {
  44         if (!(options & PINYIN_INCOMPLETE))
  45             return false;
  46     }
  47
  48     /* handle correct pinyin, currently only one flag per item. */
  49     flags &= PINYIN_CORRECT_ALL;
  50     options &= PINYIN_CORRECT_ALL;
  51
  52     if (flags) {
  53         if ((flags & options) != flags)
  54             return false;
  55     }
  56
  57     return true;
  58 }
  59
  60 static bool check_chewing_options(guint32 options, const chewing_index_item_t * item) {
  61     guint32 flags = item->m_flags;
  62     assert (flags & IS_CHEWING);
  63
  64     /* handle incomplete chewing. */
  65     if (flags & CHEWING_INCOMPLETE) {
  66         if (!(options & CHEWING_INCOMPLETE))
  67             return false;
  68     }
  69
  70     return true;
  71 }
  72
  73
  74 /* methods for Chewing Keys to access pinyin parser table. */
  75 const char * ChewingKeyRest::get_pinyin_string(){
  76     if (m_table_index == 0)
  77         return NULL;
  78
  79     /* check end boundary. */
  80     assert(m_table_index < G_N_ELEMENTS(content_table));
  81     return content_table[m_table_index].m_pinyin_str;
  82 }
  83
  84 const char * ChewingKeyRest::get_chewing_string(){
  85     if (m_table_index == 0)
  86         return NULL;
  87
  88     /* check end boundary. */
  89     assert(m_table_index < G_N_ELEMENTS(content_table));
  90     return content_table[m_table_index].m_chewing_str;
  91 }
  92
  93
  94 /* Pinyin Parsers */
  95
  96 /* internal information for pinyin parsers. */
  97 struct parse_value_t{
  98     ChewingKey m_key;
  99     ChewingKeyRest m_key_rest;
 100     gint16 m_num_keys;
 101     gint16 m_parsed_len;
 102     gint16 m_last_step;
 103
 104     /* constructor */
 105 public:
 106     parse_value_t(){
 107         m_num_keys = 0;
 108         m_parsed_len = 0;
 109         m_last_step = -1;
 110     }
 111 };
 112
 113 const guint16 max_full_pinyin_length   = 7;  /* include tone. */
 114
 115 const guint16 max_double_pinyin_length = 3;  /* include tone. */
 116
 117 const guint16 max_chewing_length       = 4;  /* include tone. */
 118
 119 static bool compare_less_than(const pinyin_index_item_t & lhs,
 120                               const pinyin_index_item_t & rhs){
 121     return 0 > strcmp(lhs.m_pinyin_input, rhs.m_pinyin_input);
 122 }
 123
 124 static inline bool search_pinyin_index(guint32 options, const char * pinyin,
 125                                        ChewingKey & key,
 126                                        ChewingKeyRest & key_rest){
 127     pinyin_index_item_t item;
 128     memset(&item, 0, sizeof(item));
 129     item.m_pinyin_input = pinyin;
 130
 131     std_lite::pair<const pinyin_index_item_t *,
 132                    const pinyin_index_item_t *> range;
 133     range = std_lite::equal_range
 134         (pinyin_index, pinyin_index + G_N_ELEMENTS(pinyin_index),
 135          item, compare_less_than);
 136
 137     guint16 range_len = range.second - range.first;
 138     assert (range_len <= 1);
 139     if ( range_len == 1 ) {
 140         const pinyin_index_item_t * index = range.first;
 141
 142         if (!check_pinyin_options(options, index))
 143             return false;
 144
 145         key_rest.m_table_index = index->m_table_index;
 146         key = content_table[key_rest.m_table_index].m_chewing_key;
 147         return true;
 148     }
 149
 150     return false;
 151 }
 152
 153 /* Full Pinyin Parser */
 154 FullPinyinParser2::FullPinyinParser2 (){
 155     m_parse_steps = g_array_new(TRUE, FALSE, sizeof(parse_value_t));
 156 }
 157
 158
 159 bool FullPinyinParser2::parse_one_key (guint32 options, ChewingKey & key,
 160                                        ChewingKeyRest & key_rest,
 161                                        const char * pinyin, int len) const {
 162     /* "'" are not accepted in parse_one_key. */
 163     assert(NULL == strchr(pinyin, '\''));
 164     gchar * input = g_strndup(pinyin, len);
 165
 166     guint16 tone = CHEWING_ZERO_TONE; guint16 tone_pos = 0;
 167     guint16 parsed_len = len;
 168     key = ChewingKey(); key_rest = ChewingKeyRest();
 169
 170     if (options & USE_TONE) {
 171         /* find the tone in the last character. */
 172         char chr = input[parsed_len - 1];
 173         if ( '0' < chr && chr <= '5' ) {
 174             tone = chr - '0';
 175             parsed_len --;
 176             tone_pos = parsed_len;
 177         }
 178     }
 179
 180     /* parse pinyin core staff here. */
 181
 182     /* Note: optimize here? */
 183     input[parsed_len] = '\0';
 184     if (!search_pinyin_index(options, input, key, key_rest))
 185         --parsed_len;
 186
 187     if (options & USE_TONE) {
 188         /* post processing tone. */
 189         if ( parsed_len == tone_pos ) {
 190             if (tone != CHEWING_ZERO_TONE) {
 191                 key.m_tone = tone;
 192                 parsed_len ++;
 193             }
 194         }
 195     }
 196
 197     key_rest.m_raw_begin = 0; key_rest.m_raw_end = parsed_len;
 198     g_free(input);
 199     return parsed_len == len;
 200 }
 201
 202
 203 int FullPinyinParser2::parse (guint32 options, ChewingKeyVector & keys,
 204                               ChewingKeyRestVector & key_rests,
 205                               const char *str, int len) const {
 206     int i;
 207     /* clear arrays. */
 208     g_array_set_size(keys, 0);
 209     g_array_set_size(key_rests, 0);
 210
 211     /* init m_parse_steps, and prepare dynamic programming. */
 212     int step_len = len + 1;
 213     g_array_set_size(m_parse_steps, 0);
 214     parse_value_t value;
 215     for (i = 0; i < step_len; ++i) {
 216         g_array_append_val(m_parse_steps, value);
 217     }
 218
 219     size_t next_sep = 0;
 220     gchar * input = g_strndup(str, len);
 221     parse_value_t * curstep = NULL, * nextstep = NULL;
 222
 223     for (i = 0; i < len; ) {
 224         if (input[i] == '\'') {
 225             curstep = &g_array_index(m_parse_steps, parse_value_t, i);
 226             nextstep = &g_array_index(m_parse_steps, parse_value_t, i + 1);
 227
 228             /* propagate current step into next step. */
 229             nextstep->m_key = ChewingKey();
 230             nextstep->m_key_rest = ChewingKeyRest();
 231             nextstep->m_num_keys = curstep->m_num_keys;
 232             nextstep->m_parsed_len = curstep->m_parsed_len + 1;
 233             nextstep->m_last_step = i;
 234             next_sep = 0;
 235             continue;
 236         }
 237
 238         /* forward to next "'" */
 239         if ( 0 == next_sep ) {
 240             int k;
 241             for (k = i;  k < len; ++k) {
 242                 if (input[k] == '\'')
 243                     break;
 244             }
 245             next_sep = k;
 246             i = next_sep;
 247         }
 248
 249         /* dynamic programming here. */
 250         for (size_t m = i; m < next_sep; ++m) {
 251             curstep = &g_array_index(m_parse_steps, parse_value_t, m);
 252             size_t try_len = std_lite::min
 253                 (m + max_full_pinyin_length, next_sep);
 254             for (size_t n = m + 1; n < try_len + 1; ++n) {
 255                 nextstep = &g_array_index(m_parse_steps, parse_value_t, n);
 256
 257                 /* gen next step */
 258                 const char * onepinyin = input + m;
 259                 gint16 onepinyinlen = n - m;
 260                 value = parse_value_t();
 261
 262                 ChewingKey key; ChewingKeyRest rest;
 263                 bool parsed = parse_one_key
 264                     (options, key, rest, onepinyin, onepinyinlen);
 265                 rest.m_raw_begin = m; rest.m_raw_end = n;
 266                 if (!parsed)
 267                     continue;
 268                 value.m_key = key; value.m_key_rest = rest;
 269                 value.m_num_keys = curstep->m_num_keys + 1;
 270                 value.m_parsed_len = curstep->m_parsed_len + onepinyinlen;
 271                 value.m_last_step = m;
 272
 273                 /* save next step */
 274                 if (-1 == nextstep->m_last_step)
 275                     *nextstep = value;
 276                 if (value.m_parsed_len > nextstep->m_parsed_len)
 277                     *nextstep = value;
 278                 if (value.m_parsed_len == nextstep->m_parsed_len &&
 279                     value.m_num_keys < nextstep->m_num_keys)
 280                     *nextstep = value;
 281             }
 282         }
 283     }
 284
 285     /* final step for back tracing. */
 286     gint16 parsed_len = final_step(step_len, keys, key_rests);
 287
 288     /* post processing for re-split table. */
 289     if (options & USE_RESPLIT_TABLE) {
 290         post_process(options, keys, key_rests);
 291     }
 292
 293     g_free(input);
 294     return parsed_len;
 295 }
 296
 297 int FullPinyinParser2::final_step(size_t step_len, ChewingKeyVector & keys,
 298                                   ChewingKeyRestVector & key_rests) const{
 299     int i;
 300     gint16 parsed_len = 0;
 301     parse_value_t * curstep = NULL;
 302
 303     /* find longest match, which starts from the beginning of input. */
 304     for (i = step_len - 1; i >= 0; --i) {
 305         curstep = &g_array_index(m_parse_steps, parse_value_t, i);
 306         if (i == curstep->m_parsed_len)
 307             break;
 308     }
 309     /* prepare saving. */
 310     parsed_len = curstep->m_parsed_len;
 311     gint16 num_keys = curstep->m_num_keys;
 312     g_array_set_size(keys, num_keys);
 313     g_array_set_size(key_rests, num_keys);
 314
 315     /* save the match. */
 316     while (curstep->m_last_step != -1) {
 317         gint16 pos = curstep->m_num_keys - 1;
 318
 319         /* skip "'" */
 320         if (0 != curstep->m_key_rest.m_table_index) {
 321             ChewingKey * key = &g_array_index(keys, ChewingKey, pos);
 322             ChewingKeyRest * rest = &g_array_index
 323                 (key_rests, ChewingKeyRest, pos);
 324             *key = curstep->m_key; *rest = curstep->m_key_rest;
 325         }
 326
 327         /* back ward */
 328         curstep = &g_array_index(m_parse_steps, parse_value_t,
 329                                  curstep->m_last_step);
 330     }
 331     return parsed_len;
 332 }
 333
 334
 335 bool FullPinyinParser2::post_process(guint32 options,
 336                                      ChewingKeyVector & keys,
 337                                      ChewingKeyRestVector & key_rests) const {
 338     int i;
 339     assert(keys->len == key_rests->len);
 340     gint16 num_keys = keys->len;
 341
 342     ChewingKey * cur_key = NULL, * next_key = NULL;
 343     ChewingKeyRest * cur_rest = NULL, * next_rest = NULL;
 344     guint16 cur_tone = CHEWING_ZERO_TONE, next_tone = CHEWING_ZERO_TONE;
 345
 346     for (i = 0; i < num_keys - 1; ++i) {
 347         cur_rest = &g_array_index(key_rests, ChewingKeyRest, i);
 348         next_rest = &g_array_index(key_rests, ChewingKeyRest, i + 1);
 349
 350         /* some "'" here */
 351         if (cur_rest->m_raw_end != next_rest->m_raw_begin)
 352             continue;
 353
 354         cur_key = &g_array_index(keys, ChewingKey, i);
 355         next_key = &g_array_index(keys, ChewingKey, i + 1);
 356
 357         if (options & USE_TONE) {
 358             cur_tone = cur_key->m_tone;
 359             next_tone = next_key->m_tone;
 360             cur_key->m_tone = next_key->m_tone = CHEWING_ZERO_TONE;
 361         }
 362
 363         /* lookup re-split table */
 364         size_t k;
 365         const resplit_table_item_t * item = NULL;
 366         for (k = 0; k < G_N_ELEMENTS(resplit_table); ++k) {
 367             item = resplit_table + k;
 368             /* no ops */
 369             if (item->m_orig_freq >= item->m_new_freq)
 370                 continue;
 371
 372             /* use pinyin_exact_compare2 here. */
 373             if (0 == pinyin_exact_compare2(item->m_orig_keys,
 374                                            cur_key, 2))
 375                 break;
 376
 377         }
 378
 379         /* find the match */
 380         if (k < G_N_ELEMENTS(resplit_table)) {
 381             /* do re-split */
 382             item = resplit_table + k;
 383             *cur_key = item->m_new_keys[0];
 384             *next_key = item->m_new_keys[1];
 385             /* assumes only moved one char in gen_all_resplit script. */
 386             cur_rest->m_raw_end --;
 387             next_rest->m_raw_begin --;
 388         }
 389
 390         /* save back tones */
 391         if (options & USE_TONE) {
 392             cur_key->m_tone = cur_tone;
 393             next_key->m_tone = next_tone;
 394         }
 395     }
 396
 397     return true;
 398 }
 399
 400 #define IS_KEY(x)   (('a' <= x && x <= 'z') || x == ';')
 401
 402 bool DoublePinyinParser2::parse_one_key (guint32 options, ChewingKey & key,
 403                                          ChewingKeyRest & key_rest,
 404                                          const char *str, int len) const{
 405
 406     if (1 == len) {
 407         if (!(options & PINYIN_INCOMPLETE))
 408             return false;
 409
 410         char ch = str[0];
 411         if (!IS_KEY(ch))
 412             return false;
 413
 414         int charid = ch == ';' ? 26 : ch - 'a';
 415         const char * sheng = m_shengmu_table[charid].m_shengmu;
 416         if (NULL == sheng || strcmp(sheng, "'") == 0)
 417             return false;
 418
 419         if (search_pinyin_index(options, sheng, key, key_rest)) {
 420             key_rest.m_raw_begin = 0; key_rest.m_raw_end = len;
 421             return true;
 422         } else {
 423             return false;
 424         }
 425     }
 426
 427     ChewingTone tone = CHEWING_ZERO_TONE;
 428     options &= ~(PINYIN_CORRECT_ALL|PINYIN_AMB_ALL);
 429
 430     /* parse tone */
 431     if (3 == len) {
 432         if (!(options & USE_TONE))
 433             return false;
 434         char ch = str[2];
 435         if (!('0' < ch && ch <= '5'))
 436             return false;
 437         tone = (ChewingTone) (ch - '0');
 438     }
 439
 440     if (2 == len || 3 == len) {
 441         /* parse shengmu here. */
 442         char ch = str[0];
 443         if (!IS_KEY(ch))
 444             return false;
 445
 446         int charid = ch == ';' ? 26 : ch - 'a';
 447         const char * sheng = m_shengmu_table[charid].m_shengmu;
 448         if (NULL == sheng)
 449             return false;
 450         if (strcmp(sheng, "'") == 0)
 451             sheng = "";
 452
 453         /* parse yunmu here. */
 454         ch = str[1];
 455         if (!IS_KEY(ch))
 456             return false;
 457
 458         charid = ch == ';' ? 26 : ch - 'a';
 459         /* first yunmu */
 460         const char * yun = m_yunmu_table[charid].m_yunmus[0];
 461         gchar * pinyin = g_strdup_printf("%s%s", sheng, yun);
 462         if (search_pinyin_index(options, pinyin, key, key_rest)) {
 463             key_rest.m_raw_begin = 0; key_rest.m_raw_end = len;
 464             key.m_tone = tone;
 465             g_free(pinyin);
 466             return true;
 467         }
 468         g_free(pinyin);
 469
 470         /* second yunmu */
 471         yun = m_yunmu_table[charid].m_yunmus[1];
 472         pinyin = g_strdup_printf("%s%s", sheng, yun);
 473         if (search_pinyin_index(options, pinyin, key, key_rest)) {
 474             key_rest.m_raw_begin = 0; key_rest.m_raw_end = len;
 475             key.m_tone = tone;
 476             g_free(pinyin);
 477             return true;
 478         }
 479         g_free(pinyin);
 480
 481     }
 482
 483     return false;
 484 }
 485
 486
 487 /* only 'a'-'z' and ';' are accepted here. */
 488 int DoublePinyinParser2::parse (guint32 options, ChewingKeyVector & keys,
 489                                 ChewingKeyRestVector & key_rests,
 490                                 const char *str, int len) const{
 491     g_array_set_size(keys, 0);
 492     g_array_set_size(key_rests, 0);
 493
 494     int maximum_len = 0; int i;
 495     /* probe the longest possible double pinyin string. */
 496     for (i = 0; i < len; ++i) {
 497         if (!IS_KEY(str[i]))
 498             break;
 499     }
 500     maximum_len = i;
 501
 502     /* maximum forward match for double pinyin. */
 503     int parsed_len = 0;
 504     while (parsed_len < maximum_len) {
 505         const char * cur_str = str + parsed_len;
 506         i = std_lite::min(maximum_len - parsed_len,
 507                           (int)max_double_pinyin_length);
 508
 509         ChewingKey key; ChewingKeyRest key_rest;
 510         for (; i > 0; --i) {
 511             bool success = parse_one_key(options, key, key_rest, cur_str, i);
 512             if (success)
 513                 break;
 514         }
 515
 516         if (0 == i)        /* no more possible double pinyins. */
 517             break;
 518
 519         key_rest.m_raw_begin = parsed_len; key_rest.m_raw_end = parsed_len + i;
 520         parsed_len += i;
 521
 522         /* save the pinyin */
 523         g_array_append_val(keys, key);
 524         g_array_append_val(key_rests, key_rest);
 525     }
 526
 527     return parsed_len;
 528 }
 529
 530 #undef IS_KEY
 531
 532 bool DoublePinyinParser2::set_scheme(DoublePinyinScheme scheme) {
 533
 534     switch (scheme) {
 535     case DOUBLE_PINYIN_ZRM:
 536         m_shengmu_table = double_pinyin_zrm_sheng;
 537         m_yunmu_table   = double_pinyin_zrm_yun;
 538         return true;
 539     case DOUBLE_PINYIN_MS:
 540         m_shengmu_table = double_pinyin_mspy_sheng;
 541         m_yunmu_table   = double_pinyin_mspy_yun;
 542         return true;
 543     case DOUBLE_PINYIN_ZIGUANG:
 544         m_shengmu_table = double_pinyin_zgpy_sheng;
 545         m_yunmu_table   = double_pinyin_zgpy_yun;
 546         return true;
 547     case DOUBLE_PINYIN_ABC:
 548         m_shengmu_table = double_pinyin_abc_sheng;
 549         m_yunmu_table   = double_pinyin_abc_yun;
 550         return true;
 551     case DOUBLE_PINYIN_PYJJ:
 552         m_shengmu_table = double_pinyin_pyjj_sheng;
 553         m_yunmu_table   = double_pinyin_pyjj_yun;
 554         return true;
 555     case DOUBLE_PINYIN_XHE:
 556         m_shengmu_table = double_pinyin_xhe_sheng;
 557         m_yunmu_table   = double_pinyin_xhe_yun;
 558         return true;
 559     case DOUBLE_PINYIN_CUSTOMIZED:
 560         assert(FALSE);
 561     };
 562
 563     return false; /* no such scheme. */
 564 }
 565
 566
 567 bool ChewingParser2::parse_one_key(guint32 options, ChewingKey & key, ChewingKeyRest & key_rest, const char *str, int len) const {
 568     assert(FALSE);
 569 }
 570
 571
 572 int ChewingParser2::parse(guint32 options, ChewingKeyVector & keys, ChewingKeyRestVector & key_rests, const char *str, int len) const {
 573     assert(FALSE);
 574 }
 575
 576
 577 bool ChewingParser2::set_scheme(ChewingScheme scheme) {
 578     switch(scheme) {
 579     case CHEWING_STANDARD:
 580         m_symbol_table = chewing_standard_symbols;
 581         m_tone_table   = chewing_standard_tones;
 582         return true;
 583     case CHEWING_IBM:
 584         m_symbol_table = chewing_ibm_symbols;
 585         m_tone_table   = chewing_ibm_tones;
 586         return true;
 587     case CHEWING_GINYIEH:
 588         m_symbol_table = chewing_ginyieh_symbols;
 589         m_tone_table   = chewing_ginyieh_tones;
 590         return true;
 591     case CHEWING_ETEN:
 592         m_symbol_table = chewing_eten_symbols;
 593         m_tone_table   = chewing_eten_tones;
 594         return true;
 595     }
 596
 597     return false;
 598 }