libGooglePinyin(一)构建词库

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
2
3
4
5
6
7
bool DictTrie::build_dict(const char* fn_raw, const char* fn_validhzs) {
DictBuilder* dict_builder = new DictBuilder();

free_resource(true);

return dict_builder->build_dict(fn_raw, fn_validhzs, this); // 🏁Step2
}

Step2 DictBuilder::build_dict(…)

1
2
3
4
5
6
7
8
9
10
// src/dictbuilder.cpp
bool DictBuilder::build_dict(const char *fn_raw,
const char *fn_validhzs,
DictTrie *dict_trie) {
...
// 读出原始数据,形成两个数据结构:
// 1. lemma_arr_数组,它的每个元素存放词、词频、拼音串
// 2. raw_spellings_哈希表,它的每个元素存放一个音节、音频(所有包含该音的词频总和)
lemma_num_ = read_raw_dict(fn_raw, fn_validhzs, 240000);
...

数据结构lemma_arr_是从rawdict_utf16_65105_freq.txt读出系统词库并组织成的数组,每个元素是一个LemmaEntry结构体。
在记录拼音的时候,它默认将拼音字母转成大写,仅对双声母中的h使用小写。 lemma_arr_
在解析拼音串的同时,它用哈希表raw_spellings_构建了一张拼音表,具体过程在Step4中分析。其有效元素即合法的音节字串个数413,这张哈希表的空间远比这个数字大,不过这个细节并不重要:
raw_spellings

1
2
3
4
5
6
7
8
9
10
11
// Arrange the spelling table, and build a spelling tree
// The size of an spelling. '\0' is included. If the spelling table is
// initialized to calculate the spelling scores, the last char in the
// spelling string will be score, and it is also included in spl_item_size.
size_t spl_item_size;
size_t spl_num;
const char* spl_buf;
// 将合法音节按顺序保存到spl_table_->spelling_buf_中,
// 返回值spl_buf指向该成员
spl_buf = spl_table_->arrange(&spl_item_size, &spl_num);
...

该函数将spltable->rawspellings中的音节串按照顺序,排列到spellingbuf中。其中每个元素包含:音节拼音串 和 音节音频,前者占7个字节,以’\0’结尾;后者占1个字节。共413个元素。如下图:spelling_buf_

spl_table_->arrange返回的splbuf即spl_table->spellingbuf,继续被传入spl_trie.construct中:

1
2
3
4
5
6
SpellingTrie &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 ![SpellingTrie::spelling_buf](0416libGooglePinyin01/img07.png)
为所有合法的音节串生成Trie树,该树的逻辑结构为:字典树的逻辑结构
实际存储结构为:字典树的存储结构
来看spellingidx的含义,当它小于30,表示它可以作为一个half音节;如果大于30,表示这是一个full音节,该值即此音节在spelling_buf中的偏移。
half音节是指可以作为音节首部的拼音串,包括声母(如bpm,双声母zhchsh)和可独立出现的韵母(如aoe)。

该段代码还生成了SpellingTrie::h2f_start_SpellingTrie::h2f_num_h2f_start_和h2f_num_这两个数据结构要结合音节字典树和spellingbuf一起来看。

该代码还生成了SpellingTrie::f2h_f2h_该数据结构用于从full到half的对应,因此可以把相关的数据结合来看。

该代码还生成了SpellingTrie::ym_buf_SpellingTrie::spl_ym_ids前者是韵母表,后者则是音节到韵母的关系:ym_buf_和spl_ym_ids,其中spl_id&spl_str这张表并不存在物理数据,这张表的转换关系是在函数SpellingTrie::get_spelling_str(...)中体现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 填充lemma_arr_数组每个元素的spl_idx_arr项,它表示每个汉字的音对应的spl_id
for (size_t i = 0; i < lemma_num_; i++) {
for (size_t hz_pos = 0; hz_pos < (size_t)lemma_arr_[i].hz_str_len;
hz_pos++) {
uint16 spl_idxs[2];
uint16 spl_start_pos[3];
bool is_pre = true;
int spl_idx_num =
spl_parser_->splstr_to_idxs(lemma_arr_[i].pinyin_str[hz_pos],
strlen(lemma_arr_[i].pinyin_str[hz_pos]),
spl_idxs, spl_start_pos, 2, is_pre);
assert(1 == spl_idx_num);

if (spl_trie.is_half_id(spl_idxs[0])) {
uint16 num = spl_trie.half_to_full(spl_idxs[0], spl_idxs);
assert(0 != num);
}
lemma_arr_[i].spl_idx_arr[hz_pos] = spl_idxs[0];
}
}
// 按照汉字串排序,更新idx_by_hz字段,为每个词分配一个唯一id
sort_lemmas_by_hz();
// 构建单字表到scis_,并根据该单字表更新lemma_arr_中的hanzi_scis_ids字段
scis_num_ = build_scis();

for循环则遍历lemma_arr_数组,更新每个元素的spl_idx_arr字段,它表示该词的每个字音对应的spl_id。

sort_lemmas_by_hz()则按照汉字串对lemmaarr排序,更新idx_by_hz字段,为每个词分配一个唯一id。

scisSingleCharItems的简写,build_scis()创建了单字表,并再次更新lemma_arr_::hanzi_scis_ids字段,该字段是每个词的每个汉字在单字表中的序号。单字表内容如下:单字表
更新后的lemma_arr_内容如下:lemma_arr_

1
2
3
4
5
6
7
8
// Construct the dict list
dict_trie->dict_list_ = new DictList();
// 将单字序列化到scis_hz_,每个元素一个单字;
// 将该单字对应的splid序列化到scis_splid_,每个元素一个SpellingId;
// 将所有的词序列化到buf_,每个元素都是变长的词串
bool dl_success = dict_trie->dict_list_->init_list(scis_, scis_num_,
lemma_arr_, lemma_num_);
assert(dl_success);

dict_trie->dict_list_->init_list(...)函数将单字表拆成两个数组:scis_hz_&scis_splid_
它把系统词库里所有汉字串成一个总串保存到DictList::buf_中,用DictList::start_pos_分别指向1字词、2字词……9字词的起点,用DictList::start_id_指向1字词、2字词……9字词在lemmaarr中的起始位置:start_pos_&start_id_

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_中

#ifdef ___DO_STATISTICS___
stat_init();
#endif

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_le0lema_nodes_ge1homo_idx_buf_三个数据结构,这三坨数据也需要结合在一起解读,它们共同把系统词库按照读音组织成一个Trie树。系统词Trie树逻辑结构它对应的存储结构为:系统词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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#ifdef ___DO_STATISTICS___
stat_print();
#endif

// Move the node data and homo data to the DictTrie
dict_trie->root_ = new LmaNodeLE0[lma_nds_used_num_le0_];
dict_trie->nodes_ge1_ = new LmaNodeGE1[lma_nds_used_num_ge1_];
size_t lma_idx_num = homo_idx_num_eq1_ + homo_idx_num_gt1_ + top_lmas_num_;
dict_trie->lma_idx_buf_ = new unsigned char[lma_idx_num * kLemmaIdSize];
assert(NULL != dict_trie->root_);
assert(NULL != dict_trie->lma_idx_buf_);
dict_trie->lma_node_num_le0_ = lma_nds_used_num_le0_;
dict_trie->lma_node_num_ge1_ = lma_nds_used_num_ge1_;
dict_trie->lma_idx_buf_len_ = lma_idx_num * kLemmaIdSize;
dict_trie->top_lmas_num_ = top_lmas_num_;

// 将lma_nodes_le0拷贝到dict_trie->root_,将lma_node_ge1_拷贝到dict_trie->nodes_ge1_
memcpy(dict_trie->root_, lma_nodes_le0_,
sizeof(LmaNodeLE0) * lma_nds_used_num_le0_);
memcpy(dict_trie->nodes_ge1_, lma_nodes_ge1_,
sizeof(LmaNodeGE1) * lma_nds_used_num_ge1_);
// 将homo_idx_buf_拷贝到dict_trie->lma_idx_buf_,该数组的每个元素是3个字节
for (size_t pos = 0; pos < homo_idx_num_eq1_ + homo_idx_num_gt1_; pos++) {
id_to_charbuf(dict_trie->lma_idx_buf_ + pos * kLemmaIdSize,
homo_idx_buf_[pos]);
}
// dict_trie->lma_idx_buf_末端10个元素是词频最高的top10系统词
for (size_t pos = homo_idx_num_eq1_ + homo_idx_num_gt1_;
pos < lma_idx_num; pos++) {
LemmaIdType idx =
top_lmas_[pos - homo_idx_num_eq1_ - homo_idx_num_gt1_].idx_by_hz;
id_to_charbuf(dict_trie->lma_idx_buf_ + pos * kLemmaIdSize, idx);
}
...
return dt_success;
}

Step3 DictTrie::save_dict(…)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool DictTrie::save_dict(const char *filename) {
...
SpellingTrie &spl_trie = SpellingTrie::get_instance();
NGram &ngram = NGram::get_instance();

FILE *fp = fopen(filename, "wb");
...
if (!spl_trie.save_spl_trie(fp) || !dict_list_->save_list(fp) ||
!save_dict(fp) || !ngram.save_ngram(fp)) {
...
}
...
return true;
}

把前面生成数据结构的过程研究透彻,这一步只不过把数据写入文件,内容如下:系统词库