最有效的数据结构添加文本样式

Question

我正在寻找最佳的数据结构来为文本添加样式（比如在文本编辑器中）。该结构应允许以下操作：

1. 快速查找绝对位置X处的所有样式
2. 在任意位置快速插入文本（该位置之后的样式必须移动）
3. 文本的每个位置必须支持任意数量的重叠样式

我已经考虑过包含文本范围的列表/数组，但它们不允许在不重新计算插入点之后所有样式的位置的情况下快速插入。

使用相对偏移量的树结构支持第二个要求，但是当我向文本添加大量样式时，树将快速退化。

还有其他选项吗？

- Aaron Digulla

---

你决定了文本本身将如何存储吗？无论文本使用什么结构，都必须有效地处理插入/删除，因此可能可以通过使文本指向样式而不是相反来扩展它。类似于将每个字符与适用样式的数组/列表的指针配对。您应该能够在字符之间共享样式和数组，并且甚至可以共享指针本身。 - thkala

@thkala：请将其发布为答案，以便我可以发表评论。 - Aaron Digulla

Answer 1

我从未开发过编辑器，不过这个想法怎么样：

我认为可以扩展用于存储文本字符本身的方案，当然具体取决于您的实现细节（语言、工具包等）和性能及资源使用要求。

与其使用单独的数据结构来存储样式，我更喜欢使用带有引用的字符，指向适用字符的数组或列表。具有相同样式集的字符可指向相同的数组或列表，因此一个可被共享。

插入和删除字符并不会影响样式本身，除了改变对它们的引用数量，这可以通过一些引用计数来处理。

根据您的编程语言，您甚至可以通过指向列表的一半来压缩一些内容，尽管此操作所需的额外管理可能使其更加低效。

这个建议的主要问题在于内存使用。在C语言中编写的ASCII编辑器中，每个字符与指针捆绑将使其有效内存使用量从1字节增加到12字节，因为结构对齐填充。

我的建议是将文本分成小的可变大小块，以便您可以高效地压缩指针。例如，在C语言中，32个字符的块可能如下所示：

struct _BLK_ {
    unsigned char size;
    unsigned int styles;
    char content[];
}

有趣的部分是结构体中变量部分的元数据处理，其中包含存储的文本和任何样式指针。大小元素将指示字符数。样式整数（因此限制为32个字符）将被视为32个1位字段的集合，每个字段都指示一个字符是否具有自己的样式指针，或者是否应使用与上一个字符相同的样式。这样，一个只有单一样式的32个字符块只需要额外的大小字符、样式掩码和单个指针以及任何填充字节的开销。在这样的小数组中插入和删除字符应该非常快速。

至于文本存储本身，树听起来是个好主意。也许是一个二叉树，每个节点值将是子节点值的总和，最终叶节点将指向其节点值作为其块大小的文本块？根节点值将是文本的总大小，每个子树理想地持有您文本的一半。不过，您仍然需要自动平衡它，有时必须合并半空的文本块。

如果您错过了，我不是树的专家:-)

编辑：

显然，我建议的是这种数据结构的修改版本：

http://en.wikipedia.org/wiki/Rope_%28computer_science%29

正如这篇文章所提到的：

文本编辑器的数据结构

编辑2：

在所提出的数据结构中，删除应该相对较快，因为它将归结为在数组中进行字节移位和样式掩码上进行一些位运算。插入基本上是相同的，除非块填满。可能有意义在每个块内保留一些空间（即样式掩码中的一些位），以允许未来直接在块中插入少量新文本而无需更改树本身。

像这样将字符和样式捆绑在块中的另一个优点是，其固有的数据局部性应该比其他替代方案更有效地利用CPU缓存，从而在某种程度上提高处理速度。

与任何复杂的数据结构一样，您可能需要使用代表性测试用例进行分析或自适应算法来确定其操作的最佳参数（块大小，任何保留空间等）。

- thkala

---

对于压缩样式的想法点个赞。我见过绳索结构，它很好，直到你需要保存样式。 - Aaron Digulla

样式的主要问题在于，您需要能够有效地回答这个问题：文本位置X处有哪些样式是活动的？此外，当插入/删除文本时，样式管理应该是简单的（拆分样式、合并样式、删除样式）。大多数编辑器使用树形结构（如区间树：http://en.wikipedia.org/wiki/Interval_tree），但如果您在某个地方添加一个字符，则需要重新计算所有朝向文本末尾的间隔。 - Aaron Digulla

@Aaron Digulla：是的，如果样式和文本没有捆绑在一起，保持它们同步可能会很麻烦。另一方面，类似我提出的方法需要（更多？）内存来存储相对较少样式更改的文本，但它们访问和修改速度快，甚至随着文本样式变得更加复杂，它们可能变得更加内存高效。 - thkala