semchunk源码剖析:merge_splits()如何用二分查找与缓存实现高效分块合并

原创2026-11-03 16:48:181,918 阅读

semchunk源码剖析:merge_splits()如何用二分查找与缓存实现高效分块合并

semchunk 是一个轻量级的 Python 文本分块库,能把长文本递归拆分成语义完整、长度可控的 chunk(用于 RAG、检索增强生成等场景)。它整个算法中最精妙的环节,是"合并阶段"的核心函数 merge_splits()——通过二分查找定位"刚好装得下的最大 chunk 边界",再配合 lru_cache 缓存 token 计数结果,把原本 O(n) 的线性试探降到 O(log n),从而实现了高效分块合并。

为什么"合并"是性能瓶颈

semchunk 的分块流程可以概括为四步:

  1. 拆:按"换行 → 制表符 → 空白 → 句号 → 逗号 → 连字符……"的优先级,用最有结构意义的分隔符把文本切开;
  2. 递归拆:超过 chunk_size 的片段继续递归切分;
  3. 合并:把切得过碎的片段按顺序拼回,直到接近 chunk_size;
  4. 清理:丢弃空块与纯空白块,按需补回非空白分隔符。

瓶颈出现在第 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"是一个单调谓词——前半段"装得下"、后半段"装不下",边界唯一。这正是二分查找的适用场景。

流程拆解为三步:

  1. 估算目标位置:函数初始 average = 0.2(估算每 token 约 5 个字符),用 target = offset + chunk_size * average 在 cum_lens 上 bisect_left,直接跳过大量不可能装得下的片段——这是把"字符空间"换算成"token 空间"的快速逼近;
  2. 实测修正:对候选边界数一次 token,用真实的 local_cum / tokens 比更新 average 并重算 target,让下一次二分的起点更准;
  3. 收敛: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 一节)

总结:可以抄走的三个设计模式

  1. 单调谓词 + 二分查找:只要"加得多就只会更超",就不必线性试探,bisect 在前缀和数组上一步到位;
  2. 前缀和数组:一次 O(n) 构建,换来后续所有区间长度查询 O(1);
  3. 缓存昂贵的成本函数:把 tokenizer 这类慢操作包进 lru_cache,让算法的常数项接近于零。

这三招组合起来,让 semchunk 在保持"语义优先切分"的前提下,把合并阶段的开销压到了日志级别——这也是它月下载量达数百万次仍然轻量快速的底层原因。

登录后查看全文
semchunk