0
$\begingroup$

Tries seem to be good at storing and querying small strings, like keys to a dictionary.

What I would like to know is if there is anything better for storing large strings such as a 1,000 page document of text. I have heard of Inverted Indexes, which seem to just add a layer of nesting to the tries: instead of building a character trie, you build a word-trie. I am not sure if this is the technique you should follow: for larger strings just build a layer of nesting/abstraction and do a trie at that level. So you could have perhaps a character-level trie for words, a word-level trie for documents, and a concept-level trie or some semantic-like trie for document collections. Something like that.

Or if not that, I would like to know what is the general approach for storing things like an arbitrary collection of BigInts ranging from like $-10^{50}$ to $10^{50}$, or an arbitrary collection of documents from a tweet to 10,000 pages of text. So that it is searchable by keyword, or by min/max, or other common queries. Wondering what the general approach is to solve a wide range of query problems like these, and if Tries can handle it well or not. If not, what some good data structures are to look into.

Another example I was thinking of is say you wanted to query by ID. Usually you would just have a 32-bit ID or something like that, with O(1) lookup from a hashtable. But say you had the ID be 10,000 32-bit segments, essentially the ID was a complete document. Then I can't see what you would do. If you had one ID be 2 32-bit chunks, and another ID be 10,000 32-bit chunks, and if the trie was a binary trie, then one would have 64-nodes, the other would have tens of thousands of nodes which is inefficient. I don't see how to simplify this sort of situation.

$\endgroup$
  • $\begingroup$ Please pick one problem statement. Right now I see three: (1) storing strings, (2) storing arbitrary collection of bigints, (3) storing something with IDs. Then edit your question to focus on that one situation. Also, do you want to store a single string or a collection of strings? What operations do you want to be able to perform on the string or on the collection? Please edit the question to specify that. $\endgroup$ – D.W. Feb 7 at 3:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.