Piece Table - 文本编辑器中被埋没的史诗算法

红龙图压镇，ACM算法日常中带有龙图片的算法文章

在文本编辑器算法中，以高性能和高可用著称的piece table算是一个被埋没的数据结构。Visual Studio Code采用了该算法，MS Word也采用了该算法。

即使很多现代化的编辑器采用了该算法，但是与之相关的文档却很少。本篇文章中，我将会解释piece table是如何工作的，以及如何让该算法为你的编辑器所使用。

我尽可能让这篇文章对新手友好，每个概念会比较慢的讲解，在开始前，需要你对数组、字符串、数据结构有比较好的理解。

当你打开一个文本文件时，首先从磁盘加载数据，这些数据会被保存在内存的数据结构中。假如是你来写这个文本编辑器，你会使用什么数据结构来表示这个文件呢？

第一直觉 - 一个字符串数组

我们的第一直觉可能是用一个字符串数组来表示，每个字符串是文件中的一行文本，比如如下文件：

the quick brown fox
jumped over the lazy dog

如下：

lines = [
    "the quick brown fox",       # line 1 of the file
    "jumped over the lazy dog",  # line 2 of the file
]

这是比较简单的一个文本文件在内存中的存储方式（可能有些童鞋会直接使用一个字符串，更简单粗暴），这种方式比较像我们看到文本在屏幕上展示的样子。

这是一个能够接受的处理方式，你会说这种直观的表示不会有太大问题。事实上，Visual Studio Code采用了类似的方法来处理文本内存存储，一直到2018年才开始采用piece table。

不幸的是，这种直观的表达方式在处理大型文本的时候会比较吃力，为什么呢？假如有人在一个大文本的中间插入一行。

the quick brown fox
went to the park and
jumped over the lazy dog

为了能够给新行腾出位置，新行下面所有的行都必须下移一个位置，对于大文本来说会很慢。

这只是这种方法的一点不足。在VSC开发团队博客中，他们指出其他一些严重问题，比如内存占用非常夸张以及在将文本中插入换行符卡顿的性能问题。

一种append-only的处理方式

如果我们只是将文本append到一个数组中，那么我们就不需要shift任何数据了，也就不会出现在中间插入的性能问题。append的复杂的是，而insert的复杂的是。

不管是新编辑器还是以前的旧编辑器，piece table都是最为强大的数据结构。最大的特点就是piece table将所有的文本插入操作转换为了append的操作。

让我们看看piece table是如何工作的。

最初，我们从磁盘读取数据交给piece table，piece table会将该文本记录为一个常量字符串S，我们称S为original buffer。

piece_table = {
    "original": "the quick brown fox\njumped over the lazy dog",
    ...
}

当我们插入文本的时候，文本是被append到piece table的add buffer中的，add buffer初始化为空字符串。

不管是在文本的开始位置插入，还是在中间位置插入，还是在末尾插入，都是将插入文本放到add buffer中。piece table由2个buffer组成，add buffer是另外一个buffer，这个buffer是append-only的。

{
    "original": "the quick brown fox\njumped over the lazy dog",
    "add": "",
  ...
}

通过这种方式，我们记录了用户插入到文本中的所有字符，避免了在中间插入文本的问题。

打开文本后，在中间插入一行文本，piece table的结构如下：

{
    "original": "the quick brown fox\njumped over the lazy dog",
    "add": "went to the park and\n",
  ...
}

我们插入的文本在add buffer中，original buffer不变（常量）。

这2个字符串buffer，original和add，包含了文本编辑器里面所有的字符，也包括历史中（从打开文本文件开始算）所有的文本。

编辑器显示文本，是将这2个buffer中的不同区域进行组合来显示的，而buffer中的某些区域会别忽略掉，比如用户删除了一些文本，这些文本就不会被显示。

如下图中，中间区域的文本来自于add buffer，这段文本是插入的，其他位置的文本字符来自于original buffer。

现在，编辑器知道了用户插入的字符串，但是不知道是在哪里插入的，piece table还没有足够的信息来显示文本内容，因此我们还需要一个用来记录位置的成员变量。

Piece descriptors

为了知道用户在哪里输入的文本，piece table需要记录哪个区域是从original buffer来的，哪些是从add buffer来的。需要遍历piece descriptors，一个piece descriptor包含3个字段：

source：属于哪个buffer

start：buffer中的开始位置

length：有多少个字符

当我们第一次打开文本编辑器时，只有original buffer有内容，只有一个piece descriptor。add buffer是空的，如下所示。

{
    "original": "the quick brown fox\njumped over the lazy dog",
    "add": "",
  "pieces": [Piece(start=0, length=44, source="original")],
}

插入文本

现在我们添加一段文本到中间，更新后的数据结构如下图所示：

{
    "original": "the quick brown fox\njumped over the lazy dog",
      "add": "went to the park and\n",
    "pieces": [
      Piece(start=0, length=20, source="original"),
      Piece(start=0, length=21, source="add"),
      Piece(start=20, length=24, source="original"),
    ],
}

插入的文本放在add buffer中，之前只有一个piece，现在有3个。

第1个piece告诉我们original中的前20个字符是我们文本中的第一个部分。

第2个piece告诉我们接下来文本中的21个字符来自于add buffer，从位置0开始。

第3个piece告诉我们文本的最后24个字符来自于origina buffer。

向编辑器中插入文本大部分时候会分割1个piece，分割后替换为为3个piece，第1个piece是左边部分，第2个piece是插入的文本，第3个piece是之前被分割文本的右边部分。

如果插入的文本刚好在1个piece的开头或者结尾，那么我们不需要分割这个piece，只需要在它之前或者之后插入1个新的piece。

保存与显示文本

本篇开头提到，当我们打开一个文本文件时，我们会读取数据然后将其放到一个数据结构中，如果我们需要保存文件，编辑器需要从piece table中获得需要写入文件的文本内容。

通过顺序读取piece descriptors，我们的文本编辑器能够将piece table中的数据结构转换为你在屏幕上看到的文本内容，也就是最终会写入到文件的内容。

for piece in piece_table["pieces"]:
    source: str = piece.source  # "original" or "add"
    buffer: str = piece_table[source]
    span_of_text: str = buffer[piece.start:piece.start+piece.length]
    print(span_of_text)  # alternatively, write to a file

注意：python中string[start:end]是返回字符串的字串，比如hello[1:4]返回ell。

删除文本

当我们从文件中删除一些文本，我们会将已有的piece分割为2个新的piece：

一个piece指向删除文本的左半部分，另一个piece指向删除文本的右半部分。

删除的文本仍然在orignal buffer或者add buffer中，只是没有piece指向它，它是不属于编辑器中的文本。

你可以认为pieces像很多聚光灯照在墙上，它们指向了所有需要在屏幕中显示的文本。任何时候，这些灯光照耀着墙上不同的区域，显示相应的内容。这些被照耀的文字是文件的内容。我们也很清楚墙上还有其他一些隐藏的文本，但这些文本是无关紧要的。

撤销与重做

即使一部分文本是隐藏的，我们也会让所有的文本都保留着，这使得撤销与重做这种操作变得相当简单。

处于“黑暗中”的文本可能会因为撤销或者重做而再次显示在文本编辑器中，而我们所需要做的只是调整一下“灯光的位置”，这些文本就能够重新被照耀了，而不需要刷新整个“墙壁”。

如果是用字符串数组存储，撤销与重做可能导致严重的性能问题，因为文本的增删需要进行字符串的修改操作。使用piece table方法，性能消耗几乎可以忽略不计，撤销与重做的文本已经存在与buffer中，只需要更新piece的属性就可以了。

总结

另外我们有多种方法可以改进piece table，piece table大部分时候会和其他数据结构组合在一起，比如树形结构（红黑树），以此改进piece table的性能。

本篇文章的目标是让你能够比较直观的理解piece table，算是文本编辑器内部实现的一篇鉴赏文，如果你有什么建议或者发现了哪里写的有问题，欢迎指出。

参考与进阶阅读

Data Structures For Text Sequences (PDF) - Charles Crowley

What’s been wrought using the Piece Table? - David Lu (I think)

Text Buffer Reimplementation, a Visual Studio Code Story - Peng Lyu