libime 原理介绍(一)

2022/06/29:感谢一些朋友的指正,更新了关于 rime 的一点信息。

写在开头的话:许多年前,在我才刚刚开始用 linux 的时候,刚好赶上了 Sunpinyin 的诞生。那个时候 Yong Sun 写了 Sunpinyin 代码导读。尽管那个时候因为知识的储备不够丰富,基本上没有能够理解文章的内容,但是现在回过头来的话,终于在 2017 年的时候,自己从头写了一个类似算法的输入法引擎,来代替早已过时的 Fcitx 4 中的默认拼音和码表。

虽然也许有人会有疑问,为什么要从头写这样一个输入法引擎,难道 Sunpinyin 不够好吗?我很久之前的一篇博客其实具体做出了一些功能上的解释。这里我们再重新从代码角度来解释一下 libime 的来龙去脉。

libime 目前的库分为 4 个部分,其中粤拼单独在一个Git 代码仓库里,粤拼大部分的代码是和拼音类似的。之后也不会特别介绍粤拼的部分。

另外一些原因是,其中很多核心的代码对我自己来说也已经不很熟悉了,也是趁此机会记录一下翻新一下自己的记忆。另外我相信这些经历的部分,对于了解 Linux 输入法和 Fcitx 的发展过程的也是很有趣的,当成一个故事来看大概也不错?

核心部分(Core)

在解说 Core 之前,就要说到为什么要写 libime 这件事。而这就不得不说说之前的几个前辈们,有些我只有大致的了解,所以可能有错误。首先是 fcitx4 的拼音输入,它的基本原理就是 Forward maximum matching,简单来说就是根据你当前的输入,找到词库中最长能匹配它的内容。这个算法本身在汉字分词的领域也有应用,优点当然就是快,缺点也很明显,就是给出的提示不够准确,没有句子的概念。而 Sunpinyin ,是一个基于N-gram统计语言模型的输入法。它根据拼音匹配到的词来计算一个最终句子的概率,从中将结果按照概率高低进行排序。

(更正一下关于 Rime 的信息) Rime 几年前确实没有语言模型,或者说只是类似 Unigarm 的算法 ,2019 年左右加入了 一个 bigarm 的实现。然而根据搜索对应的文件名,似乎没有哪个 Linux 发行版打包了对应的数据…所以可能根本也没什么人实际用上了 rime 的这个功能。

但 Sunpinyin 作为实现输入法来说,缺少很多丰富功能方面的 API,例如词库只有一个。也没有特别方便的修改词库的方式。另外词库本身还是采用 sqlite 进行存储,对输入法来说并没有很大的必要。

因此,libime 的核心目标就是,实现一个类似 Sunpinyin 的基于 N-gram 的输入法引擎,并且需要可以方便地支持我需要的功能,包括多词库等功能。

作为 Fcitx 4 的精神续作,我还希望它能够占用尽量少的资源。

作为核心部分,我主要想要包括的数据结构包括两个,Trie 和语言模型。如果查看早期的历史的话,可以看到好几种已经删掉的 Trie 的代码的实现。如果学习过数据结构代码的话,可能会知道 Trie 是一个表示树的数据结构,适合存储许多字符串。当你在 trie 上游走的时候,根据字符串当前字母的位置就可以找到其他匹配这个前缀的节点。

其中我对于它的数据结构功能的要求主要是这样的:

1、可以在运行时修改(有一些 Trie 的实现是无法动态修改的)
2、内存占用紧凑

在尝试了多个实现之后,最后采用了 double array trie 作为 Trie 的实现,采用了 cedar 的代码作为实现,但把其中可以用 C++ 标准库替代的部分都进行了替代从而精简了许多不需要的代码。这其中还踩了一个坑,简单来说就是 std::vector 替代之后的性能不如原本的性能,最终发现原因是 C++ 的 allocator 没有能对应 realloc 的函数。在可以原地 realloc 的时候,可以节省很多操作。因此又实现了一个 naivevector ,把 std::vector 里面实现替换成采用 malloc 和 realloc 的,从而获得了和原版类似的性能。

而语言模型我则找到了 kenlm 作为实现,在其上封装了对应的 API 方便调用。对应的就封装在 LanguageModel 类中。kenlm 提供了多种存储方式这里 libime 直接采用了一种内存占用较小的选项。

到此 Core 中两个核心数据结构的问题就都解决了。

kenlm 提供的核心功能就是给出一个当前状态,查询对应的词的概率。

    LanguageModel model(LIBIME_BINARY_DIR "/data/sc.lm");
    State state(model.nullState()), out_state(model.nullState());
    std::string word;
    float sum = 0.0f;
    while (std::cin >> word) {
        float s;
        WordNode w(word, model.index(word));
        std::cout << w.idx() << " " << (s = model.score(state, w, out_state))
                  << '\n';
        std::cout << "Prob" << std::pow(10, s) << '\n';
        state = out_state;
        sum += s;
    }

State 保存了当前的状态信息,本质上就是存储之前出现的 WordNode 有哪些,从而计算对应的下一个词出现的概率。概率的数值都采用对数。因此只需要将获得的概率简单相加,即可得到整体的概率。

在有了 Trie 和语言模型之后,Core 最后要提供的核心功能就是利用 Trie 和模型进行搜索,来获得最终的匹配的句子的结果,这个过程在 NLP 中一般称做 decode。对应的实现在 libime 里就放在了 Decoder 里。这里采用的算法就是 Viterbi。当然,为了简化做了对应的剪枝,整体的算法一般被称做 Beam search。(非NLP 专业,用词可能有不准确的地方)

而在此之前,我们先回到我们需要实现的输入法上来,这样才能更好的讲解这里算法是怎么起作用的。

首先我们要提到的就是这个类,SegmentGraph。它表示的是将字符串切分的方式的图。其中每个可以切分的节点都是图中的一个节点。对应到拼音当中,就是拼音进行切分的方式。切分的方式是完全的。对于一个最复杂的情况来说,例如(anana),可能的切分就是这样的。

对应表示了 a na na,an a na,an an a 三种切分方式。

decoder 的输入是一个 Segment Graph,而输出则是一个 Lattice(网格)。这里发生了什么呢?简单来说,就是把 Segment Graph 的上每一条路径,都放到词典上去匹配。具体采用的匹配方式由词典决定。例如,对于上面的例子,a na na 这种切分,就要匹配 a na na,a na,a,na na,na 几种不同的路径。针对这种路径构建出来的 Lattice 就类似:

当然,这仅仅是针对 a na na 这一种切分,其他的切分还会在上面加上不同的边。而上图的每条边上标注的拼音,在使用 Pinyin 词典进行 decoder 时就会去词典中进行匹配。每一条边都将对应的 SegmentGraph 中的 SegmentGraphNode,扩展为对应的词的 LatticeNode。

这里我们稍微换一个别的例子来进行解释。例如拼音内切分的经典例子xian(xi an)。在 xian 这个前缀所对应的节点,我们就有通过 xian 作为整体匹配的「先,线,县,现……」。而在 xi 这个前缀节点,则只有 xi(西,喜,系,洗……),然后这些 xi 的节点又通过 an 可以到达 xian 这个 SegmentGraphNode。例如有 an 「俺,按,安,……)。最后,还有直接通过 xi an 作为整词到达 xian 的(西安)。

将 SegmentGraph 经过词典匹配转换成 Lattice 之后的图就如图所示。当然,因为它在 Segment Graph 上是有联系的,并不需要把其中的每一条边都在内存当中直接展示出来。只需要管理好 Lattice Node 和 Segment Graph Node 之间的映射关系即可。

在建立好 Lattice 之后,就是经典的 Beam search 发挥作用的地方了。通过动态规划的方式计算每条可能路径的概率(或称作score),在某些情况下会减少可能的搜索结果,否则可能搜索空间巨大。

这里的 Beam search 整体来说分成三个步骤,第一步就是上面说的构建 Lattice(网格),第二步 forward search,第三步 backward search。

第二步 forward search 的基本步骤就是,广度优先遍历 Segment Graph 上的所有节点,或者换句话说,就是遍历所有可能的切分点(不论切分路径为何),然后计算切分点 Segment Graph Node 对应的 Lattice Node 的最高得分,计算方法就是找到 Lattice Node 对应的 Segment Graph Node 的父 Segment Graph Node。这个节点是唯一的,因为 Lattice Node 是通过计算某段拼音匹配的词找到的。然后针对这个父 Segment Graph Node 内的 Lattice Node 进行遍历,计算其中的最高分。简单来说就是 latticeNode.score = latticeNodeFrom.score + languageModel.score(latticeNodeFrom.state, latticeNode.word) 。这样不断求解,直到求出 Lattice End Node 的得分。

而 Backward Search 的主要目的是计算 N-Best score,如果只需要一个结果的话,那显而易见就是 Lattice End Node 的最高分对应路径。但怎么求解次一级的得分的路径呢?

简单来说就是从结尾倒推回去。最高分的 Lattice Node 的父 Segment Graph Node 的其他候选替换,来对比获得更好的结果。

Posted in fcitx development | 2 Comments

Analysis on a recent issue between Vivaldi and fcitx5-gtk

This article intends to explain the technical details between a issue happens when using fcitx5 on Vivaldi. I’m not a Vivaldi user and Vivaldi is not fully open source, so I can’t really comment what change actually caused this, but I’ll just describe my findings. Based on the information from forum post and social network, the issue happens on vivaldi 5.2 but not 5.1.

The Symptom:

https://forum.vivaldi.net/topic/75398/when-closing-one-window-all-other-windows-are-also-closed/48

When open multiple vivaldi windows, and close the vivaldi window afterwards, the whole browser may be closed instead. Only happened when fcitx5 im module is used.

What actually happened?

So first of all, let me talk about some technical details of how fcitx5 im module works: Fcitx 5 im module a plugin to Gtk 3 library used by vivaldi. In the plugin code, it initiates a DBus connection to dbus-daemon, and using dbus to interact with Fcitx 5 server.

Based on some debugging by attach to the relevant vivaldi process, the actual cause of the exiting is the dbus connection being closed. Fcitx 5 im module use gdbus API in gio to get a shared dbus connection (shared means shared within this process) and using it to handle dbus communications. For such shared dbus connection, a property “exit-on-close” is set to true by default. Which means, if the dbus connection is broken, the program will exit. Usually, such things can only happen on system logout when dbus daemon quits.

For some reason, Vivaldi breaks the dbus connection and then triggers the “exit-on-close” behavior defined in gio. I believe there is a bug in Vivaldi browser that caused this. My guess would be Vivaldi wrongly closed a wrong file descriptor which accidentally belongs to the dbus connection, or some weird interaction between glib mainloop within vivaldi, makes dbus connection think it’s closed. Though I don’t have enough evidence for this claim, but for the following reason:

  1. No other Gtk application (including chromium/chrome which is what vivaldi based on) suffers from same issue.
  2. Vivaldi older version doesn’t have this issue.
  3. Even though the gdbus connection is shared, it is only used by fcitx5, otherwise vivaldi will trigger the issue without using fcitx5, but actually not.

I would say the root cause is that there is a bug in Vivaldi code that closes the dbus connection.

Workaround implemented on fcitx5-gtk side (version 5.0.14)

Even though we think the bug is in Vivaldi, we’d like to avoid such issue from happening. So we applied following workaround:

  1. Use a private dbus connection object for the fcitx dbus client object. While it would use more resource, but in general it is acceptable. And make sure “exit-on-close” is not set on those private dbus connection objects.
  2. Even though we applied (1), we still noticed that dbus connection would be closed by Vivaldi. So we applied workaround (2): always try to recreate the dbus connection object if the original connection is closed.
    The necessity of (2) also confirms our previous guess of root cause, even if the dbus connection object is only owned by fcitx5 im module, somehow the connection will still be closed when Vivaldi window is closed.

Summary

To user who are affected by the issue, you may upgrade to fcitx5-gtk 5.0.14.

While explaining the technical details and debugging experience is fun, I just want to correct some incorrect understanding on this bug:

The root cause of the bug is not in fcitx5-gtk, and the bug is only triggered by fcitx5-gtk. The bug is in Vivaldi and is NOT fixed and the bug itself may have side effect on Vivaldi’s own code. fcitx5-gtk only implements a workaround to this Vivaldi’s bug.

While implementing workaround is not an ideal solution, we still choose to do that because:

  1. We want to get the actual problem solved for user.
  2. While using a private dbus connection will use a little bit more resource, it may still have some potential benefit from the isolation between the main program that also uses dbus. So workaround part (1) is not entirely a bad idea.

Thank you for your time reading this message.

Posted in 日志 | Tagged , , , | 1 Comment

Chrome/Chromium 今日 Wayland 输入法支持现状

似乎有不少人总是有疑问,Chrome的Wayland输入法支持到底是什么情况,能不能输入,支不支持,那么就姑且来总结一番。本文仅代表写作时的状态,不代表后续的情况。(以下用 Chrome 指代 Chrome/Chromium)。

首先简单介绍一下 Chrome 对 Wayland 支持的情况。对于 Chrome 这种跨平台的项目来说,肯定有自己的抽象层,从而能够高效地利用对应平台的 GPU,图形栈。现阶段来说,这一层抽象的项目的名称是 Ozone,更多详细的介绍可以参考 https://chromium.googlesource.com/chromium/src.git/+/HEAD/docs/ozone_overview.md。这里的描述是这样的:Ozone 是在使用了底层输入和图形的 Aura 窗口系统下的平台抽象层。一旦完成,这个抽象将支持各种系统,包括嵌入式 SoC,或者新的 Linux X11 替代:Wayland/Mir 来启动 Aura。

现在如果要在 Wayland 上用原生 Wayland 而不是 XWayland 来显示,那么将要使用 Ozone 作为它的图形栈。那么 Ozone 有什么样的输入法支持呢?在很长的一段时间内,它的输入法支持只有 text_input_v1,并且需要使用 –enable-wayland-ime 来启用。对于不了解 Wayland 输入法架构的人来说,这里对 Wayland 输入法的现状做一个解释。

Wayland 上的输入法分为两个部分,程序和 Wayland Compositor 之间的协议,和 Wayland Compositor 和输入法服务之间的协议。无论对哪个协议,都需要通信的双方同时支持相同的协议才能正常运作。Compositor 和程序间的协议名称是 text-input,目前的版本有 v1 – v4。Compositor 方面 v1 几乎没有支持,只有 weston 作为一个 demo 有简单的实现。v2 的功能是 v1 的扩展,但没有获得广泛的支持,也没有合并到上游的 wayland-protocols 里面。v3 则是 v1 的精简版。因为它已经合并到了 wayland-protocols 里,因此有较为广泛的 Compositor 和程序支持。text-input-v3 Compositor 的支持包括 mutter,kwin,wlroots,基本上可以说涵盖了所有 linux 主流 Compositor。text-input-v2 的 Compositor 支持则只有 KWin。而在 Toolkit 方面,Gtk 和其他一些基于 Rust 或者完全手写的 Wayland 程序支持的是 text-input-v3。 不知出于什么理由,Qt 只支持 v2 和 v4,相信主要有两个原因,v3 的功能不足,以及单纯的诞生时间的问题。

Toolkit / Compositorwestonmutter(GNOME Shell)kwinwlroots(sway等)
Gtkv3v3v3
Qtv2
Chromev1
其他如 winit 等v3v3v3
text-input 的支持情况

和输入法之间的协议则主要有 zwp_input_method_v1 和 v2,v2 并未合并到上游,只被 wlroots 部分支持,以至于至今稳定版的 sway 也不能支持显示输入框。v1 则有 weston 和 kwin 支持。KWin 支持 zwp_input_method_v1 主要是为了 Plasma mobile 和 Maliit,在 PLasma 5.24 我修复了绝大部分 kwin 的 zwp_input_method_v1 在桌面上的使用问题,现在可以和 Fcitx 5 使用。具体配置方式可以参考之前的一篇博客。而特立独行的 GNOME 则采用了 IBus 的 DBus 协议作为程序和 Compositor 的协议,间接导致我不得不在 Fcitx 5 里实现 IBus 的 DBus 协议。Fcitx 5 做到了完全支持所有现存的 Compositor 和输入法之间的协议支持。所以不要说什么 Fcitx 不支持,根本不是 Fcitx 这一边的问题。

zwp-input-method 版本westonmutter(GNOME Shell)kwinwlroots(sway等)
v1
v2
zwp-input-method 支持情况

让话题回到 Chrome 的情况上来。Chrome 早在 2018年就实现了 text-input-v1 的支持,后续虽然有 text-input-v3 的支持请求,但并没有任何后续动作。前面我们说道,支持 text-input-v1 的 Compositor 有且仅有 weston,几乎等于是没有桌面支持。Ozone 作为抽象,没有使用 Gtk 作为图形栈,因此也就没有自动获得使用 im module 的能力。而在 2021 年,他们添加了 gtk im module 的支持,但是仅限启用 gtk 4 的情况。尽管他们添加了这样的支持,由于他们完全没有用 Gtk 作为图形栈实现图形显示,因此他们的实现仅有部分能正常工作。主要体现在一些按键处理,以及输入法窗口弹出位置上。这里为了解释发生问题的原因,再稍微介绍一下相关的 gtk im module 的工作流程。gtk im module 需要程序调用对应的 API gtk_im_context_set_client_widget 来告知程序当前是哪个 Widget。而对于完全没有使用 Gtk 作为图形栈的 Ozone 来说,他们没有这样一个 GtkWidget 可以传递给 gtk im module。因此,他们目前的实现就是创建一个从不显示的 dummy gtk window,作为传递给这个 API 的参数。这里略微对比一下架构不同的 Firefox,Firefox 是采用 Gtk 作为他们的窗口的 API 的,因此 Firefox 的窗口是一个货真价实的 GtkWindow,而 Ozone 的 Window 则是他们自己直接使用 wayland API 创建的,和 Gtk 完全没有关系。而他们创建的 Dummy window 是完全无法用于让输入法弹出窗口定位在正确位置上的。甚至于由于这个窗口完全不被显示,Fcitx 5 im module 的 client side input panel 技术受限于 Wayland 的限制(xdg_popup 的父窗口必须被显示才能显示)甚至无法显示。而即使考虑是否能使用 gtk 自己的 text-input-v3 的 im module,也因为这个 dummy gtk window 对应的 wl_surface 不被显示,因此不会获取焦点(和 text-input 绑定的 surface 必须获得焦点才能使用 text-input 进行输入法相关操作),也无法正常工作。也就是说,采用 gtk im module 在 Wayland 下 Chrome 正常使用输入法的道路是「几乎」被堵死的。存在两个问题 1、输入事件处理栈并非 Gtk,一些输入法 API (Forward Key,但是是小问题)并不能正常使用 2、图形栈并非 Gtk,弹出窗口的显示既无法使用 Gtk 自身的 text-input-v3 实现,也无法使用 fcitx 5 im module 的 client side input panel。

对于 Fcitx 5 的现状来说,在使用 Chrome + Ozone Wayland + fcitx 5 im module 的情况会 Fallback 到 Fcitx 5 的 X11 输入窗口。也许你有疑问,为什么要 Fallback 到 X11 的输入窗口,不能用 Wayland 窗口显示吗?因为 Wayland 完全无法指定要把窗口显示在哪里,而 Gtk im module 尽管不能获得 Gtk Widget,但好歹能获得一个相对浏览器窗口的坐标。尽管把窗口完全显示在正常位置需要获得窗口自身位置,但如果在「单屏幕」,「窗口最大化」的前提下,这个不完全的相对坐标能够利用 XWayland「恰好」把窗口显示在一个差不多的位置上,总比随机显示在不知道哪里要强得多。

弹出窗口位置能够相对正常显示的唯一的情况,则是 Chrome + GNOME + Fcitx im module + Kimpanel 的组合。这里稍微再讲解一下 Kimpanel 的显示窗口位置逻辑帮助理解为什么这个组合可以工作。Fcitx im module 获取的坐标位置,根据 im module 获取的当前显示服务器类型,会针对 Wayland 额外设置一个标记「Relative/相对」,表示这个坐标是相对当前窗口的坐标。而 GNOME 上刚好运行在 Mutter 同一个进程的 GNOME 插件,则可以获得当前激活窗口的坐标。因此 Kimpanel 如果看到「相对坐标」,就会请求当前窗口坐标然后加上相对坐标来显示输入法弹出窗口。而反过来,对于 KDE Kimpanel 的情况,KWin 和 Plasma 在不同进程的情形,则拿着一个相对坐标束手无策,只能「假装」它是绝对坐标移动一下。而对 KDE Plasma 一个刚刚好的巧合是,Plasma 自身是占用全部屏幕的全屏窗口,因此如果拿到绝对坐标它是可以任意的移动窗口位置的。

综上所述,当前 Chrome 如果要在 Wayland 下使用输入法,各种桌面的组合和实际效果如下:

1、weston + chrome –enable-wayland-ime ,完美支持

2、GNOME + fcitx im module + chrome –gtk-version=4 + kimpanel,支持,但坐标似乎有些小偏移量问题(疑似和边框大小有关)

3、非GNOME,或者不使用 Kimpanel 的 GNOME + fcitx im module + chrome –gtk-version=4 可以输入,但窗口位置不对。

4、chrome Xwayland,完美支持(或者说和 X11 支持程度一致)

而根据 Chrome 当前架构设计,想要完美支持大部分 Linux 桌面的道路只有一条,就是原生支持 text-input-v3 。事实上,考虑已经有 text-input-v1 的实现情况下,代码应该不是很难写。所以如果想要让 Chrome 听见你的呼声,顶这个 bug 就对了 https://bugs.chromium.org/p/chromium/issues/detail?id=1039161

顺便,这个问题也对 electron on wayland 适用。

最后说一些不算解决方案的解决方案,如果你只是想用 chromium 的网页渲染引擎,你可以考虑一些基于 QtWebEngine 的浏览器,例如 https://www.falkon.org/ QtWebEngine 的输入法实现是对接给 Qt 的,可以完全正常在 Wayland 下使用,但缺点也明显,就是不支持 Web Extensions,但 falkon 内置了一些常用功能如油猴 adblock,所以没有复杂要求也可以考虑使用。或者也可以换成 Firefox,它的 Wayland 下输入法支持很好。

P.S. 最后的最后 Fcitx 5 能对这件事做什么?什么也做不了。这不是 Fcitx 5 的 Bug。我是想不到目前有任何改动属于 Fcitx 项目代码的方式能够完美支持 Chrome。

如果非要让「我」力所能及支持点什么的话,1、可能就是给 KWin/Plasma 写一个Wayland 私有协议,允许把窗口移动到相对当前活动窗口的坐标位置上去给 Kimpanel 用。2、或者加回 KWin 删掉了的「没人用」的text-input-v1 支持。说实话,这两种如果写了都是技术债,第一个可能还有点用(通用意义上),但我也并非什么 KWin 的专家。就像我之前说的,我一个臭写输入法的,怎么就去开发 Compositor 去了。

Posted in fcitx development | Tagged , , , , | 7 Comments

New compose mode in Fcitx 5

1.5MB gif for demostration.

Basically it allows you to use backspace to modify the compose sequence, or type character directly with dead keys (e.g. you may simply press dead key once and continue to type).

If you want the old traditional X11 behavior back, you may simply uncheck the “Use new behavior” option in keyboard input method.

Posted in fcitx development | Tagged , , | Leave a comment

Setup Fcitx 5 on Linux (Video)

Recently I started to make some video with detailed step on how to setup Fcitx 5 on different distribution.

Helps are also welcome if you want to make an instruction for the distribution that you use.

Fedora/KDE: https://www.youtube.com/watch?v=FwqTtGEN4vQ (Vocal by me in English)

Archlinux: https://www.youtube.com/watch?v=8XDmLr6wb4M (No voice, English/Chinese subtitled)

Posted in 日志 | 1 Comment