Get event order right (Try 2!)

TL;DR: this is not considered as a user facing change.

In a previous post, we discussed the issue between the input method event order and the blocking dbus call. To put it simple, input method may generate multiple different outcomes from a single key press, such as committing text, set preedit, etc. The key press comes as a Inter-process communication(IPC) from an application to Fcitx.

If this IPC is blocking, then the event can only arrive after the call is done. Previously, we tried to always use async call to ensure the event happens before the reply is delivered to application first. This can’t be used for Gtk 4 GtkIMContext anymore. Gtk 4 hides too much API comparing to Gtk3, which prevents us from doing a lot of things, for example, re-inject the key event into the application.

In the old async mode, the key event will always be filtered by Fcitx IM Context, then re-inject into the application when the result of event handling returns. Upon the result is received, Fcitx IM Context will copy the GdkKeyEvent back into the application with a special flag on the modifier, to prevent it from being handled by Fcitx IM Context again.

In Gtk 4, there is no API to create a synthetic key event (which is problematic for some other features that Fcitx supports, but we will not discuss that here), which means we will need to implement using the synchronous mode anyway.

Well, not really “must”, because I do find some API to allow a hacky asynchronous implementation, by memorizing the pointer address of GdkEvent and use gdk_put_event to reinject the event. Though that doesn’t work for chromium code because it doesn’t use gdk for event handling.

So what we can do here? The answer is, we create a new version of ProcessKeyEvent API, ProcessKeyEventBatch.

In the old synchronous mode, the root cause of wrong event order is the event sending from input method can only be handled “after” the synchronous ends, which is not we want to see.

In the new ProcessKeyEventBatch, what we do is we do not send the event from input method to application immediately. We block the sending procedure on the input method side until the reply happens. When the reply is finally being sent, Fcitx will put all the events that need to be handled by application in the reply.

Say, application want to commit some text before the key event is handled by application. After commitString() is called on the input method side, the CommitString dbus signal doesn’t happen in the new mode, instead, we wait and put them together in the return value of “ProcessKeyEventBatch”. Upon receiving the reply, the FcitxIMContext first decodes the reply to see if there is anything piggybacked in the same reply, and handles them first. This will make the event order consistent on both of the input method side and the application side.

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

Redmi AirDots 3 Pro 原神版体验兼我的十年耳机史

本来想要标题写个「评测」但是想了想,觉得自己完全不是那种能认真客观评价这种产品的。耳机从来我要求也就是听个响。而买这款的主要原因当然也是觉得这次联动做的特别有诚意想要收藏。

所以最多也就是横向对比一下用过的其他耳机了。

老实说,这几年买过的蓝牙耳机加起来可能有8个了,算上非蓝牙可能一共得有十几个,与其说这次是评价这款耳机,倒不如说是某种对我不断尝试蓝牙耳机的总结。

首先,我对音质是真的没有要求,通俗的说就是听个响。这么多耳机音质方面我其实分不出什么高下。真要说的话,我看中的大概最重要的是舒适度。

把时间倒回10年前,从10人民币级耳机毕业的第一款……是 Panasonic RP-HTX7,纯粹是因为看了《花开伊吕波》之后觉得这个耳机颜值很好才买的。当然因为是头一次买上百元级别的,至少是真的发现音质不一样了。唯一的问题是我太能造耳机了,侧躺着也经常强行带着,以至于耳罩坏的很快。

当时考虑的是买个入耳式的蓝牙,因为也确实体验到了有线毕竟是不够爽。下一款就是 Avantree Sacool Bluetooth 这个蓝牙耳机。牌子自然是没听过的,买来之后总之是觉得不太爽,结果反而入了 Comply 的记忆海绵耳塞的坑。而我这个人老实说,耳油是特别重的,以至于 Comply 的消耗速度在我这实在是太快。所以又打起了要不要试试骨传导的想法。

AfterShokz TREKZ Titanium 然后就尝试了骨传导。总之下场是这个被我最后造坏了……另外舒适度来说,实在也没有达到预期。贴在后脸上的位置总之是感觉也怪怪的。

之后又尝试了另一个 Bose Soundsport ,也试了用别的耳塞,总之是怎么戴怎么不得劲。然后我觉得我可能不适合戴入耳式的耳机,想起HTX 7是覆耳式的,于是又鬼迷心窍去买了有线的 AKG Q 701 。AKG Q 701 可能是这么多耳机里我最后悔的一个了。因为 TM 这玩意它压脑袋,戴上之后头顶会很痛。我尝试了许久各种姿势乃至自己用尼龙扣强行让某些地方减轻用力都没有得到什么效果。

之后又听说了主动降噪……我是真的听一个什么新玩意就想要试试…这次学乖了,买了个二手的 Sony MDRNC500D。效果来说是还不错,舒适度也可以,然而最后连接杆被我造坏了……

然后就进入到正题,也就是我还在用的几个耳机。首先是 Bose QuietComfort 35,这个是五年前买的了,用到现在的话换过三次耳罩,不过还算方便吧,但是外壳的损耗程度已经快接近没的可换的状态了。目前大部分时间懒得充电,当有线使用。

然后是 AirPods 第二代,这个我甚至买了两个……如果说我以前怀疑入耳式有多难受,AirPods 是我这么多年以来发现的难得的一个戴着不会难受的耳机。说实话, 不会耳朵痛的耳机真的是爽到不行……相反 AirPods Pro就完全让我的体验回到过去的那个入耳式难受的状态。

在 Redmi 这款联动耳机到之前,基本上是一直在用 AirPods 的状态。偶尔用一下 Bose QC35。首先说一下 AirPods 的优点……那就是一个拆成两个用,双倍续航时间充电还快。充电盒也非常的方便。即使偶尔有个没电了也可以塞进去用另一个。

Redmi 这款耳机基本上也是类似的设计,很惊喜的一点是……虽然是类似 AirPods Pro 的入耳式,但是竟然不会耳朵痛,这真是太神奇了…光是为了可莉语音的情怀也打算多尝试一段时间看看。续航的话没有认真对比,但是感觉上好像不如 AirPods,不过也算可以接受吧。功能上除了双击,长按,还有三击,可操作性上比 AirPods 多了一个按键功能,这点还是颇为满意的。可以同时连接两个设备不需要切换,相比 AirPods 需要手动切换(我并不用 Mac 所以也体会不到自动切换到电脑之类的功能)要稍微方便一点点。

可莉的书包和嘟嘟可故事集也都制作的颇为精致,收藏感觉很好。充电是 USB-C 线,颜色和外形的 Logo 也都很好的制作了相关的四叶草,火元素标志。音质反正我分辨不能。因为到手还没几天所以也很难评价更详细的内容,但是我带着耳朵不会痛这一点是巨大的加分项,光冲着这一点我也愿意继续尝试使用看看。

Posted in 日志 | Leave a comment

libime 原理介绍(二)

之前第一篇主要介绍了关于 beam search 和输入切分相关的内容,以及提供的一些基础数据结构。接下来主要着重补全介绍上次没有提及的 UserLanguageModel 和 HistoryBigram 的实现细节。

声明,本文需要的很多前置知识都可以在大学本科的自然语言处理类课程找到,关键词「统计语言模型」,「N-gram」。概括的说,N-gram模型是对现实语言的不精确概括,它不关心语法,只关心词与词之间出现的频率,尽管不精确,但对于输入法,机器翻译,语音识别等等领域都有不错的效果。

首先上一篇当中提到了我们的输入法的算法核心是 N-gram 和 beam search。一般对采用这种算法的输入法来说,N会取 3 或者 2。可以取得效果和内存占用的平衡。这里姑且来说我们也继承了一部分 Sunpinyin 的精神,因为最初最初的数据就是采用 Sunpinyin 使用的 Open-Gram。当然这里顺便一提,在最新的版本我们重新用全新的数据训练了语言模型。但依然采用了和 Sunpinyin 一样的 Trigram。

HistoryBigram,顾名思义,是一个存储用户输入的 Bigram。它干的事情其实非常之简单,就是把用户的输入的句子根据词一条一条的储存起来。而在内存中,它被存储在 DATrie 中。你也许想问一个问题,就是 DATrie 抽象起来看,可以被看作一个字符串到 4 byte 数据的映射,那么它究竟是怎么存储 Bigarm 这样有两个级别的 Key 的映射表呢?

答案其实很简单,就是你把 Key 做特殊的编码让它能够承载更多的内容。简单的把两个字符串加一个分割符拼成一个就可以了。Bi-gram 和 Uni-gram 计算得分的公式也是来自 Sunpinyin 。最直 的来说,Bigram 的概率应该是 P(B|A) = Freq(AB) / Freq(B) 也即出现 AB 的次数除以 A 出现的次数。对于没有 AB 的情况只会得到 0。这对于一个模型来说效果并不好,语言模型会采取平滑(Smoothing)来保证即使数据很稀疏(用户输入的历史是很少的),也能得到有意义的结果。这里就是把 B 单独出现的次数也拿来做一个加权平均。来减少因为采样而导致的数据缺失。

而这距离实际的输入法的情况,还有两个问题亟待解决。1、如何混合系统模型和用户模型,2、如何保证用户的输入能够快速在排序上体现效果。

第一个问题,尽管不精确,但是我们采用的方式是两个概率值加权平均。当然这里也小提一下 sunpinyin 的实现。在最初实现 libime 的时候,很多具体的细节的方案都尝试参考了 sunpinyin 的做法,但也发现了 sunpinyin 很多「奇怪的设计」。例如概率值为了减少浮点数运算,通用的做法都是采用对数概率,这样概率的乘积就是简单的求和了,效率要高的多。但 sunpinyin 的概率权重却是用对对数概率计算加权的算术平均,这就非常奇怪了(很奇怪也不太符合数学)。libime 这里就采用了至少道理上更说得通的原始概率计算算术平均。不过这里有一个小问题,假设你有了 log(P_sys) 和 log(P_user) 怎么计算 log( w * P_sys + (1 – w) * P_user) 的问题。

如果你直接计算的话,我们代换一下数字就可以得到 log(a * pow(10, log(P_sys)) + (1 – a) * pow(10, log(P_user))),总共调用了 3 次 math 的函数。能不能减少一些呢?其实是可以的。

假设我们需要计算 log10(exp10(a) + exp10(b))
log10(exp10(a) + exp10(b))
   = log10(exp10(b) * (1 + exp10(a - b)))
   = b + log10(1 + exp10(a - b))
   = b + log1p(exp10(a - b)) / log(10)

得到上面的公式之后,为什么特意弄出 log1p(exp10(a-b)) 的形式呢?是因为标准库中提供了这样一个函数 log1p10exp,可以一步到位计算这个数值。为了更加精确,可以根据 a b 相对大小来选择是 a – b 还是 b – a。其中 log(10) (e为底)这种常数都可以预先计算,就将 math 库函数调用精简到了 1 次。

可能你会问,原本公式的 w 和 (1 – w) 的权重去哪了呢?这个问题也很简单,你只需要把他们先转化为对数计算即可。

log10(w * exp10(log_sys) + (1-w) * exp10(log_user))
   = log10(exp10(log10(w)) * exp10(log_sys) + exp10(log10(1-w)) * exp10(log_user))
   = log10(exp10(log10(w) + log_sys) + exp10(log10(1-w) + log_user))

这样就可以完美带入到之前的公式当中了。log10(w) 和 log10(1-w) 对输入法来说也都是常数,可以直接计算。

另一个问题就是如何保证用户「新」输入的内容能够快速排序到结果的前列。sunpinyin 的做法我做了一定的参考,但是理性上觉得不太合理所以根据情况优化了一下。sunpinyin 只记录 1024 个词在历史当中,当有新的词进入历史的时候,会踢出老的历史。这个设计让用户输入不会偏离系统输入太远,但也会相对影响用户历史的记录。然后最近输入的一些词的频率会乘以一个系数,来变相增加新输入的内容的权重。但这个范围的数字其实很小,可能会导致这部分改变结果顺序的行为很快被遗忘。

libime 这里采取了类似但做了一些自己的改进。第一,将用户输入的词按句子记录,第二,将用户输入的句子分成三个不同大小的 pool (128,8192,65536),每个 pool 给予不同的概率权重。(具体的数字的选择纯粹就是所谓的 heuristic 的了),这样相对保证记住的历史较多(65536个句子 vs 1024 个词),同时也有根据输入时间有衰减的效果。

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

Fcitx 5 Plasma Theme support

Kimpanel is a plasma applet that uses plasma and dbus to display the input method popup window. In X11, people who want to have native plasma theme based input method window may use it to provide a nice integration with plasma.

So you might ask, we already having kimpanel in Plasma desktop, what’s point to have this feature in Fcitx 5?

Well, if you use the wayland.. you will notice that kimpanel does not work properly in terms of window positioning. The input window is a small popup window used by input method. It needs to be shown at the cursor position in order to make user eye focused at the point where they are typing. This popup window is critical for CJK input method users.

And you might ask again, why can’t we just fix kimpanel? Unfortunately, it’s hard to fix.

There are quite a few technical difficulties behind this. Kimpanel applet currently runs in plasmashell. Unlike the gnome implementation (also maintained by me, BTW :D), running within the compositor, Plasma’s kimpanel right now have no ability to obtain the information of other windows nor to move the window position freely. Kimpanel requires following things to make it work:

  1. If the client cursor position is absolute, move it to the position.
  2. If the client cursor position is relative, move it to current window top left corner + offset.
  3. For text-input client, there’s no position sending to input method, and compositor need to help input method to move the popup.

Unfortunately, to implement this support in wayland is really hard and would involves lots of changes in KWin. That somehow defeat the point to all the works we have done for zwp-input-method-v1 in KWin, because zwp-input-method-v1 protocol already has a concept of popup surface (need to be a surface from the same input method process). So I never try to do that due to the reasons above. Only until recently, I learned that KWin script can actually show real QML items, so I make a prototype that runs kimpanel within the KWin. You hit lots of KWin issues during writing the prototype, including kwin crash, flicker, etc. Luckily we are making progress with the help from KWin developer on unblocking the possibility of porting kimpanel to kwin (only for the popup, the action panel will still be in plasmashell). But until all the known issue are resolved, I can’t really submit the change the implementation of kimpanel from plasma-desktop to kwin script otherwise it will be totally broken. Also, we’d like to only use this on wayland, because for X11, expert user may choose not to use kwin at all.

Back to the original topic, Fcitx 5 is hardcoded to use client side input panel on KDE Wayland. The client side input panel always uses the classic ui theme (im module load classicui theme and render it). If kimpanel is allowed to be used wayland right now, the popup won’t show at the right position. In order to use Plasma theme, we need some support in the classicui addon of Fcitx 5. I wrote a simple tool to automatically generate a fcitx theme from plasma theme. I used to have such a tool around fcitx 4 era. This time, it’s even better, because we integrate the support of this tool in Fcitx 5 natively. If the Plasma theme is selected in classicui, it will run a small daemon, keep monitoring the plasma theme change and automatically regenerate the theme when needed. It can also be used as an standalone tool to generate the theme for one-time.

To use this feature, just get the latest stable version of fcitx5 & fcitx5-configtool. Simply choose “KDE Plasma (Experimental)” as Theme in fcitx5’s classic ui configuration, and that’s it.

Posted in fcitx development | Tagged , , , | 1 Comment

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