smart-dict

基于词典的中文分词及反查整句最短编码算法的Rust实现。

功能描述

1. 初始化导入：若干存储着从编码到词组的多对多映射关系的输入法词典（该算法库支持Rime输入法平台词典的直接导入，词典具体格式见https://github.com/rime/home/wiki/UserGuide#%E5%B0%8E%E5%87%BA%E5%8F%8A%E5%B0%8E%E5%85%A5%E6%96%87%E6%9C%AC%E7%A2%BC%E8%A1%A8）
2. 输入：由若干词组组成的整句。
3. 输出：根据所导入的词典，对于输入的整句，有着最短总码长的词组序列。

示例

导入中文输入方案"星空键道6"的词典，包含如下条目：

编码	词组
w	我
wi	我们
e	是
ekfw	是非
jpi	常
fio	非常
fwjp	非常
xa	喜欢
xhn	喜欢你
xhni	瞎胡闹
n	你
d	的
nui	你的
,	，
.	。

由以上词典构建反查表rev_dict之后，运行算法：

assert_eq!(
  vec!["w", " e", " fio", "xa", "nui", "."],
  rev_dict.shortest("我是非常喜欢你的。").unwrap()
);

则对于输入的整句"我是非常喜欢你的。"，shortest返回该句最短编码为"w e fioxanui."，码长为13，同时由返回值得分词结果为"我/是/非常/喜欢/你的/。"。 考虑另一种可能的分词方式"我/是非/常/喜欢你/的/。"，由反查表得该句编码为"w ekfwjpixhn d."，码长为15。

数据结构

• 字典树（Trie），树结点的子树列表采用HashMap存储。
• 反查表（RevDict）：在一个字典树中，从词组到其最短编码的映射。

算法设计

动态规划，记所输入的整句为sentence，则总码长的状态转移方程为dp[i] = min { dp[j] + rev_dict.get(sentence[j..i]).length } for 0 <= j < i，其中1 < i <= sentence.length，初始码长dp[0] = 0，返回dp[sentence.length]。

阐释：对于sentence，考虑其各前缀子句，如“你好吗”的前缀子句有“”、“你”、“你好”、“你好吗”，从dp数组中取得各前缀子句的最短码长，将除去前缀子句的sentence的剩余部分视作一个可能存在的词组，尝试从反查表中取得该词组的编码，若：

1. 不能取得，则忽略这个前缀子句并抛弃这个可能的词组；
2. 能取得，则将该词组的编码长度与前缀子句的最短码长相加。

这些加和值的最小值即为所求。