分词器对比2026：BPE/SentencePiece/Unigram

def train_bpe(texts, vocab_size=32000):
    """BPE训练算法"""
    # 1. 将文本拆分为字符序列
    word_freqs = {}
    for text in texts:
        words = text.split()
        for word in words:
            chars = tuple(word)
            word_freqs[chars] = word_freqs.get(chars, 0) + 1
    
    # 2. 初始化词表为所有字符
    vocab = set()
    for word in word_freqs:
        for char in word:
            vocab.add(char)
    
    # 3. 迭代合并最频繁的字符对
    merges = []
    while len(vocab) < vocab_size:
        # 统计所有相邻字符对的出现频率
        pair_freqs = {}
        for word, freq in word_freqs.items():
            for i in range(len(word) - 1):
                pair = (word[i], word[i+1])
                pair_freqs[pair] = pair_freqs.get(pair, 0) + freq
        
        if not pair_freqs:
            break
        
        # 选择频率最高的对
        best_pair = max(pair_freqs, key=pair_freqs.get)
        new_token = best_pair[0] + best_pair[1]
        
        # 合并
        merges.append(best_pair)
        vocab.add(new_token)
        
        # 更新词频
        new_word_freqs = {}
        for word, freq in word_freqs.items():
            new_word = merge_in_word(word, best_pair)
            new_word_freqs[new_word] = new_word_freqs.get(new_word, 0) + freq
        word_freqs = new_word_freqs
    
    return vocab, merges

def bpe_encode(text, merges, special_tokens):
    """BPE编码"""
    tokens = []
    
    for word in text.split():
        # 先检查是否是特殊token
        if word in special_tokens:
            tokens.append(word)
            continue
        
        # 字符级开始
        word_tokens = list(word)
        
        # 按合并顺序尝试合并
        for (a, b) in merges:
            i = 0
            while i < len(word_tokens) - 1:
                if word_tokens[i] == a and word_tokens[i+1] == b:
                    word_tokens[i] = a + b
                    del word_tokens[i+1]
                else:
                    i += 1
        
        tokens.extend(word_tokens)
    
    return tokens

def byte_level_bpe_encode(text):
    """Byte-level BPE"""
    # 将文本编码为UTF-8字节
    byte_seq = text.encode('utf-8')
    
    # 将每个字节映射到Unicode字符（避免控制字符冲突）
    mapped = ''.join(byte_to_unicode[b] for b in byte_seq)
    
    # 在映射后的字符序列上应用BPE
    return bpe_encode(mapped)

def wordpiece_score(pair, pair_freq, char1_freq, char2_freq, total_freq):
    """WordPiece合并分数：互信息"""
    return pair_freq / (char1_freq * char2_freq)

def wordpiece_encode(word, vocab, max_chars=100):
    """WordPiece编码：贪心最长匹配"""
    if len(word) > max_chars:
        return ['[UNK]']
    
    tokens = []
    start = 0
    
    while start < len(word):
        end = len(word)
        cur_substr = None
        
        # 从最长到最短尝试匹配
        while start < end:
            substr = word[start:end]
            if start > 0:
                substr = '##' + substr  # 非首字符加##前缀
            if substr in vocab:
                cur_substr = substr
                break
            end -= 1
        
        if cur_substr is None:
            return ['[UNK]']
        
        tokens.append(cur_substr)
        start = end
    
    return tokens

def train_unigram(texts, vocab_size=32000, initial_factor=100):
    """Unigram训练算法"""
    # 1. 构建初始大词表（所有可能的子串）
    substrings = {}
    for text in texts:
        for word in text.split():
            for i in range(len(word)):
                for j in range(i+1, len(word)+1):
                    substr = word[i:j]
                    substrings[substr] = substrings.get(substr, 0) + 1
    
    # 2. 保留频率最高的子串作为初始词表
    vocab = sorted(substrings.items(), key=lambda x: -x[1])
    vocab = [item[0] for item in vocab[:vocab_size * initial_factor]]
    
    # 3. 迭代删除对似然贡献最小的子词
    while len(vocab) > vocab_size:
        # 计算当前词表的对数似然
        base_likelihood = compute_likelihood(texts, vocab)
        
        # 尝试删除每个子词，计算似然下降
        deltas = []
        for i, token in enumerate(vocab):
            reduced_vocab = vocab[:i] + vocab[i+1:]
            new_likelihood = compute_likelihood(texts, reduced_vocab)
            delta = base_likelihood - new_likelihood
            deltas.append((i, delta))
        
        # 删除似然下降最小的子词（按比例删除，而非逐个）
        deltas.sort(key=lambda x: x[1])
        n_remove = max(1, len(vocab) // 10)  # 每轮删除10%
        
        remove_indices = set(idx for idx, _ in deltas[:n_remove])
        vocab = [t for i, t in enumerate(vocab) if i not in remove_indices]
    
    return vocab

def unigram_encode(word, vocab, vocab_probs):
    """Unigram编码：维特比最优分词"""
    n = len(word)
    
    # dp[i] = (对数概率, 前驱位置, token)
    dp = [(-float('inf'), -1, None) for _ in range(n + 1)]
    dp[0] = (0, -1, None)
    
    for end in range(1, n + 1):
        for start in range(end):
            substr = word[start:end]
            if substr in vocab_probs:
                prob = vocab_probs[substr]
                score = dp[start][0] + math.log(prob)
                if score > dp[end][0]:
                    dp[end] = (score, start, substr)
    
    # 回溯获取最优分词
    tokens = []
    pos = n
    while pos > 0:
        _, prev_pos, token = dp[pos]
        tokens.append(token)
        pos = prev_pos
    
    return list(reversed(tokens))

# SentencePiece将空格替换为特殊字符▁（U+2581）
# "Hello world" → "▁Hello▁world"

# 这意味着：
# 1. 不依赖预分词（空格切分）
# 2. 编码-解码完全可逆
# 3. 语言无关（中日韩等无空格语言同样处理）

import sentencepiece as spm

spm.SentencePieceTrainer.train(
    input='corpus.txt',
    model_prefix='llama_tokenizer',
    vocab_size=32000,
    model_type='bpe',        # 使用BPE算法
    character_coverage=0.9998,
    byte_fallback=True,      # 字节回退
    normalization_rule_name='identity',  # 不做归一化
)

spm.SentencePieceTrainer.train(
    input='corpus.txt',
    model_prefix='t5_tokenizer',
    vocab_size=32000,
    model_type='unigram',    # 使用Unigram算法
    character_coverage=0.99995,
    byte_fallback=True,
)