找到以指定字符串开头的单词数量的最快方法（单词存储在AVL树中）

Question

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

如：

string prefix = "fa"; 

output: 4 

我找到了为O工作（N），但是，我听说它可以更快地完成。 我当然可以在节点中保存附加信息，比如下面的节点和其他类似的东西。

Answer 1

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

与每个节点存储其子树的大小。这可以在修改树的过程中轻松更新。

要找到一个给定的范围内键的数量：

• 查找在此范围内的顶级元素。也就是说，范围内的唯一节点，但它的祖先都不是。调用元素“top”。
• 如果不存在这样的元素，则返回0
• 初始化sum = 1（表示顶部）。
• 查找范围开始在“顶”的左子树：
  • 如果您下降从一个节点离开，加上它的整个右子树的总和的大小，并添加一个。
  • 如果您正确下载，请勿添加任何内容。
• 查找“顶”的右子树范围的结束：
  • 如果从节点下降权，增加其整个左子树的总和的大小，并添加一个。
  • 如果您下降，请不要添加任何内容。
• 返回总和。

给定前缀的范围包含具有前缀的所有元素。需要注意的是，具有给定前缀的字符串集合是连续的w.r.t.它的排序顺序 - 也就是说，它确实是一个范围。

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

前缀范围的端部是位置仅这一个后字典序第一不相交前缀之前（FA =>FB; FZ=>GA当只有A-Z在字母表）。

Unicode通过引入实际上可能不会出现在文本中的“顶部”字符来简化该操作，并比较所有其他字符。那就是，end = prefix + "\uFFFF"。

Answer 2

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

例如用于[竖琴，帽子，喜]

  h(3) 
     a(2)  i() 
    r(1) t() 
p() 

Answer 3

AVL树可以被修改，以便每个节点也将知道它的“指数” （索引元素编号，如果集合是一个排序的数组）。

你现在需要做的是：

1. 搜索"FA"，得到一个指数的最接近i1但大（或等于） 元素树为它
2. 搜索"FB"，得到最接近的索引i2，但在树中得到最小的个元素。
3. 查找i1和i2之间的差异的元素数量（区分“FA”在1中找到和不在其中的情况）。

两个1,2-是O(logn) - 3是恒定的，因此总的复杂性是O(logn)（实际上O(logn * |S|)，因为每个比较为O（| S |）本身，并且您有O(logn)比较）。 （1）这是通过让每个节点“记住”它有多少个儿子来完成的，并且你可以使用这些信息来最终提取索引。

Answer 4

AVL树不是实现你想要的正确的数据结构。还有一个叫做基数树的数据结构，它可以回答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 

因此，要检查有多少字树的前缀，例如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;