4
$\begingroup$

EDIT: Seems like what this structure is nothing more than a 26-bit bitwise trie, as KWillets suggested in the comments! You can think of the words we insert the trie as 26-bit Bitsets where the i-th bit indicates whether the word contains the i-the letter in the alphabet.

As I was tackling an interview problem I came up with this tree-like data structure. Actually it IS a binary tree that is maximum 26(English alphabet size) nodes deep. Basically the problem is:

There are a set of dictionary words and a set of license plate numbers. Write a code/algorithm to find the shortest dictionary word which contains all the letters in the license plate, irrespective of the order of characters

This data structure is specifically designed for the problem of finding words from a given list containing all letters from a set of letters.
I call this operation getSupersetWords().

It can also be used for finding words containing ONLY a set of letters.(In fact my empirical tests show that this is the use case giving the best performance gain over linear search (over 16 times faster on average for a list of 73k English words)).
I call this operation getSubsetWords().

To give you an example:

Lets say we have list of words = [ “cat” ,”dog” “cow”, “case”].

On query getSupersetWords([‘a’, ‘c’]) we get [“cat”, “case”].

On query getSubsetWords(['c', 'o', 'w', 'a', 't']) we get ["cat", "cow"].

How to add a string to this data structure ?
As I said earlier the data structure is a binary tree. At every level of the tree we make a decision. If the word contains the next letter of the alphabet(we start from 'a' at level 1) we go right, else we go left.
If we have made all the 'right' possible decisions for the given word we place it in the current node.(A node contains a reference list of strings).

How to answer a query from this data structure ?
Now to answer a getSubsetWords() query we traverse the tree recursively in DFS making both decisions if the query contains the character at the current letter, or 'left' if it doesn't and adding the words at the given Node to a list
(this is VERY confusing to type out...but not so much in code :/).

It sounds confusing, that's why I made a simple diagram illustrating the idea.

Assume we have a list of strings = {"a","aaa","baa","ab","bb"}.

Now If we had 'z' in the list the tree would be 26 nodes deep, but because the 'biggest' letter is 'b' We only need 3 levels. enter image description here

The circle shapes are lists of strings, the rectangles are the nodes. I was wondering if this structure is something I have 'invented' or it is already well known, (Which probably is the case :).

$\endgroup$
  • 2
    $\begingroup$ It's a binary trie of 26-bit words. $\endgroup$ – KWillets May 18 '17 at 22:42
  • $\begingroup$ @KWillets Wow. Thinking about it you are absolutely right! It IS a binary trie which I guess is quite common. There goes my dream of 'invention' lol... $\endgroup$ – Anonymous May 18 '17 at 22:48
  • $\begingroup$ Surely a trie of the sorted words in the dictionary would be faster and probably more compact. It would index into the shortest word at each node. Nodes without shortest words don't exist. $\endgroup$ – Thumbnail May 20 '17 at 11:34
7
+50
$\begingroup$

I've never seen this data structure before. However, it doesn't seem like a good choice for storing a set of words, for most purposes. I see three significant disadvantages:

  • Performance. Looking up a word in this data structure can potentially be quite slow. In particular, when looking up a word of length $n$, checking whether it contains a particular letter involves looking at all $n$ characters of the word. Therefore, traversing the entire tree (all 26 levels) might require reading the entire word 26 times. In contrast, a trie reads each character of the word only once, so might be about 26x times faster. Same for a hashtable.

  • Space usage. This might take a lot of space. I am assuming you won't construct a node unless it is needed (i.e., if it has only one child, you'll omit the node). With that optimization, the depth of the tree is at most 26 if you're using words with letters a-z. If you are storing strings in Unicode, the depth of the tree might be enormous, and in the worst case this might devolve to a data structure where the depth of the tree is proportional to the number of words in the set, and then the space usage is bad and the time for a lookup is very bad (linear in the size of the set). Without that optimization, the number of the nodes in the tree can be as large as $2^{26}$ for letters a-z, or enormous for Unicode strings.

  • Incomplete. This isn't a complete data structure. It cannot distinguish between two words with the same set of letters, e.g., between words that are permutations of each other (anagrams). Therefore, you'll need another data structure for storing the second-level sets (your circle shapes). If we had a good data structure for that purpose, why wouldn't we use it for all the words, and skip your data structure? Conversely, if you use a poor data structure for that, then your data structure inherits the limitations of that data structure: for instance, if you store all the words in the circle in a linked list, then lookups will be slow as they might need to traverse the entire list.

$\endgroup$
  • $\begingroup$ Well, my if we preprocess the word we can create a hashSet of the word's letters so letter testing is O(1). $\endgroup$ – Anonymous May 18 '17 at 20:21
  • $\begingroup$ I concur with the above points. The space usage here is crazy high. I think there are ways of fixing the incomplete part however. Also have you looked at a trie yet? I believe it to effectively be a far more space efficient version of what you wanted. $\endgroup$ – Jake May 18 '17 at 21:09
  • $\begingroup$ @Jake Interestingly enough the space usage is not so bad(It was around 100 MB for my Java implementation). Note that all 26 levels WONT be constructed if they are not needed. If the 'biggest' letter is 'b' for example we will have only 3 levels. Now that I see I've made a mistake in my descrition for the diagram :) $\endgroup$ – Anonymous May 18 '17 at 21:20
  • $\begingroup$ That's because 2^26 isn't that big. 100MB is on the order of magnitude you'd expect for the maximum number of nodes. As said before this is problematic for ASSCI and infesiable for Unicode $\endgroup$ – Jake May 18 '17 at 21:30
2
$\begingroup$

After a short research on the subject I found out that this data structure is first examined in paper by Rivest from 1976 http://epubs.siam.org/doi/abs/10.1137/0205003

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.