1
$\begingroup$

I've just implemented a Trie and I thought it would be a good idea to store strings in the Trie nodes in contrast to storing single characters.

Storing strings is for sure more space-efficient and one needs to make less jumps between nodes.

However, I think it might be way slower.

For example, if you wanted to use a trie for auto-complete. So you want a method trie.get_words_by_prefix(prefix). I've added the implementations I have in mind for both solutions below.

Runtime Thoughts

  • Let $n$ be the words in the trie,
  • $m_p$ the matches for the prefix $p$
  • $l_w$ the length of the word $w$

Contains and Insert

Checking if a word is in the trie (contains) and inserting a word is in both cases in $\mathcal{O}(l_w)$. I'm not sure if there might be in practice a significant difference.

Get Words by Prefix

The amortized worst-case runtime for the char-trie is in $\mathcal{O}(m_p + l_w)$ as one has to touch every match. Non-matches are not touched due to the usage of the dictionary for the children.

The worst-case runtime for the string-trie is in $\mathcal{O}(n)$ even if there is only a single match. One can see this if there are $(n-1)$ children of the root node which are not a match but checked first.

If one restricts the complete Unicode charset to only 26 lowercase latin characters I think the string-trie might also be in $\mathcal{O}(m_p)$, but right now I'm not quite sure of this.

Question

Should a prefix tree (trie) node store only a single character or a string? Are there use-cases where one or the other solution is clearly better?

What model is usually used in practice? Are there reasonable benchmarks? Any big implementations? I have seen pygtrie, but was surprised not to find anything commonly used for Java and only some smaller things for C++.

(By the way, I am aware that there are intermediate solutions, e.g. storing two characters or having the common characters as pointers directly and uncommon stuff maybe a longer string)

Example

Suppose we have a Trie with the following words:

  • cat
  • cattle
  • tom
  • tomcat

Storing Strings: 5 nodes

.
cat
   tle
tom
   tomcat

Pythonic pseudo-code:

TrieNode(object):
    value: str
    is_word: bool
    children: List[TrieNode]

    def get_words_by_prefix(self, prefix):
        if not is_prefix(prefix, self.value):
            return []
        matched_words = []

        if self.is_word:
            matched_words.append(self.get_word())
        remainder = prefix[len(self.value):]

        for child in self.children:
            matched_words += child.get_words_by_prefix()
        return matched_words

Storing Characters: 13 nodes

.
c
 a
  t
   t
    l
     e
t
 o
  m
   c
    a
     t

Pythonic pseudo-code

TrieNode(object):
    value: str  # only one character
    is_word: bool

    # mapping from the character of the child to the child
    children: Dict[str, TrieNode]

    def get_words_by_prefix(self, prefix):
        if not is_prefix(prefix, self.value):
            return []
        matched_words = []

        if self.is_word:
            matched_words.append(self.get_word())
        remainder = prefix[len(self.value):]
        if len(remainder) > 0:
            matched_words += self.children.get(remainder[0], EmptyTrieNode).get_words_by_prefix(remainder)
        return matched_words

However, one could even do this just as a dictionary. The get_words_by_prefix would work a bit different and need to keep track of what it already looked at to generate the words again.

What I tried

I've implemented versions of both ideas (Char/Dict-Trie vs String/List-Trie) in Python and added 466,551 English words (4.9 MB).

The code is in the "trie" branch of mpu. I want to check some more things before I merge it.

                                            | Char/Dict-Trie   | String/List-Trie 
 ------------------------------------------ | ---------------- | ---------------- 
 Size in Byte                               | 548,615,536 Byte | 254,573,936 Byte 
 Building the Trie                          | 7.8s             | 15.8s            
 Checking all words if they are in the trie | 3.9s             | 29.1s

size-comparison

Word file:                       4,863,005 byte
File read into a single string:  4,863,056 byte
Word list:                      33,130,512 byte
Word set:                       45,708,872 byte
String-Trie:                   254,573,936 Byte
$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.