基于词典的中文分词及反查整句最短编码算法的Rust实现。
- 初始化导入：若干存储着从编码到词组的多对多映射关系的输入法词典（该算法库支持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）
- 输入：由若干词组组成的整句。
- 输出：根据所导入的词典，对于输入的整句，有着最短总码长的词组序列。
导入中文输入方案"星空键道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的剩余部分视作一个可能存在的词组，尝试从反查表中取得该词组的编码，若：
- 不能取得，则忽略这个前缀子句并抛弃这个可能的词组；
- 能取得，则将该词组的编码长度与前缀子句的最短码长相加。
这些加和值的最小值即为所求。