Module: DidYouMean::Jaro

Defined in:
lib/did_you_mean/jaro_winkler.rb

Class Method Summary collapse

Class Method Details

.distance(str1, str2) ⇒ Object 



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
50
51
52
53
54
55
56
57
58
 
# File 'lib/did_you_mean/jaro_winkler.rb', line 5

def distance(str1, str2)
  str1, str2 = str2, str1 if str1.length > str2.length
  length1, length2 = str1.length, str2.length

  m          = 0.0
  t          = 0.0
  range      = length2 > 3 ? length2 / 2 - 1 : 0
  flags1     = 0
  flags2     = 0

  # Avoid duplicating enumerable objects
  str1_codepoints = str1.codepoints
  str2_codepoints = str2.codepoints

  i = 0
  while i < length1
    last = i + range
    j    = (i >= range) ? i - range : 0

    while j <= last
      if flags2[j] == 0 && str1_codepoints[i] == str2_codepoints[j]
        flags2 |= (1 << j)
        flags1 |= (1 << i)
        m += 1
        break
      end

      j += 1
    end

    i += 1
  end

  k = i = 0
  while i < length1
    if flags1[i] != 0
      j = index = k

      k = while j < length2
        index = j
        break(j + 1) if flags2[j] != 0

        j += 1
      end

      t += 1 if str1_codepoints[i] != str2_codepoints[index]
    end

    i += 1
  end
  t = (t / 2).floor

  m == 0 ? 0 : (m / length1 + m / length2 + (m - t) / m) / 3
end