Class: Dat::Logic

Inherits:

Object

• Object
• Dat::Logic

Defined in:

ext/logic/logic.c

Instance Attribute Summary

• #min_size ⇒ Object readonly

Instance Method Summary

• #damlev(a, b) ⇒ Object

  precondition: a and b not nil and the words are uppercase.

• #initialize(*args) ⇒ Object constructor
• #jaro_winkler(a, b) ⇒ Object
• #leven(a, b) ⇒ Object
• #perturb(*args) ⇒ Object

Constructor Details

#initialize(*args) ⇒ Object

# File 'ext/logic/logic.c', line 33

static VALUE init(int argc, VALUE *argv, VALUE self) {
  VALUE dict, opt, add, replace, delete, transpose;
  rb_scan_args(argc, argv, "11", &dict, &opt);
  if (NIL_P(opt)) opt = rb_hash_new();

  rb_iv_set(self, "@dict", dict);

  add = rb_hash_lookup2(opt, ID2SYM(rb_intern("add")), Qtrue);
  replace = rb_hash_lookup2(opt, ID2SYM(rb_intern("replace")), Qtrue);
  delete = rb_hash_lookup2(opt, ID2SYM(rb_intern("delete")), Qtrue);
  transpose = rb_hash_lookup2(opt, ID2SYM(rb_intern("delete")), Qfalse);

  rb_iv_set(self, "@add", add);
  rb_iv_set(self, "@replace", replace);
  rb_iv_set(self, "@delete", delete) ;
  rb_iv_set(self, "@transpose", transpose);

  rb_iv_set(self, "@min_size", rb_hash_lookup2(opt, ID2SYM(rb_intern("min_size")), INT2FIX(MIN_SIZE)));

  rb_iv_set(self, "@cachable", (RTEST(add) && RTEST(replace) && RTEST(delete) && !RTEST(transpose) ? Qtrue : Qfalse));
  rb_iv_set(self, "@perturb_cache", rb_hash_new());

  return self;
}

Instance Attribute Details

#min_size ⇒ Object (readonly)

Instance Method Details

#damlev(a, b) ⇒ Object

precondition: a and b not nil and the words are uppercase

# File 'ext/logic/logic.c', line 193

static VALUE damlev(VALUE self, VALUE a, VALUE b) {
  size i, j, w, x, y, z;
  char *s = StringValueCStr(a);
  char *t = StringValueCStr(b);
  size m = (size) RSTRING_LEN(a);
  size n = (size) RSTRING_LEN(b);

  if (!m) return INT2FIX(n);
  if (!n) return INT2FIX(m);

  size h[SIZE_BYTES][SIZE_BYTES];
  size inf = m + n;
  h[0][0] = inf;
  for (i = 0; i <= m; i++) { h[i+1][1] = i; h[i+1][0] = inf; }
  for (j = 0; j <= n; j++) { h[1][j+1] = j; h[0][j+1] = inf; }

  size da[ALPHABET_SIZE];
  for (i = 0; i < ALPHABET_SIZE; i++) {
    da[i] = 0;
  }

  size db, i1, j1, d;
  for (i = 1; i <= m; i++) {
    db = 0;
    for (j = 1; j <= n; j++) {
      i1 = da[t[j-1]-ASCII_A];
      j1 = db;
      d = ( (s[i-1] == t[j-1]) ? 0 : 1);
      if (!d) {
        db = j;
      }
      w = h[i][j]+d; x = h[i+1][j] + 1; y = h[i][j+1]+1; z = h[i1][j1] + (i-i1-1) + 1 + (j-j1-1);
      h[i+1][j+1] = MIN( MIN( MIN(w, x), y ), z );
    }
    da[s[i-1]-ASCII_A] = i;
  }

  VALUE val = INT2FIX(h[m+1][n+1]);
  return val;
}

#jaro_winkler(a, b) ⇒ Object

# File 'ext/logic/logic.c', line 141

static VALUE jaro_winkler(VALUE self, VALUE a, VALUE b) {
  int i, j, start, fin;
  char *s = StringValueCStr(a);
  char *t = StringValueCStr(b);
  size m = (size) RSTRING_LEN(a);
  size n = (size) RSTRING_LEN(b);
  if (m == 0) return rb_float_new(n == 0 ? 1.0 : 0.0);

  size range = MAX(0, (MAX(m,n)/2) - 1);

  char s_matched[SIZE_BYTES];
  char t_matched[SIZE_BYTES];
  for (i = 0; i < m; i++) s_matched[i] = 0;
  for (i = 0; i < n; i++) t_matched[i] = 0;

  int common = 0;
  for (i = 0; i < m; i++) {
    start = MAX(0,i-range);
    fin = MIN(i+range+1, n);
    for (j = start; j < fin; j++) {
      if (t_matched[j] || s[i] != t[j]) continue;
      s_matched[i] = 1;
      t_matched[j] = 1;
      common++;
      break;
    }
  }

  if (!common) return rb_float_new(0.0);

  int transposed = 0;
  j = 0;
  for (i = 0; i < m; i++) {
    if (!s_matched[i]) continue;
    while (!t_matched[j]) j++;
    if (s[i] != t[j]) transposed++;
    j++;
  }
  transposed /= 2;

  double weight = (((double)common/m) + ((double)common/n) + ((double)(common-transposed)/common)) / 3.0;
  if (weight <= WEIGHT_THRESHOLD) return rb_float_new(weight);

  int max = MIN(NUM_CHARS, MIN(m,n));
  int pos = 0;
  while (pos < max && s[pos] == t[pos]) pos++;
  if (pos == 0) return rb_float_new(weight);

  return rb_float_new(weight + 0.1 * pos * (1.0 - weight));
}

#leven(a, b) ⇒ Object

# File 'ext/logic/logic.c', line 234

static VALUE leven(VALUE self, VALUE a, VALUE b) {
  size i, j;
  char *s = StringValueCStr(a);
  char *t = StringValueCStr(b);
  size m = (size) RSTRING_LEN(a);
  size n = (size) RSTRING_LEN(b);

  /* for all i and j, d[i,j] will hold the Levenshtein distance between
   * the first i characters of s and the first j characters of t;
   * note that d has (m+1)x(n+1) values */
  size d[SIZE_BYTES][SIZE_BYTES];

  for (i = 0; i <= m; i++) {
    d[i][0] = i;
    for (j = 0; j <= n; j++) {
      d[0][j] = j;
    }
  }

  for (j = 1; j <= n; j++) {
    for (i = 1; i <= m; i++) {
      if (s[i-1] == t[j-1]) {
        d[i][j] = d[i-1][j-1];
      } else {               /* delete */     /* insert */      /* replace */
        d[i][j] = MIN( MIN((d[i-1][j] + 1), (d[i][j-1] + 1)), (d[i-1][j-1] + 1) );
      }
    }
  }

  VALUE val = INT2FIX(d[m][n]);
  return val;
}

#perturb(*args) ⇒ Object

# File 'ext/logic/logic.c', line 133

static VALUE perturb(int argc, VALUE *argv, VALUE self) {
  VALUE str, used;
  rb_scan_args(argc, argv, "11", &str, &used);
  if (NIL_P(used)) used = rb_hash_new();
  VALUE result = rb_block_call(perturb_impl(self, str), id_reject, 0, 0, reject_i, used);
  return result;
}