Mercurial > octave-nkf
annotate libinterp/corefcn/levenshtein.cc @ 20583:d746695bf494
levenshtein.cc: use Array<T>::numel() instead of the deprecated ::length()
author | Carnë Draug <carandraug@octave.org> |
---|---|
date | Sun, 04 Oct 2015 16:24:32 +0100 |
parents | fcb792acab9b |
children | f90c8372b7ba |
rev | line source |
---|---|
20568
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
1 /* |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
2 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
3 Copyright (C) 2014 Jacopo Corno |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
4 Copyright (C) 2014 Carlo de Falco |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
5 Copyright (C) 2013 Roberto Porcu |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
6 Copyright (C) 2013 Mattia Penati |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
7 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
8 This file is part of Octave. |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
9 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
10 Octave is free software; you can redistribute it and/or modify it |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
11 under the terms of the GNU General Public License as published by |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
12 the Free Software Foundation; either version 3 of the License, or (at |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
13 your option) any later version. |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
14 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
15 Octave is distributed in the hope that it will be useful, but |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
16 WITHOUT ANY WARRANTY; without even the implied warranty of |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
18 General Public License for more details. |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
19 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
20 You should have received a copy of the GNU General Public License |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
21 along with Octave; see the file COPYING. If not, see |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
22 <http://www.gnu.org/licenses/>. |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
23 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
24 */ |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
25 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
26 #ifdef HAVE_CONFIG_H |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
27 #include <config.h> |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
28 #endif |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
29 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
30 #include "defun.h" |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
31 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
32 #define MIN2(A,B) ((A)<(B)?(A):(B)) |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
33 #define MIN3(A,B,C) (MIN2(MIN2((A),(B)),(C))) |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
34 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
35 DEFUN (levenshtein, args, nargout, |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
36 "-*- texinfo -*-\n\ |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
37 @deftypefn {Loadable Function} {@var{d} =} levenshtein (@var{str1}, @var{str2}, [@var{u_bound}])\n \ |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
38 @deftypefnx {Loadable Function} {[@var{d}, @var{mat}] =} levenshtein (@var{str1}, @var{str2}, [@var{u_bound}])\n \ |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
39 This function file computes the Levenshtein distance between two strings. More details at @url{http://en.wikipedia.org/wiki/Levenshtein_distance}.\n \ |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
40 This function can be called with one or two output arguments: @var{d} is the distance between the two strings and @var{mat} is the matrix computed by Levenshtein algorithm.\n \ |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
41 The first and the second input arguments, @var{str1} and @var{str2}, are the two strings to be compared. This comparison is case-sensitive.\n \ |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
42 The third argument @var{u_bound} is optional and fixes an upper bound for the distance. If the distance is greater than this limit then the function ends and returns a value equal to Inf.\n \ |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
43 @seealso{odeset}\n\ |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
44 @end deftypefn") |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
45 { |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
46 octave_value_list retval; |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
47 int nargin = args.length (); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
48 octave_idx_type ub; |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
49 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
50 if (nargin < 2 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
51 || nargin > 3 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
52 || nargout > 2) |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
53 { |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
54 print_usage (); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
55 return retval; |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
56 } |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
57 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
58 if (nargin == 3) |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
59 ub = args(2).idx_type_value (); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
60 else |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
61 ub = std::numeric_limits<int32_t>::max (); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
62 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
63 Array<char> s1 (args(0).char_array_value ()); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
64 char *s1_p = s1.fortran_vec (); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
65 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
66 Array<char> s2 (args(1).char_array_value ()); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
67 char *s2_p = s2.fortran_vec (); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
68 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
69 octave_idx_type |
20583
d746695bf494
levenshtein.cc: use Array<T>::numel() instead of the deprecated ::length()
Carnë Draug <carandraug@octave.org>
parents:
20568
diff
changeset
|
70 s1len = s1.numel (), |
d746695bf494
levenshtein.cc: use Array<T>::numel() instead of the deprecated ::length()
Carnë Draug <carandraug@octave.org>
parents:
20568
diff
changeset
|
71 s2len = s2.numel (), |
20568
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
72 ii, jj; |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
73 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
74 if (! error_state) |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
75 { |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
76 Array<octave_idx_type> |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
77 dist (dim_vector (s1len + 1, s2len + 1), 0); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
78 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
79 for (ii = 1; ii <= s1len; ii++) |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
80 dist.xelem (ii, 0) = ii; |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
81 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
82 for (jj = 1; jj <= s2len; jj++) |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
83 dist.xelem (0, jj) = jj; |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
84 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
85 for (jj = 1; jj <= s2len; jj++) |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
86 { |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
87 for (ii = 1; ii <= s1len; ii++) |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
88 if (s1_p[ii-1] == s2_p[jj-1]) |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
89 dist.xelem (ii, jj) = dist.xelem (ii-1, jj-1); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
90 else |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
91 dist.xelem (ii, jj) = |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
92 MIN3(dist.xelem (ii-1, jj) + 1, |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
93 dist.xelem (ii, jj-1) + 1, |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
94 dist.xelem (ii-1, jj-1) + 1); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
95 |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
96 if (dist(MIN2(jj, s1len), jj) > ub) |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
97 { |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
98 retval(0) = std::numeric_limits<int32_t>::max (); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
99 if (nargout == 2) |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
100 retval(1) = Matrix (); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
101 return retval; |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
102 } |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
103 } |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
104 retval(0) = dist.xelem (s1len, s2len); |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
105 if (nargout == 2) |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
106 retval(1) = dist; |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
107 } |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
108 return retval; |
fcb792acab9b
Moving ode45, odeset, odeget, and levenshtein from odepkg to core.
jcorno <jacopo.corno@gmail.com>
parents:
diff
changeset
|
109 } |