GADDAG data structure in Ruby

A GADDAG is a data structure that allows for fast lookup of words by substring. It is a directed acyclic graph, where each word can be constructed from the root via any of its reversed prefixes. Its main application is move generation in Scrabble. The data structure is explained in more detail in the original research paper.

Installation

The gaddag gem is available via Rubygems. Install the gem by adding it to your Gemfile or by running:

gem install gaddag

Usage

Initializing the GADDAG is simple:

require 'gaddag'
gaddag = GADDAG.new

Adding words is done via the add method. This will expand the graph with paths for all the reversed prefixes of the word. Note that this may take some time when adding a large number of words.

File.readlines('/usr/share/dict/words') do |word|
  gaddag.add(word.strip) if word.strip.length == 10 # => #<Gaddag:0x007fc6c24367b0 ... >
end

In order to find all words that contain a given substring, use the find method:

gaddag.find('elevi') => # ["televiewer", "television", "televisual"]

Examples

• dictionary.rb

License

See LICENSE.txt.