Module: StringMetric::Levenshtein

Defined in:
lib/string_metric/levenshtein.rb,
lib/string_metric/levenshtein/recursive.rb,
lib/string_metric/levenshtein/trie_node.rb,
lib/string_metric/levenshtein/experiment.rb,
lib/string_metric/levenshtein/trie_radix_tree.rb,
lib/string_metric/levenshtein/trie_radix_tree_ext.rb,
lib/string_metric/levenshtein/iterative_with_full_matrix.rb,
lib/string_metric/levenshtein/iterative_with_two_matrix_rows.rb,
lib/string_metric/levenshtein/iterative_with_two_matrix_rows_ext.rb,
lib/string_metric/levenshtein/iterative_with_two_matrix_rows_optimized.rb,
ext/string_metric/levenshtein/trie_radix_tree/trie_radix_tree_ext.c,
ext/string_metric/levenshtein/iterative_with_two_matrix_rows/iterative_with_two_matrix_rows_ext.c

Overview

Levenshtein Distance implementation

See Also:

Defined Under Namespace

Classes: Experiment, IterativeWithFullMatrix, IterativeWithTwoMatrixRows, IterativeWithTwoMatrixRowsExt, IterativeWithTwoMatrixRowsOptimized, Recursive, TrieNode, TrieRadixTree, TrieRadixTreeExt

Constant Summary collapse

STRATEGIES = 
{
  experiment:   Experiment,
  full_matrix:  IterativeWithFullMatrix,
  recursive:    Recursive,
  two_matrix_rows:    IterativeWithTwoMatrixRows,
  two_matrix_rows_v2: IterativeWithTwoMatrixRowsOptimized
}

Class Method Summary collapse

Class Method Details

.default_strategy ⇒ Object

Currently the default strategy is set to IterativeWithTwoMatrixRows



59
60
61
62
63
64
65
 
# File 'lib/string_metric/levenshtein.rb', line 59

def default_strategy
  if RUBY_ENGINE == "ruby"
    pick_strategy(:two_matrix_rows_ext)
  else
    pick_strategy(:two_matrix_rows)
  end
end

.distance(from, to, options = {}) ⇒ Fixnum, Float

Levenshtein Distance of two strings

Parameters:

  • from (String) —

    the first string

  • to (String) —

    the second string

  • options (Hash) (defaults to: {}) —

    options

Options Hash (options):

  • :max_distance (Fixnum, Float) —

    If this option is passed then levenstein distance is trimmed to this value (if greater)

  • :insertion_cost (Fixnum, Float) —

    If this option is passed then new insertion cost is taken into account (by default is 1)

  • :deletion_cost (Fixnum, Float) —

    If this option is passed then new deletion cost is taken into account (by default is 1)

  • :substitution_cost (Fixnum, Float) —

    If this option is passed then new substitution cost is taken into account (be default is 1)

  • :strategy (Symbol) —

    The desired strategy for Levenshtein distance. Supported strategies are :recursive, :two_matrix_rows, :full_matrix, :two_matrix_rows_v2 and :experiment. The default strategy is :two_matrix_rows_v2 for MRI and :two_matrix_rows for other platforms. One should not depend on :experiment strategy.

Returns:

  • (Fixnum, Float) —

    the Levenshtein Distance



50
51
52
53
54
55
 
# File 'lib/string_metric/levenshtein.rb', line 50

def distance(from, to, options = {})
  strategy = pick_strategy(options[:strategy]) || Levenshtein.default_strategy
  args = [from, to, options]

  strategy.distance(*args)
end