trie的實現中的空間差異

Question

我閱讀的內容越多，出於某種原因，我越感到困惑。
現在讓我困惑的是：
我已經閱讀了大約2種類型的實現。

1. 使用數組來表示字符（不存儲所述字符 本身），並在每一個節點也將索引存儲到實際字（如果 我們達到了一個字）。
2. 使用存儲字符，並在每個節點的末尾 使用一個布爾值來確定，如果我們達到了一個字去 沿着這條路

在第一種情況下，它沒有被提及，但它節點Collection似乎我們必須實際保留所有的字典單詞（因爲我們間接引用它們）。所以我們有array_size*numberOfNodes*lengthOfword + size of dictionary processed

在後一種情況下，我們不需要字典，因爲字符直接存儲在樹中。所以在我看來，第二個實現更節省空間。但我不確定多少。
我的理解在實現方面是否正確，是否有具體的理由來選擇其中一個呢？我們又如何計算第二種情況的空間需求？

Answer 1

嘗試不存儲任何地方的原始單詞，而是隱式存儲它們。一線索的基本結構如下：在字典樹存儲每個節點

• 單個比特確定到達節點的路徑是否形成一個字，並
• 指針子的集合由字符標記的節點。

要確定單詞是否在樹中，您從根開始，然後按照適當標記的指針一次一個。如果您到達標記爲單詞的節點，則該單詞存在於trie中。如果你到達一個沒有標記的節點或者你脫離了節點，這個詞不存在。

上面列出的兩個結構之間的區別是如何存儲子指針。在第一個版本中，子指針被存儲爲字母表中每個符號一個指針的數組，這使得以下子指針非常快，但是可能非常空間低效。在第二個版本中，您顯式地存儲某種類型的集合，只保存您需要的帶標籤的指針。這比較慢，但對於稀疏嘗試來說更有效率。

一個trie的空間使用量取決於節點的數量（稱之爲n），字母表的大小（稱之爲k）以及表示子指針的方式。如果存儲固定大小的指針數組，則空間使用量大約爲kn指針（n個節點，每個節點有k個指針），每個節點的標記加n個位。如果您擁有以排序順序存儲的指針的動態數組，則開銷將總共爲n個子指針，再加上n位，再加上存儲單個集合所需空間量的n倍。

第一種方法的優點是速度和簡單性，在密集嘗試中具有非常好的性能。第二種速度較慢，但​​對於稀疏嘗試而言效率更高。

這些並不是唯一可能的空間優化。Patricia試圖只與一個孩子一起壓縮節點，並且非常節省空間。 DAWG嘗試儘可能多地合併節點，但不支持有效的插入。

希望這會有所幫助！