Menu
I'm trying to build a Trie but on a mobile phone which has very limited memory capacity.
I figured that it is probably best that the whole structure be stored on disk, and only loaded as necessary since I can tolerate a few disk reads. But, after a few attempts, it seems like this is a very complicated thing to do.
What are some ways to store a Trie on disk (i.e. only partially loaded) and keep the fast lookup property?
Is this even a good idea to begin with?
846
In its original form the trie [2] is a data structure where a set of strings from an alphabet containing m characters is stored in an m-ary tree and each string is represented by a unique path from the root to a leaf node.
Iterator: trie<T>::iterator Iterators are a very important part of STL. Trie project also has iterators to support the same.
Trie, especially Patricia trie, is widely used in forwarding table implementation for its memory efficiency. Using this structure, searching for names that share the same prefix only needs to save one copy of the shared part. It also naturally supports both exact match and LPM.
A Trie is a special data structure used to store strings that can be visualized like a graph. It consists of nodes and edges. Each node consists of at max 26 children and edges connect each parent node to its children.
The paper B-tries for disk-based string management answers your question.
It makes the observation:
To our knowledge, there has yet to be a proposal in literature for a trie-based data structure, such as the burst trie, the can reside efficiently on disk to support common string processing tasks.
187
I've only glanced at it briefly, but Shang's "Trie methods for text and spatial data on secondary storage" discusses paged trie representations, and might be a useful starting point.
22
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
