class String
Public Instance Methods
levenshtein(p1)
click to toggle source
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)
click to toggle source
# 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