May 23, 2025 在上一篇 比 tiktoken 还快？BPE 分词优化小结 中提到，我们假设 Pre-Tokenizer 后的子串都是比较短的，所以类似于 tiktoken 中的实现，我们只用了 vector 遍历的方式来实现 bpe 分词（详见源码~/src/tokenizer/BPE.cpp#L157），即使改成链表，时间复杂度仍然是 O(nm) 的，通常 m(merge次数) 与 n(字符串长度) 接近，所以也可以看作是 O(n^2) ，这在 n 较小的情况下问题不大，但如果 n 很大呢？我们用 tiktoken 实测一下： tiktoken_enc = tiktoken.Encoding(…) start = time.perf_counter_ns() tiktoken_enc.encode("a" * 102400) end = time.perf_counter_ns() cost = (end – start) / 1e6 print(f"{cost:.3f} ms") 5182 ms 也就是说一个Continue reading “BPE 分词超长 token 优化”