1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
# frozen_string_literal: true
module TTY
class Prompt
# A class responsible for string comparison
class Distance
# Calculate the optimal string alignment distance
#
# @api public
def distance(first, second)
distances = []
rows = first.to_s.length
cols = second.to_s.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
end # Distance
end # Prompt
end # TTY
|
