【文件属性】：
文件名称：data structures for text sequences.pdf
文件大小：327KB
文件格式：PDF
更新时间：2023-01-11 09:53:12
数据结构
1998 年发表的data structures for text sequences
The data structure used ot maintain the sequence of characters is an important part of a text
editor. This paper investigates and evaluates the range of possible data structures for text
sequences. The ADT interface to the text sequence component of a text editor is examined.
Six common sequence data structures (array, gap, list, line pointers, xed size buers and piece
tables) are examined and then a general model of sequence data structures that encompasses
all six structures is presented. The piece table method is explained in detail and its advantages
are presented. The design space of sequence data structures is examined and several variations
on the ones listed above are presented. These sequence data structures are compared experimentally and evaluated based on a number of criteria. The experimental comparison is done by
implementing each data structure in an editing simulator and testing it using a synthetic load
of many thousands of edits. We also report on experiments on the senstivity of the results to variations in the parameters used to generate the synthetic editing load.