DarkNode

Life, the Universe and Everything

用 Rust 重写博客并为英文部分自动断字

本文发表于:
最后修改于:
分类:system
合计信息量:3.67kb

背景

在很长的一段时间里,我使用 Hexo 来作为博客生成器,但 JavaScript 实现的 自动断字插件 性能很差,严重拖慢了生成器的性能。

另一方面,Hexo 复杂的依赖也是一大麻烦,node_mod­ules 目录里上万个零碎 js 文件着实让人生厌。

于是乎,借着学习 Rust 的机会,用 Rust 重写了整个博客系统,并加入了自动断字与中英文间加入空格的功能。

Liang 的断字算法

目前最常用的断字算法来自 Franklin M. Liang 的博士论文《Word Hy-phen-a-tion by Com-pu-ter》,论文中 3/4 的内容是在介绍如何产生一组模式(Pat­tern),用什么数据结构储存这些模式,只有大约 1/4 的内容介绍了如何使用 Pat­tern 进行断字。

模式是一组英文字符(Char)和码点(Point)构成的序列,比如 hy3ph,其实对应了 hyph 这个字符序列,和 0, 0, 3, 0, 0 这组码点。

这个模式会匹配包含 hyph 的字符串,并指出在 y 和 p 之间可以断开。

一个英文单词包含的全部模式被合并到一起就得到了这个英文单词的码点,其中相同位置上较大的码点值会覆盖较小的。

       . H y p h e n a t i o n .
hy3ph => h y p h
        0,0,3,0,0
he2n  =>       h e n
              0,0,2,0
   ...   ...   ...   ...   ...   ...
1tio  =>               t i o
                      1,0,0,0
o2n   =>                   o n
                          0,2,0
       [0,0,3,0,0,2,5,4,2,0,2,0] <- This is Points
            ↓       ↓
         H y-p h e n-a t i o n

单词前后会加入一个点,用于标识单词的开头或者结尾,这样就能用.ach4 这样的模式匹配位于单词头部的 ach 字符串了。

所以本质上说,这一断字算法其实是在进行多模式匹配,实现时,最常见的是使用一个 Trie Tree,逐个遍历.Hy­phen­ation.Hy­phen­ation.yphen­ation.等等能否在 Trie Tree 中匹配到,不过这一做法的时间复杂度显然较大。

性能最好的算法是 Aho–Cora­sick 算法,遍历一次单词即可找出全部的匹配模式。Aho–Cora­sick 算法可以用 Map 实现,也可以使用 Ar­ray 实现,有两点值得注意:

  1. Rust 默认的 HashMap 其实空间利用率非常高,而 Ar­ray 的空间利用率优势并不明显
  2. 但是 Fail 跳转不同节点这个操作在 Rust 下非常麻烦,在一个节点里保存对其他节点的引用非常麻烦

所以这里选用了 Dou­ble Ar­ray Trie 这种方式,用数组索引的方式来保存引用。

从结果来看,这种实现的性能是 hy­phen­ation = "0.6.1"这个实现的 3 倍左右,传统的 HashMap+Tire Tree 似乎更容易 Cache Miss。

用 Cachegrind 简单的检查了一下,D1mr=0.44,DLmr=0.16,还算能接受吧。

中英文间距

中英文间距问题其实涉及两个问题,首先是在哪些字符之间加,其次是加什么?

目前参考 中文文案排版指北,在中文与英文,中文与数字之间加入了间距。其中中文部分根据 Uni­code 11 的定义,采用如下几段:

根据 Uni­code 空格预览 在几个主要的平台下的主流字体里的显示效果,选择 U+2009 THIN SPACE,这是一个比一般空格稍窄的空格,明确表明了其排版功能,也方便后期可能需要全部去除时与正常的空格的区分。

纯 CSS 解决方案

一个备选方案是将所有的英文部分用<span lang="en-US">包裹,并且配置 hy­phens: auto;这个 CSS 属性,这样就能为英文部分加入自动断字了。

但是想用 CSS 3 为<span lang="en-US">解决中英文之间的间隔问题却很难。

首先想到的是为<span>添加 mar­gin,但是想取消两个相邻的<span>之间的 mar­gin。需要用相邻兄弟选择器选择第二个 span 元素并为其添加一个负的 mar­gin-left。因为 CSS 3 下是无法选择到两个相邻兄弟元素中的第一个的 mar­gin-right,只能选择到第二个元素的 mar­gin-left,

那如果是更加复杂的嵌套情况呢?例如:

<em><span lang="en-US">Eng­lish Text</span></em>
<strong><span lang="en-US">Eng­lish Text</span></strong>

我们需要选择((拥有 lang 属性为 en-US 的子元素)的行内元素,且这个元素是((拥有 lang 属性为 en-US 的子元素)的元素))。

em:has(span[href="en-US"]) + strong span[href="en-US"] {
    mar­gin-left: -0.3em
}

事实上,我们需要为每种行内元素和紧接着的每种行内元素都创建这个规则,考虑 em, strong, code, a, img 共 5 种,这个 CSS 3 选择器的运行效率实在是很糟糕。

小结

所以最终选择了要编写更多逻辑的 hack 方法,把更多的工作放在生成器上完成,也算是练习 Rust 了。

在使用了这两个 hack 之后,博客的排版效果好了很多,并且省去了人工干预的过程,实在是可喜可贺,又有动力继续写点东西了。