专栏首页氧化先生的专栏编辑器背后的数据结构

编辑器背后的数据结构

大约刚上大二的时候,想做一个编辑器控件。不是一个用Scintilla套上外壳的编辑器,而是一个能被套上外壳的控件。当然它最后也成为了我众多流产了的练手项目中的一员,不过人人黑历史里还留存着当时的一张截图

那段时间也对编辑器所使用的数据结构非常感兴趣。我们需要一种数据结构,能够支持字符串高效地索引、遍历、插入和删除。当时找的一些论文和书还躺在硬盘里一直没删,如今拿出来再嚼一嚼。下面介绍几种在编辑器中常见的数据结构。

朴素一维数组

不用说,效率比较低,几乎没有人会直接采用这种方式。把整篇文档看做一个字符串,即便我们预留了空间,也会在字符串头插入字符时暴毙。

不过,虽然这种方式无法满足需求,把它稍加改进却能够得到一个非常不错的结构。

Gap Buffer

Gap Buffer是朴素的一维数组的改进版本,它将“空白”(指字符串没有填满Buffer的部分)移动到了Buffer中间。如下图所示:

简而言之,当我们执行插入或删除动作的时候,Buffer中的空白(Gap)随之移动。例如,下面一句话中,初始情况下空白在Buffer的最后:

This is a smple txt.[        ]  

我们使用中括号[ ]来表示空白。然后当我想要在smple中插入a时,编辑器首先把空白移动到s后面:

This is a s[        ]mple txt.  

然后在s后面插入a

This is a sa[       ]mple txt.  

如果我想在txt中插入一个e,则需要同样的步骤:

This is a sample t[       ]xt.  
This is a sample te[      ]xt.  

这种方法所基于的假设是,编辑文本时通常为连续作战,而打游击的时候并不会连续工作。

Linked Line

文本通常是一种二维结构,同时“行”这个概念在文档渲染等方面又有着不一样的意义,因此把它们单独做一层抽象也比较合理。在每一行内部,直接使用字符串或者Gap Buffer都可以。

Piece Table Buffer

Piece Table Buffer是一种效率更高的结构,但是会浪费更多的内存。Piece Table Buffer的核心思想是:在字符串末尾添加字符的代价很低(我们预留了空间),字符的移动代价很高。因此它会尽可能避免字符串的移动操作。

Piece Table Buffer由两部分Buffer组成。第一个Buffer保存的是原始的文件内容,这个Buffer是只读的。另一个Buffer用于新加入的内容,它只能进行Append操作。同时,用一张表(Piece Table)来表明当前文档的组成。例如:

Original Buf: This is a smple txt.  
Append Buf: [Empty]  

Piece Table:

BUFFER

FROM

TO

CONTENT

original

0

21

This is a smple txt.

首先我将smple删掉,则它们变成了:

Original Buf: This is a smple txt.  
Append Buf: [Empty]  

Piece Table:

BUFFER

FROM

TO

CONTENT

original

0

11

This is a

original

16

21

txt.

则此时的句子为This is a txt.。随后,我在原来smple处又插入了new,则

Original Buf: This is a smple txt.  
Append Buf: new  

Piece Table:

BUFFER

FROM

TO

CONTENT

original

0

11

This is a

append

0

4

new

original

16

21

txt.

句子就变为了This is a new txt.

Piece Buffer的好处还在于能够比较轻松地实现Redo/Undo,不需要额外的Buffer记录修改过的字符串,因为所有编辑过的历史信息都存在两个Buffer中。

Rope

Rope是一种二叉树结构,如下图所示:

其中Rope的叶子节点存储字符串,内部节点存储叶子节点中字符串的长度。为了避免树的深度过深的问题,可以采用一定的平衡策略。

编辑器们都用了哪种数据结构?

部分Emacs使用了Gap Buffer,包括古老的 Emacs on TECO[1]、现代的GNU/Emacs[8]及其前辈Gosling Emacs[2]。Scintilla (即包括Code::Blocks在内的很多IDE/编辑器使用的代码编辑控件) 也使用了Gap Buffer。[4]

Emacs进入由Lisp实现的时代后,一些Emacs版本使用了LinkedLine[1]。

Vim使用的是一种基于行的数据结构[5],但行与行之间不是简单地使用链表连接,而是用一种树结构进行管理[6]。

KDE的Okteta 16进制编辑器使用了Piece Table Buffer。[7] 本文开头的示例编辑器也使用了Piece Table Buffer

Reference

  1. The Craft of Text Editing, Craig A. Finseth, 1991.
  2. Data Structures in the Andrew Text Editor, Wilfred J. Hansen, 1986.
  3. Data Structures for Text Sequences, CharlesCrowley, 1998.
  4. Scintilla CVS CellBuffer.h
  5. NeoVim Wiki Page Architectural musing and ideas
  6. Vim memline.c
  7. Okteta repo folder
  8. GNU Emacs Lisp Reference Manual

原文链接:http://dontpanic.blog/data-structures-under-editors/

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 良心GitHub项目:各种机器学习任务的顶级结果(论文)汇总

    项目地址:https://github.com//RedditSota/state-of-the-art-result-for-machine-learning...

    不知雨
  • 在腾讯云上搭建 Hadoop 完全分布式集群

    搭建完全分布式的 Hadoop 集群,需要三台同号同区腾讯云服务器,配置可根据所需求自行加减,三台系统为 CentOS 6.5 64位。

    不知雨
  • 机器之心深度研学社每周干货:2017年第26周

    Siraj Raval 是油管上一位非常活跃的主播,他能通过幽默有趣的视频形式,教会你如何理解和应用人工智能,以及许多其它有趣的编程项目。在这期视频中,他主要介...

    不知雨
  • Build2Vec:向量空间中的建筑表示(cs)

    本文提出了一种图嵌入算法,该算法用于转换从建筑信息模型(BIM)中获得的标记属性图。工业基础类(IFC)是BIM的一个标准模式,用于将建筑数据转换为图形表示。本...

    用户7454091
  • Shell编程基础

    我们可以使用任意一种文字编辑器,比如gedit、kedit、emacs、vi等来编写shell脚本,它必须以如下行开始(必须放在文件的第一行):

    阳光岛主
  • GitLab 之 PlantUML 的配置及使用

    目录 PlantUML介绍 环境、软件准备 PlantUML Server 安装及 GitLab 配置 实例 Demo 时序图 流程图 活动图 状态图 用例图...

    哎_小羊
  • 【计算机本科补全计划】Mysql 学习小计(4)

    正文之前 昨天终于把我苦命的毕业设计审批表送出去了。结果暑假的生产实习开始对账,我这儿又开始忙活了,还要签字,我有时候都在想要不全班代签一遍算了。不然真的揪心啊...

    用户1687088
  • 左手用R右手Python系列之——字符串格式化进阶

    关于R语言字符串格式化之前无论是专题还是案例教程中均有所涉及,今日这一篇之所以重提是因为又找到了一个很好用的字符串格式化包。 这个包的语法源于Python风格,...

    数据小磨坊
  • 7kb目录爆破神器重大更新!WebPathBrute 1.6.0新鲜上架

    加入暴力爆破等功能 修复变量不支持非80端口获取 修复多url不支持https 优化代码加密 使用更流畅 内嵌运行库 程序目录更清爽

    洛米唯熊
  • OpenCV之播放视频

    创建一个VideoCapture类的实例,如果传入对应的参数,可以直接打开视频文件或者要调用的摄像头。官网文档

    李小白是一只喵

扫码关注云+社区

领取腾讯云代金券