红龙图压镇,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到一个数组中,那么我们就不需要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 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