可能的字符串匹配的数据结构

4 回答

• 4

  您的问题的最佳数据结构将是trie特里允许以空间为代价进行快速查找 .

  请点击此链接获取更多信息：link

  回复于 2024-05-01T12:45:02+08:00
• 1

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

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

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

  迭代输入单词下面的树（所以在'pre'下面的子树）并查找所有单词（可能是节点有一个布尔'单词'字段或其他东西） . 当找到一个单词（单词== 1）时，您将（单词，优先级）添加到列表的末尾 .

  假设i是新条目的位置，然后将列表（i）与列表（i-1）进行比较 . 如果列表（i-1）的优先级小于列表（i），则切换其位置 . 继续这样做，直到第i-1项具有与新添加项相同或更高的优先级 .

  一旦trie-searching功能完成，您将有一个按降序排列的（单词，优先级）条目列表 .

  我希望这是有道理的 .

  回复于 2024-05-01T12:45:02+08:00
• 0

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

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

  回复于 2024-05-01T12:45:02+08:00
• 0

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

  参考：Trie example

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

  例如，您的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）遍历trie（L = len of pre）

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

  3）增加使用的字的优先级后重建堆 . O（nlogn）

  注意：您也可以尝试将后缀存储为BST，优先级为关键 . 有序遍历将为您提供优先级排序的后缀列表（O（n）） . 通过从BST中删除后缀并使用新优先级重新添加（插入/搜索/删除将为 balancer BST的O（高度）），可以增加使用的字的优先级 .

  回复于 2024-05-01T12:45:02+08:00