code_ruby/lib/maasha/levenshtein.rb

   1 # Copyright (C) 2013 Martin A. Hansen.
   2
   3 # This program is free software; you can redistribute it and/or
   4 # modify it under the terms of the GNU General Public License
   5 # as published by the Free Software Foundation; either version 2
   6 # of the License, or (at your option) any later version.
   7
   8 # This program is distributed in the hope that it will be useful,
   9 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 # GNU General Public License for more details.
  12
  13 # You should have received a copy of the GNU General Public License
  14 # along with this program; if not, write to the Free Software
  15 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16
  17 # http://www.gnu.org/copyleft/gpl.html
  18
  19 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  20
  21 # This software is part of the Biopieces framework (www.biopieces.org).
  22
  23 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  24
  25 require 'inline'
  26
  27 # Class to calculate the Levenshtein distance between two
  28 # given strings.
  29 # http://en.wikipedia.org/wiki/Levenshtein_distance
  30 class Levenshtein
  31   BYTES_IN_INT = 4
  32
  33   def self.distance(s, t)
  34     return 0        if s == t;
  35     return t.length if s.length == 0;
  36     return s.length if t.length == 0;
  37
  38     v0 = "\0" * (t.length + 1) * BYTES_IN_INT
  39     v1 = "\0" * (t.length + 1) * BYTES_IN_INT
  40
  41     l = self.new
  42     l.distance_C(s, t, s.length, t.length, v0, v1)
  43   end
  44
  45   # >>>>>>>>>>>>>>> RubyInline C code <<<<<<<<<<<<<<<
  46
  47   inline do |builder|
  48     builder.prefix %{
  49       unsigned int min(unsigned int a, unsigned int b, unsigned int c)
  50       {
  51           unsigned int m = a;
  52
  53           if (m > b) m = b;
  54           if (m > c) m = c;
  55
  56           return m;
  57       }
  58     }
  59
  60     builder.c %{
  61       VALUE distance_C(
  62         VALUE _s,       // string
  63         VALUE _t,       // string
  64         VALUE _s_len,   // string length
  65         VALUE _t_len,   // string length
  66         VALUE _v0,      // score vector
  67         VALUE _v1       // score vector
  68       )
  69       {
  70         char         *s     = (char *) StringValuePtr(_s);
  71         char         *t     = (char *) StringValuePtr(_t);
  72         unsigned int  s_len = FIX2UINT(_s_len);
  73         unsigned int  t_len = FIX2UINT(_t_len);
  74         unsigned int  *v0   = (unsigned int *) StringValuePtr(_v0);
  75         unsigned int  *v1   = (unsigned int *) StringValuePtr(_v1);
  76
  77         unsigned int i    = 0;
  78         unsigned int j    = 0;
  79         unsigned int cost = 0;
  80
  81         for (i = 0; i < t_len + 1; i++)
  82           v0[i] = i;
  83
  84         for (i = 0; i < s_len; i++)
  85         {
  86           v1[0] = i + 1;
  87
  88           for (j = 0; j < t_len; j++)
  89           {
  90             cost = (s[i] == t[j]) ? 0 : 1;
  91             v1[j + 1] = min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);
  92           }
  93
  94           for (j = 0; j < t_len + 1; j++)
  95             v0[j] = v1[j];
  96         }
  97
  98         return UINT2NUM(v1[t_len]);
  99       }
 100     }
 101   end
 102 end
 103
 104 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 105
 106
 107 __END__