diff options
Diffstat (limited to 'src/lookup/pinyin_lookup.cpp')
| -rw-r--r-- | src/lookup/pinyin_lookup.cpp | 546 |
1 files changed, 0 insertions, 546 deletions
diff --git a/src/lookup/pinyin_lookup.cpp b/src/lookup/pinyin_lookup.cpp deleted file mode 100644 index 547031a..0000000 --- a/src/lookup/pinyin_lookup.cpp +++ /dev/null @@ -1,546 +0,0 @@ -/* - * libpinyin - * Library to deal with pinyin. - * - * Copyright (C) 2006-2007 Peng Wu - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - */ - - -#include "pinyin_lookup.h" -#include <math.h> -#include <assert.h> -#include "stl_lite.h" -#include "novel_types.h" -#include "pinyin_phrase2.h" -#include "facade_chewing_table.h" -#include "ngram.h" -#include "winner_tree.h" - -using namespace pinyin; - -const gfloat PinyinLookup::bigram_lambda = LAMBDA_PARAMETER; -const gfloat PinyinLookup::unigram_lambda = 1 - LAMBDA_PARAMETER; - -static void clear_steps(GPtrArray * steps_index, GPtrArray * steps_content){ - /* clear steps_index */ - for ( size_t i = 0; i < steps_index->len; ++i){ - GHashTable * table = (GHashTable *) g_ptr_array_index(steps_index, i); - g_hash_table_destroy(table); - g_ptr_array_index(steps_index, i) = NULL; - } - - /* clear steps_content */ - for ( size_t i = 0; i < steps_content->len; ++i){ - GArray * array = (GArray *) g_ptr_array_index(steps_content, i); - g_array_free(array, TRUE); - g_ptr_array_index(steps_content, i) = NULL; - } -} - -PinyinLookup::PinyinLookup(pinyin_option_t options, - FacadeChewingTable * pinyin_table, - FacadePhraseIndex * phrase_index, - Bigram * system_bigram, - Bigram * user_bigram){ - m_options = options; - m_pinyin_table = pinyin_table; - m_phrase_index = phrase_index; - m_system_bigram = system_bigram; - m_user_bigram = user_bigram; - - m_winner_tree = new WinnerTree; - m_steps_index = g_ptr_array_new(); - m_steps_content = g_ptr_array_new(); - m_table_cache = g_array_new(FALSE, TRUE, sizeof(PhraseIndexRanges)); - g_array_set_size(m_table_cache, 1); -} - -PinyinLookup::~PinyinLookup(){ - if ( m_winner_tree ) - delete m_winner_tree; - m_winner_tree = NULL; - - //free resources - for ( size_t i = 0; i < m_table_cache->len; ++i){ - PhraseIndexRanges * ranges = &g_array_index(m_table_cache, PhraseIndexRanges, i); - m_phrase_index->destroy_ranges(*ranges); - } - - g_array_free(m_table_cache, TRUE); - - clear_steps(m_steps_index, m_steps_content); - g_ptr_array_free(m_steps_index, TRUE); - g_ptr_array_free(m_steps_content, TRUE); -} - -size_t PinyinLookup::prepare_table_cache(int nstep, int total_pinyin){ - /* free resources */ - for ( size_t i = 0; i < m_table_cache->len; ++i){ - PhraseIndexRanges * ranges = &g_array_index(m_table_cache, PhraseIndexRanges, i); - m_phrase_index->destroy_ranges(*ranges); - } - - ChewingKey * pinyin_keys = (ChewingKey *)m_keys->data; - pinyin_keys += nstep; - g_array_set_size(m_table_cache, MAX_PHRASE_LENGTH + 1); - - int len, total_len = std_lite::min(total_pinyin, MAX_PHRASE_LENGTH); - - for ( len = 1; len <= total_len; ++len){ - PhraseIndexRanges * ranges = &g_array_index(m_table_cache, PhraseIndexRanges, len); - m_phrase_index->prepare_ranges(*ranges); - int result = m_pinyin_table->search(len, pinyin_keys, *ranges); - if (!( result & SEARCH_CONTINUED)){ - ++len; - break; - } - } - g_array_set_size(m_table_cache, std_lite::min(len, MAX_PHRASE_LENGTH + 1)); - return m_table_cache->len - 1; -} - -bool PinyinLookup::get_best_match(TokenVector prefixes, - ChewingKeyVector keys, - CandidateConstraints constraints, - MatchResults & results){ - //g_array_set_size(results, 0); - - m_constraints = constraints; - m_keys = keys; - int nstep = keys->len + 1; - - clear_steps(m_steps_index, m_steps_content); - - //add null start step - g_ptr_array_set_size(m_steps_index, nstep); - g_ptr_array_set_size(m_steps_content, nstep); - - for ( int i = 0; i < nstep; ++i ){ - //initialize m_steps_index - g_ptr_array_index(m_steps_index, i) = g_hash_table_new(g_direct_hash, g_direct_equal); - //initialize m_steps_content - g_ptr_array_index(m_steps_content, i) = g_array_new(FALSE, FALSE, sizeof(lookup_value_t)); - } - - for ( int i = 0; i < prefixes->len; ++i ){ - phrase_token_t token = g_array_index(prefixes, phrase_token_t, i); - lookup_key_t initial_key = token; - lookup_value_t initial_value(log(1)); - initial_value.m_handles[1] = token; - - GArray * initial_step_content = (GArray *) g_ptr_array_index(m_steps_content, 0); - initial_step_content = g_array_append_val(initial_step_content, initial_value); - GHashTable * initial_step_index = (GHashTable *) g_ptr_array_index(m_steps_index, 0); - g_hash_table_insert(initial_step_index, GUINT_TO_POINTER(initial_key), GUINT_TO_POINTER(initial_step_content->len - 1)); - } - - /* begin the Viterbi beam search. */ - for ( int i = 0; i < nstep - 1; ++i ){ - LookupStepContent tmp_step = (LookupStepContent) g_ptr_array_index(m_steps_content, i); - IBranchIterator * iter = m_winner_tree->get_iterator(tmp_step); - size_t npinyin = prepare_table_cache(i, keys->len - i); - search_bigram(iter, i, npinyin), - search_unigram(iter, i, npinyin); - delete iter; - } - return final_step(results); -} - -bool PinyinLookup::search_unigram(IBranchIterator * iter, int nstep, int npinyin){ - lookup_constraint_t* constraint = &g_array_index(m_constraints, lookup_constraint_t, nstep); - if ( CONSTRAINT_NOSEARCH == constraint->m_type ) - return false; - GArray * lookup_content = (GArray *) g_ptr_array_index(m_steps_content, nstep); - if ( 0 == lookup_content->len ) - return false; - lookup_value_t max_step = iter->max(); - if ( CONSTRAINT_ONESTEP == constraint->m_type){ - return unigram_gen_next_step(nstep, &max_step, constraint->m_token); - } - if ( NO_CONSTRAINT == constraint->m_type ){ - bool found = false; - for ( size_t i = 1; i < m_table_cache->len && i <= MAX_PHRASE_LENGTH; ++i){ - lookup_constraint_t * constraint = &g_array_index(m_constraints, lookup_constraint_t, nstep + i - 1); - if ( constraint->m_type == CONSTRAINT_NOSEARCH ) - break; - PhraseIndexRanges * ranges = &g_array_index(m_table_cache,PhraseIndexRanges, i); - for ( size_t m = 0; m < PHRASE_INDEX_LIBRARY_COUNT; ++m){ - GArray * array = (*ranges)[m]; - if ( !array ) continue; - for ( size_t n = 0; n < array->len; ++n){ - PhraseIndexRange * range = &g_array_index(array, PhraseIndexRange, n); - for ( phrase_token_t token = range->m_range_begin; - token != range->m_range_end; ++token){ - found = unigram_gen_next_step(nstep, &max_step, token)|| found; - } - } - } - } - return found; - } - return false; -} - - -bool PinyinLookup::search_bigram(IBranchIterator * iter, - int nstep, int npinyin){ - lookup_constraint_t* constraint = &g_array_index(m_constraints, lookup_constraint_t, nstep); - if ( CONSTRAINT_NOSEARCH == constraint->m_type ) - return false; - - bool found = false; - BigramPhraseArray bigram_phrase_items = g_array_new(FALSE, FALSE, - sizeof(BigramPhraseItem)); - while ( iter->has_next() ){ - lookup_value_t cur_step = iter->next(); - //printf("token:%d\t%d\n", cur_step.m_handles[0], cur_step.m_handles[1]); - phrase_token_t index_token = cur_step.m_handles[1]; - SingleGram * system, * user; - m_system_bigram->load(index_token, system); - m_user_bigram->load(index_token, user); - - if ( !merge_single_gram(&m_merged_single_gram, system, user) ) - continue; - - if ( CONSTRAINT_ONESTEP == constraint->m_type ){ - phrase_token_t token = constraint->m_token; - - guint32 freq; - if( m_merged_single_gram.get_freq(token, freq) ){ - guint32 total_freq; - m_merged_single_gram.get_total_freq(total_freq); - gfloat bigram_poss = freq / (gfloat) total_freq; - found = bigram_gen_next_step(nstep, &cur_step, token, bigram_poss) || found; - } - } - - if ( NO_CONSTRAINT == constraint->m_type ){ - for ( size_t i = 1; i < m_table_cache->len - && i <= MAX_PHRASE_LENGTH; ++i ){ - lookup_constraint_t * constraint = &g_array_index(m_constraints, lookup_constraint_t, nstep + i - 1); - if ( constraint->m_type == CONSTRAINT_NOSEARCH ) - break; - - PhraseIndexRanges * ranges = &g_array_index(m_table_cache, PhraseIndexRanges, i); - for( size_t m = 0; m < PHRASE_INDEX_LIBRARY_COUNT; ++m){ - GArray * array = (*ranges)[m]; - if ( !array ) continue; - - for ( size_t n = 0; n < array->len; ++n){ - PhraseIndexRange * range = - &g_array_index(array, PhraseIndexRange, n); - - g_array_set_size(bigram_phrase_items, 0); - m_merged_single_gram.search(range, bigram_phrase_items); - for( size_t k = 0; k < bigram_phrase_items->len; - ++k){ - BigramPhraseItem * item = &g_array_index(bigram_phrase_items, BigramPhraseItem, k); - found = bigram_gen_next_step(nstep, &cur_step, item->m_token, item->m_freq) || found; - } - } - } - } - } - if (system) - delete system; - if (user) - delete user; - } - g_array_free(bigram_phrase_items, TRUE); - return found; -} - - -bool PinyinLookup::unigram_gen_next_step(int nstep, lookup_value_t * cur_step, phrase_token_t token){ - ChewingKey * pinyinkeys = ((ChewingKey *)m_keys->data) + nstep; - if (m_phrase_index->get_phrase_item(token, m_cache_phrase_item)) - return false; - size_t phrase_length = m_cache_phrase_item.get_phrase_length(); - gdouble elem_poss = m_cache_phrase_item.get_unigram_frequency() / (gdouble) - m_phrase_index->get_phrase_index_total_freq(); - if ( elem_poss < DBL_EPSILON ) - return false; - gfloat pinyin_poss = m_cache_phrase_item.get_pronunciation_possibility(m_options, pinyinkeys); - if (pinyin_poss < FLT_EPSILON ) - return false; - lookup_value_t next_step; - next_step.m_handles[0] = cur_step->m_handles[1]; next_step.m_handles[1] = token; - next_step.m_poss = cur_step->m_poss + log(elem_poss * pinyin_poss * unigram_lambda); - next_step.m_last_step = nstep; - - return save_next_step(nstep + phrase_length, cur_step, &next_step); -} - -bool PinyinLookup::bigram_gen_next_step(int nstep, lookup_value_t * cur_step, phrase_token_t token, gfloat bigram_poss){ - ChewingKey * pinyinkeys = ((ChewingKey *)m_keys->data) + nstep; - if (m_phrase_index->get_phrase_item(token, m_cache_phrase_item)) - return false; - size_t phrase_length = m_cache_phrase_item.get_phrase_length(); - gdouble unigram_poss = m_cache_phrase_item.get_unigram_frequency() / - (gdouble) m_phrase_index->get_phrase_index_total_freq(); - - if ( bigram_poss < FLT_EPSILON && unigram_poss < DBL_EPSILON ) - return false; - gfloat pinyin_poss = m_cache_phrase_item.get_pronunciation_possibility(m_options, pinyinkeys); - if ( pinyin_poss < FLT_EPSILON ) - return false; - lookup_value_t next_step; - next_step.m_handles[0] = cur_step->m_handles[1]; next_step.m_handles[1] = token; - next_step.m_poss = cur_step->m_poss + - log(( bigram_lambda * bigram_poss + unigram_lambda * unigram_poss) *pinyin_poss); - next_step.m_last_step = nstep; - - return save_next_step(nstep + phrase_length, cur_step, &next_step); -} - -bool PinyinLookup::save_next_step(int next_step_pos, lookup_value_t * cur_step, lookup_value_t * next_step){ - lookup_key_t next_key = next_step->m_handles[1]; - GHashTable * next_lookup_index = (GHashTable *) g_ptr_array_index(m_steps_index, next_step_pos); - GArray * next_lookup_content = (GArray *) g_ptr_array_index(m_steps_content, next_step_pos); - - gpointer key, value; - gboolean lookup_result = g_hash_table_lookup_extended(next_lookup_index, GUINT_TO_POINTER(next_key), &key, &value); - size_t step_index = GPOINTER_TO_UINT(value); - if ( !lookup_result ){ - g_array_append_val(next_lookup_content, *next_step); - g_hash_table_insert(next_lookup_index, GUINT_TO_POINTER(next_key), GUINT_TO_POINTER(next_lookup_content->len - 1)); - return true; - }else{ - lookup_value_t * orig_next_value = &g_array_index(next_lookup_content, lookup_value_t,step_index); - if ( orig_next_value->m_poss < next_step->m_poss) { - orig_next_value->m_handles[0] = next_step->m_handles[0]; - assert(orig_next_value->m_handles[1] == next_step->m_handles[1]); - orig_next_value->m_poss = next_step->m_poss; - orig_next_value->m_last_step = next_step->m_last_step; - return true; - } - return false; - } -} - -bool PinyinLookup::final_step(MatchResults & results){ - //reset results - g_array_set_size(results, m_steps_content->len - 1); - for ( size_t i = 0 ; i < results->len ; ++i){ - phrase_token_t * token = &g_array_index(results, phrase_token_t, i); - *token = null_token; - } - //find max element - size_t last_step_pos = m_steps_content->len - 1; - - GArray * last_step_array = (GArray *)g_ptr_array_index(m_steps_content, last_step_pos); - if ( last_step_array->len == 0 ) - return false; - lookup_value_t * max_value = &g_array_index(last_step_array, lookup_value_t, 0); - for ( size_t i = 1; i < last_step_array->len; ++i){ - lookup_value_t * cur_value = &g_array_index(last_step_array, lookup_value_t, i); - if ( cur_value->m_poss > max_value->m_poss ) - max_value = cur_value; - } - - //backtracing - while( true ){ - int cur_step_pos = max_value->m_last_step; - if ( -1 == cur_step_pos ) - break; - - phrase_token_t * token = &g_array_index(results, phrase_token_t, cur_step_pos); - *token = max_value->m_handles[1]; - - phrase_token_t last_token = max_value->m_handles[0]; - - - GHashTable * lookup_step_index = (GHashTable *)g_ptr_array_index(m_steps_index, cur_step_pos); - gpointer key, value; - gboolean result = g_hash_table_lookup_extended(lookup_step_index, GUINT_TO_POINTER(last_token), &key, &value); - if (!result) - return false; - GArray * lookup_step_content = (GArray *)g_ptr_array_index(m_steps_content, cur_step_pos); - - max_value = &g_array_index(lookup_step_content, lookup_value_t, GPOINTER_TO_UINT(value)); - } - - //no need to reverse the result - - return true; -} - -bool PinyinLookup::train_result2(ChewingKeyVector keys, - CandidateConstraints constraints, - MatchResults results) { - const guint32 initial_seed = 23 * 15; - const guint32 expand_factor = 2; - const guint32 unigram_factor = 7; - const guint32 pinyin_factor = 1; - const guint32 ceiling_seed = 23 * 15 * 64; - - /* begin training based on constraints and results. */ - bool train_next = false; - ChewingKey * pinyin_keys = (ChewingKey *) keys->data; - - phrase_token_t last_token = sentence_start; - /* constraints->len + 1 == results->len */ - for (size_t i = 0; i < constraints->len; ++i) { - phrase_token_t * token = &g_array_index(results, phrase_token_t, i); - if (null_token == *token) - continue; - - lookup_constraint_t * constraint = &g_array_index - (constraints, lookup_constraint_t, i); - if (train_next || CONSTRAINT_ONESTEP == constraint->m_type) { - if (CONSTRAINT_ONESTEP == constraint->m_type) { - assert(*token == constraint->m_token); - train_next = true; - } else { - train_next = false; - } - - guint32 seed = initial_seed; - /* train bi-gram first, and get train seed. */ - if (last_token) { - SingleGram * user = NULL; - m_user_bigram->load(last_token, user); - - guint32 total_freq = 0; - if (!user) { - user = new SingleGram; - } - assert(user->get_total_freq(total_freq)); - - guint32 freq = 0; - /* compute train factor */ - if (!user->get_freq(*token, freq)) { - assert(user->insert_freq(*token, 0)); - seed = initial_seed; - } else { - seed = std_lite::max(freq, initial_seed); - seed *= expand_factor; - seed = std_lite::min(seed, ceiling_seed); - } - - /* protect against total_freq overflow */ - if (seed > 0 && total_freq > total_freq + seed) - goto next; - - assert(user->set_total_freq(total_freq + seed)); - /* if total_freq is not overflow, then freq won't overflow. */ - assert(user->set_freq(*token, freq + seed)); - assert(m_user_bigram->store(last_token, user)); - next: - if (user) - delete user; - } - - /* train uni-gram */ - m_phrase_index->get_phrase_item(*token, m_cache_phrase_item); - m_cache_phrase_item.increase_pronunciation_possibility - (m_options, pinyin_keys + i, seed * pinyin_factor); - m_phrase_index->add_unigram_frequency - (*token, seed * unigram_factor); - } - last_token = *token; - } - return true; -} - -guint8 PinyinLookup::add_constraint(CandidateConstraints constraints, size_t index, phrase_token_t token){ - if ( m_phrase_index->get_phrase_item(token, m_cache_phrase_item) ) - return 0; - - size_t phrase_length = m_cache_phrase_item.get_phrase_length(); - if ( index + phrase_length > constraints->len ) - return 0; - - for ( size_t i = index; i < index + phrase_length ; ++i ){ - clear_constraint(constraints, i); - } - - lookup_constraint_t * constraint = &g_array_index(constraints, lookup_constraint_t, index); - constraint->m_type = CONSTRAINT_ONESTEP; - constraint->m_token = token; - - for (size_t i = 1; i < phrase_length; ++i){ - constraint = &g_array_index(constraints, lookup_constraint_t, index + i); - constraint->m_type = CONSTRAINT_NOSEARCH; - constraint->m_constraint_step = index; - } - return phrase_length; -} - -bool PinyinLookup::clear_constraint(CandidateConstraints constraints, size_t index){ - if ( index < 0 || index >= constraints->len ) - return false; - lookup_constraint_t * constraint = &g_array_index(constraints, lookup_constraint_t, index); - if (constraint->m_type == NO_CONSTRAINT) - return false; - if (constraint->m_type == CONSTRAINT_NOSEARCH){ - index = constraint->m_constraint_step; - constraint = &g_array_index(constraints, lookup_constraint_t, index); - } - - assert(constraint->m_type == CONSTRAINT_ONESTEP); - - phrase_token_t token = constraint->m_token; - if (m_phrase_index->get_phrase_item(token, m_cache_phrase_item)) - return false; - - size_t phrase_length = m_cache_phrase_item.get_phrase_length(); - for ( size_t i = 0; i < phrase_length; ++i){ - if ( index + i >= constraints->len ) - continue; - constraint = &g_array_index(constraints, lookup_constraint_t, index + i); - constraint->m_type = NO_CONSTRAINT; - } - return true; -} - -bool PinyinLookup::validate_constraint(CandidateConstraints constraints, ChewingKeyVector keys){ - //resize constraints array - size_t constraints_length = constraints->len; - if ( keys->len > constraints_length ){ - g_array_set_size(constraints, keys->len); - //initialize new element - for( size_t i = constraints_length; i < keys->len; ++i){ - lookup_constraint_t * constraint = &g_array_index(constraints, lookup_constraint_t, i); - constraint->m_type = NO_CONSTRAINT; - } - }else if (keys->len < constraints_length ){ - g_array_set_size(constraints, keys->len); - } - - ChewingKey * pinyin_keys = (ChewingKey *)keys->data; - - for ( size_t i = 0; i < constraints->len; ++i){ - lookup_constraint_t * constraint = &g_array_index(constraints, lookup_constraint_t, i); - if ( constraint->m_type == CONSTRAINT_ONESTEP ){ - phrase_token_t token = constraint->m_token; - m_phrase_index->get_phrase_item(token, m_cache_phrase_item); - size_t phrase_length = m_cache_phrase_item.get_phrase_length(); - //clear too long constraint - if ( i + phrase_length > constraints->len ){ - clear_constraint(constraints, i); - continue; - } - //clear invalidated pinyin - gfloat pinyin_poss = m_cache_phrase_item.get_pronunciation_possibility(m_options, pinyin_keys + i); - if ( pinyin_poss < FLT_EPSILON ){ - clear_constraint(constraints, i); - } - } - } - return true; -} |