3

以下操作的最佳数据结构是什么：
该数据结构存储单词列表
输入：一个字符串说我们将其命名为“pre”
输出：以pre为前缀的所有字符串的列表（来自存储的列表words) 并且列表中的单词应按优先级降序排列。
如果在作为输出返回的字符串列表中使用特定字符串，则它的优先级会增加。
我将使用它进行单词预测，因此每次用户选择某个单词（从返回的单词列表中）时，它的优先级都会增加 1。
我已经实现了一个 trie，但它按字母顺序给出了输出（列表）希望它按优先级排序。

4

4 回答 4

4

解决您的问题的最佳数据结构是trie一个 trie 将允许以空间为代价进行快速查找。

点击此链接了解更多信息：链接

于 2013-08-02T20:25:21.920 回答
1

这可能不是最好的解决方案，但也许它会给你一些想法。

使用 trie 存储所有单词，并让您的节点包含优先级字段。

具有某种列表数据结构，您的 trie 可以看到它与您的查询函数具有相同的范围。该列表将包含（单词，优先级）条目。

迭代输入单词下方的树（因此“pre”下方的子树）并查找所有单词（可能节点具有布尔“单词”字段或其他内容）。当找到一个单词 (word == 1) 时，您会将 (word, priority) 添加到列表的末尾。

假设 i 是新条目的位置，然后将 list(i) 与 list(i - 1) 进行比较。如果 list(i - 1) 的优先级小于 list(i) 则您切换它们的位置。继续这样做，直到第 i-1 个项目的优先级等于或高于新添加的项目。

一旦 trie 搜索功能完成，您将获得一个列表，其中包含（单词，优先级）条目按降序排列。

我希望这是有道理的。

于 2013-08-02T21:12:35.980 回答
0

正如其他答案所示，您可以使用 trie 快速获取具有给定前缀的所有单词，然后根据它们的优先级对单词进行排序。忽略从 trie 中获取匹配词的访问时间，如果得到k匹配词，则根据优先级排序需要O(k log k)时间。这非常接近理论上的最佳O(k)时间，您可能不想费心尝试在实际应用中对其进行改进，特别是因为k在排序后打印单词实际上有运行时间O(kl)，l匹配单词的平均长度是多少，并且的乘数l可能通常与 大致相同log k。但是，如果您愿意将使用的空间量乘以O(L_avg)whereL_avg是所有单词的平均长度，那么您可以获得按排序顺序访问单词并将优先级 +1 更新到优先级 +1O(k + L log n)的L所选单词的长度，并且n是您的总单词数.

O(L_avg)这个想法一开始可能听起来有点疯狂，但请耐心等待，正如我将解释的那样，记忆真的只会成倍增加。这个想法是，在 trie 的每个节点上，将所有具有相应前缀的单词及其优先级存储在自平衡二叉搜索树中（根据优先级排序）。您可以将单词表示为存储单词的数组的索引，而不是完整的单词，因此 trie 的每个节点的存储需求与具有相应前缀的单词数量成线性关系。当一个词获得优先级+1时，您必须向上遍历trie并更新该词的对应trie节点及其所有父节点的平衡二叉搜索树，这需要O(L log n)时间。但是，要按排序顺序获取单词的索引以响应查询，您所要做的就是按顺序遍历二叉树，这需要O(k)时间。现在关于存储。一个单词的长度L存储在 L二叉树中：单词的 trie 节点上的树，以及其所有L-1父节点的树。因此，如果您将树中所有节点的所有树的总存储量相加，通过计算每个单词在树中出现的次数，总树存储量与所有单词的总长度呈线性关系，即O(n L_avg). 如果您可以在存储上处理该乘数，那么我相信这是理论上处理查询和优先级更改的最快方法，如果您真的想删除log k通过对查询结果进行排序获得的乘数。

于 2013-08-03T16:29:40.653 回答
0

这是内存效率低下的解决方案。

参考：特里示例

在每个节点上存储所有可能的有效后缀，这些后缀具有到目前为止遍历的父节点的前缀。同样为了快速检索，使用基于优先级的最大堆来存储这些后缀。

例如，您的 c++ trie 节点将如下所示（我尚未测试代码）

typedef pair<int, string> SUFFIX;
class Compare {
public:
    bool operator() (SUFFIX &d1, SUFFIX &d2) {
        return d1.first < d2.first;
    }
};
typedef priority_queue<SUFFIX, vector<SUFFIX>, Compare> max_heap;

struct TrieNode {
    char data; // char at current node
    max_heap word_suffixes; 
    bool is_complete;
};

/* Note: max_heap word_suffixes basically hold all strings without prefix so far. 
For example: You have dictionary of egg, eye at the starting node "e" your max
heap will have two entries "gg" and "ye" (with highest priority say "gg" 
as root of max heap) 
*/

现在时间复杂度将是

1) 按照前缀 "pre" O(L) (L=len of pre) 遍历 trie

2）在节点从最大堆中弹出每个字符串，这将为您提供按优先级排序的列表。O(nlogn) (n=堆大小)

3) 增加已用字的优先级后重建堆。O(nlogn)

注意：您也可以尝试将后缀存储为 BST，优先级为键。有序遍历将为您提供按优先级排序的后缀列表 (O(n))。可以通过从 BST 中删除后缀并重新添加新的优先级来增加使用过的单词的优先级（对于平衡的 BST，插入/搜索/删除将是 O（高度））。

于 2016-05-07T04:56:58.137 回答