What’s New in SunPinyin2 — Quanpin Segmentor

如在上篇介绍的那样,SunPinyin原先是借助CPinyinTrie来进行拼音切分的,因为CPinyinTrie是一棵前缀树,因此切分是按最大前向匹配的方式进行的。还有一些额外的处理,例如fangan会被切分为fan'gan,但是dier是被切分为die'r的(我们也因此收到了很多用户的反馈)。在SunPinyin2中,我们依然借助一个trie树来进行音节切分。不过这个tire树是由所有有效音节组成的一棵后缀树。因此,我们的切分原则是以最大后向匹配为基础的。

简单的后向匹配还是有一些问题,例如zhonge(中俄),会被切分成zh'o'n'ge,如果你留意FIT或者ibus-pinyin,就会发现他们都有上述的问题。那这个问题在SunPinyin2中的全拼切分器是如何解决的呢,用户在输入g的当下,切分结果是zh'o'n,加入g之后,segments发生了向前的合并,那么我们就把'g'换成'G'(实际的处理是高位置1)放到内部匹配的buffer中。那么下次用户在输入e的时候,最大后向匹配zhonGe的结果,就会产生正确的结果了。还有一种可能性要处理,例如feng,fe不是一个合法的音节,所以在输入n的当下,切分的结果是f'e,在输入n之后,音节发生了向前的合并,因此N被加入到内部匹配的buffer中,变为feN,但是再输入g时,最大后向匹配却无法返回正确的切分结果了。所以,所以我们还要尝试在某些情况下,将N临时改为n再match一次,如果得到的segment长度是原先的长度+1,就接受这个新的结果,否则再把n改回到N。

我们前面提到了,SunPinyin2使用一棵后缀trie树进行拼音切分的。trie树可以通过逐级二分来实现(如果是内存中的,可以是hash或map)。为了尽可能地保障切分器的效率和性能,我们使用了Double Array Trie(DAT)的方式。DAT的优势在于,可以直接load/mmap到内存中,并且查询子节点的复杂度是O(1)的,缺点是后续的插入和删除比较复杂。因此十分适合作为构造静态词典的方法。在SunPinyin2中,DAT的构造是用python实现的。我们定义了一个C++的模板类CDATrie来访问DAT,其中match_longest (first, last, length)是最核心的方法。读者有兴趣可以去查看相关的代码和资料,这里就不赘述了。

接下来我们看看CQuanpinSegmentor的实现细节。CQuanpinSegmentor有两个助手类,CGetFuzzySyllablesOpCGetCorrectionPairOp。这两个助手类分别用来得到易混淆音(例如zhan -> zan/zang/zhang),和纠错结果(例如ign -> ing)。这两个类都是可配置的。并且所有的CQuanpinSegmentor实例,应该共享相同的助手类的实例。这种可配置项,我们称为shared & global的,在用户修改用户配置的时候,不会影响已经创建的那些会话(sessions)。我们后面还会看到,有些配置项是non-shared  but global的,对这种配置项的更改,需要重新创建已存的那些会话。这是后话,暂且不表。

这两个助手类比较直观,这里也就不赘述了,读者可以参考相关的代码。

CQuanpinSegmentor的核心是_push方法。目前的实现中,deleteAt/insertAt都是用_push方法来实现的,也就是把修改位置后面的字符串重新push了一遍。这个实在是比较粗笨,应该还有一定的改进空间。不过因为用户输入的拼音字符串长度有限(缺省的设置是512个字符),性能目前还是可以接受的。

_push方法首先将传入的字符ch,push到m_pystr中,然后调用m_pytrie的match_longest (m_pystr.rbegin(), m_pystr.rend(), l)方法进行后向匹配,匹配的结果主要有以下几种情况:

  1. l == 0,表明ch不是一个有效的音节,根据字符的特征选定一个seg_type,创建一个长度为1的segment并push到m_segs中。
  2. l == 1,可能是一个新的segment,但是如果是上面类似feNg这样的情况,就修改上一个segment的属性。否则,创建一个新的长度为1的segment,并push到m_segs中。
  3. l == m_segs.back().m_len + 1,也就是说ch可以扩展上一个segment,那么修改上一个segment的属性。
  4. 其他情况,一种是 l > m_segs.back().m_len + 1,例如zhon+g,l = 5,但是上一个segment(n)的长度是1。另一种情况是 l < m_segs.back().m_len + 1,例如die+r,l=2,但是上一个segment(die)的长度是3。这两种情况都会涉及合并或拆分现有的segments。并且在此过程中,可能会引起进一步的合并和拆分动作。因此我们用一个while循环来追赶,直到达到一个既有的音节边界为止。

最后,所有的分支都会跳到RETURN,进行post-editing的操作,这里我们只有一个post-editing的action,就是处理易混淆音。

SunPinyin2中的双拼切分器是由William来实现的,期待他会写一篇文档来总结一下他的实现细节。我将在下一篇介绍对CIMIContext类的改造。

Leave a Reply

Your email address will not be published. Required fields are marked *

To submit your comment, click the image below where it asks you to...
Clickcha - The One-Click Captcha