一个特殊字典的最佳数据结构

Question

一个特殊字典的最佳数据结构

algorithmdata-structureshashcomplexity-theorytrie

10

哪种数据结构在计算复杂性方面最适合实现一个仅支持以下命令的(key,val)项字典：

1. Insert(key) - 将值为1的项（key，val）附加到字典末尾 2. Increment(key) - 增加已存在的（key，val）的val 3. Find(key) - 返回（key，val）的val 4. Select(part_of_key) - 如果在其中strstr(key，part_of_key)!= NULL，则以新字典的形式返回所有项（key，val）的列表（如果可能，不分配新内存）；例如，如果字典是{(red,3)，(blue,4)，(green,1)}，则Select(re)={(red,3)，(green,1)} 5. Max(i) - 返回具有i个最大值的项；例如，如果字典是{(red,3)，(blue,4)，(green,1)}，则Max(1)= blue，Max(2)= red，Max(3)= green。

键是字符串，值是正整数。预计字典中的项数非常大。

我认为它必须是两种不同数据结构的综合。但应该是哈希表+二叉树还是trie +排序数组或其他东西？

- psihodelia

这个问题似乎与C语言没有任何关系...我建议删除该标签并添加数据结构或其他标签。 - Tomas

请注意，4永远无法比它需要返回的项目数量更快，因此，如果选择通常会返回所有、一半或十分之一的项目，则可以遍历所有键。 - Thomas Ahle

你能提供更多关于各种操作的频率的信息吗？例如，你会比插入更频繁地查找吗？你是否知道需要多少元素？... - Foo Bah

5个回答

4

对于前三个操作，哈希表可能是一个好的选择。

对于第四个操作（选择关键字的一部分），您可能需要编写不同的哈希函数。是的，哈希函数用于从给定的关键字中找到/计算哈希值。由于您想支持部分匹配且关键字是字符串，因此您可能想使用后缀树或trie。

对于第五个操作（第i大的元素），您可能需要维护与哈希表交互的堆或排序的链表（或跳表）。

您还需要查看各种用例并找到应该优化哪些操作。例如：如果您在part_of_key操作上有很多查询，则应使用后缀树/LC-trie等结构，并且这将产生良好的结果。但是，您的查找操作可能不会很快，因为它需要O(logN)而不是常数查找。

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

- Jack

如何在常量时间内查找字符串？常量时间意味着您甚至不能读取整个输入字符串。 - amit

@amit：你有什么问题？你是在问哈希如何在常数时间内查找键值对吗？ - Jack

不，我的意思是在数据结构中实现一个准确的字符串find()函数时间复杂度为O(1)是不可能的，因为至少需要读取字符串，这需要O(S)的时间，其中S是字符串的长度。 - amit

在包含N个单词的字典中（每个单词长度为S），O（S）<< O（N）。通常，这被认为是常数。是的，你的观点是正确的，我们至少需要查找字符串的S个字符。那是下限。 - Jack

你的说法是错误的。在文献中, 字符串查找一直被认为是O(S)算法。因为无论词典中有多少字符串，在查找一个200个字符的字符串和一个20个字符的字符串时，前者都需要更长的时间。 - amit

如果O(S)是非常重要的问题，可以使用LC-trie来大大减少平均字符串查找。请参阅http://www.academypublisher.com/jnw/vol02/no03/jnw02031827.pdf获取详细信息。 - Jack

3

具体答案取决于操作的频率，您的选项列表应包括一个后缀数组

- thiton

1

我认为一个高效的数据库将是一个修改过的trie，具有双向链接[可以从叶子到根重构单词]，并且每个终止节点将有额外的“值”字段。
您还需要一个multimap [即一个map，在其中每个值都是一组地址]。
键将按树形排列，而值集将基于哈希。 [在Java中，它应该类似于TreeMap<Integer,HashSet<Node>>]

伪代码：[好吧，非常伪...它只显示了每个操作的一般思想]。

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) [trie插入是O(S)]。将地图中最小的元素（1）缓存，因此可以在O(1)的时间内访问。
递增：O(S+logk)：在Trie中查找字符串需要O(S)，在哈希集合中删除元素需要O(1)，查找树中的下一个元素也是O(logk) [实际上可以是O(1)，基于skip-list的映射]，插入值需要O(1)。注意，通过将节点链接到地图中的相关键，复杂度甚至可以提高到O(S)，因为实际上不需要搜索。
查找：O(S)：在trie中查找并返回值。
选择：O(S*n)：在最坏的情况下，您需要检索所有元素，这迫使您遍历整个trie以查找所有单词。
最大值：O(logk+S)：在排序地图中查找键，重构单词。

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

- amit

1

我认为使用带有多个快捷方式的Trie树是最好的选择。

1-3可以通过Trie树实现尽可能快的查找（键的长度）。

对于第4点，我会在所有可以从该字符进入的Trie节点上添加一个额外的256元素表。这样，我就可以快速查找字符串的部分，而无需像后缀树那样显式构造或存储后缀。

对于第5点，我会在叶子节点上添加一个链表，在插入数据时进行排序更新。您可能需要另一个指向列表头部的引用以及Trie中的反向链接来查找正确的值并获取键。

这些添加不会改变Trie树的内存复杂度，因为它受到Trie节点数量的限制。但是，由于链表的低效排序，插入所需的时间可能会发生变化。

最终结构可能应该称为哈希叶Trie树。但我不想实现这样的东西。

- LiKao

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Branko Dimitrijevic · Accepted Answer

这是一种结合了平衡树（如红黑树）和后缀树（或后缀数组）的方法。

平衡树：操作1、2（通过删除+插入实现）、3和5。
后缀树：操作4。

注意：哈希表将无法高效地支持操作5。

我认为你在实现后缀树时会遇到困难。你可以使用Mark Nelson的Ukkonen算法的C++实现，但它存在内存泄漏问题，并且本质上是一个单例，因此在生产中使用之前需要对其进行清理。即使你解决了这个问题，你也需要调整它，使其能够与“另一个”数据结构（在我的提议中是平衡树）一起运行，而不是一个大的普通字符串。

如果你比操作4更频繁地执行操作1，和/或者你可以接受线性操作4，我建议你跳过使用后缀树的所有复杂性，直接线性遍历你的数据结构。