特殊字典的最优数据结构

Question

在计算复杂度方面，哪种数据结构最适合实现包含(key,val)项的字典，该字典必须只支持以下命令:

1. Insert(key) -附加一个val=1的项(key,val)
2. Increment(key) -增加存在的值(键，值)
3. Find(key) -返回(key,val)
的值
4. Select(part_of_key) -以相同类型的新字典的形式返回strstr(key,part_of_key)!=NULL中的所有项(key,val)的列表(如果可能的话，不分配新的内存);例如，如果字典为{(红色，3)，(蓝色，4)，(绿色，1)}，则Select(re)={(红色，3)，(绿色，1)}
5. Max(i) -返回所有项中值第i大的项;例如，如果字典是{(红色，3)，(蓝色，4)，(绿色，1)}，那么Max(1)=蓝色，Max(2)=红色，Max(3)=绿色

键为字符串，值为正整数。

我认为它一定是两种不同数据结构的综合。但它应该是哈希表+二叉树还是三叉树+排序数组，还是别的什么?

Answer 1

平衡树(如红黑树)和后缀树(或后缀数组)的组合。

• 平衡树:操作1、2(实现为删除+插入)、3和5。
• 后缀树:操作4.

注意:哈希表将不能有效地支持操作5。

我认为你将很难实现后缀树。您可能会使用Mark Nelson对Ukkonen算法的c++实现，但是它有内存泄漏并且本质上是一个单例，所以您需要在准备生产使用之前清理它。即使在你修复它之后，你也需要调整它，使它与你的"其他"数据结构(在我的建议中是平衡树)一起工作，而不是一个大的普通字符串。

如果操作1比操作4更频繁，并且/或者你可以接受线性操作4，我建议你跳过后缀树的整个复杂性，只线性遍历你的数据结构。

Answer 2

对于前三个操作，哈希表可能是一个好主意。

对于第四个操作(选择键的一部分)，您可能必须以不同的方式编写哈希函数。是的，哈希函数用于查找/计算给定键的哈希值。由于您希望支持部分匹配并且您的键是string，因此您可能希望使用Suffix-tree或trie。

对于第5个操作(最大元素)，您可能需要维护堆或排序链表(或跳过表)，它与哈希表交互。

您还必须查看各种用例并找到应该优化的操作。例如:如果您有很多关于part_of_key操作的查询，您应该使用后缀树/lc -tree类型的结构，这样会得到很好的结果。然而，Find操作可能不会很快，因为它将花费O(logN)而不是不断查找。

总而言之，您需要集成哈希表，堆和后缀树来实现所有操作。

Answer 3

虽然确切的答案取决于您的操作频率，但您的选项列表应包括后缀数组

Answer 4

我认为有几个快捷键的trie将是最好的。

1-3已经被一个trie尽可能快地支持(键的长度)。

对于4，我将为所有可以从该字符输入的树节点添加一个包含256个元素的额外表。这样我就可以快速查找字符串的各个部分，而不必像在后缀树中那样显式地构造或存储后缀。

对于5，我会在叶子上添加一个链表，当数据插入时，得到更新排序。您可能需要对列表头部的另一个引用和树中的反向链接来找到正确的值并获得键。

内存复杂度不会随着这些添加而改变，因为它受到树节点数量的限制。然而，插入所花费的时间可能会因为链表的低效排序而改变。

最后一个结构可能应该称为哈希叶树。但是我不希望实现这样一个野兽。

Answer 5

我认为一个高效的数据库应该是一个经过修改的树，具有双向链接[可以从叶子到根并重建单词]，并且每个终止节点都将有额外的'value'字段。
你还需要一个multimap[即一个映射，其中每个值都是一组地址]。
键将按树状排列，值集将基于哈希。[在java中，应该是TreeMap<Integer,HashSet<Node>>]

伪代码:[嗯，很伪…它只显示了每个op的大致思路。

Insert(key):
1. Insert a word into the trie
2. add the value `1` to the terminating node.
3. add the terminating field to the multimap [i.e. map.add(1,terminating_node_address)]
Increment(key):
1. read the word in the trie, and store the value from the terminating node as temp.
2. delete the entree (temp,terminating_node_address) from the multimap.
3. insert the entree (temp+1,terminating_node_address) to the multimap.
4. increase the value of the terminating node's address by 1.
Find(key):
1. find the terminating node for the key in the trie, return its value.
Select(part_of_key):
1. go to the last node you can reach with part_of_key.
2. from this node: do BFS and retrieve all possible words [store them in an empty set you will later return].
Max(i):
1. find the i'th biggest element key in the multimap.
2. choose an arbitrary address, and return get the relevant terminating word node.
3. build the string by following the uplinks to the root, and return it.

复杂性:
设n为字符串的个数，k为最大值，S为字符串的长度。
插入:O (S) [单词查找树插入是O (S)]。映射中最小的元素(1)可以被缓存，因此可以在0(1)时访问。
Increment: O(S+logk):在树中查找字符串是O(S)，查找相关键是O(logk)，从哈希集中删除元素是O(1)，在树中查找下一个元素也是O(logk)[对于基于跳表的映射，实际上可以是O(1)]，插入一个值是O(1)。注意，通过将节点链接到映射中的相关键，复杂度甚至可以提高到O(S)，因为实际上不需要搜索。
Find: O(S):只在树中查找并返回值。
Select: O(S*n):在最坏的情况下，您需要检索所有元素，这迫使您遍历整个树以找到所有单词。
Max: O(logk+S):在排序映射中找到一个键，重建单词。

EDIT:注意，在这里，我假设对于find(I)，您需要第I个不同的最大元素。如果不是这样，您需要稍微修改一下set，并使用允许重复键的multimap[而不是将set作为值]。这将使所有基于树的操作O(logn)而不是O(logk)，在我看来仍然是有效的…