2

我已经实现了自己的 AVL 树，并将其用作字典。我想知道，计算所有以某个字符串开头的单词的最快方法是什么。

例如：

string prefix = "fa";

在此处输入图像描述

output: 4

我已经让它在 O(n) 中工作，但是，我听说它可以做得更快。我当然可以在节点中保存额外的信息，比如下面的节点和其他类似的东西。

4

4 回答 4

2

如果您想更改数据结构，则可以从trie获得卓越的性能。如果 trie 包含静态数据，您可以通过使用子树计数大小（使用动态编程生成）注释分支来获得更好的性能。

例如对于[竖琴，帽子，嗨]

           h(3)
      a(2)     i()
  r(1)    t()
p()
于 2012-12-19T13:11:20.063 回答
1

可以修改 AVL 树，因此每个节点也将知道其“索引” 1（如果集合是排序数组，则索引是元素编号）。

您现在要做的就是：

  1. 搜索"FA"，获取树i1中最近但更大（或等于）元素的索引
  2. 搜索"FB"，获取树i2中最接近但更小的元素的索引。
  3. i1找出和之间有差异的元素数i2（区分在 1 中找到“FA”的情况和不在 1 中的情况）。

1,2 都是O(logn)- 3 是常数，因此总复杂度是O(logn)（实际上O(logn * |S|)，因为每个比较都是 O(|S|) 本身，并且你有O(logn)比较）。

(1) 它是通过让每个节点“记住”它有多少个儿子来完成的，你可以使用这些信息来最终提取索引。

于 2012-12-19T13:17:42.010 回答
1

如果您想在保持相同的渐近时间界限的同时尽可能减少内存占用，您可以为每个节点使用一个整数并仍然达到O(log n) 时间（假设恒定时间键比较）。

与每个节点一起存储其子树的大小。这可以在树修改期间轻松更新。

要查找给定范围内的键数：

  • 查找此范围内的顶部元素。也就是说，在范围内但没有其祖先的唯一节点。将元素称为“顶部”。
  • 如果不存在这样的元素，则返回 0
  • 初始化 sum = 1（代表顶部）。
  • 在 "top" 的左子树中找到范围的开始：
    • 如果从一个节点向左下降，则将其整个右子树的大小加到总和中，然后加一。
    • 如果你向右下降，什么都不加。
  • 在 "top" 的右子树中找到范围的结尾：
    • 如果从一个节点向右下降，则将其整个左子树的大小加到总和中，然后加一。
    • 如果您向左下降，则不添加任何内容。
  • 返回总和。

给定前缀的范围包含所有具有该前缀的元素。重要的是要注意，具有给定前缀的字符串集在其排序顺序上是连续的——也就是说，它确实是一个范围。

前缀范围的开始是前缀本身之前的位置。

前缀范围的结尾是在字典序上第一个不相交前缀之前的位置（FA=> FB;FZ=>GA当仅A-Z在字母表中时）。

Unicode 通过引入一个可能实际上不会出现在文本中的“顶部”字符来简化这一点，并在所有其他字符之上进行比较。即，end = prefix + "\uFFFF"。

于 2012-12-19T13:29:06.797 回答
0

AVL-tree 不是实现您想要的正确数据结构。还有另一种数据结构，称为基数树，它可以回答 O(lg N) 复杂度的前缀计数查询。基数树中的每个节点n都有 0 到 26 个子节点。它还有一个辅助变量 ，prefix_count它告诉我们在基数树中有多少词以前缀结尾n。例如，这是单词abbaba和的基数树abbacba

        X <-- root node: it has no value
        |
        a <-- prefix count: 2
        |
        b <-- prefix count: 2
        |
        b <-- prefix count: 2
        |
        a <-- prefix count: 2
       / \
      b   c <-- prefix count: 1, 1
      |   |
      a   b <-- prefix count: 1, 1
          |
          a <-- prefix count: 1

因此，要检查树中有多少单词以前缀 example 开头ab，只需跟随节点a --> b，并返回该节点的前缀计数。如果找不到给定的前缀，则返回 0。

实现技巧：每个节点应该保留一个 26 个字符的数组，以提高所有操作的复杂性。

psevdocode中的实现：

struct node :
  let child -> array of 26 characters;
  let pc -> integer prefix counter;

struct radix-tree :
  node array[ MAXN ];
  let size -> integer size of the trie

init( rt ) :
  size := 1; // add the root

insert( rt, x ) :
  cn := 1; // root
  foreach i in x :
    if rt.array[ cn ].child[ i ] = null : // node doesn't exist
      rt.array[ cn ].child[ i ] := ++rt.size;
      cn := rt.size;
    else : // node exists
      cn := rt.array[ cn ].child[ i ];
    tr.array[ cn ].pc += 1;

该prefix_count功能的实现将类似于插入过程。

prefix-count( rt, x ) :
  cn := 1; // root
  foreach i in x :
    if rt.array[ cn ].child[ i ] = null :
      return 0; // 0 prefixes found
    else :
      cn := rt.array[ cn ].child[ i ];
  return rt.array[ cn ].pc;
于 2012-12-19T19:56:30.490 回答