Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
1answer
87 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 ...
1
vote
0answers
21 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 ...
0
votes
0answers
20 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 ...
2
votes
0answers
150 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 ...
2
votes
1answer
93 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 ...
0
votes
0answers
185 views

How to structure a bitwise trie to do a range query

I am wondering about how to perform a range query on a bitwise trie. So say I have a trie like this. ▲ Black (any shape) is 0. △ White (any shape) is 1. ■ Black square means there is no value ...
0
votes
1answer
85 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)...
1
vote
0answers
117 views

speed up search in string array [closed]

Suppose we have sorted array of strings e.g. std::vector<std::string> or some other elements with string as key - for example std::vector<std::pair<std::string,data_type>. Normally to ...
3
votes
3answers
5k 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)...
7
votes
4answers
4k 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> ...
-2
votes
1answer
509 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 ...
3
votes
1answer
101 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 ...
6
votes
1answer
4k 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:/...
1
vote
1answer
688 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) ...
2
votes
2answers
1k 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 ...
3
votes
1answer
287 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 ...
3
votes
4answers
2k 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" ...
5
votes
2answers
993 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 ...
11
votes
2answers
4k 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 ...
19
votes
2answers
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, ...
3
votes
3answers
470 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: ...