A tree-like data structure used to hold an associative array, also called a Prefix Tree.
3
votes
3answers
228 views
Building prefix tree from dictionary, performance issues
I'm trying to build a prfix tree. So, using the following dictionary 'and','anna','ape','apple', graph should look like this:
I've tried 2 approaches: using ...
3
votes
0answers
51 views
Inserting nodes into a trie data structure
I have a recursive algorithm that inserts nodes into a trie data structure but it seems to be running not well and takes over 10 mins to complete on a data set of about 1 million. All nodes contain a ...
3
votes
1answer
72 views
Char Trie and scanner in one
This is from the Resin codebase. It is fast at lookup but I could use some help making it faster at buildup. Loaded with 210K words, it looks up pretty much any node and its descendants in zero time. ...
1
vote
0answers
43 views
1
vote
0answers
76 views
Given an input list of words and a string, output every different set of words that can make up that string
Problem:
Given an input list of words and a string, output every different set of words that you can find in the string from the given words. For example, input: word_list = ['dog', 'cats', 'sand',...
3
votes
0answers
52 views
D trie implementation
I just started to learn D and ported my a bit over-templated trie. It looks way better than on C++.
I'm sure there is still room for improvement and to make it be real D code.
I checked an the array ...
4
votes
1answer
60 views
TrieSet with Wildcard Search
What I'm ultimately trying to accomplish is a tool in which I pour some documents. Then I mark #x documents as desired and #y documents as undesired.
My tool now is to analyse and compare the ...
6
votes
2answers
71 views
Unicode-capable symbol table (N-way search tree with hash buckets)
As in my previous question, this module is coupled with its own testing framework.
As a symbol-table for a Unicode-capable programming language interpreter, I decided to combine the 3 types of ...
7
votes
2answers
350 views
Trie key/value store implementation comparing with HashMap
I have implemented a Trie-based concurrent key/value store using hashcode similar to HashMap.
It is something like, if your ...
5
votes
1answer
104 views
Auto-complete using Tries in Python with OOP
I am working on a problem to develop auto-complete functionality to practice different applications of Tries. The auto-complete function will return all the possible words in the wordlist given a ...
6
votes
1answer
224 views
Checking for spelling errors with a trie
I have been lately working in my C++, and I finished up this trie, and I want to know how my C++ is looking so far.
Node.hpp
...
2
votes
1answer
207 views
Implementing a Trie in Python - follow-up
This is a follow-up of Wikipedia Trie pseudocode in Python
Code quality improvements
find has been fixed and a regression test ("bana" vs "banana") has been ...
6
votes
2answers
101 views
Wikipedia Trie pseudocode in Python
I translated the Wikipedia pseudo-code into Python code (little changes only were required), but I do not like the end result, as it looks like C with all those while loops and counters.
The fact is ...
7
votes
2answers
85 views
Trie for lowercase words
I need to develop a dictionary program so I used a trie data structure to implement it. I have created a array of object with size of 26 - so each object of class ...
6
votes
1answer
160 views
Trie data structure in Java
I have implemented a trie data structure in my way, though it is very similar to what major implementations I found but would like to get it reviewed by experts.
I don't see the need to store ...
5
votes
1answer
107 views
Cache aware, Key/value dictionary based on 4-bit(16-slot) Trie (Prefix Tree), with deferred allocation
Deferred allocation is a memory optimizing trick of using the Node** as Node* when there is only one item in the "bucket". Thus "...
4
votes
1answer
933 views
C++ Trie Implementation
I recently tried a basic C++ implementation of a Trie, and was looking for some feedback on my code style/choices. In particular I was wondering if I'd made the right choice spitting the program up ...
8
votes
1answer
531 views
Java Trie structure
I recently have been working on a Trie in Java. I have looked at the related posts here on Code Review to try and enhance my code, but I do have some methods and constraints not present on other posts....
2
votes
2answers
203 views
Trie structure with three classes
I have implemented a trie in Java and I would request you to review it and suggest improvements or new features.
The code is split into 3 files.
TrieNode (...
2
votes
2answers
500 views
Implementing a Trie in Python using lists alone
I've been working on implementing a Trie in Python for educational purposes. I tried implementing one using dictionaries and I was successful.
The structure of a trie with the words ...
3
votes
1answer
1k views
Trie Implementation in Java
I am trying to implement a Trie class in Java which just supports insertion and searching operation up until now. I think it works perfectly on the several examples ...
17
votes
4answers
396 views
Name Filtering using a Trie
This question suggests a different (improved?) implementation for searching/filtering names based on a search query. This is based on the question here: Name filtering in Java
A Trie allows the ...
6
votes
2answers
157 views
A reversed-string Trie data structure
This is a simple Trie data structure for strings, except it puts the strings into the structure backwards.
The insert method simply iterates over chars from the string-to-be-inserted backwards, and ...
3
votes
1answer
840 views
Autocomplete Trie Optimization
I'm currently playing with the Typeahead problem on Talentbuddy. There are already 2 questions on this subject (Typeahead Talent Buddy and Typeahead autocomplete functionality challenge), but none of ...
4
votes
1answer
104 views
Writing a faster mutable trie
I am implementing a mutable trie. I tested and it produces correct results. However, it is very slow. I benchmark it against plain old Data.Map, which is more than ...
8
votes
2answers
4k views
Java Trie Implementation
I am creating a Trie class in Java, and am wondering what else can be done to make it even better. I am hoping to add concurrency to speed querying up.
...
3
votes
5answers
5k views
Loading dictionary using trie in C very slow with large data set
The code below works for very small dictionary files I used to test (two words). However when I run this using a more typical dictionary file, my machine slows to the point of near crash. I would ...
5
votes
1answer
3k views
Spell Check and Trie implementation
I have written this code for an Edx course called CS50x (a beginner course).
This problem set required me to write a program which:
loaded a dictionary into some sort of data structure (I choose to ...
2
votes
1answer
308 views
Trie SPOJ Problem - PhoneList TLE
In this problem you are given input of phone numbers and you are supposed to determine whether any number is the prefix of another. I have an addchild method that ...
4
votes
1answer
309 views
Trie string iterations
\0
/ \
a b-a-t-s
/|\
m s t
which contains [am, as, at, bat, bats]
The goal I'm trying to reach is to iterate through the trie to find if there's a next ...
5
votes
2answers
7k views
Trie (tree form) in Java
I created a Java Trie as part of a project someone challenged me to do. I'm not sure that this is the most efficient way to go about producing a Trie, I know that this works but I was hoping someone ...
0
votes
1answer
750 views
Trie - code review request for improvement
Ok, code reviewers, I want you to pick my code apart and give me some feedback on how I could make it better or more simple.
...
3
votes
2answers
148 views
Improving Trie Implementation
This is an implementation of a trie, that I will be using on a code editor to parse keywords from a given programming language. I decided to use a trie when I asked this question, and the ...
2
votes
1answer
2k views
Next word prediction using n-grams
I have written the following program for next word prediction using n-grams. The data structure is like a trie with frequency of each word.
Any suggestions are welcome, but I am more concerned about ...
11
votes
1answer
4k views
Simple trie implementation in JavaScript
After experimenting with a sorted trie implementation in C, I felt that I understood tries pretty well, but was having trouble explaining how they work. Since the C code was based on existing code, I ...
1
vote
1answer
1k views
Sorted trie implementation in C
I wanted to store some dictionary data (key/value pairs of strings) in C, and decided to use a trie.
I found what looks like a good implementation here, along with some nice notes.
In this ...
8
votes
3answers
1k views
Readability and Performance of my Trie implementation
As an interesting exercise in Python 3.3, I implemented a Trie (also known as a Prefix Tree).
Example usages
Create from list of key-value-tuples
...
3
votes
1answer
1k views
delete a key in a trie
To delete a key from a trie, there are four cases:
For the explanation of trie data structure, please check
the following link:
http://www.geeksforgeeks.org/trie-insert-and-search/
(1) Key is not in ...
1
vote
1answer
459 views
Is this a valid implementation of trie Data structure?
i am trying to learn Trie Data Structure and just implemented it without giving much attention to the code standards , its a raw implementation , can you guys help me to understand whether this ...
10
votes
2answers
11k views
Implementation of Trie data structure accommodating varying number of children
I've used the Trie data structure to solve the following problem:
Given an array of words, print all anagrams together. For example, if the given array is {"cat", "dog", "tac", "god", "act"}, then ...
0
votes
1answer
535 views
use trie data structure to solve the problem of clustering anagrams
Given an array of words, print all anagrams together. For example, if
the given array is {“cat”, “dog”, “tac”, “god”, “act”}, then output
may be “cat tac act dog god”.
The following is my c++ ...
8
votes
1answer
3k views
A trie implementation for left to right wild card search
I was working on a task to implement auto suggest from an array of couple of thousands of strings.
Ofcourse the first and the easiest implementable was to go through each element and do a[i]....
2
votes
1answer
135 views
Serialising missing values in trie
There are two aspects to this question that are inter-related.
Change I've made to the trie module in python (PyPI, GitHub) to make it serialisable (and ...
