Fork了一份libGooglePinyin,并在此基础上稍作修改,以便能跑起来。开源的代码,方便讨论,并以此为切入点研究输入法引擎当中,解决具体问题的方法。libGooglePinyin的本尊在这里,在Github上还有很多拷贝。
本文讨论libGooglePinyin构建词库的过程,以及词库格式。由于对代码做了一些改动,我就以自己的代码树为标准来讨论。
词库的构建代码在tools/pinyinime_dictbuilder.cpp,生成可执行文件dictbuilder.exe,调用格式为:dictbuilder.exe <rawdict_utf16_65105_freq.txt的路径> <valid_utf16.txt的路径> <系统词库dict_pinyin.dat的生成路径>
main函数的代码很简单:1
2
3
4
5
6
7
8
9
10
11
12
13// tools/pinyinime_dictbuilder.cpp
int main(int argc, char* argv[]) {
DictTrie* dict_trie = new DictTrie();
...
// 🏁Step1
success = dict_trie->build_dict("../data/rawdict_utf16_65105_freq.txt",
"../data/valid_utf16.txt");
...
// 🏁Step3
success = dict_trie->save_dict("dict_pinyin.dat");
...
return 0;
}
文件rawdict_utf16_65105_freq.txt
是词库的文本形式;
文件valid_utf16.txt
存放所有合法的汉字。
Step1 DictTrie::build_dict(…)
1 | bool DictTrie::build_dict(const char* fn_raw, const char* fn_validhzs) { |
Step2 DictBuilder::build_dict(…)
1 | // src/dictbuilder.cpp |
数据结构lemma_arr_
是从rawdict_utf16_65105_freq.txt
读出系统词库并组织成的数组,每个元素是一个LemmaEntry结构体。
在记录拼音的时候,它默认将拼音字母转成大写,仅对双声母中的h使用小写。
在解析拼音串的同时,它用哈希表raw_spellings_
构建了一张拼音表,具体过程在Step4中分析。其有效元素即合法的音节字串个数413,这张哈希表的空间远比这个数字大,不过这个细节并不重要:
1 | // Arrange the spelling table, and build a spelling tree |
该函数将spltable->rawspellings中的音节串按照顺序,排列到spellingbuf中。其中每个元素包含:音节拼音串 和 音节音频,前者占7个字节,以’\0’结尾;后者占1个字节。共413个元素。如下图:
spl_table_->arrange
返回的splbuf即spl_table->spellingbuf,继续被传入spl_trie.construct
中:1
2
3
4
5
6SpellingTrie &spl_trie = SpellingTrie::get_instance();
// 把所有合法音节组织成一个Trie树
if (!spl_trie.construct(spl_buf, spl_item_size, spl_num,
spl_table_->get_score_amplifier(),
spl_table_->get_average_score()))
{...}
在spl_trie.construct(...)
中,生成的数据结构比较多:
它从参数splbuf中拷贝了一份spelling_buf 
为所有合法的音节串生成Trie树,该树的逻辑结构为:
实际存储结构为:
来看spellingidx的含义,当它小于30,表示它可以作为一个half音节;如果大于30,表示这是一个full音节,该值即此音节在spelling_buf中的偏移。
half音节是指可以作为音节首部的拼音串,包括声母(如b
、p
、m
,双声母zh
、ch
、sh
)和可独立出现的韵母(如a
、o
、e
)。
该段代码还生成了SpellingTrie::h2f_start_
和SpellingTrie::h2f_num_
:这两个数据结构要结合音节字典树和spellingbuf一起来看。
该代码还生成了SpellingTrie::f2h_
:该数据结构用于从full到half的对应,因此可以把相关的数据结合来看。
该代码还生成了SpellingTrie::ym_buf_
和SpellingTrie::spl_ym_ids
前者是韵母表,后者则是音节到韵母的关系:,其中spl_id&spl_str这张表并不存在物理数据,这张表的转换关系是在函数
SpellingTrie::get_spelling_str(...)
中体现的。
1 | // 填充lemma_arr_数组每个元素的spl_idx_arr项,它表示每个汉字的音对应的spl_id |
for循环则遍历lemma_arr_
数组,更新每个元素的spl_idx_arr
字段,它表示该词的每个字音对应的spl_id。
sort_lemmas_by_hz()
则按照汉字串对lemmaarr排序,更新idx_by_hz字段,为每个词分配一个唯一id。
scis
是SingleCharItems
的简写,build_scis()
创建了单字表,并再次更新lemma_arr_::hanzi_scis_ids
字段,该字段是每个词的每个汉字在单字表中的序号。单字表内容如下:
更新后的lemma_arr_
内容如下:
1 | // Construct the dict list |
dict_trie->dict_list_->init_list(...)
函数将单字表拆成两个数组:
它把系统词库里所有汉字串成一个总串保存到DictList::buf_
中,用DictList::start_pos_
分别指向1字词、2字词……9字词的起点,用DictList::start_id_
指向1字词、2字词……9字词在lemmaarr中的起始位置:1
2
3
4// 🏁Step9 将词频数据归拢到256个值
NGram& ngram = NGram::get_instance();
ngram.build_unigram(lemma_arr_, lemma_num_,
lemma_arr_[lemma_num_ - 1].idx_by_hz + 1);
它生成NGram::lma_freq_idx_
、NGram::freq_codes_df_
、NGram::freq_codes_
三个数据结构。其中NGram::freq_codes_df_
将系统词库里每个词条的词频归拢成256个值,并经过多伦迭代求均值,让这256个归拢值尽量接近被归拢的原始值;NGram::lma_freq_idx_
则记录原始词频与归拢词频之间的对应关系:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 // sort the lemma items according to the spelling idx string
myqsort(lemma_arr_, lemma_num_, sizeof(LemmaEntry), compare_py);
get_top_lemmas(); // 取出词频最大的top_lmas_num_个LemmaEntry,由大到小排到top_lmas_中
stat_init();
lma_nds_used_num_le0_ = 1; // The root node
bool dt_success = construct_subset(static_cast<void*>(lma_nodes_le0_),
lemma_arr_, 0, lemma_num_, 0);
if (!dt_success) {
free_resource();
return false;
}
函数construct_subset(...)
主要生成了lema_nodes_le0
、lema_nodes_ge1
和homo_idx_buf_
三个数据结构,这三坨数据也需要结合在一起解读,它们共同把系统词库按照读音组织成一个Trie树。它对应的存储结构为:
首先把lemmaarr按照拼音排序,将其idxby_hz抽取出来存储到homo_idx_buf中。
lemanodes_le0和lema_nodes_ge1的逻辑结构是完全一致的,只是出于空间开销的考虑,前者每个元素占用16个字节,后者仅占用8个字节。
lema_nodes_le0的首个元素记录Trie树第0层信息。字段son_1st_off表示第一个子元素在本表中的下标;num_of_son表示子元素个数。
lema_nodes_le0第2个及之后的元素记录第1层Trie节点信息。son_1st_off表示首个子元素在lema_node_ge1中的下标;homo_idx_buf_off表示该音节对应得以个系统词在homo_idx_buf中的下标;spl_idx表示当前节点代表的音节;num_of_son表示当前节点的子节点个数;num_of_homo表示当前节点下有多少个系统词。
lema_nodes_ge1与lema_nodes_le0第2行以后的元素各字段表示的含义一致。
1 |
|
Step3 DictTrie::save_dict(…)
1 | bool DictTrie::save_dict(const char *filename) { |
把前面生成数据结构的过程研究透彻,这一步只不过把数据写入文件,内容如下: