A tree-like data structure used to hold an associative array, also called a Prefix Tree.

learn more… | top users | synonyms

3
votes
3answers
164 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
40 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
66 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
36 views

Trie implementation

Are there any suggestions about this? ...
1
vote
0answers
52 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', ...
3
votes
0answers
32 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
41 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
70 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
320 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
96 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
197 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
154 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
92 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
84 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
152 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
102 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
667 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
492 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 ...
2
votes
2answers
191 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
449 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 ...
16
votes
4answers
389 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
155 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
800 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
96 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
4k 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
296 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
289 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
6k 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
740 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
143 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
450 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
527 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 ...
2
votes
1answer
134 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 ...