Ulm 分词算法（通常指 ULM, Unsupervised Language Modeling 分词，或与 SentencePiece 中的 Unigram 语言模型算法高度相关）是一种基于统计概率的子词（Subword）分词算法。

与传统的结巴分词（基于词典）或简单的 BPE（基于频次合并）不同，ULM 的核心逻辑是：从一个巨大的候选词表出发，通过概率模型不断“剔除”对整体语言模型贡献度低的词，直到达到目标词表大小。

1. 原理详解

ULM 算法建立在假设：一个句子 $S$ 的分词序列 $x = (x_1, x_2, …, x_n)$ 的概率等于各子词概率的乘积：

$$
P(x) = \prod_{i=1}^{n} P(x_i)
$$

核心步骤：

初始化：生成一个非常大的初始词表（例如：所有出现的字符 + 频繁出现的子串）。
期望最大化 (EM 训练)：
- E-Step：在当前词表下，利用维特比算法 (Viterbi) 找到语料库中最优的分词路径。
- M-Step：根据分词结果更新词表中每个词的出现概率 $P(x_i)$。
计算损失 (Loss)：计算如果删除某个词，语料库整体的似然值 (Likelihood) 会下降多少。
剪枝：剔除损失最小（即”最没用”）的前 10%~20% 的词。
循环：重复上述过程，直到词表缩减到预设的大小。

与 BPE 的核心区别

特性	BPE	Unigram LM
训练方向	自底向上（从小到大合并）	自顶向下（从大到小剪枝）
优化目标	频次统计	最大化语料似然值
词表选择	贪婪合并最高频对	概率模型最优路径
未知词处理	继续拆分为子词	拆分为字符序列

2. 算法流程详解

2.1 初始词表构建

初始词表通常包含：

所有出现的字符
所有出现的子串（通过 substring 提取）
预设的最长子词长度（如 16 个字符）

# 伪代码示例
def build_initial_vocab(corpus, max_subword_length=16):
    vocab = set()
    for sentence in corpus:
        for length in range(1, max_subword_length + 1):
            for i in range(len(sentence) - length + 1):
                vocab.add(sentence[i:i+length])
    return list(vocab)

2.2 EM 训练过程

E-Step（期望步）：给定当前词表和每个词的概率，找到最优分词。

使用维特比算法找到使 $P(x)$ 最大的分词路径：

def viterbi_segment(sentence, vocab_probs):
    “””找到概率最大的分词方式”””
    n = len(sentence)
    dp = [0] * (n + 1)
    backpointer = [0] * (n + 1)
    dp[0] = 1.0  # 空序列概率为1

    for i in range(1, n + 1):
        for j in range(max(0, i - max_len), i):
            word = sentence[j:i]
            if word in vocab_probs:
                prob = dp[j] * vocab_probs[word]
                if prob > dp[i]:
                    dp[i] = prob
                    backpointer[i] = j

    # 回溯得到分词结果
    segments = []
    pos = n
    while pos > 0:
        prev = backpointer[pos]
        segments.append(sentence[prev:pos])
        pos = prev

    return list(reversed(segments))

M-Step（最大化步）：更新每个词的概率。

$$P(w) = \frac{\text{count}(w)}{\sum_{w’ \in V} \text{count}(w’)}$$

2.3 剪枝策略

计算删除每个词对整体似然的影响：

$$\text{Loss}(w) = \sum_{s \in \text{corpus}} \log P(s \mid V \setminus {w}) - \log P(s \mid V)$$

删除 Loss 增加最小的词（即删除后影响最小的词）。

3. 代码实现（使用 SentencePiece）

SentencePiece 是实现 Unigram LM 最常用的库：

import sentencepiece as spm

# 训练 Unigram 模型
spm.SentencePieceTrainer.train(
    input='corpus.txt',
    model_prefix='unigram_model',
    vocab_size=10000,
    model_type='unigram',  # 关键参数
    character_coverage=0.995,
    max_sentence_length=2048,
)

# 加载并使用模型
sp = spm.SentencePieceProcessor()
sp.load('unigram_model.model')

# 编码（分词）
text = “这是一个示例句子”
pieces = sp.encode(text, out_type=str)
print(pieces)  # ['▁这是', '一个', '示例', '句子']

# 解码
decoded = sp.decode(pieces)
print(decoded)  # “这是一个示例句子”

# 获取词表
vocab = {sp.id_to_piece(i): sp.get_score(i) for i in range(sp.get_piece_size())}

关键参数说明

参数	说明	推荐值
`model_type`	模型类型	`'unigram'`
`vocab_size`	目标词表大小	10,000 - 100,000
`character_coverage`	字符覆盖率	0.995 - 0.999
`max_sentence_length`	最大句子长度	2048 - 8192
`shrinking_factor`	每次剪枝比例	0.75（剪枝 25%）

4. 优缺点分析

✅ 优点

基于概率模型：使用似然值优化，理论上更合理
灵活的分词：同一句子可以根据上下文选择不同分词方式
适合多语言：不依赖空格分词，适合中文、日文等语言
子词共享：通过子词分解有效处理 OOV（Out of Vocabulary）问题

❌ 缺点

训练复杂度高：需要多次 EM 迭代，训练时间较长
内存占用大：初始词表可能非常大（百万级别）
超参数敏感：剪枝比例、词表大小等参数需要调优
不如 BPE 流行：社区支持和工具链相对较少

5. 应用场景

5.1 大型语言模型

Unigram LM 曾被以下模型使用：

T5 (Text-to-Text Transfer Transformer)：使用 SentencePiece 的 Unigram 模型
ALBERT：早期版本使用过 Unigram 分词
mT5：多语言 T5 模型

5.2 多语言场景

对于中文、日文等没有明确词边界的语言，Unigram LM 表现优异：

# 中文示例
sp.encode_as_pieces(“我爱自然语言处理”)
# ['▁我', '爱', '自然', '语言', '处理']

# 日文示例
sp.encode_as_pieces(“私は自然言語処理が好きです”)
# ['▁私', 'は', '自然', '言語', '処理', 'が', '好き', 'です']

5.3 低资源语言

Unigram LM 可以从较小的语料中学习有效的子词分解。

6. 与其他分词算法对比

6.1 BPE (Byte Pair Encoding)

1 2	# BPE 示例 “BPE” -> [“B”, “P”, “E”] -> [“BP”, “E”] -> [“BPE”]

合并策略：总是合并最高频的字符对
确定性：相同输入产生相同输出
适用：GPT-2, RoBERTa, GPT-3

6.2 WordPiece

训练目标：最大化训练数据的似然值
选择策略：选择使似然值增加最大的合并
适用：BERT, DistilBERT

6.3 Unigram LM

剪枝策略：从大词表中逐步删除低概率词
分词灵活性：可以有多种分词方式
适用：T5, mT5

7. 实践建议

7.1 词表大小选择

任务	推荐词表大小
小型数据集	5,000 - 10,000
中型数据集	10,000 - 30,000
大型数据集	30,000 - 100,000
多语言	50,000 - 250,000

7.2 训练数据准备

# 合并多个文本文件
cat *.txt > corpus.txt

# 清洗数据
# - 去除特殊字符
# - 统一换行符
# - 去除空白行

7.3 调优技巧

调整 shrinking_factor：控制剪枝速度
使用 character_coverage：平衡字符覆盖率和词表大小
设置 user_defined_symbols：添加特殊token（如 <mask>, <unk>）
控制 max_sentence_length：防止内存溢出

8. 总结

Unigram Language Model 是一种基于概率模型的子词分词算法：

核心思想：从大词表开始，通过剪枝优化到目标大小
数学基础：EM 算法 + 维特比解码
主要优势：灵活的分词、适合多语言
应用场景：T5 等模型、多语言 NLP

尽管目前 BPE 更为流行，但 Unigram LM 在特定场景（如多语言、需要灵活分词的任务）中仍然具有价值。

Unigram Language Model (ULM)