Questions tagged [trie]
A tree-like data structure used to hold an associative array, also called a Prefix Tree.
1,108
questions
0
votes
0
answers
25
views
Find string match among a large list of (prefix, suffix) pairs [closed]
Consider a large list of (prefix, suffix) string pairs. For each pair, len(prefix)+len(suffix) doesn't exceed L (21 in practice).
We will be getting many query strings that can be answered in batches ...
2
votes
1
answer
46
views
CS50 Trie Week 5: check function not working
I have been trying to complete the trie practice problem from the CS50 course. The check function that I wrote must check whether the user input is found within the trie that has been created in the ...
-1
votes
0
answers
30
views
Finding Compound Words in A Text File Using A Trie in the Fast Amount of Time
I want to find all of the compound words in my text file in the fastest amount of time. I have completed my code so that my trie works and all 173,000 words get entered into the trie, but I'm not sure ...
1
vote
0
answers
54
views
Finding Compound Words in A Text File of 150,000+ Words [closed]
I have to find all of the compound words in a text file. This file contains almost 200,000 words and I am trying to implement this in the least amount of time.
So for example, the text file contains ...
0
votes
1
answer
63
views
How does this code work and not crash or seg fault?
So this question is a bit different, the code works I just don't know why or how.
I'm taking the CS50 course and I'm solving this practice problem aiming at training us at searching tries databases. ...
0
votes
0
answers
32
views
Indexing JSON Commands with a tree model of GTK+ GUI
I have an idea that I want to implement but have no idea on how to proceed or an algorithm for that.
I have a json file that has a list of strings as commands
In the Client Side of the GUI, I use GTK+...
0
votes
0
answers
51
views
What's the fastest way for Longest Prefix Match algorithm?
I am looking for an algorithm that does a fast lookup on the longest prefix match that can be used to match an input number(between 6 and 16 digits long) to a large set of prefixes (about 200k entries)...
0
votes
0
answers
43
views
When implementing Trie Data Structure using smart pointer is it necessary to use shared pointers?
Link to gfg: Trie Data Structure using smart pointer
I came across this implementation of Trie Data Structure using shared pointers. But I don't understand the purpose of using shared pointers.
Can we ...
0
votes
1
answer
53
views
NULL values are being reassigned to garbage at runtime
I have a C program to implement of Trie in which each not stores some data (see below). The trie should use strings in it's branches to arrange data (ie as keys) with integer data at each terminating ...
0
votes
1
answer
27
views
Unexpected error in Trie delete string method
I am trying to build a method to delete a string from Trie , when i run the code it says the following error despite the fact that everything is correct ( according to me ) whats the error in my code
...
-2
votes
1
answer
89
views
Maximum XOR with all possible subsets of an array with a specific integer
Given an array of integers P = [P1, P2, ...] and a function F(M) that returns the XOR of all integers present in set M. If M is empty, then F(M) = 0.
The task is to find the maximum possible value of ...
1
vote
1
answer
34
views
Is there an existing Data Structure like this? ( A modified Trie )
I have been working on trie data structure recently and an alternative immediately struck to me.
For example :
This is a trie with 2 words : football and goofball.
This is the alternate data structure ...
0
votes
0
answers
60
views
How to use marisa-trie in Python for nlp processing
I'm working for a NLP function to store tokens in a trie.
This my well working code for tokenization:
import spacy
def preprocess_text_spacy(text):
stop_words = ["a", "the",...
2
votes
1
answer
74
views
How to create slice of LPM trie record for IPs/CIDRs
I am trying to use the BatchUpdate and BatchDelete API from https://github.com/cilium/ebpf/blob/master/map.go#L952-L1038. from my understanding, I need to create slice of LPM trie of IPs/CIRDs, for ...
0
votes
1
answer
37
views
How to iterate over each word in a Trie using __iter__()and __next__() functions and generators in Python
I have a Trie that is structured below. I am trying to write an iterator and next function that will iterate over each word in the Trie and then raise StopIteration once it is completed but I'm ...
0
votes
0
answers
19
views
Trie class method is not working in search auto complete
I Am triyng to autocomplete and also want pass category as parameter in url. I have two table
1. First table name product_search_history and it has column id,catuid, search_term, search_date,status
2. ...
-1
votes
1
answer
47
views
c++: segmentation fault for Trie data structure [closed]
I am a noobie to c++ and I'm recently learning trie data structure. As I was implementing the header file for the Trie, I've encountered segmentation fault that I cannot resolve. I used the typical ...
0
votes
0
answers
61
views
How to calculate the time complexity for Leetcode's Longest Common Prefix with a solution using Tries
I am trying to improve my problem solving skills, and have solved problem #14 in Leetcode "Longest Common Prefix" using the Trie data structure.
My solution runs in 106ms and beats 42.91%. ...
0
votes
0
answers
20
views
How to split the sentence where there is no space between in the sentence
How Google splits the sentence entered on the Google search bar into meaningful words
For example Whatispython? Into
What is python?
Which algorithm to use for splitting the sentence to meaningful ...
0
votes
3
answers
73
views
Python Trie implementation - Inserting elements into a trie recursively
I have implemented a trie tree using a list in Python which stores words.
I am trying to write a function that insert words into a trie recursively.
Here my trie class and the function insert() :
...
0
votes
0
answers
25
views
How to implement/ deploy a TRIE made with Python?
I have created a TRIE based structure for a search algorithm for the company I work for, and each node in the TRIE stores some data related to the product it maps to, for example, a node (when ...
0
votes
0
answers
20
views
How to solve this ==31==error Address sanitizer heap buffer overflow error?
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
char memo[10];
int count[500]={0,};
typedef struct Trie{
int count;
struct Trie * next[26];
}Trie;
void ...
0
votes
1
answer
62
views
Is there an alternative to Trie for my needs?
I have a program that requires an ID to load a template.
The template is assigned based on the ID. Each template has a key, e.g. tx. IDs that contain this pattern will have this template assigned, e.g ...
0
votes
0
answers
204
views
How do I implement a memory arena allocator to reduce memory request calls in a trie-based spell checker?
As part of the cs50x course, I made a trie-based dictionary spell checker that passes all of check50's tests as well as valgrind so no memory errors. Now I'm trying to implement a memory bucket to ...
0
votes
1
answer
47
views
why the pointer is not incrementing at line 27
i am implementing the trie data structure, why my pointer is not incrementing at line# 27. all the characters are getting into forst node only.
this is my code
class Trienode:
data:str
next:...
1
vote
1
answer
177
views
Why isn't bitwise trie a popular implementation of associative array
I have to store billions of entries with Int64 keys in an ordered map.
If I use a usual BST then each search operation costs log(N) pointer dereferencings (20-30 for millions to billions entries),
...
0
votes
0
answers
118
views
How to specify a lifetime for a borrow in a struct in Rust?
I have a Trie struct whose nodes have children which are also nodes:
pub struct Trie<'a, T: marker::Copy> {
nodes: [Option<TrieNode<'a, T>>; MAX_NODE_LEN],
min_len: usize,
...
1
vote
0
answers
36
views
How would a patricia tree look like after adding a word that starts as the substring of another but has additional letters?
Take this trie as example:
I want to add the word "luan" to this representation, but luan takes 20 bits to represent, while lua takes 15. So, they "differ" from each other on the ...
0
votes
1
answer
19
views
Unset element from trie using reference
I am having some difficulties to delete empty parent node if empty from a trie. I can correctly identify the node that has the value 3, but then I cannot unset nodes that do not have any children.
...
0
votes
0
answers
64
views
Which products or database use Trie data structure and for what purposes?
Wanted to understand the usage of Trie data structure. I have seen that for Type ahead suggestions Trie is good.
My understanding was that for distributed searching as well Trie is used. But I learnt ...
0
votes
0
answers
14
views
Data structure to store, update and search very large size of Gazetteers?
I have a set of Gazetteer which contains tens of millions of entities, and I need that to do entity spotting in texts, and the Gazetteer set would be updated if necessary.
Is compressed trie the best ...
0
votes
2
answers
131
views
Algorithm to find all duplicate sequences of tokens in a long string
Let's say I have a really long string consists of 10^6 tokens (for simplicity, token is a space-separated word, so this string is splitted to list of tokens)
now I need to find all possible duplicated ...
0
votes
0
answers
62
views
Longest Common Substring from Trie
i'm trying to obtain the longest common substring from two strings and have coded a trie, but im not too sure how to obtain the longest common substring based on this trie. Could someone please help, ...
-1
votes
1
answer
32
views
why my code doesn't change the head value in c# or i have to use somethings like pointers?
ok, guys, so I was doing the ReplaceWord problems from leetcode in c# ! and I had to initialize a prefix tree. the reason why I use c# that because it has split method which c++ doesn't have.the ...
0
votes
0
answers
50
views
Handle and search large json file (android)
I have a json file that have a large (~200K) data set (non-complex objects with 4 fields). I should do prefix search for some of its field.
There wont be any retrofit/api call, pagination stuff, or ...
0
votes
1
answer
27
views
Why are the Trie Functions unable to produce my desired output?
Your task is to create a trie system that is hosted online with a global state that supports multiple concurrent clients and the following operations:
Add keyword to trie
Delete a keyword from trie
...
0
votes
1
answer
41
views
What is the problem with fill() here ? I used normal for loop for assigning NULL and it worked , with fill() it was giving error
The code below is a Trie implementation in C++. Kindly checkout what is the problem in using fill(). And if any suggestions improving my implementation are welcome
Commented fill() in the TrieNode ...
0
votes
2
answers
122
views
How to return an int within a trie in python
I'm trying to search for a word within my trie data structure and if it exists in the trie, return the word and its frequency.
This is what the trie looks like:
{'c': {'u': {'t': {('e', 10): True, ('s'...
-1
votes
5
answers
278
views
how to write a function that returns all elements with same attribute from domtree?
I saw somewhere that this question was asked in a faang interview and I cannot come up with an optimized solution or find it anywhere. So the question basically wants us to write a function that ...
1
vote
0
answers
151
views
Difference between a patricia trie (radix tree with r = 2) and a binary trie?
I am trying to consolidate my understanding of the difference between a patricia trie (radix tree with r = 2) and a binary trie. As far as I can see the implementation of a binary trie and a patricia ...
0
votes
0
answers
75
views
How to add callback function in Tries (prefix Tree) python
I am wondering how to implement callback function (watch) based on current function in prefix tree
path is a / separated string describing the node. Example /animals/dogs/german_shepard.
Values are ...
-1
votes
2
answers
69
views
What is wrong with my trie suggestion algorithm?
I am coding an algorithm that uses the trie data structure. Basically, if input is "he", it will return ["hello","help","held","hen",...
0
votes
1
answer
57
views
Leetcode Testing of Trie Results Don't Match Local NodeJs Output
Description:
I implemented a [Trie on Leetcode][1] and when I test it locally, running Node v16.15.1, the output of the test case I get does not match the output on LeetCode.
I ran the initial test ...
0
votes
0
answers
33
views
Listing suggestions in a phonebook
Implement a phonebook where you can insert a contact, search for a
contact, also provide suggestions based on user's input
The insertion and search can be done using a simple hashmap.
This is a ...
-3
votes
1
answer
244
views
How do I implement code to search word in a Trie?
Code: Search word in Trie
Implement the function SearchWord for the Trie class.
For a Trie, write the function for searching a word. Return true if the word is found successfully, otherwise return ...
0
votes
1
answer
83
views
How to paginate a trie, so you can find 100 words matching prefix in the trie, starting at a paginated offset?
I am using a trie made to work on alphabets/scripts from any language.
class TrieNode {
constructor(key) {
// the "key" value will be the character in sequence
this.key = key;
...
1
vote
2
answers
137
views
How to find all words that "contain" or "unscramble" an input string using a Trie?
Here is a trie made to work on alphabets/scripts from any language.
class TrieNode {
constructor(key) {
// the "key" value will be the character in sequence
this.key = key;
// ...
-2
votes
1
answer
326
views
Design In-Memory File System - Python - Trie - Leetcode Error
I am trying to solve the below leetcode problem
Design a data structure that simulates an in-memory file system.
Implement the FileSystem class:
FileSystem() Initializes the object of the system.
List ...
0
votes
1
answer
129
views
Get words from trie containing specific letters
I'd like to retrieve words from a trie that contain specific letters. For example: List all words that contain the letters [a, g]. If my trie has the words ["APPLE", "EGG", "...
1
vote
1
answer
94
views
Trie is Using Too Much Memory
I'm trying to get all the words made from the letters, 'crbtfopkgevyqdzsh' from a file called web2.txt. The posted cell below follows a block of code which improperly returned the whole run up to a ...