Skip to content

宇浩输入法开发技术文档

宇浩输入法开发非一日之功,使用了很多 Python (numpy, pandas, porlas...) 程序的辅助决策。这里,谨将部分编程相关的内容予以展示和讨论,供输入法或数据分析的同好参研,以期共同进步。 本文的写作也不会是一朝一夕,我将逐渐往里面增加内容。 繁简通打、动静低重、字根分区、兼顾手感,这是宇浩输入法的四个基本设计原则,目的在于避免机器学习中的「过拟合问题」,防止输入法被局限于特定的文本空间和字形状态,以期获得更大的适用性。在保证这四个原则的基础上,作者还采用了其他的客观指标作为「宇浩算法」的约束条件,以提高输入法的整体素质,防止有严重的短板产生。做到「整体性能均衡,部分指标优异」。

以下介绍为作者设计本输入法时所考量的客观指标,这些指标在编写优化算法的时候得到了应用,并且配以不同的权重。在此将其中重要的予以列出,方便用户进行深入了解。某些指标的详细计算公式,可以参考本网站研究板块,方便有一定统计背景的研究者评议。

宇浩输入法优化时,进行局部最大化的指标,按重要性排列:

  • 字根键位空间聚合度。或者说是字根排布的规律性。光华方案采用类似五笔的「首笔分区布局」,星陈方案采用类似郑码的「相似字形聚合」。该布局下,每个字根可能存在的键位空间在 4 - 6 之间。故而,每个字根优化空间只有全乱序布局的 25%。优点:依照形码设计原理,易于上手,方便学习。缺点:各项指标理论极限低于纯乱序排布方案。
  • 最大化键位舒适度(简体、繁体)。键盘上每一个按键,都有一个得分。食指、中指上的按键的分较高,无名指、中指上的按键得分较低。中排的按键得分较高,下派的按键的分较低。手指位移小的按键得分较高。比如 T 得分大于 Y。因为 Z 键比较难按,在部分输入平台又预留为功能键,故而本输入法不在 Z 上设置大码。优点:提升手感,增加平台通用性。缺点:全码理论编码空间只有 26 键方案的 85%,理论极限离散水平低于 26 键方案。
  • 最大化各文本空间 双手互击率。在连续文本的情况下,计算编码的双手互击率(包括标点符号)。如:「我今天去那里」,编码为 qaggtobufgdihvvtvacjksij。出现了 14 次同手击键,9 次双手互击,故而互击率为 39.13%。这里用到了隐马尔科夫链或大样本统计,以计算每个汉字后下一个汉字的频率,从而得到连续文本的双手互击率。因为宇浩输入法是将字根按照键盘分区进行排布的,相对于全乱序字根排布的方案,双手互击方面有天生的劣势。如果不进行优化,那么会影响手感。这也是为什么宇浩输入法将双手互击率专门拿出来进行优化。宇浩输入法在保证字根分区、二十五键、重码极低、繁简通打这四个原则下,将双手互击率拉到可观的水平,星陈方案的双手互击率甚至达到了 62.5%.

宇浩输入法优化时,进行局部最小化的指标,按重要性排列:

  • 最小化简体文本、繁体文本、混合文本下的 全码动态选重率。优点:实现真正意义上的繁简通打。用户使用本方案就可以自由切换繁简输入,不用选重。缺点:影响了极限简体/繁体文本各自的动态选重率,不过本输入方案的简体/繁体动态选重率已经是市面上最低的,所以这个缺点可以忽略。
  • 最小化 GB2312、国字常用字的静态重码数量。这是因为动态选重率高度依赖文本的状态,而静态重码数量在非典范白话文的情况下更具有代表性。
  • 最小化 GBK 的静态重码数量和翻页次数。这是为了不丢失检字的性能。本输入法 CJK 全汉字单编码最高重码字数为 18 个,也就是说,即使是生僻字,最多翻页一次即可找到。
  • 最小化简体文本下的 完美词语选重率,使用了当代汉语词频表。例如,「我今天去那里」被分割成「我·今天·去·那里」,一共有 4 个词语。倘若「我」和「那里」发生了重码,则选重率为 1 / 4 = 25%。优点:考虑该指标,可以优化用户打词时的选重体验。缺点:本指标的成立条件,只有当用户的分词习惯和词频表一致才有效。大多时候,用户会将词语拆成单字输入,避免词语不存在时的回删。因此,真实的文本选重率,介于单字动态选重率和完美词语选重率之间。另外,当样本空间改变时,比如输入非典范白话文的情况下,本指标参考价值也会降低。
  • 最小化速度当量(陈一凡,张鹿,周志农,1990,《键位相关速度当量的研究》,《中文信息学报 Vol.4》)。速度当量是关于「手感」的最宏观、量化的指标,是由大量实验得出的结果,具有很高的参考价值。这个指标越小,表明输入的速度越快。宇浩输入法在优化过程中,最小化字频加权速度当量。

算法代码

以下为「宇浩算法」伪代码,谨供参考。

python
# 「宇浩算法」僞代碼
k_max: int  # 外層淬火輪數
l_max: int  # 内層貪婪輪數
t_k: float  # 混亂度
x_1: Sequence[str]  # 字根編碼
y_1: float  # = f(x_1) 當前各指標加權分值
x_1_best, y_1_best = x_1, y_1  # 最優解
# 外層淬火 開始
for k in range(1, k_max):
    x_2 = rand(x_1)  # 隨機擾動
    y_2 = f(x_2)
    x_2_best, y_2_best = x_2, y_2
    # 内層貪婪 開始
    for l in range(1, l_max):
        # 同大碼字根組遍歷 開始
        for roots in groups_of_roots:
            # 該組字根大碼遍歷候選鍵位或分區 開始
            for dama in dama_candidates:
                # 該組字根小碼遍歷候選鍵位的組合 開始
                for xiaoma in product(*xiaoma_candidates):
                    x_trial: Sequence[str]  # = f(x_2, dama, xiaoma)
                    y_trial: float  # = f(x_trial)
                    y_delta = y_trial - y
                    if y_delta <= 0:
                        x_2, y_2 = x_trial, y_trial
                    if y_trial < y_2_best:
                        x_2_best, y_2_best = x_trial, y_trial
                # 該組字根小碼遍歷候選鍵位的組合 結束
            # 該組大碼遍歷候選鍵位或分區 結束
        # 同大碼字根組遍歷 結束
    # 内層貪婪 結束
    y_delta = y_2_best - y_1
    if (y_delta <= 0) or (random.uniform(0, 1) < np.exp(-y_delta / t_k)):
        x_1, y_1 = x_2_best, y_2_best
    if y_2_best < y_1_best:
        x_1_best, y_1_best = x_2_best, y_2_best
    t_k = 0.75 * t_k  # 使用指數降溫
# 外層淬火結束
print(x_1_best)

量化指标

评价一个输入法的好坏,需要从不同的维度进行判断。同时,每一个人对于不同维度的偏好也是不同的。这就说明不存在一个完美的输入法,使得它对于不同维度的权重排序满足所有人的偏好排序(经济学上,有个著名的「阿罗不可能定理」 Arrow's impossibility theorem). 但是,通过显示不同维度的量化数据,可以帮助用户进行权衡。 量化的数据可以反映实际的体验,但不一定能完美代表真实体验。因为量化指标无法覆盖全部的维度,且在实际当中,影响输入体验的要素(杂音)很多。例如,键盘字母的排序,是传统的还是德沃夏克的,都会影响所谓的「手感」. 再比如,所谓的动态选重率,一般是基于一个大样本的文字频率,这个频率虽具有代表性,但也只是代表一种社会文化的均值。对于每一个用户来说,未必会使用相同的样本空间,例如个人姓名用字的使用频率往往会较高。如果姓名出现重码,需要选重,会使得用户的体验不佳。 在宇浩输入法的首页和 这篇文章 中,我对宇浩输入法所采用算法和指标进行了介绍。在这篇文章中,我将展示它们是如何在 Python 中被计算和实现的。Python 的特点是部署效率很高但运行效率不高,所以我对某些需要大量循环的函数进行了一些优化,主要是利用了 numpy, pandas, polars 等包的一些特性。这些包一般使用 C/C++/Fortran/Rust 编写,对于向量计算有着高度的优化。这篇文章中,我也会讨论某些代码为什么要这样写。

字集静态重码数

单字的静态重码,指的是在一个字符集中,编码完全相同的汉字的个数。 假设 Z 为一个汉字的集合,M 为一个编码的集合,p:Z[0,1] 为汉字到某文本状态下单字频率的映射。 用编码和字频对汉字排序,使汉字 zij 是编码为 mi 的第 j 个汉字,iI, jJi, 且满足 ab 时,f(zia)f(zib).

那么,静态重码数可以表达为:

Ns=∣{zia,zib if M(zia)=M(zib) for all a,bJi and iI}.

对于此指标的计算,较为简单。但为了运行的效率考虑,我们可以使用 numpy 包。

python
import numpy as np
import typing
import numpy.typing as npt

本文其他代码都使用以上引用。

python
def get_static_dup_rate(
    char: npt.NDArray[np.dtype("<U1")],
    code: npt.NDArray[np.dtype("<U4")],
    charset: typing.Sequence,
) -> int:
    """计算某个字集内的静态重码数

    Args:
        char (npt.NDArray[np.dtype): 元素为汉字。
        code (npt.NDArray[np.dtype): 元素为编码。
            宇浩输入法编码不超过四位,所以编码的格式是 4 个 Unicode 组成的字符串。
        charset (typing.Sequence): 字集。元素为汉字。比如通规汉字或 GBK.

    Returns:
        int: 静态重码数:
    """
    idx_char_in_scope = np.isin(char, charset)
    _, dup_counts = np.unique(code[idx_char_in_scope], return_counts=True)
    return dup_counts[dup_counts > 1].sum()

字频加权选重率

字频加权选重率,又可以称为「动态选重率」, 可以表达为:

Nd=iI,jJi/{1}p(zij).
python
def get_dynamic_dup_rate(
    code: npt.NDArray[np.dtype("<U4")],
    freq: npt.NDArray,
    idx_sorted_freq: npt.NDArray[np.dtype("i")],
) -> float:
    """计算字频加权选重率(动态重码率)

    Args:
        code (npt.NDArray[np.dtype): 元素为汉字对应的编码。
            宇浩输入法编码不超过四位,所以编码的格式是 4 个 Unicode 组成的字符串。
        freq (npt.NDArray): 元素为汉字对应的字频。
        idx_sorted_freq (npt.NDArray[np.dtype): 根据字频进行降序排列的索引。
            一般的:idx_sorted_freq = np.argsort(-freq)
            因为这一项操作只需要进行一次,故而不需要放入函数中循环。
    Returns:
        float: 字频加权选重率。
    """
    # 字频降序后的编码和字频列表
    code = code[idx_sorted_freq]
    freq = freq[idx_sorted_freq]
    # 得到第一个非重复的编码的索引
    _, idx_unique_freq = np.unique(code, return_index=True)
    # 生成一个掩码层,将重复的编码筛出
    duplicated_mask = np.full(freq.shape, True)
    duplicated_mask[idx_unique_freq] = False
    # 重复的编码,就是需要选重的字
    # 将这些重复的编码所对应的字频进行求和
    return freq[duplicated_mask].sum()

速度當量

python
def get_equiv_table(file_path: str) -> dict:
    """Read the speed-equivalent table (速度當量表).

    Args:
        file_path (str): 文件位置

    Returns:
        dict (dict[str, float]): 任意兩鍵的速度當量.
    """
    equiv_table = pd.read_csv(file_path)
    equiv_table = equiv_table.loc[equiv_table.loc[:, "equiv"].notna()]
    equiv_table_dict = dict(
        zip(equiv_table.loc[:, "keys"], equiv_table.loc[:, "equiv"])
    )
    return equiv_table_dict


def get_equiv_score(
    data: pd.DataFrame | pl.DataFrame,
    equiv_table: dict,
    freq_col: str,
    code_col: str,
    full_len: int = 4,
) -> float:
    """計算字頻加權速度當量.

    Args:
        data (pd.DataFrame | pl.DataFrame): 數據.
        equiv_table (dict): 當量表(字典格式)
        freq_col (str): 字頻列名
        code_col (str): 編碼列名
        full_len (int, optional): 編碼最大長度. Defaults to 4.

    Returns:
        float: 字頻加權速度當量
    """

    def aux(text: str) -> float:
        twograms: list[str] = []
        left = list("qwertasdfgzxcvb")
        right = list("yuiophjklnm")
        for i in range(len(text) - 1):
            twograms.append(text[i : i + 2])

        score: float = 0
        count: int = 0
        for s in twograms:
            if s in equiv_table.keys():
                count += 1
                score += equiv_table[s]
            elif (s[0] == " ") or (s[1] == " "):
                pass
            else:
                count += 1
                if (s[0] in left) and (s[1] in right):
                    score += 1.1
                elif s[0] == s[1]:
                    score += 1.3
                else:
                    score += 1.5
        return score / count

    if isinstance(data, pd.DataFrame):
        data = data[[freq_col, code_col]].copy()
        data[code_col] = np.where(
            (data[code_col].map(len) < full_len) & (~data[code_col].str.endswith("_")),
            data[code_col] + "_",
            data[code_col],
        )
        data[code_col] = data[code_col].str.lower()

        data["equiv"] = data[code_col].map(aux)
        return (data["equiv"] * data[freq_col]).sum()

    else:
        data = data.with_columns(
            pl.when(
                (pl.col(code_col).str.len_chars() < full_len)
                & (~pl.col(code_col).str.ends_with("_"))
            )
            .then(pl.col(code_col).str.to_lowercase() + "_")
            .otherwise(pl.col(code_col).str.to_lowercase())
            .map_elements(aux, return_dtype=pl.Float64)
            .alias("equiv")
        )
        return float(data.get_column("equiv").dot(data.get_column(freq_col)))

宇浩输入法官网