3 * Library to deal with pinyin.
5 * Copyright (C) 2011 Peng Wu <alexepico@gmail.com>
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.
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.
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.
23 #include "pinyin_parser2.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"
37 using namespace pinyin;
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);
43 /* handle incomplete pinyin. */
44 if (flags & PINYIN_INCOMPLETE) {
45 if (!(options & PINYIN_INCOMPLETE))
49 /* handle correct pinyin, currently only one flag per item. */
50 flags &= PINYIN_CORRECT_ALL;
51 options &= PINYIN_CORRECT_ALL;
54 if ((flags & options) != flags)
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);
65 /* handle incomplete chewing. */
66 if (flags & CHEWING_INCOMPLETE) {
67 if (!(options & CHEWING_INCOMPLETE))
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);
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;
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];
89 if (CHEWING_ZERO_TONE == m_tone) {
90 return g_strdup(item.m_pinyin_str);
92 return g_strdup_printf("%s%d", item.m_pinyin_str, m_tone);
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];
101 if (CHEWING_ZERO_TONE == m_tone) {
102 return g_strdup(item.m_chewing_str);
104 return g_strdup_printf("%s%s", item.m_chewing_str,
105 chewing_tone_table[m_tone]);
110 /* methods for Chewing Keys to access pinyin parser table. */
111 const char * ChewingKeyRest::get_pinyin_string(){
112 if (m_table_index == 0)
115 /* check end boundary. */
116 assert(m_table_index < G_N_ELEMENTS(content_table));
117 return content_table[m_table_index].m_pinyin_str;
120 const char * ChewingKeyRest::get_chewing_string(){
121 if (m_table_index == 0)
124 /* check end boundary. */
125 assert(m_table_index < G_N_ELEMENTS(content_table));
126 return content_table[m_table_index].m_chewing_str;
132 /* internal information for pinyin parsers. */
133 struct parse_value_t{
135 ChewingKeyRest m_key_rest;
149 const guint16 max_full_pinyin_length = 7; /* include tone. */
151 const guint16 max_double_pinyin_length = 3; /* include tone. */
153 const guint16 max_chewing_length = 4; /* include tone. */
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);
160 static inline bool search_pinyin_index(pinyin_option_t options, const char * pinyin,
162 ChewingKeyRest & key_rest){
163 pinyin_index_item_t item;
164 memset(&item, 0, sizeof(item));
165 item.m_pinyin_input = pinyin;
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);
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;
178 if (!check_pinyin_options(options, index))
181 key_rest.m_table_index = index->m_table_index;
182 key = content_table[key_rest.m_table_index].m_chewing_key;
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);
194 static inline bool search_chewing_index(pinyin_option_t options, const char * chewing,
196 ChewingKeyRest & key_rest){
197 chewing_index_item_t item;
198 memset(&item, 0, sizeof(item));
199 item.m_chewing_input = chewing;
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);
207 guint16 range_len = range.second - range.first;
208 assert (range_len <= 1);
210 if (range_len == 1) {
211 const chewing_index_item_t * index = range.first;
213 if (!check_chewing_options(options, index))
216 key_rest.m_table_index = index->m_table_index;
217 key = content_table[key_rest.m_table_index].m_chewing_key;
224 /* Full Pinyin Parser */
225 FullPinyinParser2::FullPinyinParser2 (){
226 m_parse_steps = g_array_new(TRUE, FALSE, sizeof(parse_value_t));
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, '\''));
237 guint16 tone = CHEWING_ZERO_TONE; guint16 tone_pos = 0;
238 guint16 parsed_len = len;
239 key = ChewingKey(); key_rest = ChewingKeyRest();
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' ) {
247 tone_pos = parsed_len;
251 /* parse pinyin core staff here. */
253 /* Note: optimize here? */
254 input[parsed_len] = '\0';
255 if (!search_pinyin_index(options, input, key, key_rest)) {
260 if (options & USE_TONE) {
261 /* post processing tone. */
262 if ( parsed_len == tone_pos ) {
263 if (tone != CHEWING_ZERO_TONE) {
270 key_rest.m_raw_begin = 0; key_rest.m_raw_end = parsed_len;
272 return parsed_len == len;
276 int FullPinyinParser2::parse (pinyin_option_t options, ChewingKeyVector & keys,
277 ChewingKeyRestVector & key_rests,
278 const char *str, int len) const {
281 g_array_set_size(keys, 0);
282 g_array_set_size(key_rests, 0);
284 /* init m_parse_steps, and prepare dynamic programming. */
285 int step_len = len + 1;
286 g_array_set_size(m_parse_steps, 0);
288 for (i = 0; i < step_len; ++i) {
289 g_array_append_val(m_parse_steps, value);
293 gchar * input = g_strndup(str, len);
294 parse_value_t * curstep = NULL, * nextstep = NULL;
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);
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;
311 /* forward to next "'" */
312 if ( 0 == next_sep ) {
314 for (k = i; k < len; ++k) {
315 if (input[k] == '\'')
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);
331 const char * onepinyin = input + pos;
332 gint16 onepinyinlen = n - pos;
333 value = parse_value_t();
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;
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;
350 if (-1 == nextstep->m_last_step)
352 if (value.m_parsed_len > nextstep->m_parsed_len)
354 if (value.m_parsed_len == nextstep->m_parsed_len &&
355 value.m_num_keys < nextstep->m_num_keys)
358 /* maximum forward, set pos to n in next iteration. */
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);
373 const char * onepinyin = input + m;
374 gint16 onepinyinlen = n - m;
375 value = parse_value_t();
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;
384 //printf("onepinyin:%s len:%d\n", onepinyin, onepinyinlen);
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;
392 if (-1 == nextstep->m_last_step)
394 if (value.m_parsed_len > nextstep->m_parsed_len)
396 if (value.m_parsed_len == nextstep->m_parsed_len &&
397 value.m_num_keys < nextstep->m_num_keys)
403 /* final step for back tracing. */
404 gint16 parsed_len = final_step(step_len, keys, key_rests);
406 /* post processing for re-split table. */
407 if (options & USE_RESPLIT_TABLE) {
408 post_process(options, keys, key_rests);
415 int FullPinyinParser2::final_step(size_t step_len, ChewingKeyVector & keys,
416 ChewingKeyRestVector & key_rests) const{
418 gint16 parsed_len = 0;
419 parse_value_t * curstep = NULL;
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)
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);
433 /* save the match. */
434 while (curstep->m_last_step != -1) {
435 gint16 pos = curstep->m_num_keys - 1;
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;
446 curstep = &g_array_index(m_parse_steps, parse_value_t,
447 curstep->m_last_step);
453 bool FullPinyinParser2::post_process(pinyin_option_t options,
454 ChewingKeyVector & keys,
455 ChewingKeyRestVector & key_rests) const {
457 assert(keys->len == key_rests->len);
458 gint16 num_keys = keys->len;
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;
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);
469 if (cur_rest->m_raw_end != next_rest->m_raw_begin)
472 cur_key = &g_array_index(keys, ChewingKey, i);
473 next_key = &g_array_index(keys, ChewingKey, i + 1);
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;
481 /* lookup re-split table */
483 const resplit_table_item_t * item = NULL;
484 for (k = 0; k < G_N_ELEMENTS(resplit_table); ++k) {
485 item = resplit_table + k;
487 if (item->m_orig_freq >= item->m_new_freq)
490 /* use pinyin_exact_compare2 here. */
491 if (0 == pinyin_exact_compare2(item->m_orig_keys,
498 if (k < G_N_ELEMENTS(resplit_table)) {
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 --;
508 /* save back tones */
509 if (options & USE_TONE) {
510 cur_key->m_tone = cur_tone;
511 next_key->m_tone = next_tone;
518 #define IS_KEY(x) (('a' <= x && x <= 'z') || x == ';')
520 bool DoublePinyinParser2::parse_one_key(pinyin_option_t options, ChewingKey & key,
521 ChewingKeyRest & key_rest,
522 const char *str, int len) const {
525 if (!(options & PINYIN_INCOMPLETE))
532 int charid = ch == ';' ? 26 : ch - 'a';
533 const char * sheng = m_shengmu_table[charid].m_shengmu;
534 if (NULL == sheng || strcmp(sheng, "'") == 0)
537 if (search_pinyin_index(options, sheng, key, key_rest)) {
538 key_rest.m_raw_begin = 0; key_rest.m_raw_end = len;
545 ChewingTone tone = CHEWING_ZERO_TONE;
546 options &= ~(PINYIN_CORRECT_ALL|PINYIN_AMB_ALL);
550 if (!(options & USE_TONE))
553 if (!('0' < ch && ch <= '5'))
555 tone = (ChewingTone) (ch - '0');
558 if (2 == len || 3 == len) {
559 /* parse shengmu here. */
564 int charid = ch == ';' ? 26 : ch - 'a';
565 const char * sheng = m_shengmu_table[charid].m_shengmu;
568 if (strcmp(sheng, "'") == 0)
571 /* parse yunmu here. */
576 charid = ch == ';' ? 26 : ch - 'a';
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;
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;
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);
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')))
621 /* maximum forward match for double pinyin. */
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);
628 ChewingKey key; ChewingKeyRest key_rest;
630 bool success = parse_one_key(options, key, key_rest, cur_str, i);
635 if (0 == i) /* no more possible double pinyins. */
638 key_rest.m_raw_begin = parsed_len; key_rest.m_raw_end = parsed_len + i;
641 /* save the pinyin */
642 g_array_append_val(keys, key);
643 g_array_append_val(key_rests, key_rest);
651 bool DoublePinyinParser2::set_scheme(DoublePinyinScheme scheme) {
654 case DOUBLE_PINYIN_ZRM:
655 m_shengmu_table = double_pinyin_zrm_sheng;
656 m_yunmu_table = double_pinyin_zrm_yun;
658 case DOUBLE_PINYIN_MS:
659 m_shengmu_table = double_pinyin_mspy_sheng;
660 m_yunmu_table = double_pinyin_mspy_yun;
662 case DOUBLE_PINYIN_ZIGUANG:
663 m_shengmu_table = double_pinyin_zgpy_sheng;
664 m_yunmu_table = double_pinyin_zgpy_yun;
666 case DOUBLE_PINYIN_ABC:
667 m_shengmu_table = double_pinyin_abc_sheng;
668 m_yunmu_table = double_pinyin_abc_yun;
670 case DOUBLE_PINYIN_PYJJ:
671 m_shengmu_table = double_pinyin_pyjj_sheng;
672 m_yunmu_table = double_pinyin_pyjj_yun;
674 case DOUBLE_PINYIN_XHE:
675 m_shengmu_table = double_pinyin_xhe_sheng;
676 m_yunmu_table = double_pinyin_xhe_yun;
678 case DOUBLE_PINYIN_CUSTOMIZED:
682 return false; /* no such scheme. */
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) {
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);
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;
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;
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))
728 gchar * chewing = NULL, * onechar = NULL;
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)) {
739 chewing = g_strdup(onechar);
741 gchar * tmp = chewing;
742 chewing = g_strconcat(chewing, onechar, NULL);
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. */
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);
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]))
777 /* maximum forward match for chewing. */
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);
784 ChewingKey key; ChewingKeyRest key_rest;
786 bool success = parse_one_key(options, key, key_rest, cur_str, i);
791 if (0 == i) /* no more possible chewings. */
794 key_rest.m_raw_begin = parsed_len; key_rest.m_raw_end = parsed_len + i;
797 /* save the pinyin. */
798 g_array_append_val(keys, key);
799 g_array_append_val(key_rests, key_rest);
806 bool ChewingParser2::set_scheme(ChewingScheme scheme) {
808 case CHEWING_STANDARD:
809 m_symbol_table = chewing_standard_symbols;
810 m_tone_table = chewing_standard_tones;
813 m_symbol_table = chewing_ibm_symbols;
814 m_tone_table = chewing_ibm_tones;
816 case CHEWING_GINYIEH:
817 m_symbol_table = chewing_ginyieh_symbols;
818 m_tone_table = chewing_ginyieh_tones;
821 m_symbol_table = chewing_eten_symbols;
822 m_tone_table = chewing_eten_tones;
830 bool ChewingParser2::in_chewing_scheme(const char key) const {
831 gchar * chewing = NULL;
832 char tone = CHEWING_ZERO_TONE;
834 bool retval = search_chewing_symbols(m_symbol_table, key, &chewing) ||
835 search_chewing_tones(m_tone_table, key, &tone);