11

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

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

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

具有相对偏移量的树结构支持#2，但是当我向文本添加大量样式时，树会快速退化。

还有其他选择吗？

4

1 回答 1

4

我从来没有开发过编辑器，但是这个怎么样：

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

与其对样式使用单独的数据结构，我更希望有一个引用，该引用将伴随每个字符并指向包含适用字符的数组或列表。具有相同样式集的字符可以指向相同的数组或列表，因此可以共享一个。

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

根据您的编程语言，您甚至可以通过指向列表的一半来进一步压缩内容，尽管为此额外的簿记实际上可能使其效率更低。

这个建议的主要问题是内存使用。在用 C 编写的 ASCII 编辑器中，由于结构对齐填充，在 64 位系统上，将指针与每个 char 捆绑在一起会将其有效内存使用量从 1 字节提高到 12 字节。

我会考虑将文本分成可变大小的小块，这样您就可以有效地压缩指针。例如，一个 32 个字符的块在 C 中可能如下所示：

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

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

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

如果你错过了，我不是树木专家:-)

编辑：

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

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

如本文所述：

文本编辑器的数据结构

编辑2：

建议的数据结构中的删除应该相对较快，因为它会归结为数组中的字节移位和样式掩码上的一些按位操作。插入几乎相同，除非一个块填满。在每个块中保留一些空间（即样式掩码中的一些位）以允许将来直接在块中插入，而不必为相对少量的新文本更改树本身，这可能是有意义的。

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

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

于 2010-11-16T17:37:31.437 回答