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