换行计数 · 二分 · monoid

行号索引：按可加权重定位

编辑器同时用两套坐标。文本操作按字符偏移说话，而界面按行列说话：光标在第 12 行第 4 列，视口显示第 300 到第 340 行，跳转到某个函数定义要给出行号。两套坐标的换算关系随每次编辑变化。

本页的问题是：lineStart(k) 给出第 $k$ 行的起始偏移，四种结构各要付多少代价。

1 · 扫一遍是唯一的下界吗

朴素字符串与 gap buffer 里没有任何行的信息。回答 lineStart(k) 只能从头扫，数到第 $k$ 个换行为止。1 MB 文档、39834 行，随机查询平均要扫 513174 个字符。

数组版 piece table 好一点点，但只好在常数上。它的每个 piece 记着自己内部有几个换行，于是可以按 piece 跳过：累加各 piece 的换行数，直到目标行落在某个 piece 里。可是 piece 内部仍然只能扫。刚打开的文件只有一个 piece，覆盖全文，「按 piece 跳过」什么也没跳过——实测每次查询仍是 513174 个字符，与朴素字符串一字不差。

这个结果推翻了本系列最初的设计。原以为在 piece 上记一个换行计数就够了，实测发现它只在文档已经碎成很多 piece 时才起作用，而那恰好是最不需要它的时候（piece 越碎，每个 piece 越短，扫起来本来就便宜）。真正的答案要分两层。

2 · 第一层：结点上的换行计数

把 piece 挂上树之后，每个结点已经存了子树的字符总数。再存一个子树的换行总数，按行定位就与按字符定位是同一套下降：

按字符：若 $i <$ 左子树字符数，往左；否则减去它，看是否落在本结点的叶子里。

按行：若 $k \le$ 左子树换行数，往左；否则减去它，看第 $k$ 个换行是否落在本结点的叶子里。

两段代码的形状完全一样，换的只是权重字段。

图 2-1 · 同一棵树上按字符与按行两种下降的路径对照。可切换查询类型与目标值，观察两条路径在同一棵树上走向不同的叶子。

rope 的叶子最长 64 个字符，走到叶子后再扫一遍就到头了，实测每次查询访问 18.8 个结点、扫 31 个字符。这一层对 rope 已经够用。

3 · 第二层：缓冲区的换行位置表

piece tree 的叶子不是这么回事。一个 piece 可以覆盖整个 original 缓冲，走到它跟前仍然要扫 100 万个字符。

补法是给每个缓冲单独建一张换行位置表：original 的表在打开文件时一次扫出，added 的表在每次追加时增量维护。要找某个 piece 内部的第 $j$ 个换行，先在表上二分出这个 piece 起始偏移对应的下标，再往后数 $j$ 个。

补上这张表之后，piece tree 的 lineStart 一个字符也不扫。这也是 VS Code 的做法：换行位置表建在缓冲上而不是 piece 上，因为缓冲不变而 piece 天天在拆。

图 3-1 · 五种实现回答行号查询的代价对照。可切换文档规模与是否先跑一轮随机编辑，观察数组版 piece table 在碎片化后从扫字符转为扫 piece。

1 MB 的全新文档、200 次随机行号查询，五者的账是：

实现	每次访问结点	每次扫读字符
朴素字符串	0	513174
gap buffer	0	513174
数组版 piece table	1.0	513174
piece tree	16.9	0
rope	18.8	31

把文档换成 10 万字符并先跑 2000 次随机编辑，账的形状变了但结论不变：

实现	每次访问结点	每次扫读字符
朴素字符串	0	49066
gap buffer	0	49066
数组版 piece table	1618.6	45.7
piece tree	26.0	0
rope	17.6	20.1

数组版 piece table 的代价从「扫 5 万个字符」变成「扫 1619 个 piece」。碎片化把它的扫读量降下来了，同时把它的 piece 遍历量抬上去，两笔账加起来并没有变便宜。

4 · 可加权重的推广

换行计数没有任何特殊之处。它能挂上树，只因为它满足一条性质：整体的值等于左右两半的值相加，且这个加法有结合律与单位元。

定义 4.1（可加权重） 设每个叶子 $x$ 带一个值 $w(x)$ ，内部结点的值定义为左右子树值与自身叶子值之和。若 $w$ 的取值构成一个 monoid（结合律 + 单位元），则「找出使前缀和首次达到 $t$ 的位置」可以在树上一次下降完成，代价与树深同阶。

字符数与换行数都是最简单的那种 monoid：非负整数与加法。换上别的权重，同一棵树立刻能回答别的问题：

权重取「显示宽度」（全角 2、半角 1、制表符对齐到 4 的倍数），下降就回答「第 $c$ 列在哪个字符上」。这正是终端与等宽编辑器需要的坐标。
权重取「grapheme cluster 数」，下降就回答用户眼里的第几个字符在哪。
权重取「是否含未闭合的块注释」这类布尔量的或运算，下降就能跳过整块无需重新分词的子树。xi-editor 的增量语法高亮走的就是这条路。

这与区间查询 · 在数组上反复「问一段、改一点」里的思路是同一件事的两种形态：前缀和数组回答「区间和是多少」，而本页回答的是它的反问题「前缀和达到 $t$ 的位置在哪」。线段树上的二分下降与本页的按行下降，是同一段代码。树本身的平衡性质则见树 · 遍历、平衡 BST 与前缀 / 度量树。

警示 · 可加只是必要条件，不是充分条件。权重必须只依赖叶子自身，否则拆开叶子时无法重算。「显示宽度」在有制表符时就不满足这一条：制表符的宽度取决于它前面已经占了几列，拆开一个叶子后左半的宽度不再能独立算出。真实实现的做法是把制表符前的列数一并作为权重的一部分，让 monoid 的元素变成一个二元组。

5 · 参考文献

Levien, R. Rope science, part 4: parenthesis matching 与 part 5: incremental computation. xi-editor documentation.
Microsoft. (2018). Text buffer reimplementation. VS Code Blog, 2018-03-23. 其中「Faster line lookup」一节记录了换行位置表的设计。
Hinze, R., & Paterson, R. (2006). Finger trees: a simple general-purpose data structure. Journal of Functional Programming, 16(2), 197–217. monoid 作为结点权重的一般化处理。
Boehm, H.-J., Atkinson, R., & Plass, M. (1995). Ropes: an alternative to strings. Software: Practice and Experience, 25(12), 1315–1330.