Metaphone vs. Levenshtien shootout

benchmark_bigo_suggest.rb

#!/usr/bin/env ruby -w

require 'benchmark/bigo'
require 'rubyfish'

require_relative 'typo_suggestor'
require_relative 'levenshtien_suggestion'
require_relative 'metaphone_suggestion'

Benchmark.bigo do |x|
  x.increments = 6
  x.generator {|size| TypoSuggestor.new(size) }

  x.exponential 10

  x.report "levenshtien" do |generated, size|
    generated.suggest_typos do |words, typo|
      LevenshteinSuggestion.new(words).suggest(typo)
    end
  end

  x.report "metaphone" do |generated, size|
    generated.suggest_typos do |words, typo|
      MetaphoneSuggestion.new(words).suggest(typo)
    end
  end

  x.data! 'chart_array_simple.json'

  x.chart! 'chart_array_simple.html'
end

chart_array_simple.csv

levenshein_suggestion.rb

require 'rubyfish'
require 'set'

class LevenshteinSuggestion
  attr_reader :words

  def initialize(words)
    @words = words
  end

  def suggest(typo)
    max = typo.length / 2
    distances = []
    words.each do |word|
      distance = RubyFish::Levenshtein.distance typo, word
      if distance < max
        distances << [word, distance]
      end
    end
    suggestions = distances.uniq.sort_by{ |name, dist| dist }
    suggestions.first(5).map(&:first)
  end
end

metaphone_suggestion.rb

class MetaphoneSuggestion
  attr_reader :metaphones

  def initialize(words)
    @metaphones = {}
    words.each do |word|
      next unless word
      codes = RubyFish::DoubleMetaphone.phonetic_code word
      codes.each do |code|
        if code
          metaphones[code] ||= []
          metaphones[code] << word
        end
      end
    end
  end

  def suggest(typo)
    suggestions = []
    codes = RubyFish::DoubleMetaphone.phonetic_code typo
    codes.each do |code|
      words = metaphones[code]
      if words
        suggestions = suggestions + words
      end
    end
    suggestions
  end
end

typo_suggestor.rb

class TypoSuggestor
  attr_reader :typos, :words, :corrections
  def initialize(size)
    @typos = ["reils", "pwerline", "parte"]
    @corrections = ["rails", "powerline", "party"]
    lines = File.readlines '/usr/share/dict/words'
    @words = lines.map(&:chomp)
    @words = @words.shuffle.first(size)
    @words = @words + @corrections
    @words = @words.uniq.sort
  end

  def suggest_typos
    typos.each_with_index do |typo, index|
      suggestions = yield words, typo
      unless suggestions.include? corrections[index]
        $stderr.puts "#{corrections[index]} not found in #{suggestions.join(', ')}"
      end
      suggestions
    end
  end
end