Implementations of the levenshtein algorithm

levenshtein.erl

-module(levenshtein).
-export([distance/2]).

first_letter_check(OneLetter, TwoLetter) ->
  if OneLetter =:= TwoLetter -> 0
    ; true -> 1
  end.

distance(String1, String1) -> 0;
distance(String, "") -> string:len(String);
distance("", String) -> string:len(String);
distance([H1|Rest1], [H2|Rest2]) ->
  Cost = first_letter_check(H1, H2),

  lists:min([
         distance(Rest1, [H2|Rest2]) + 1,
         distance([H1|Rest1], Rest2) + 1,
         distance(Rest1, Rest2) + Cost
         ]).

levenshtein.rb

class Levenshtein
  attr_reader :distance

  def initialize(first, second)
    @from = first
    @to = second
  end

  def distance
    @distance ||= calculate_distance(@from, @to)
  end

  private
  def calculate_distance(from, to)
    return 0 if from == to
    return from.length if to.empty?
    return to.length if from.empty?

    [
      calculate_distance(from[1..-1], to) + 1,
      calculate_distance(from, to[1..-1]) + 1,
      calculate_distance(from[1..-1], to[1..-1]) + (from[0] <=> to[0]).abs
    ].min

  end
end

updated erlang bogus stats:

simple = < 10ms
complex = 1248.75ms

about a 4 sample avg for each run (wallclock).

Moar better stats:
33> timer:tc(levenshtein, distance, ["kitten", "sitting"]).
{4893,3}
34> timer:tc(levenshtein, distance, ["space balls", "base spalls"]).
{2347887,5}

microsec.

https://gist.github.com/4029680