2

我需要跟踪大型文本文件中的索引。我一直保留一些std::map索引和随附的数据作为快速破解。如果用户在文本中的第 230,400 个字符上，我可以显示文本的任何元数据。

现在我的地图越来越大，我遇到了一些速度问题（如预期的那样）。

例如，如果文本在开头被修改，我需要将地图中该位置之后的索引加一，这是一个 O(N) 操作。

将其更改为 O(log N) 复杂度的好方法是什么？我一直在看AVL Arrays，它很接近。

我希望 O(log n) 时间进行更新和搜索。例如，如果用户在文本数组中的字符 500,000 上，我想非常快速地查找该字符是否有任何元数据。

（忘记添加：用户可以随时添加元数据）

4

2 回答 2

1

简单的。制作偏移量的二叉树。

任何偏移量的值都是通过从叶子到根遍历树来计算的，只要节点是右子节点，就添加偏移量。

然后，如果您在文件的早期添加文本，您只需要更新节点的偏移量，这些节点是更改的偏移量的父节点。也就是说，您在第一个偏移量之前添加了文本，您添加了添加到根节点的字符数。现在您的一半偏移量已得到纠正。现在遍历左孩子并再次添加偏移量。现在 3/4 的偏移量已更新。继续遍历左孩子添加偏移量，直到所有偏移量都被更新。

@OP：

假设您有一个包含 8 个字符的文本缓冲区，以及奇数字节的 4 个偏移量：

the tree:              5
                      / \
                     3   2
                    / \ / \
                    1 0 0 0
sum of right
children (indices) 1  3 5  7

现在假设您在偏移量 4 处插入了 2 个字节。缓冲区是：

01234567

现在它的

0123xx4567

因此，您只修改支配数组中已更改部分的节点。在这种情况下，只需要修改根节点。

the tree:              7
                      / \
                     3   2
                    / \ / \
                    1 0 0 0
sum of right
children (indices) 1  3 7  9

求和规则是从叶到根我对自己求和，如果我是父母的正确孩子，我的父母的价值。

要查找我当前位置是否有索引，我从根开始并询问此偏移量是否大于我的位置。如果是，我会向左移动并且什么都不添加。如果没有，我会向右遍历并将值添加到我的索引中。如果在遍历结束时我的值等于我的索引，那么是的，有一个注释。您可以使用最小和最大索引进行类似的遍历，以找到支配范围内所有索引的节点，找到我正在显示的文本的所有索引。

哦..这只是一个玩具示例。实际上，您需要定期重新平衡树，否则如果您继续在文件的一部分中添加新索引，您将得到一棵失去平衡的树，最坏情况下的性能将不再是 O( log2 n) 但将是 O(n)。为了保持树的平衡，您需要实现一个平衡的二叉树，如“红/黑树”。这将保证 O(log2 n) 性能，其中 N 是元数据的数量。

于 2012-06-22T18:44:44.637 回答
0

不要存储索引！没有办法做到这一点，同时性能更好O(n)- 在数组的开头添加一个字符，你将不得不增加n - 1索引，没有办法解决它。

但是，如果您改为存储子字符串长度，则只需更改每一级树结构的一个，即可将您提升到O(log n). 我的（未经测试的）解决方案是使用带有附加到节点的元数据的绳索- 您可能需要稍微尝试一下，但我认为这是一个坚实的基础。

希望有帮助！

于 2012-06-22T19:00:15.770 回答