Databases
StackOverflow2013
Postsdbo
POPerformance issue while getting all the words with common prefix in Prefix Tree
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POPerformance issue while getting all the words with common prefix in Prefix Tree
    primarykey
    data
    text
    <p>I have a prefix tree to store a huge collection of words. Right now, if i want to find all the words with the common prefix say "a", I first retrieve the first node containing a and then exhaustively search in the Depth First fashion in the children nodes of the first node. While this idea looks naive and straightforward, it in-fact is pathetically slow if the possible number of words with common prefix is VERY HIGH(>20K). Is there some other way to retrieve all the words starting with a common prefix efficiently? Or should i adopt some other data structure? Thanking you in advanced.</p> <p><strong>EDIT1</strong> Basically I am creating a full word by visiting every node and adding character incrementally. All the words are later stored in a vector container. And yes, i have recursive implementation. </p> <p><strong>EDIT2</strong></p> <pre><code>vector&lt;int&gt; getNonEmptyEdgeIndices(Node* parent) { vector&lt;int&gt; indices; for(int i=0; i&lt;EDGE; i++) { if (parent-&gt;edges[i] != NULL) { indices.push_back(i); } } return indices; } vector&lt;string&gt; getSubsequentStrings(vector&lt;string&gt; wordsStartingWith, Node* node, string prefix) { vector&lt;int&gt; indices = getNonEmptyEdgeIndices(node); // push the word to the container if node is a leaf if (indices.empty()) { wordsStartingWith.push_back(prefix); return wordsStartingWith; } // if frequency is set in node, push the word but still continue recursion if (node-&gt;frequency != 0) { wordsStartingWith.push_back(prefix); } // look all the children of the node for(unsigned int i=0; i&lt;indices.size(); i++) { string newPrefix = prefix + getNodeChar(indices[i]); Node* child = node-&gt;edges[indices[i]]; // recursively get the prefix for all children wordsStartingWith = getSubsequentStrings(wordsStartingWith, child, newPrefix); } return wordsStartingWith; } vector&lt;string&gt; Trie::getWordsStartingWith(string prefix) { vector&lt;string&gt; wordsStartingWith; Node* lastNode = getLastNode(prefix); if (lastNode != NULL) { wordsStartingWith = getSubsequentStrings(wordsStartingWith, lastNode, prefix); } return wordsStartingWith; } </code></pre> <p><strong>EDIT 3</strong> SOLVED!!! There was actually a problem with my implementation. I was passing this huge vector string container in recursive calls which was in-fact the problem. Thank you everyone for your kind advice.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USconsumer
    1. USconsumer
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COSome implementation details would be good. Prefix trees are meant to be good at this, they can do it in linear space and time. Potentially your issue is that you are copying all of the strings out of the tree to generate an array before doing anything with it? Perhaps instead you want to write an iterator that let's you do what you want with each element without copying them all?
      singulars
      1. POPerformance issue while getting all the words with common prefix in Prefix Tree
      1. USamnn
    2. COCan you share the code that you tried? It might be the code and not the data structure that can be improved.
      singulars
      1. POPerformance issue while getting all the words with common prefix in Prefix Tree
      1. USGlenn Teitelbaum
    3. COHmm, @asQuirrel: you are pretty right. I am building string by visiting every edge. Probably I should write an iterator. I will implement that part and come back.
      singulars
      1. POPerformance issue while getting all the words with common prefix in Prefix Tree
      1. USconsumer
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload