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
  33
  34 using namespace pinyin;
  35
  36 static bool check_pinyin_options(guint32 options, const pinyin_index_item_t * item) {
  37     guint32 flags = item->m_flags;
  38     assert (flags & IS_PINYIN);
  39
  40     /* handle incomplete pinyin. */
  41     if (flags & PINYIN_INCOMPLETE) {
  42         if (!(options & PINYIN_INCOMPLETE))
  43             return false;
  44     }
  45
  46     /* handle correct pinyin, currently only one flag per item. */
  47     flags &= PINYIN_CORRECT_ALL;
  48     options &= PINYIN_CORRECT_ALL;
  49
  50     if (flags) {
  51         if ((flags & options) != flags)
  52             return false;
  53     }
  54
  55     return true;
  56 }
  57
  58 static bool check_chewing_options(guint32 options, const chewing_index_item_t * item) {
  59     guint32 flags = item->m_flags;
  60     assert (flags & IS_CHEWING);
  61
  62     /* handle incomplete chewing. */
  63     if (flags & CHEWING_INCOMPLETE) {
  64         if (!(options & CHEWING_INCOMPLETE))
  65             return false;
  66     }
  67
  68     return true;
  69 }
  70
  71
  72 /* methods for Chewing Keys to access pinyin parser table. */
  73 const char * ChewingKeyRest::get_pinyin_string(){
  74     if (m_table_index == 0)
  75         return NULL;
  76
  77     /* check end boundary. */
  78     assert(m_table_index < G_N_ELEMENTS(content_table));
  79     return content_table[m_table_index].m_pinyin_str;
  80 }
  81
  82 const char * ChewingKeyRest::get_chewing_string(){
  83     if (m_table_index == 0)
  84         return NULL;
  85
  86     /* check end boundary. */
  87     assert(m_table_index < G_N_ELEMENTS(content_table));
  88     return content_table[m_table_index].m_chewing_str;
  89 }
  90
  91
  92 /* Pinyin Parsers */
  93
  94 /* internal information for pinyin parsers. */
  95 struct parse_value_t{
  96     ChewingKey m_key;
  97     ChewingKeyRest m_key_rest;
  98     gint16 m_num_keys;
  99     gint16 m_parsed_len;
 100     gint16 m_last_step;
 101
 102     /* constructor */
 103 public:
 104     parse_value_t(){
 105         m_num_keys = 0;
 106         m_parsed_len = 0;
 107         m_last_step = -1;
 108     }
 109 };
 110
 111 /* Full Pinyin Parser */
 112 FullPinyinParser2::FullPinyinParser2 (){
 113     m_parse_steps = g_array_new(TRUE, FALSE, sizeof(parse_value_t));
 114 }
 115
 116 const guint16 max_full_pinyin_length = 7;  /* include tone. */
 117
 118 static bool compare_less_than(const pinyin_index_item_t & lhs,
 119                               const pinyin_index_item_t & rhs){
 120     return 0 > strcmp(lhs.m_pinyin_input, rhs.m_pinyin_input);
 121 }
 122
 123 bool FullPinyinParser2::parse_one_key (guint32 options, ChewingKey & key,
 124                                        ChewingKeyRest & key_rest,
 125                                        const char * pinyin, int len) const {
 126     /* "'" are not accepted in parse_one_key. */
 127     assert(NULL == strchr(pinyin, '\''));
 128     gchar * input = g_strndup(pinyin, len);
 129
 130     guint16 tone = CHEWING_ZERO_TONE; guint16 tone_pos = 0;
 131     guint16 parsed_len = len;
 132     key = ChewingKey(); key_rest = ChewingKeyRest();
 133
 134     if (options & USE_TONE) {
 135         /* find the tone in the last character. */
 136         char chr = input[parsed_len - 1];
 137         if ( '0' < chr && chr <= '5' ) {
 138             tone = chr - '0';
 139             parsed_len --;
 140             tone_pos = parsed_len;
 141         }
 142     }
 143
 144     /* parse pinyin core staff here. */
 145     pinyin_index_item_t item;
 146     memset(&item, 0, sizeof(item));
 147
 148     /* Note: optimize here? */
 149     for (; parsed_len >= len - 1; --parsed_len) {
 150         input[parsed_len] = '\0';
 151         item.m_pinyin_input = input;
 152         std_lite::pair<const pinyin_index_item_t *,
 153                        const pinyin_index_item_t *> range;
 154         range = std_lite::equal_range
 155             (pinyin_index, pinyin_index + G_N_ELEMENTS(pinyin_index),
 156              item, compare_less_than);
 157
 158         guint16 range_len = range.second - range.first;
 159         assert (range_len <= 1);
 160         if ( range_len == 1 ) {
 161             const pinyin_index_item_t * index = range.first;
 162
 163             if (!check_pinyin_options(options, index))
 164                 continue;
 165
 166             key_rest.m_table_index = index->m_table_index;
 167             key = content_table[key_rest.m_table_index].m_chewing_key;
 168             break;
 169         }
 170     }
 171
 172     if (options & USE_TONE) {
 173         /* post processing tone. */
 174         if ( parsed_len == tone_pos ) {
 175             if (tone != CHEWING_ZERO_TONE) {
 176                 key.m_tone = tone;
 177                 parsed_len ++;
 178             }
 179         }
 180     }
 181
 182     key_rest.m_raw_begin = 0; key_rest.m_raw_end = parsed_len;
 183     g_free(input);
 184     return parsed_len == len;
 185 }
 186
 187
 188 int FullPinyinParser2::parse (guint32 options, ChewingKeyVector & keys,
 189                               ChewingKeyRestVector & key_rests,
 190                               const char *str, int len) const {
 191     size_t i;
 192     /* clear arrays. */
 193     g_array_set_size(keys, 0);
 194     g_array_set_size(key_rests, 0);
 195
 196     /* init m_parse_steps, and prepare dynamic programming. */
 197     size_t step_len = len + 1;
 198     g_array_set_size(m_parse_steps, 0);
 199     parse_value_t value;
 200     for (i = 0; i < step_len; ++i) {
 201         g_array_append_val(m_parse_steps, value);
 202     }
 203
 204     size_t str_len = len; size_t next_sep = 0;
 205     gchar * input = g_strndup(str, len);
 206     parse_value_t * curstep = NULL, * nextstep = NULL;
 207
 208     for (i = 0; i < len; ) {
 209         if (input[i] == '\'') {
 210             curstep = &g_array_index(m_parse_steps, parse_value_t, i);
 211             nextstep = &g_array_index(m_parse_steps, parse_value_t, i + 1);
 212
 213             /* propagate current step into next step. */
 214             nextstep->m_key = ChewingKey();
 215             nextstep->m_key_rest = ChewingKeyRest();
 216             nextstep->m_num_keys = curstep->m_num_keys;
 217             nextstep->m_parsed_len = curstep->m_parsed_len + 1;
 218             nextstep->m_last_step = i;
 219             next_sep = 0;
 220             continue;
 221         }
 222
 223         /* forward to next "'" */
 224         if ( 0 == next_sep ) {
 225             size_t k;
 226             for (k = i;  k < len; ++k) {
 227                 if (input[k] == '\'')
 228                     break;
 229             }
 230             next_sep = k;
 231             i = next_sep;
 232         }
 233
 234         /* dynamic programming here. */
 235         for (size_t m = i; m < next_sep; ++m) {
 236             curstep = &g_array_index(m_parse_steps, parse_value_t, m);
 237             size_t try_len = std_lite::min
 238                 (m + max_full_pinyin_length, next_sep);
 239             for (size_t n = m + 1; n < try_len + 1; ++n) {
 240                 nextstep = &g_array_index(m_parse_steps, parse_value_t, n);
 241
 242                 /* gen next step */
 243                 const char * onepinyin = input + m;
 244                 gint16 onepinyinlen = n - m;
 245                 value = parse_value_t();
 246
 247                 ChewingKey key; ChewingKeyRest rest;
 248                 bool parsed = parse_one_key
 249                     (options, key, rest, onepinyin, onepinyinlen);
 250                 rest.m_raw_begin = m; rest.m_raw_end = n;
 251                 if (!parsed)
 252                     continue;
 253                 value.m_key = key; value.m_key_rest = rest;
 254                 value.m_num_keys = curstep->m_num_keys + 1;
 255                 value.m_parsed_len = curstep->m_parsed_len + onepinyinlen;
 256                 value.m_last_step = m;
 257
 258                 /* save next step */
 259                 if (-1 == nextstep->m_last_step)
 260                     *nextstep = value;
 261                 if (value.m_parsed_len > nextstep->m_parsed_len)
 262                     *nextstep = value;
 263                 if (value.m_parsed_len == nextstep->m_parsed_len &&
 264                     value.m_num_keys < nextstep->m_num_keys)
 265                     *nextstep = value;
 266             }
 267         }
 268     }
 269
 270     /* final step for back tracing. */
 271     gint16 parsed_len = final_step(step_len, keys, key_rests);
 272
 273     /* post processing for re-split table. */
 274     if (options & USE_RESPLIT_TABLE) {
 275         post_process(options, keys, key_rests);
 276     }
 277
 278     g_free(input);
 279     return parsed_len;
 280 }
 281
 282 int FullPinyinParser2::final_step(size_t step_len, ChewingKeyVector & keys,
 283                                   ChewingKeyRestVector & key_rests) const{
 284     size_t i;
 285     gint16 parsed_len = 0;
 286     parse_value_t * curstep = NULL;
 287
 288     /* find longest match, which starts from the beginning of input. */
 289     for (i = step_len - 1; i >= 0; --i) {
 290         curstep = &g_array_index(m_parse_steps, parse_value_t, i);
 291         if (i == curstep->m_parsed_len)
 292             break;
 293     }
 294     /* prepare saving. */
 295     parsed_len = curstep->m_parsed_len;
 296     gint16 num_keys = curstep->m_num_keys;
 297     g_array_set_size(keys, num_keys);
 298     g_array_set_size(key_rests, num_keys);
 299
 300     /* save the match. */
 301     while (curstep->m_last_step != -1) {
 302         gint16 pos = curstep->m_num_keys - 1;
 303
 304         /* skip "'" */
 305         if (0 != curstep->m_key_rest.m_table_index) {
 306             ChewingKey * key = &g_array_index(keys, ChewingKey, pos);
 307             ChewingKeyRest * rest = &g_array_index
 308                 (key_rests, ChewingKeyRest, pos);
 309             *key = curstep->m_key; *rest = curstep->m_key_rest;
 310         }
 311
 312         /* back ward */
 313         curstep = &g_array_index(m_parse_steps, parse_value_t,
 314                                  curstep->m_last_step);
 315     }
 316     return parsed_len;
 317 }
 318
 319
 320 bool FullPinyinParser2::post_process(guint32 options,
 321                                      ChewingKeyVector & keys,
 322                                      ChewingKeyRestVector & key_rests) const {
 323     size_t i;
 324     assert(keys->len == key_rests->len);
 325     gint16 num_keys = keys->len;
 326
 327     ChewingKey * cur_key = NULL, * next_key = NULL;
 328     ChewingKeyRest * cur_rest = NULL, * next_rest = NULL;
 329     guint16 cur_tone = CHEWING_ZERO_TONE, next_tone = CHEWING_ZERO_TONE;
 330
 331     for (i = 0; i < num_keys - 1; ++i) {
 332         cur_rest = &g_array_index(key_rests, ChewingKeyRest, i);
 333         next_rest = &g_array_index(key_rests, ChewingKeyRest, i + 1);
 334
 335         /* some "'" here */
 336         if (cur_rest->m_raw_end != next_rest->m_raw_begin)
 337             continue;
 338
 339         cur_key = &g_array_index(keys, ChewingKey, i);
 340         next_key = &g_array_index(keys, ChewingKey, i + 1);
 341
 342         if (options & USE_TONE) {
 343             cur_tone = cur_key->m_tone;
 344             next_tone = next_key->m_tone;
 345             cur_key->m_tone = next_key->m_tone = CHEWING_ZERO_TONE;
 346         }
 347
 348         /* lookup re-split table */
 349         size_t k;
 350         const resplit_table_item_t * item = NULL;
 351         for (k = 0; k < G_N_ELEMENTS(resplit_table); ++k) {
 352             item = resplit_table + k;
 353             /* no ops */
 354             if (item->m_orig_freq >= item->m_new_freq)
 355                 continue;
 356             /* TODO: refine code style here. */
 357 #if 0
 358             if (item->m_orig_first_key == *cur_key &&
 359                 item->m_orig_second_key == *next_key)
 360                 break;
 361 #endif
 362             /* TODO: should use pinyin_exact_compare2 here. */
 363             assert(FALSE);
 364         }
 365         if (k < G_N_ELEMENTS(resplit_table)) {
 366             /* do re-split */
 367             item = resplit_table + k;
 368             *cur_key = item->m_new_first_key;
 369             *next_key = item->m_new_second_key;
 370             /* assumes only moved one char in gen_all_resplit script. */
 371             cur_rest->m_raw_end --;
 372             next_rest->m_raw_begin --;
 373             /* save back tones */
 374             if (options & USE_TONE) {
 375                 cur_key->m_tone = cur_tone;
 376                 next_key->m_tone = next_tone;
 377             }
 378         }
 379     }
 380
 381     return true;
 382 }