宇浩输入法开发技术文档
宇浩输入法开发非一日之功,使用了很多 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》)。速度当量是关于「手感」的最宏观、量化的指标,是由大量实验得出的结果,具有很高的参考价值。这个指标越小,表明输入的速度越快。宇浩输入法在优化过程中,最小化字频加权速度当量。
算法代码
以下为「宇浩算法」伪代码,谨供参考。
# 「宇浩算法」僞代碼
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 编写,对于向量计算有着高度的优化。这篇文章中,我也会讨论某些代码为什么要这样写。
字集静态重码数
单字的静态重码,指的是在一个字符集中,编码完全相同的汉字的个数。 假设
那么,静态重码数可以表达为:
对于此指标的计算,较为简单。但为了运行的效率考虑,我们可以使用 numpy 包。
import numpy as np
import typing
import numpy.typing as npt
本文其他代码都使用以上引用。
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()
字频加权选重率
字频加权选重率,又可以称为「动态选重率」, 可以表达为:
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()
速度當量
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)))