找到以指定字符串開頭的單詞數量的最快方法（單詞存儲在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;