Blue Blazer

Achieve perfection by constant effort and creative will.
Code every day, no matter what...

简单文本编辑器的数据结构

先说vim和emacs吧。
vim文本存储采用的是链表,每个节点代表一行。
emacs采用的是间隙缓冲区(Gap buffer),如: abcdI____efg I是光标,这样在光标处插入删除就变得很快速,缺点是当光标移动距离过大时需要移动大量数据。

这两种方法各有优点,但是有没有更好的方法呢?
Data Structures for Text Sequences
介绍了Piece Table方法,就是使用两个缓冲区,一个只读,一个只能做尾部附加操作。
只读缓冲区的数据是原始文件,用户每次修改添加的数据记录在附加缓冲区中。
然后使用链表来表示当前文档:每个链表的节点有三个域:哪个缓冲区,起始偏移,长度。
插入操作最多让链表长度加2,删除操作最多让其长度加1。
这样链表长度是编辑次数的函数,而不是文档长度。
不妨设编辑次数为 m , 文本长度为 n,插入操作的长度为p,来分析复杂度,容易得:
时间复杂度:从上次临近位置插入 O(1),随机位置插入O(m),删除时间复杂度同插入。获得某个位置字符O(m),获得长度为l的字符串O(m+l),遍历所有字符O(n)。
内容占用:约等于S(n+mp),因为以前插入的内容会被一直保留在附加缓冲区中。
可以看到大部分操作的时间复杂度是与长度无关的,并且只读缓冲区可以根本不载入到内存中来,这样可以支持编辑非常大的文件(几百MB)。

如果采用平衡树而不是链表来表示节点的话,固定位置,随机位置插入/删除时间复杂度变为O(log m),
获得某个位置字符O(log m),获得长度为l的字符串O(log (m) +l),遍历所有字符O(n),但是这样实现(撤销/重做等操作)耗费更多内存,实现起来麻烦,并且一般需要用户交互的文档编辑软件的编辑次数不会太多(用户经常就会存盘,也不可能连续几小时编辑)。

因此这样的数据结构才是最适合简单文本编辑器使用的。

0 comments: