Questions tagged [trie]
A trie is a data-structure used for matching strings in a set of strings using a tree like structure. It can be either a prefix or a suffix trie. This tag shall not be confused with trees.
24 questions
-2
votes
1
answer
145
views
Time complexity of an HAMT
A Hashed Array Mapped Trie has a time complexity of log32(n).
According to the paper referred by this implementation, the 32 comes from the cardinality of the alphabet, which in this case is a 32 bits ...
- 163
1
vote
1
answer
105
views
How to reuse parts of a Trie data structure (like a Trie DAG)?
I am playing around with a cross-language spell-check sort of thing, and am still in the prototyping/ideation phases. Basically I have thought of something like a Trie data structure, but I keep ...
- 2,787
2
votes
3
answers
1k
views
Efficient way to detect duplicates in a stream of up to 20M numeric strings
I have a stream of documents, each having an ID which is a 64 bit unsigned long given as a (maximum length is 20) string.
Sometimes an ID appears multiple times in the stream. I don't want to process ...
- 1,139
1
vote
1
answer
406
views
Ternary search tries vs. r-way search tries with hashtable child node list
I was watching the Coursera algorithms lecture series' portion on tries. R-way tries are introduced first, where each node has an array the size of the possible character space (R) with potential ...
- 273
1
vote
1
answer
2k
views
How do I store a trie in memory in a Spring Boot Application?
I have a spring boot application, that simply does, takes a set of characters and lists out possible english words.
Now, as everyone knows , its fairly easy, build a trie data-structure to load up a ...
- 127
2
votes
1
answer
956
views
Explanation of how to resolve Hash conflicts in HAMT or hashtables in general
I am working on trying to understand HAMT and now am uncertain generally what to do when you run into a conflict in a hash. All I understand so far is you create a list to append the keys to, but I ...
- 259
2
votes
0
answers
37
views
How to build a HAMT with multi-index keys
By that I mean, forming a Hash Array Mapped Trie with 2 or more indexed fields, such as a User model by email and location name, or email + username + last logged in + isActive. Basically any ...
- 259
0
votes
0
answers
114
views
How to combine multiple Tries for complex searching and filtering across tables?
Say I have a database with 100 tables. Scattered throughout the tables are some string columns for short things that could be considered usernames/tags/categories/hashtags/addresses/placenames/other ...
- 259
6
votes
1
answer
1k
views
Autosuggest at scale - trie sharding
While reading on the design for autosuggest implementation on large scale systems (like google), I'm able to understand the usage of trie and how top "n" terms are stored at each node to quickly ...
- 69
2
votes
1
answer
358
views
trie iteration should include root?
I'm working on a trie data structure. My simple, initial understanding: trie data structures require a fixed root node. This node cannot be deleted.
When iterating through all nodes in a trie (in ...
- 371
0
votes
1
answer
984
views
Limitations of Tries in Comparison to B-Trees for a Database
I am wondering about how range queries work, and the standard solution is to use B+trees. However, I am a fan of tries as a general data structure and would like to know if they (or variations of them)...
- 2,787
6
votes
3
answers
14k
views
What is the space complexity for inserting a list of words into a Trie data structure?
There is a quite a bit of information about the time complexity of inserting words into a Trie data structure, but not a whole lot about the space complexity.
I believe the space complexity is O(n**m)...
- 605
10
votes
5
answers
10k
views
Is it bad practice to read large file in constructor?
So, I am trying to create an English language trie data structure implementation in C++. I have created a Trie and TrieNode class. The TrieNode class takes in its constructor a vector<string> ...
- 724
-2
votes
1
answer
615
views
How do I implement autocomplete functionality for a big website? [closed]
I am looking to implement a custom autocomplete functionality for a travel website with huge amounts of data. I am thinking of implementing it using a trie. But how do I handle it if the data cannot ...
- 139
3
votes
1
answer
132
views
PHI, NoSQL, and searching
I am working with a system that is using NoSQL (Azure Table Storage) primarily to house its data. Unfortunately, the work also involves billing and medical records - meaning the data itself will need ...
- 110k
9
votes
1
answer
8k
views
Efficient data structure to implement fake file system
I want to implement a data structure that will hold the paths of directories, sort of fake file system.
Input:- I have a text configuration file containing the paths as follows
...
C:/temp1
C:/...
- 99
2
votes
1
answer
2k
views
Best Data structure for implementation of dependent drop-downs
I want to implement dependent drop-down feature on a web page in my website containing the following drop-downs:
User's group name
Group events (dependent drop-down)
Locations (dependent drop-down)
...
- 21
4
votes
3
answers
3k
views
Finding common prefixes for a set of strings
I am trying to find common prefixes for a sorted set of strings. i.e. if the following strings are given:
AB123456
AB123457
ABCDEFGH
ABCDEFGX1
ABCDEFGY
XXXX
then my function should return three ...
- 141
3
votes
1
answer
861
views
Data structure for traversing hierarchical hostnames
So, quite often I'll come across a situation where I'd like to process hostnames in a hierarchical manner.
For example, given a hostname "foo.bar.baz.example.com", I might want to compare it against ...
- 421
3
votes
4
answers
3k
views
fast n-gram access data structure
TL;DR
Is there a data structure that'd quickly let me match words at any point (e.g., 'foo' matches 'foobar' and 'zoofoo'), and, ideally, returns a list of "characters that show up after the needle" ...
- 454
5
votes
2
answers
1k
views
Fast set indexing data structure for superset retrieval
I am given a set of sets:
{{a,b}, {a,b,c}, {a,c}, {a,c,f}}
I would like to have a data structure to index those sets such that the following "lookup" is executed fast: find all supersets of a given ...
- 161
15
votes
2
answers
6k
views
Efficient Trie implementation for unicode strings
I have been looking for an efficient String trie implementation. Mostly I have found code like this:
Referential implementation in Java (per wikipedia)
I dislike these implementations for mostly two ...
- 2,451
22
votes
2
answers
2k
views
What is an Aguri tree?
Going through some old Hacker News items, I came across a post from a user that said
Aguri trees, which marry a bounded-size radix trie (like you'd use in a software routing table) to an LRU list, ...
- 458
3
votes
3
answers
550
views
What is the name of this tree? [closed]
It has a single root and each node has 0..N ordered sub-nodes . The keys represent a distinct set of paths. Two trees can only be merged if they share a common root. It needs to support, at minimum: ...
- 699