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