1 | static int leven_limited(S left, S right, int threshold) {
|
2 | if (--threshold < 0) ret 0; |
3 | |
4 | int n = left.length(); // length of left |
5 | int m = right.length(); // length of right |
6 | |
7 | // if one string is empty, the edit distance is necessarily the length |
8 | // of the other |
9 | if (n == 0) {
|
10 | return m <= threshold ? m : threshold+1; |
11 | } else if (m == 0) {
|
12 | return n <= threshold ? n : threshold+1; |
13 | } |
14 | |
15 | if (n > m) {
|
16 | // swap the two strings to consume less memory |
17 | final S tmp = left; |
18 | left = right; |
19 | right = tmp; |
20 | n = m; |
21 | m = right.length(); |
22 | } |
23 | |
24 | int[] p = new int[n + 1]; // 'previous' cost array, horizontally |
25 | int[] d = new int[n + 1]; // cost array, horizontally |
26 | int[] tempD; // placeholder to assist in swapping p and d |
27 | |
28 | // fill in starting table values |
29 | final int boundary = Math.min(n, threshold) + 1; |
30 | for (int i = 0; i < boundary; i++) {
|
31 | p[i] = i; |
32 | } |
33 | // these fills ensure that the value above the rightmost entry of our |
34 | // stripe will be ignored in following loop iterations |
35 | Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE); |
36 | Arrays.fill(d, Integer.MAX_VALUE); |
37 | |
38 | // iterates through t |
39 | for (int j = 1; j <= m; j++) {
|
40 | final char rightJ = right.charAt(j - 1); // jth character of right |
41 | d[0] = j; |
42 | |
43 | // compute stripe indices, constrain to array size |
44 | final int min = Math.max(1, j - threshold); |
45 | final int max = j > Integer.MAX_VALUE - threshold ? n : Math.min( |
46 | n, j + threshold); |
47 | |
48 | // the stripe may lead off of the table if s and t are of different |
49 | // sizes |
50 | if (min > max) {
|
51 | return threshold+1; |
52 | } |
53 | |
54 | // ignore entry left of leftmost |
55 | if (min > 1) {
|
56 | d[min - 1] = Integer.MAX_VALUE; |
57 | } |
58 | |
59 | // iterates through [min, max] in s |
60 | for (int i = min; i <= max; i++) {
|
61 | if (left.charAt(i - 1) == rightJ) {
|
62 | // diagonally left and up |
63 | d[i] = p[i - 1]; |
64 | } else {
|
65 | // 1 + minimum of cell to the left, to the top, diagonally |
66 | // left and up |
67 | d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]); |
68 | } |
69 | } |
70 | |
71 | // copy current distance counts to 'previous row' distance counts |
72 | tempD = p; |
73 | p = d; |
74 | d = tempD; |
75 | } |
76 | |
77 | // if p[n] is greater than the threshold, there's no guarantee on it |
78 | // being the correct |
79 | // distance |
80 | if (p[n] <= threshold) {
|
81 | return p[n]; |
82 | } |
83 | return threshold+1; |
84 | } |
Began life as a copy of #1007596
download show line numbers debug dex old transpilations
Travelled to 13 computer(s): aoiabmzegqzx, bhatertpkbcr, cbybwowwnfue, cfunsshuasjs, gwrvuhgaqvyk, ishqpsrjomds, lpdgvwnxivlt, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tslmcundralx, tvejysmllsmz, vouqrxazstgt
No comments. add comment
| Snippet ID: | #1007737 |
| Snippet name: | leven_limited - limited Levenshtein distance (backup) |
| Eternal ID of this version: | #1007737/2 |
| Text MD5: | 220af06dc1a6614afc8a6339d4d959a5 |
| Author: | stefan |
| Category: | javax |
| Type: | JavaX fragment (include) |
| Public (visible to everyone): | Yes |
| Archived (hidden from active list): | No |
| Created/modified: | 2019-07-28 15:39:17 |
| Source code size: | 2561 bytes / 84 lines |
| Pitched / IR pitched: | No / No |
| Views / Downloads: | 444 / 605 |
| Version history: | 1 change(s) |
| Referenced in: | [show references] |