# DictionaryMatcher (#103)

**URL:** <https://www.ruby-forum.com/t/dictionarymatcher-103/77849>\
**Category:** Ruby\
**Created:** [December 1, 2006, 12:19am UTC](https://www.ruby-forum.com/t/dictionarymatcher-103/77849 "2006-12-01T00:19:52Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [December 1, 2006, 12:19am UTC](https://www.ruby-forum.com/t/dictionarymatcher-103/77849/1 "2006-12-01T00:19:52Z")

</div>

As stated in the quiz, this question comes up quite a bit. There are a  
few ways  
to address including a fairly simple approach. Let’s examine Jamie  
Macey’s  
rather short solution for an example of that:

```
class DictionaryMatcher < Array
 alias_method :===, :=~
 alias_method :match, :=~

 def initialize(default = [], options = nil)
   super(default)

   unless options.nil? or options.is_a? Fixnum
     options = Regexp::IGNORECASE
   end
   @regexp_options = options
 end

 def =~(string)
   self.map{|e| Regexp.new(e, @regexp_options) =~ string }.compact.min
 end
end

```

Jamie’s idea is easy enough to follow: DictionaryMatcher is just an  
Array of  
expressions and we can hit the String with them one at a time to find a  
match.  
This code even has an advantage over many of the solutions in that the  
individual expressions themselves can be arbitrarily complex (full  
regular  
expressions).

The big downside to this approach though is speed. Unfortunately, it’s  
a pretty  
big downside in this case because if you had been dealing with a small  
number of  
matches to begin with, you probably wouldn’t have needed a  
DictionaryMatcher.  
The main reason performance is bad is that all expressions must be  
tested, to  
find the match that occurs first in the String. All that context  
shifting in  
and out of the regular expression engine just takes time.

If we’re going to get around that, we need a clever way to store the  
terms we  
are looking for and a custom match process that takes advantage of that  
data  
structure.

The structure used by the majority of the solutions to store the words  
is called  
a trie or prefix tree. Louis J Scoras wrote a solution using Trie  
objects, and  
even taught them how to display themselves. This might help you see how  
this  
works. Have a look at this example (with corrected indentation):

```
>> t = Trie.new
=>
>> t["cat"] = true
=> true
>> t["cab"] = true
=> true
>> t["cate"] = true
=> true
>> t["bob"] = true
=> true
>> t
=> b =>
     o =>
       b =>
         value: true
   c =>
     a =>
       b =>
         value: true
       t =>
         value: true
         e =>
           value: true

```

This structure is similar to a Hash, in that it has keys and values.  
(Values  
are only used to indicate word boundaries, so we will leave those as  
true and  
focus on the keys.) Where a Trie differs from a Hash is how it stores  
the keys.

The key “cat” isn’t stored as one complete String, instead it is stored  
as a  
separate “c”, “a”, and “t”. Those individual letters are nested beneath  
each  
other in the structure to indicate order. “c” comes before the “a”  
beneath it,  
which comes before the “t” beneath it.

Now, to add “cab” or even “cate” into the structure just involves adding  
in the  
new letters at the right depth. “bob”, on the other hand, begins a new  
tree,  
since it starts with a different letter.

This structure can be used to make rather efficient large matches.  
Where a  
Regexp has to ask does “cat”, “cab”, or “cate” match here, the tree  
version just  
checks to see if the “c” matches here. When it does, more letters still  
need to  
be checked, but when it doesn’t we instantly know that all “c” words are  
no good  
and we can move on.

To see how that comes together, let’s examine some of Ross B.'s  
solution:

```
class DictionaryMatcher
  # ...

  def initialize(*words)
    @pt = {}
    words.each { |word| self << word }
  end

  def <<(word)
    # small memory optimization - if there's a longer word that shares
    # this prefix, we can discard it since we'll only ever take the
    # shortest match anyway.
    word.split('').inject(@pt) do |pt, chr|
      pt[chr] ||= {}
    end.clear[: __WORD__] = true

    self
  end

  # ...

  def match(str, start_ofs = 0)
    start_ofs.upto(str.length) do |i|
      word = ""
      next_pt = @pt
      si = i
      while next_pt = next_pt[chr = str[i,1]]
        word << chr
        return MatchData.new(si, i, word, str) if next_pt[: __WORD__]
        i+=1
      end
    end

    nil
  end

  def =~(str)
    m = match(str) and m.start_offset
  end

  # ...
end

```

I’ve trimmed a lot of code here, but what I’ve shown is the heart of the  
matching algorithm. Ross uses a simple set of nested Hashes to build  
his prefix  
tree (@pt) in initialize().

Words are inserted into the tree in the \<\<() method. It splits the word  
into  
letters, and walks the nested Hashes inserting each letter. When it  
reaches the  
end of the word, any further nesting is cleared (an optimization  
explained in  
the comment) and the special : **WORD** marker is inserted to indicate a  
word  
boundary.

The rest of the magic is in the match() method. It works much as I  
explained  
before. It walks the String index by index. If a character is found in  
the  
prefix tree, it tries to find a run of matches by walking the tree  
forward (the  
while loop). When it makes it all the way to a word boundary marker, it  
declares victory by returning Ross’s custom MatchData object (not  
shown). If  
the tree walk fails, the code advances to the next index and when the  
indices  
are exhausted, nil is tossed to indicate that no match could be found.

The =~() method also uses match(), but changes the return value to mimic  
Ruby.

There’s certainly more to see in the solutions and I hope this gives you  
enough  
of a map to encourage your own spelunking expidition into the code. A  
big thank  
you to all of the programmers who helped reduce this FAQ to a link we  
can pass  
on to those who ask.

Sharpen your turtles folks, because it’s pretty picture drawing time  
with  
tomorrow’s Ruby Q…