semchunk源码剖析:merge_splits()如何用二分查找与缓存实现高效分块合并
semchunk源码剖析:merge_splits()如何用二分查找与缓存实现高效分块合并
semchunk 是一个轻量级的 Python 文本分块库,能把长文本递归拆分成语义完整、长度可控的 chunk(用于 RAG、检索增强生成等场景)。它整个算法中最精妙的环节,是"合并阶段"的核心函数 merge_splits()——通过二分查找定位"刚好装得下的最大 chunk 边界",再配合 lru_cache 缓存 token 计数结果,把原本 O(n) 的线性试探降到 O(log n),从而实现了高效分块合并。
为什么"合并"是性能瓶颈
semchunk 的分块流程可以概括为四步:
- 拆:按"换行 → 制表符 → 空白 → 句号 → 逗号 → 连字符……"的优先级,用最有结构意义的分隔符把文本切开;
- 递归拆:超过
chunk_size的片段继续递归切分; - 合并:把切得过碎的片段按顺序拼回,直到接近
chunk_size; - 清理:丢弃空块与纯空白块,按需补回非空白分隔符。
瓶颈出现在第 3 步。判断"能不能再塞进一个片段"必须调用 tokenizer 数 token,而 token 计数是整个流程里最贵的操作。如果朴素地逐个片段线性试探,每个 chunk 都要重复数很多次,成本会线性放大。
semchunk 的解法只有两个关键词:二分查找 + 缓存。
merge_splits() 的 8 个参数一览
函数定义位于 src/semchunk/semchunk.py#L142-L179:
| 参数 | 含义 |
|---|---|
text |
原始完整文本(最终切片直接来自它) |
split_starts |
每个片段(split)在原文中的起始偏移 |
splitter_len |
当前使用的分隔符长度 |
cum_lens |
片段起始偏移的前缀和数组,是二分查找的搜索空间 |
chunk_size |
单个 chunk 允许的最大 token 数 |
token_counter |
数 token 的函数(已被缓存包装) |
start / high |
本次合并的搜索区间 [start, high) |
其中 cum_lens 来自 semchunk.py#L515 的一行代码:
local_split_starts = list(accumulate([len(split) + splitter_len for split in splits], initial=0))
它用 itertools.accumulate 一次遍历算出"每个片段从原文哪个位置开始"。前缀和让"从第 i 个片段到第 j 个片段共多少字符"变成一次减法——这正是后面二分查找能成立的地基。
二分查找核心:定位"刚好装得下的最大 chunk"
merge_splits() 的主循环只有十几行(semchunk.py#L160-L176):
while low < high:
i = bisect_left(cum_lens, target, lo=low, hi=high)
midpoint = min(i, high - 1)
tokens = token_counter(text[split_starts[start] : split_starts[midpoint] - splitter_len])
local_cum = cum_lens[midpoint] - offset
if local_cum and tokens > 0:
average = local_cum / tokens # 用实测值修正估算
target = offset + (chunk_size * average)
if tokens > chunk_size:
high = midpoint # 太大了,往左收
else:
low = midpoint + 1 # 装得下,再试试更多
它为什么能二分?关键在单调性:合并区间从 start 向右扩展时,字符数和 token 数都只增不减,因此"是否超过 chunk_size"是一个单调谓词——前半段"装得下"、后半段"装不下",边界唯一。这正是二分查找的适用场景。
流程拆解为三步:
- 估算目标位置:函数初始
average = 0.2(估算每 token 约 5 个字符),用target = offset + chunk_size * average在cum_lens上bisect_left,直接跳过大量不可能装得下的片段——这是把"字符空间"换算成"token 空间"的快速逼近; - 实测修正:对候选边界数一次 token,用真实的
local_cum / tokens比更新average并重算target,让下一次二分的起点更准; - 收敛:token 超标就把
high收到midpoint,否则把low推到midpoint + 1。循环结束时end = low - 1就是不超限的最大合并终点,直接切片原文即可取出合并后的 chunk(semchunk.py#L178-L179)。
注意一个细节:候选文本是通过 text<a href="https://link.gitcode.com/i/b2fe79b72f0ec475a1d54cc66feceb5f" target="_blank">split_starts[start] : split_starts[midpoint] - splitter_len] 直接从原文索引取出的,而不是把片段逐个 join 起来——CHANGELOG 里明确记录,这个改动消除了 merge_splits() 曾有的最大瓶颈(见 [CHANGELOG.md 4.0.0 条目),同时 bisect_left 也替换了更慢的自定义二分实现。
缓存核心:让 token_counter 变"免费"
二分查找每次迭代都要数 token,如果每次都真实分词,缓存的省幅会打折扣。semchunk 在入口处就解决了这个问题:
- 全局注册表 + lru_cache:模块级字典
_memoized_token_counters(semchunk.py#L35-L36)把每个token_counter与其缓存版本一一绑定。首次调用chunk()或chunkerify()时执行setdefault(token_counter, lru_cache(cache_maxsize)(token_counter))(semchunk.py#L231-L232、semchunk.py#L920-L921),同一 tokenizer 的缓存在整个进程生命周期内共享。 - 长文本短路:若能从词表推断出最长 token 长度,
faster_token_counter会先用chunk_size * 6字符的启发式前缀试数——若前缀已超标,直接返回chunk_size + 1,完全跳过对超长文本的真实分词(semchunk.py#L909-L917)。 - 可控容量:
chunkerify()的cache_maxsize参数决定lru_cache上限,默认None即无界缓存;不想吃内存可以传memoize=False关闭。
于是二分查找中反复数同一区间时,第二次起全部命中缓存。二分贡献 O(log n) 的次数,缓存贡献 O(1) 的命中代价,两者相乘才是"高效分块合并"的完整答案。
一个最小合并流程走查 🕹️
以字符数计数、chunk_size = 4 的测试输入 ThisIs\tATest. 为例(见 tests/test_semchunk.py#L25-L38):
- 制表符是最高优先级分隔符,文本被切成
ThisIs和ATest.两个 split,local_split_starts前缀和为[0, 6, 13]; merge_splits()从start=0出发,二分判定ThisIs(6 token)已超 4,合并块止步于第 0 个 split,得到This;- 外层
chunk()把i直接跳到next_i,已合并进 chunk 的 split 永远不会被再访问——这是 4.1.1 版本引入的另一处加速("直接从一个 chunk 的起点跳到下一个")。
最终输出 ['This', 'Is', 'ATes', 't.'],与测试断言完全一致。
相关文件与延伸阅读
| 文件 | 看点 |
|---|---|
| src/semchunk/semchunk.py#L142-L179 | merge_splits() 完整实现 |
| src/semchunk/semchunk.py#L511-L582 | 外层主循环:切分、递归、调 merge_splits()、补回分隔符 |
| src/semchunk/semchunk.py#L88-L139 | _split_text():分隔符优先级策略 |
| tests/test_semchunk.py | 确定性输出、offsets、多进程、overlap 的完整断言 |
| tests/bench.py | 基于 Gutenberg 语料的基准对比脚本 |
| README.md | 算法总览(How It Works 一节) |
总结:可以抄走的三个设计模式
- 单调谓词 + 二分查找:只要"加得多就只会更超",就不必线性试探,
bisect在前缀和数组上一步到位; - 前缀和数组:一次 O(n) 构建,换来后续所有区间长度查询 O(1);
- 缓存昂贵的成本函数:把 tokenizer 这类慢操作包进
lru_cache,让算法的常数项接近于零。
这三招组合起来,让 semchunk 在保持"语义优先切分"的前提下,把合并阶段的开销压到了日志级别——这也是它月下载量达数百万次仍然轻量快速的底层原因。