tokenizer_rs

尝试用 rust 复现一个类似 jieba 的分词功能

---

jieba

$jieba$ 分词的主体是一个 $dp$ 。
对于待分割字符串 $S[0..n - 1]$ ，连接有向边 $(i, j, \frac{W}{WTotal})$ ， $W$ 为子串 $S[i..j - 1]$ 在所收集词库中出现的词频， $WTotal$ 为所有子串的词频总和，这样得到一张有向图 $dag$ 。
最终目的为找到 $dag$ 上一条 $0 \rightarrow n$ 的路径使得路径权重最大，这里的路径权重含义为以该路径切分字符串的概率大小。

$dag$ 上具体转移方程如下，定义 $f[i]$ 为 $i \rightarrow n$ 的最大切分路径概率：

$$\begin{cases} f[i] = \max (f[i + k] * \frac{W(i..k)}{Wtotal})\\ f[n] = 1\\ \end{cases}$$

为了减小浮点数精度的影响，对方程取对数 $ln$ ：

$$\begin{cases} g[i] = ln(f[i])\\ g[i] = \max (ln(f[i + k]) + ln(W(i..k)) - ln(Wtotal))\\ g[n + 1] = 0 \end{cases}$$

转移中记录路径，最后从 $0$ 开始回溯即可找出切分方法。

hmm

$TODO$