Class: TTY::Text::Distance

Inherits:
Object
  • Object
show all
Includes:
Unicode
Defined in:
lib/tty/text/distance.rb

Overview

A class responsible for string comparison

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Unicode

#as_unicode, #clean_utf8, #utf8?

Constructor Details

#initialize(first, second, *args) ⇒ Distance

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Initalize a Distance

Parameters:

  • first (String) —

    the first string for comparision

  • second (String) —

    the second string for comparison



23
24
25
26
27
28
 
# File 'lib/tty/text/distance.rb', line 23

def initialize(first, second, *args)
  options = Utils.extract_options!(args)
  @first = first.to_s
  @second = second.to_s
  # TODO: add option to ignore case
end

Instance Attribute Details

#first ⇒ Object (readonly)

Returns the value of attribute first.



10
11
12
 
# File 'lib/tty/text/distance.rb', line 10

def first
  @first
end

#second ⇒ Object (readonly)

Returns the value of attribute second.



12
13
14
 
# File 'lib/tty/text/distance.rb', line 12

def second
  @second
end

Instance Method Details

#distance ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Calculate the optimal string alignment distance



33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/tty/text/distance.rb', line 33

def distance
  distances = []
  rows      = first.length
  cols      = second.length

  0.upto(rows) do |index|
    distances << [index] + [0] * cols
  end
  distances[0] = 0.upto(cols).to_a

  1.upto(rows) do |first_index|
    1.upto(cols) do |second_index|
      first_char  = first[first_index - 1]
      second_char = second[second_index - 1]
      cost        = first_char == second_char ? 0 : 1

      distances[first_index][second_index] = [
        distances[first_index - 1][second_index], # deletion
        distances[first_index][second_index - 1],     # insertion
        distances[first_index - 1][second_index - 1]  # substitution
      ].min + cost

      if first_index > 1 && second_index > 1
        first_previous_char = first[first_index - 2]
        second_previous_char = second[second_index - 2]
        if first_char == second_previous_char && second_char == first_previous_char
          distances[first_index][second_index] = [
            distances[first_index][second_index],
            distances[first_index - 2][second_index - 2] + 1 # transposition
          ].min
        end
      end

    end
  end
  distances[rows][cols]
end