Just Enough Charaters —— 让你的电脑不再爆炸

Posted by Towdium on February 19, 2019

扯两句

好久不见,别来无恙阿。说来惭愧,我这破站已经足足一年没有更新了。这当然有很大一部分是因为我的懒惰,另外一部分则是因为我去年大四,时间基本上都用来肝毕业设计了。不出意外的话,我接下来相当一段时间还要继续忙碌下去,所以不要对我更新有什么期待。今天来吹一波 Just Enough Characters 的实现。虽然这本来是我一年前就想好的内容,现在拿来说也并不过时嘛。

文本匹配

在我写完上一篇 JECh 的博文之后,我花了相当多时间研究匹配算法的性能优化,并且最终证明之前那一套东西就是屎。最大的问题就在于这个缓存过于庞大,而且难以分离,以至于一些小 bug 根本无从下手。另外就是这套东西换下来对于性能的提升微乎其微。在我拿 profiler 跑了 n 遍之后,诡异的发现 HashMap 的索引占据了相当一部分的开销。这使得我对 HashMap 的看法急转直下,并且最终使我认定在极端高频环境下,使用 HashMap 莫过于自找没趣。

这里我觉得对于不熟悉这个项目的读者,我觉得有必要重新描述一边我的需求:对于一段中英混合的文本,判断一个 ascii 字符串(拼音文本混合英文原文)是否能匹配其中的一部分。这有点类似于 String.contains,不过提供了汉语拼音的兼容,而且汉语拼音还要包括各种简拼和模糊音设置。举个例子,对于“智障T”,下列字符串都应该能够匹配:“zhi障T”,“zhizhangT”, “zhizhT”, “zhizhang4T”, “zhizh4T”。对于不同的模糊音设置,它还应该匹配“zhizangT”, “zhizT”, “zhizhanT”, “zhizanT”等若干拼法。它还应该接受各种片段如“zhizh”, “zhizhang”, “zhT”, “zhangT”等。在注音模式下,它则应该匹配“545;4T”, “545T”,“54障T”等类似的拼法。这里只提供了“障”的几个变种,同样适用于“智”,我就不列出了。我原本没必要兼容声调,毕竟汉语拼音用户几乎不打声调,不过考虑到注音用户习惯打声调,所以也就顺便兼容了。如你所见,这里允许的组合数量巨大而且相当复杂。虽然它在表面上看只是 String.contains 的变种,但是实现却要复杂得多。

至于新的实现,反而又回到了遍历匹配的老路上。这套新东西虽然在理论上毫无亮点,但是他在工程上比起之前的那套东西却有数量级的提升。更让人满意的是,新的框架和之前比起来,几乎可以算是 stateless,仅仅是极小部分的核心对象用到缓存。得益于缓存的大幅削减,他在启动和重载时几乎可以在一瞬间完成缓存的构建,比之前的复杂缓存不知道高到哪里去了。我对于这个问题的最终看法是,由于模组环境以及汉语拼音本身的复杂性,在不限制缓存深度的情况下,大部分过于依赖缓存的设计,性能都会随着容量的增加而锐减。我们随便找一个10长度的中文字符串,遍历所有的拼法就可以轻松产生 2^20 数量级的组合,在这种环境下足以拖垮相当一部分的缓存了。

这里小伙伴们大概要开始骂了,你改变了 JECh,你又把它改回去了,性能优化大概是在做梦吧。这自然不是这么简单,不然我也没有必要花时间写这篇文章。这次改动的核心在于对字符串的匹配进行预处理,或多或少和正则表达式的思路有些类似,同样是先编译模板,再在运行时使用模板进行匹配。但是这个结构是针对我目前的需要而开发的,一方面他的使用很简单,另一方面还可以提供一些额外的特性。

示例结构

上图展示了一个典型的模板结构。每个模板通常有三层结构:字符层(Character),拼音层(Instance)和音节层(Phoneme)。每一层通过引用相连接,这就避免了拼音层和音节层的重复构造。这三层均建立了缓存和索引,其中字符层是主要的开销:大约三万个汉字,而其他层因为对象是共用的,总共也就几十个而已。算上绝大部分的生僻字,这个缓存总容量目测也不会超过 1MB,和之前的缓存相比简直可以忽略不计。值得一提的是,考虑到之前 HasmMap 的惨案,我这里直接把汉字存在数组里,通过 unicode 码直接索引,免去了后顾之忧。

匹配的算法属于再普通不过的字符串算法,基本靠遍历。对于字符层,汉字基本使用 CharacterMul 进行多重匹配,而其他文本使用 CharacterSin 进行原文匹配。对于汉字而言,通常会包括一个原文和一个或多个(多音字)拼音。每个拼音(InstancePinyin)都会被拆分为声母,韵母和声调(均为Phoneme对象),分别匹配以适应各类简拼。每个 Phoneme 内含多个字符串组合,对应不同的拼法,其中包含了各类模糊音。在使用不同拼音键盘时,这些字符串也会相应地重载为当前键盘下的拼法。这个结构的好处在于完全分解了拼音的各种组合,运行时几乎只需要执行 equals 就可以进行判断,而不需要反复地拆分拼音,进位退位。

整个体系使用传统的“向前移动 n 位”进行交流,举个例子:对于文本“晚安”和“wan”,匹配字符“晚”时,光标可以移动 1 位或 3 位。移动 1 位是由于省略韵母的简拼,使得 “wan” 可以完全匹配“晚安”。至于移动两位,“wa” 在传统拼音拼法中不应当对应“晚”,所以不允许。这里的位数是通过 IndexSet 传递的。它表面上是一个整形集合,但本质上是一个整形(或者说 32 位二进制)。这里使用二进制编码实现的集合,一方面可以节省内存开销,另一方面可以用位运算进行包括遍历以内的大部分操作,比起容器类就大幅节省了 overhead。它当然也有一个弊端,就是范围很小,只能存储 0 到 31,但是这个范围足以覆盖单个字符的所有拼法了。

你可能已经注意到了,每个字符对应拼音文本都可能产生多个进位结果。我这里的选择是直接递归。一方面绝大部分的分支都会在一到两次调用内匹配失败而跳出,所以不会产生过多的性能损失,另一方面 Java 的调用栈性能相当可靠,我尝试过各种所谓的递归优化方法,都不如直接递归来的快。正常桌面环境下 Java 的调用栈可以达到数千层,这对于我的文本而言也是绰绰有余了。当然使用一些技巧可以在几乎没有性能开销的情况下将调用栈的高度对任意长度的文本控制在 10 层以内,但是当前环境下没有必要。

键盘适配

这是一个我可以大吹特吹的特性,但是我实在没这个时间,就稍微说一下好了。对于不同的键盘(全拼/注音),整个系统使用同一套拼音码表,使用全拼编码。至于注音拼法,完全是运行时生成的。相关代码在 Keyboard 这个类可以找到,首先查表将特定拼法转换成普通拼法,比如处理各种整体认读音节和 Ü 的省略问题,然后拆分成发音,映射到注音符号,再由注音符号映射到注音键盘的键位。这里最后两步可以合并,但是写都写了,就算了。比较蛋疼的是大陆和台湾的发音已经有一些区别,比如“锡”在大陆读“xi1”,而在台湾读“xi2”。为了适配各种读音,目前内置的码表实际上进行了合并,不过好在区别很少,所以基本上注意不到。

这个逻辑看起来非常简单,但是核心就在下一步。当用户切换键盘时,只需要刷新拼音层以下的(大约几十个对象)缓存,整个系统的行为就可以完成转换,不需要读取额外的码表,也不用在判断的实现中添加额外的逻辑,而且可以在运行时直接操作。这一过程同样适用于模糊音的切换。这个思路可以说是提供了极致性能,但是对于用户而言感受大概并不明显,很大程度上是我写着自娱自乐的(笑)。虽然这一系统相对于一些性能稍弱的实现所带来的提升难以察觉,但是相比于 JEI 动辄好几分钟的缓存重载,其中的差距还是很明显的。

动态替换

这是我之前念叨很久的一个特性,也算是做出来了。它允许本模组基于外部的列表对给定的函数调用进行替换。其中的实现非常普通,我也就不拿出来细讲了。现在的兼容列表可以在 这里 找到。其中的思路就是每次启动时在线抓取兼容性列表,解码为目标类,目标函数和替换类型,再在运行时查表替换。其中对于函数句柄和 Kotlin 函数的兼容虽说有点折腾,不过最后还是搞出来了。为了避免阻塞主线程,原本的设计是每次抓取都只缓存在本地,并在下次游戏启动时应用。我最终利用 Java 引用赋值的原子性配合时序做出来了一个非阻塞的模型,每次抓取完成后就即时生效。由于 Java 的懒加载模式,在网速正常且没有被墙的情况下,绝大部分替换都可以在同一次运行内生效。

因为暴力匹配替换已经被弃用了,这套系统最大的难点其实是如何找到特定的调用。为此我开发了一些小工具,使得查找在绝大部分情况下易如反掌。你只需要在游戏内执行 /jech profile,他就会自动扫描所有模组文件,并将可疑的函数调用汇总输出。配合这套工具,只需要少量的人工筛查,就可以定位需要替换的函数位置。配置文件中还提供了可以随时修改的替换列表(ListAdditionalXXXXX),来帮助确认替换效果。这套工具支持的调用包括 Java 的 String.containsPattern.match,Minecraft 的 SuffixArray 和 Kotlin 的 CharSequence.contains。即使是普通用户,只要稍有开发经验,就可以独立完成查找,应用与测试。JECh 之所以可以有如此长的兼容性列表,这套工具功不可没。这也是标题“让你的电脑不再爆炸”的来源,现在的每个替换位置我都人工审核过,确保不会有明显的兼容性问题。相比起之前的暴力替换,毫无疑问要安全得多。

发展方向

尽管这套替换系统已经兢兢业业地工作了一年多,但是在将来仍然有些前途未卜。Forge 1.13+ 已经完全重写了 CoreMod 的部分,强制使用 JavaScript 开发,并要求与其他逻辑分离。而 1.14 的 Fabric 则是默认使用 Sponge Mixin 执行 ASM 相关的操作。毫无疑问的是目前这套系统比起前一篇博文之前使用的暴力替换系统,已经无比接近各类新框架的需求。但是其中的一些特性,比如动态替换列表,我就不能保证保留了。比如 Mixin 的替换只能通过 Annotation 注明,也就是说只允许硬编码,所以动态列表前景尚不乐观。虽然现在社区还停留在 1.12,不过眼下看来新版本已经在快速逼近了。在接下来几个月我大概还可以保持观望,但是很快就会不得不作出改变。

另外一件事,虽然不如新版本那么迫切,但是也是毫无疑问位于计划列表顶端的,就是为匹配系统搭建新的缓存。我之前提到目前使用的匹配系统性能已经完全可以适应游戏内实时搜索的需求,但是对于一些极端的场景就有些捉襟见肘了。你可能会好奇究竟还会有什么场景,我可以举个最简单的例子,就是 JEI 的实时物品隐藏。有些整合包会在初期禁用绝大部分物品(说的就是你,SevTech),以致于每次载入存档时都会执行上千甚至上万次搜索,直接造成数十秒的卡顿。我虽然用了一些改动避开了相关的开销,但是还是治标不治本。

JEI 目前使用的是一个典型的后缀树(generalized suffix tree)来索引词条,以替代 contains 的调用。对于长度为 m 的子串,它可以达到 O(m) 的复杂度,而与总字符串容量无关。这使得 JEI 即使在有巨量物品的环境下,仍然可以可以以极高的速度索引物品。但是对于长串的缓存,最大的问题就是空间占用的高速膨胀。这在 Minecraft 内,并且使用英文搜索的情况下并不是个问题,因为英文单词可以被切分为短串。但是中文在不进行拆分的情况下,包含大量长串,而且对于拼音环境,组合又极多,还不是简单的 contains 匹配,所以后缀树并不能解决我们的问题。

所以思路还是回到前缀树(字典树,Trie)。既然手动建立索引费时费力,我们不如直接先执行搜索,然后把搜索结果缓存下来。这一设计的基础是子串长度每增加 1,就会有大量词条被过滤掉。每次搜索时,我们直接基于最长子串的结果进行过滤。这样只要我们建立 3 层索引,就有可能获得数量级上的提升。这一设计在远古版本的 JEI,和当前版本的 JECh 都有使用,基于 Guava 的 LoadingCache 实现,但是缓存策略相对温和。目前的思路是通过 fastutil 的 IntSet (参考 JEI) 来优化性能和内存占用,并且尝试压缩重复项,在有限的缓存体积内实现更深的索引。我希望这个结构的性能能满足前文所述的场景下的需求。

使用这一结构有一个很重要的前置要求,就是任意一个字符串搜索的结果集合必须是其子串搜索结果的子集,然而传统拼音拼法是不满足这一要求的。举个最简单的例子:“ji”不应该匹配“阶”。我们可以做的是对于最后一个音节进行不完整拼法的优化。简而言之,当“ji”在搜索串末尾时就允许匹配“阶”,也就是“taiji”可以匹配“台阶”而“jiti”不可以匹配“阶梯”。这就保证了结果集合随着搜索串的增长必然缩小。这一优化听起来稍微有些别扭,但是因为我们的场景只是用于过滤,对精度要求有限,所以几乎察觉不到。

篇幅有限,一些细节的实现我就不细说了,比如前文提到的“组合简拼”和“不完整拼法”。真想知道的话稍微花点时间读读源码就好。我写这篇文章一方面是记录一下目前的开发进度,这样如果当真有人想知道内部逻辑的话也有据可查,另外一方面是提供一些汉语拼音实现的思路。如你所见,我这里的场景和拼音输入法本质上是有不少出入的,但是一些思路仍然可以互相借鉴。我之前找资料的时候相关问题下面的答案大多是“不清楚,等搜狗大佬来答”之流;而网上所谓的“教你开发输入法”之流也大多数集中于系统交互,而拼音的匹配却非常简陋,不免有些遗憾。如果当真对一些人的开发能有帮助,自然是最好不过;即使没有帮助,单纯作为一篇开发日志内容也足够丰富了。