SunPinyin代码导读(二)

上回所说,在SunPinyin中,第一遍分词使用的正向最大匹配方法(FMM,forward maximum matching)。辞典加载之后,保存在trie树的数据结构中,其key是以USC-4编码(32位)的字符。其中某些节点是有效的词,例如在下图中最左侧的一条路径中,“中国”是一个有效的词。而有些节点,则是不成词的。例如“中华人民共和国”这个路径中的,“共”节点,就不成为一个有效的词。(和参考3中的数据结构相似)

需要注意的是,root的所有子节点都是有效词,因为所有的“字”都被被视为“单字词”。

sim_dict.[h|cpp]:

parseText ()   : 加载text格式的辞典,并以trie树的形式保存在内存中。
matchLongest (): 进行最长匹配,并返回匹配的长度。
step ()        : 从当前节点转移到匹配给定key的一个孩子节点,并返回。

mmseg/mmseg.cpp:

processSingleFile()中,逐句读取语料库,例如,"为人民办实事的精神",然后进行调用SIMDict::matchLongest()进行最长匹配。

因为辞典中有“为人民”这个词条,因此分割到的第一个词是“为人民”,其长度为3,然后调用getAmbiLen(),来分析是否有交集歧义,并返回最大交集歧义的长度。下面是每次迭代的情况:

  1. 人民, 办实事的精神 -> i=1, len=2, word_len=3, 对“人民办实事”进行最长匹配,分割到的词为“人民”,其长度为2,
  2. 民办, 实事的精神 -> i=2, len=2, word_len=4, 对“民办实事”进行最长匹配,分割到的词为“民办”,其长度为2,因为i与len的合超过了最初传入的word_len,则设置word_len为4,继续迭代。可以看出,此时歧义已经检测到了。
  3. 办实事, 的精神 -> i=3, len=3, word_len=6
  4. 实事, 的精神 -> i=4, len=2, word_len=6
  5. 事, 的精神 -> i=5, len=1, word_len=6, 最后歧义的长度为6
  6. 退出循环,返回得到的长度,即6

如果指定了ambiguous-id,则会将这6个字符作为一个AMBI-ID(由参数-a指定),输出到分词的结果中。然后跳过这6个字符,继续进行分词。当句子结束时,如果使用二进制格式输出,则会输出一个句子结束的ID(由参数-s指定)。最后得到的结果是:

$ echo "为人民办实事的精神" | ./mmseg -d ../raw/dict.utf8 -f text -s 10  -a 9
<ambi>为人民办实事</ambi> 的 精神

那么,我们最终得到的分词结果中,所有的交集歧义都作为作为一个词AMBI-ID,相当于我们忽略了这部分信息(这个比例并不低)。这样在我们后面的统计中,绝大部分的3元组都可以保证是有意义和有价值的。进而训练得到的统计语言模型,能够排除交集歧义的影响。然后,可以这个模型,使用slmseg,重新对语料库进行分词,并计算新的语言模型。这一次,原来忽略的带有歧义的信息,我们也加以利用了。

$ echo "为人民办实事的精神" | ./slmseg -d ../raw/dict.utf8 -f text -s 10 -m ../data/lm_sc.t3g
为人民 办实事 的 精神

(注,因为版权的原因,我们无法公开内部使用的生语料库。不过,要使用slmseg,您可以在slm/data目录中,建立一个指向ime/data/lm_sc.t3g.<arch>的符号链接。)

References:

  1. 数学之美 系列二 -- 谈谈中文分词
  2. 中文搜索引擎技术揭密:中文分词
  3. “天堂的阶梯”设计的中文分词算法

Be careful about the associated containers in Cstd of SunStudio

If your program has a lot of std::set<T> or std::map<T> object instances, while mostly have small sizes (e.g., 1..5), you'd better change them to Vector or other unassociated container types if you built your code with Cstd in SunStudio.

The genpyt utility in sunpinyin/slm module, takes over 800M virtual memory, and about 4~500M is allocated for the unused __rb_tree_node buffer. If your machine has less memory than 1GB, the paging in/out (to/from swap) will make the program (and your system) running very slowly.

E.g., for the following example,

std::set<TNode*> nodeset;
nodeset.insert (new TNode());

During the std::set<TNode*>::insert(TNode*), the underlying __rb_tree structure would allocate 32 __rb_tree_node (whose size is 20 bytes), in total 640 bytes. While you just want it to hold a 4/8 bytes pointer. If your program has a lot of such small Set objects, the "wasted" memory is quite large.

I tested g++, and SunStudio with stlport4, they do not has such problem (or feature ;) ).