Class: String

Inherits:
Object
  • Object
show all
Defined in:
lib/string_dot_levenshtein/levenshtein_rb.rb,
ext/levenshtein.c

Instance Method Summary collapse

Instance Method Details

#levenshtein(arg) ⇒ 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
 
# File 'ext/levenshtein.c', line 5

VALUE levenshtein(VALUE obj, VALUE arg) {
  char *a = StringValuePtr(obj), *b = StringValuePtr(arg) ;
  char b_i_1 ;

  if (strcmp(a, b) == 0) return INT2FIX(0) ;
  if (strcmp(a, "") == 0) return INT2FIX(strlen(b)) ;
  if (strcmp(b, "") == 0) return INT2FIX(strlen(a)) ;

  uint64_t a_len = strlen(a) + 1 ;
  uint64_t b_len = strlen(b) + 1 ;

  if (a_len > 4096 || b_len > 4096)
    rb_raise(rb_eRuntimeError, "More than 4096 characters were given") ;

  uint16_t ary[b_len][a_len], *ary_i, *ary_i_1 ;
  uint16_t i, i_1 ;
  uint16_t j, j_1 ;
  uint16_t diag, up, left, min ;

  for(i = 0 ; i < a_len ; ++i) ary[0][i] = i ;
  for(i = 0 ; i < b_len ; ++i) ary[i][0] = i ;

  for(i = 1 ; i < b_len ; ++i) {
    i_1 = i - 1 ;
    ary_i = ary[i] ;
    ary_i_1 = ary[i_1] ;
    b_i_1 = b[i_1] ;

    for(j = 1 ; j < a_len ; ++j) {
      j_1 = j - 1 ;
      diag = ary_i_1[j_1] ;

      if (a[j_1] == b_i_1) {
        ary_i[j] = diag ;
      } else {
        up = ary_i_1[j] ;
        left = ary_i[j_1] ;

        min = diag ;
        if (up < min) min = up ;
        if (left < min) min = left ;

        ary_i[j] = min + 1 ;
      }
    }
  }

  return INT2FIX(ary[b_len - 1][a_len - 1]) ;
}

#levenshtein_rb(arg) ⇒ Object 



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
 
# File 'lib/string_dot_levenshtein/levenshtein_rb.rb', line 2

def levenshtein_rb(arg)
  a_len = length + 1
  b_len = arg.length + 1

  x_chars = chars
  y_chars = arg.chars

  ary = Array.new(b_len) { Array.new(a_len) }

  i = -1
  ary[0][i] = i while (i += 1) < a_len

  i = -1
  ary[i][0] = i while (i += 1) < b_len

  i = 0
  while (i += 1) < b_len
    j = 0
    i_1 = i - 1
    ary_i = ary[i]
    ary_i_1 = ary[i - 1]

    while (j += 1) < a_len
      j_1 = j - 1
      diag = ary_i_1[j_1]

      if x_chars[j_1] == y_chars[i_1]
        ary_i[j] = diag
      else
        up = ary_i_1[j]
        left = ary_i[j_1]

        min = diag
        min = up if up < min
        min = left if left < min

        ary_i[j] = min + 1
      end
    end
  end

  ary[b_len - 1][a_len - 1]
end