Trie Search

In the first part of the topic of Trie, we layed out the fundamentals of what it is and semantics of the source code. But you can’t get maximum benefit from the Trie without the functionality of searching.

The first implementation of a search will be simply searching for an exact match of the word in the trie. Consider searching for the word ‘aces’. To begin search, we would need to break down the word into individual characters, and in a indexed loop, check if our Hash contains the matching key. So our first character would be ‘a’, and we would then progress to determine if at the heighest level, the key itself is ‘a’; which we can see is true from the diagram above. We will then move to or if you prefer retrieve the child of ‘a’. We will iterate in our loop to the next character in the word ‘aces’ which would be ‘c’. As before, we will determine if at that height the key has the matching character ‘c’. Again in light of the diagram that proves true and we will rinse and repeat, and thus find the ‘aces’ character by character. However, if in the process instead of ‘e’ (in aces), we find a key of ‘k’, that would mean the word does not exist, and we would return nil.

Here’s the code to which this would make more sense.

private
    def search_node(string)
      children = @root.children
      trienode = TrieNode.new
      string.split('').each_with_index do |char, index|
        if children.has_key?(char)
          trienode = children[char]
          children = trienode.children
        else
          return nil
        end
      end
      trienode
    end

We can also apply another form of search, that is ‘starts_with’ to find a matching prefix in a Trie of words. For example, our Trie has ‘aces, acer and actor’, we would want to determine if the following prefix ‘act’ exists. The concept is exactly the same as above with the word search as you will see in the code below. I’ve included all the pieces including Rspec.

context 'search' do
    before :each do
      @trie.insert('ace') # initial prefix
      @trie.insert('acer')
      @trie.insert('aces')
      @trie.insert('actor')
    end

    it 'should determine if a word exists in the trie' do
      expect(@trie.search('aces')).to eq true
    end

    it 'should return false if the word does not exist in the trie' do
      expect(@trie.search('ant')).to eq false
    end

    it 'should determine if there is any word in the trie that starts with the given prefix' do
      expect(@trie.starts_with('act')).to eq true
    end
  end

The full code:

def search(word)
      trienode = search_node(word)
      return true if (not trienode.nil? and trienode.is_leaf)
      false
    end

    def starts_with(prefix)
      return false if search_node(prefix).nil?
      true
    end

Leave a Reply

Your email address will not be published. Required fields are marked *