diff options
Diffstat (limited to 'src/plugins/pinyin/3rdparty/pinyin/include/matrixsearch.h')
| -rw-r--r-- | src/plugins/pinyin/3rdparty/pinyin/include/matrixsearch.h | 460 |
1 files changed, 460 insertions, 0 deletions
diff --git a/src/plugins/pinyin/3rdparty/pinyin/include/matrixsearch.h b/src/plugins/pinyin/3rdparty/pinyin/include/matrixsearch.h new file mode 100644 index 00000000..61e78aa6 --- /dev/null +++ b/src/plugins/pinyin/3rdparty/pinyin/include/matrixsearch.h @@ -0,0 +1,460 @@ +/* + * Copyright (C) 2009 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef PINYINIME_ANDPY_INCLUDE_MATRIXSEARCH_H__ +#define PINYINIME_ANDPY_INCLUDE_MATRIXSEARCH_H__ + +#include <stdlib.h> +#include "./atomdictbase.h" +#include "./dicttrie.h" +#include "./searchutility.h" +#include "./spellingtrie.h" +#include "./splparser.h" + +namespace ime_pinyin { + +static const size_t kMaxRowNum = kMaxSearchSteps; + +typedef struct { + // MileStoneHandle objects for the system and user dictionaries. + MileStoneHandle dict_handles[2]; + // From which DMI node. -1 means it's from root. + PoolPosType dmi_fr; + // The spelling id for the Pinyin string from the previous DMI to this node. + // If it is a half id like Shengmu, the node pointed by dict_node is the first + // node with this Shengmu, + uint16 spl_id; + // What's the level of the dict node. Level of root is 0, but root is never + // recorded by dict_node. + unsigned char dict_level:7; + // If this node is for composing phrase, this bit is 1. + unsigned char c_phrase:1; + // Whether the spl_id is parsed with a split character at the end. + unsigned char splid_end_split:1; + // What's the length of the spelling string for this match, for the whole + // word. + unsigned char splstr_len:7; + // Used to indicate whether all spelling ids from the root are full spelling + // ids. This information is useful for keymapping mode(not finished). Because + // in this mode, there is no clear boundaries, we prefer those results which + // have full spelling ids. + unsigned char all_full_id:1; +} DictMatchInfo, *PDictMatchInfo; + +typedef struct MatrixNode { + LemmaIdType id; + float score; + MatrixNode *from; + // From which DMI node. Used to trace the spelling segmentation. + PoolPosType dmi_fr; + uint16 step; +} MatrixNode, *PMatrixNode; + +typedef struct { + // The MatrixNode position in the matrix pool + PoolPosType mtrx_nd_pos; + // The DictMatchInfo position in the DictMatchInfo pool. + PoolPosType dmi_pos; + uint16 mtrx_nd_num; + uint16 dmi_num:15; + // Used to indicate whether there are dmi nodes in this step with full + // spelling id. This information is used to decide whether a substring of a + // valid Pinyin should be extended. + // + // Example1: shoudao + // When the last char 'o' is added, the parser will find "dao" is a valid + // Pinyin, and because all dmi nodes at location 'd' (including those for + // "shoud", and those for "d") have Shengmu id only, so it is not necessary + // to extend "ao", otherwise the result may be "shoud ao", that is not + // reasonable. + // + // Example2: hengao + // When the last 'o' is added, the parser finds "gao" is a valid Pinyin. + // Because some dmi nodes at 'g' has Shengmu ids (hen'g and g), but some dmi + // nodes at 'g' has full ids ('heng'), so it is necessary to extend "ao", thus + // "heng ao" can also be the result. + // + // Similarly, "ganga" is expanded to "gang a". + // + // For Pinyin string "xian", because "xian" is a valid Pinyin, because all dmi + // nodes at 'x' only have Shengmu ids, the parser will not try "x ian" (and it + // is not valid either). If the parser uses break in the loop, the result + // always be "xian"; but if the parser uses continue in the loop, "xi an" will + // also be tried. This behaviour can be set via the function + // set_xi_an_switch(). + uint16 dmi_has_full_id:1; + // Points to a MatrixNode of the current step to indicate which choice the + // user selects. + MatrixNode *mtrx_nd_fixed; +} MatrixRow, *PMatrixRow; + +// When user inputs and selects candidates, the fixed lemma ids are stored in +// lma_id_ of class MatrixSearch, and fixed_lmas_ is used to indicate how many +// lemmas from the beginning are fixed. If user deletes Pinyin characters one +// by one from the end, these fixed lemmas can be unlocked one by one when +// necessary. Whenever user deletes a Chinese character and its spelling string +// in these fixed lemmas, all fixed lemmas will be merged together into a unit +// named ComposingPhrase with a lemma id kLemmaIdComposing, and this composing +// phrase will be the first lemma in the sentence. Because it contains some +// modified lemmas (by deleting a character), these merged lemmas are called +// sub lemmas (sublma), and each of them are represented individually, so that +// when user deletes Pinyin characters from the end, these sub lemmas can also +// be unlocked one by one. +typedef struct { + uint16 spl_ids[kMaxRowNum]; + uint16 spl_start[kMaxRowNum]; + char16 chn_str[kMaxRowNum]; // Chinese string. + uint16 sublma_start[kMaxRowNum]; // Counted in Chinese characters. + size_t sublma_num; + uint16 length; // Counted in Chinese characters. +} ComposingPhrase, *TComposingPhrase; + +class MatrixSearch { + private: + // If it is true, prediction list by string whose length is greater than 1 + // will be limited to a reasonable number. + static const bool kPredictLimitGt1 = false; + + // If it is true, the engine will prefer long history based prediction, + // for example, when user inputs "BeiJing", we prefer "DaXue", etc., which are + // based on the two-character history. + static const bool kPreferLongHistoryPredict = true; + + // If it is true, prediction will only be based on user dictionary. this flag + // is for debug purpose. + static const bool kOnlyUserDictPredict = false; + + // The maximum buffer to store LmaPsbItems. + static const size_t kMaxLmaPsbItems = 1450; + + // How many rows for each step. + static const size_t kMaxNodeARow = 5; + + // The maximum length of the sentence candidates counted in chinese + // characters + static const size_t kMaxSentenceLength = 16; + + // The size of the matrix node pool. + static const size_t kMtrxNdPoolSize = 200; + + // The size of the DMI node pool. + static const size_t kDmiPoolSize = 800; + + // Used to indicate whether this object has been initialized. + bool inited_; + + // Spelling trie. + const SpellingTrie *spl_trie_; + + // Used to indicate this switcher status: when "xian" is parseed, should + // "xi an" also be extended. Default is false. + // These cases include: xia, xian, xiang, zhuan, jiang..., etc. The string + // should be valid for a FULL spelling, or a combination of two spellings, + // first of which is a FULL id too. So even it is true, "da" will never be + // split into "d a", because "d" is not a full spelling id. + bool xi_an_enabled_; + + // System dictionary. + DictTrie* dict_trie_; + + // User dictionary. + AtomDictBase* user_dict_; + + // Spelling parser. + SpellingParser* spl_parser_; + + // The maximum allowed length of spelling string (such as a Pinyin string). + size_t max_sps_len_; + + // The maximum allowed length of a result Chinese string. + size_t max_hzs_len_; + + // Pinyin string. Max length: kMaxRowNum - 1 + char pys_[kMaxRowNum]; + + // The length of the string that has been decoded successfully. + size_t pys_decoded_len_; + + // Shared buffer for multiple purposes. + size_t *share_buf_; + + MatrixNode *mtrx_nd_pool_; + PoolPosType mtrx_nd_pool_used_; // How many nodes used in the pool + DictMatchInfo *dmi_pool_; + PoolPosType dmi_pool_used_; // How many items used in the pool + + MatrixRow *matrix_; // The first row is for starting + + DictExtPara *dep_; // Parameter used to extend DMI nodes. + + NPredictItem *npre_items_; // Used to do prediction + size_t npre_items_len_; + + // The starting positions and lemma ids for the full sentence candidate. + size_t lma_id_num_; + uint16 lma_start_[kMaxRowNum]; // Counted in spelling ids. + LemmaIdType lma_id_[kMaxRowNum]; + size_t fixed_lmas_; + + // If fixed_lmas_ is bigger than i, Element i is used to indicate whether + // the i'th lemma id in lma_id_ is the first candidate for that step. + // If all candidates are the first one for that step, the whole string can be + // decoded by the engine automatically, so no need to add it to user + // dictionary. (We are considering to add it to user dictionary in the + // future). + uint8 fixed_lmas_no1_[kMaxRowNum]; + + // Composing phrase + ComposingPhrase c_phrase_; + + // If dmi_c_phrase_ is true, the decoder will try to match the + // composing phrase (And definitely it will match successfully). If it + // is false, the decoder will try to match lemmas items in dictionaries. + bool dmi_c_phrase_; + + // The starting positions and spelling ids for the first full sentence + // candidate. + size_t spl_id_num_; // Number of splling ids + uint16 spl_start_[kMaxRowNum]; // Starting positions + uint16 spl_id_[kMaxRowNum]; // Spelling ids + // Used to remember the last fixed position, counted in Hanzi. + size_t fixed_hzs_; + + // Lemma Items with possibility score, two purposes: + // 1. In Viterbi decoding, this buffer is used to get all possible candidates + // for current step; + // 2. When the search is done, this buffer is used to get candiates from the + // first un-fixed step and show them to the user. + LmaPsbItem lpi_items_[kMaxLmaPsbItems]; + size_t lpi_total_; + + // Assign the pointers with NULL. The caller makes sure that all pointers are + // not valid before calling it. This function only will be called in the + // construction function and free_resource(). + void reset_pointers_to_null(); + + bool alloc_resource(); + + void free_resource(); + + // Reset the search space totally. + bool reset_search0(); + + // Reset the search space from ch_pos step. For example, if the original + // input Pinyin is "an", reset_search(1) will reset the search space to the + // result of "a". If the given position is out of range, return false. + // if clear_fixed_this_step is true, and the ch_pos step is a fixed step, + // clear its fixed status. if clear_dmi_his_step is true, clear the DMI nodes. + // If clear_mtrx_this_sTep is true, clear the mtrx nodes of this step. + // The DMI nodes will be kept. + // + // Note: this function should not destroy content of pys_. + bool reset_search(size_t ch_pos, bool clear_fixed_this_step, + bool clear_dmi_this_step, bool clear_mtrx_this_step); + + // Delete a part of the content in pys_. + void del_in_pys(size_t start, size_t len); + + // Delete a spelling id and its corresponding Chinese character, and merge + // the fixed lemmas into the composing phrase. + // del_spl_pos indicates which spelling id needs to be delete. + // This function will update the lemma and spelling segmentation information. + // The caller guarantees that fixed_lmas_ > 0 and del_spl_pos is within + // the fixed lemmas. + void merge_fixed_lmas(size_t del_spl_pos); + + // Get spelling start posistions and ids. The result will be stored in + // spl_id_num_, spl_start_[], spl_id_[]. + // fixed_hzs_ will be also assigned. + void get_spl_start_id(); + + // Get all lemma ids with match the given spelling id stream(shorter than the + // maximum length of a word). + // If pfullsent is not NULL, means the full sentence candidate may be the + // same with the coming lemma string, if so, remove that lemma. + // The result is sorted in descendant order by the frequency score. + size_t get_lpis(const uint16* splid_str, size_t splid_str_len, + LmaPsbItem* lma_buf, size_t max_lma_buf, + const char16 *pfullsent, bool sort_by_psb); + + uint16 get_lemma_str(LemmaIdType id_lemma, char16 *str_buf, uint16 str_max); + + uint16 get_lemma_splids(LemmaIdType id_lemma, uint16 *splids, + uint16 splids_max, bool arg_valid); + + + // Extend a DMI node with a spelling id. ext_len is the length of the rows + // to extend, actually, it is the size of the spelling string of splid. + // return value can be 1 or 0. + // 1 means a new DMI is filled in (dmi_pool_used_ is the next blank DMI in + // the pool). + // 0 means either the dmi node can not be extended with splid, or the splid + // is a Shengmu id, which is only used to get lpi_items, or the result node + // in DictTrie has no son, it is not nccessary to keep the new DMI. + // + // This function modifies the content of lpi_items_ and lpi_total_. + // lpi_items_ is used to get the LmaPsbItem list, lpi_total_ returns the size. + // The function's returned value has no relation with the value of lpi_num. + // + // If dmi == NULL, this function will extend the root node of DictTrie + // + // This function will not change dmi_nd_pool_used_. Please change it after + // calling this function if necessary. + // + // The caller should guarantees that NULL != dep. + size_t extend_dmi(DictExtPara *dep, DictMatchInfo *dmi_s); + + // Extend dmi for the composing phrase. + size_t extend_dmi_c(DictExtPara *dep, DictMatchInfo *dmi_s); + + // Extend a MatrixNode with the give LmaPsbItem list. + // res_row is the destination row number. + // This function does not change mtrx_nd_pool_used_. Please change it after + // calling this function if necessary. + // return 0 always. + size_t extend_mtrx_nd(MatrixNode *mtrx_nd, LmaPsbItem lpi_items[], + size_t lpi_num, PoolPosType dmi_fr, size_t res_row); + + + // Try to find a dmi node at step_to position, and the found dmi node should + // match the given spelling id strings. + PoolPosType match_dmi(size_t step_to, uint16 spl_ids[], uint16 spl_id_num); + + bool add_char(char ch); + bool prepare_add_char(char ch); + + // Called after prepare_add_char, so the input char has been saved. + bool add_char_qwerty(); + + // Prepare candidates from the last fixed hanzi position. + void prepare_candidates(); + + // Is the character in step pos a splitter character? + // The caller guarantees that the position is valid. + bool is_split_at(uint16 pos); + + void fill_dmi(DictMatchInfo *dmi, MileStoneHandle *handles, + PoolPosType dmi_fr, + uint16 spl_id, uint16 node_num, unsigned char dict_level, + bool splid_end_split, unsigned char splstr_len, + unsigned char all_full_id); + + size_t inner_predict(const char16 fixed_scis_ids[], uint16 scis_num, + char16 predict_buf[][kMaxPredictSize + 1], + size_t buf_len); + + // Add the first candidate to the user dictionary. + bool try_add_cand0_to_userdict(); + + // Add a user lemma to the user dictionary. This lemma is a subset of + // candidate 0. lma_from is from which lemma in lma_ids_, lma_num is the + // number of lemmas to be combined together as a new lemma. The caller + // gurantees that the combined new lemma's length is less or equal to + // kMaxLemmaSize. + bool add_lma_to_userdict(uint16 lma_from, uint16 lma_num, float score); + + // Update dictionary frequencies. + void update_dict_freq(); + + void debug_print_dmi(PoolPosType dmi_pos, uint16 nest_level); + + public: + MatrixSearch(); + ~MatrixSearch(); + + bool init(const char *fn_sys_dict, const char *fn_usr_dict); + + bool init_fd(int sys_fd, long start_offset, long length, + const char *fn_usr_dict); + + void init_user_dictionary(const char *fn_usr_dict); + + bool is_user_dictionary_enabled() const; + + void set_max_lens(size_t max_sps_len, size_t max_hzs_len); + + void close(); + + void flush_cache(); + + void set_xi_an_switch(bool xi_an_enabled); + + bool get_xi_an_switch(); + + // Reset the search space. Equivalent to reset_search(0). + // If inited, always return true; + bool reset_search(); + + // Search a Pinyin string. + // Return value is the position successfully parsed. + size_t search(const char *py, size_t py_len); + + // Used to delete something in the Pinyin string kept by the engine, and do + // a re-search. + // Return value is the new length of Pinyin string kept by the engine which + // is parsed successfully. + // If is_pos_in_splid is false, pos is used to indicate that pos-th Pinyin + // character needs to be deleted. If is_pos_in_splid is true, all Pinyin + // characters for pos-th spelling id needs to be deleted. + // If the deleted character(s) is just after a fixed lemma or sub lemma in + // composing phrase, clear_fixed_this_step indicates whether we needs to + // unlock the last fixed lemma or sub lemma. + // If is_pos_in_splid is false, and pos-th character is in the range for the + // fixed lemmas or composing string, this function will do nothing and just + // return the result of the previous search. + size_t delsearch(size_t pos, bool is_pos_in_splid, + bool clear_fixed_this_step); + + // Get the number of candiates, called after search(). + size_t get_candidate_num(); + + // Get the Pinyin string stored by the engine. + // *decoded_len returns the length of the successfully decoded string. + const char* get_pystr(size_t *decoded_len); + + // Get the spelling boundaries for the first sentence candidate. + // Number of spellings will be returned. The number of valid elements in + // spl_start is one more than the return value because the last one is used + // to indicate the beginning of the next un-input speling. + // For a Pinyin "women", the returned value is 2, spl_start is [0, 2, 5] . + size_t get_spl_start(const uint16 *&spl_start); + + // Get one candiate string. If full sentence candidate is available, it will + // be the first one. + char16* get_candidate(size_t cand_id, char16 *cand_str, size_t max_len); + + // Get the first candiate, which is a "full sentence". + // retstr_len is not NULL, it will be used to return the string length. + // If only_unfixed is true, only unfixed part will be fetched. + char16* get_candidate0(char16* cand_str, size_t max_len, + uint16 *retstr_len, bool only_unfixed); + + // Choose a candidate. The decoder will do a search after the fixed position. + size_t choose(size_t cand_id); + + // Cancel the last choosing operation, and return the new number of choices. + size_t cancel_last_choice(); + + // Get the length of fixed Hanzis. + size_t get_fixedlen(); + + size_t get_predicts(const char16 fixed_buf[], + char16 predict_buf[][kMaxPredictSize + 1], + size_t buf_len); +}; +} + +#endif // PINYINIME_ANDPY_INCLUDE_MATRIXSEARCH_H__ |