Contents

# coding: utf-8

module StringMetric
  module Levenshtein
    class IterativeWithTwoMatrixRowsOptimized
      def self.distance(from, to, options = {})
        max_distance      = options[:max_distance]
        insertion_cost    = options[:insertion_cost]    || 1
        deletion_cost     = options[:deletion_cost]     || 1
        substitution_cost = options[:substitution_cost] || 1

        m = from.length
        n = to.length

        if max_distance && (n - m).abs >= max_distance
          return max_distance
        end

        return 0 if from == to
        return n if m.zero?
        return m if n.zero?

        from = from.codepoints.to_a
        to = to.codepoints.to_a

        v0 = (0..m).to_a
        x = 0

        n.times do |i|
          current = x = i + 1
          sub_cell = v0[0]

          m.times do |j|
            cost = (from[j] == to[i]) ? 0 : substitution_cost
            ins_cell = v0[j + 1]

            x = [current + deletion_cost,   # deletion
                 ins_cell + insertion_cost, # insertion
                 sub_cell + cost            # substitution
                ].sort![0]

            v0[j] = current
            current = x
            sub_cell = ins_cell
          end

          v0[m] = x
          break if max_distance && v0.sort[0] > max_distance
        end

        if max_distance && x > max_distance
          max_distance
        else
          x
        end
      end
    end
  end
end

Version data entries

3 entries across 3 versions & 1 rubygems

Version	Path
string_metric-0.1.4	lib/string_metric/levenshtein/iterative_with_two_matrix_rows_optimized.rb
string_metric-0.1.3	lib/string_metric/levenshtein/iterative_with_two_matrix_rows_optimized.rb
string_metric-0.1.2	lib/string_metric/levenshtein/iterative_with_two_matrix_rows_optimized.rb