1 | // diff format: array of character numbers out of s used to reconstruct t |
2 | |
3 | static int leven(String s, String t) { |
4 | // degenerate cases |
5 | if (s.equals(t)) return 0; |
6 | if (s.length() == 0) return t.length(); |
7 | if (t.length() == 0) return s.length(); |
8 | |
9 | // create two work vectors of integer distances |
10 | L<int>[] v0 = new ArrayList<int>[t.length() + 1]; |
11 | L<Int>[] v1 = new ArrayList<int>[t.length() + 1]; |
12 | |
13 | // initialize v0 (the previous row of distances) |
14 | // this row is A[0][i]: edit distance for an empty s |
15 | // the distance is just the number of characters to delete from t |
16 | for (int i = 0; i < v0.length; i++) |
17 | v0[i] = i; |
18 | |
19 | for (int i = 0; i < s.length(); i++) |
20 | { |
21 | // calculate v1 (current row distances) from the previous row v0 |
22 | |
23 | // first element of v1 is A[i+1][0] |
24 | // edit distance is delete (i+1) chars from s to match empty t |
25 | v1[0] = i + 1; |
26 | |
27 | // use formula to fill in the rest of the row |
28 | for (int j = 0; j < t.length(); j++) |
29 | { |
30 | int cost = s.charAt(i) == t.charAt(j) ? 0 : 1; |
31 | v1[j + 1] = Math.min(Math.min(v1[j] + 1, v0[j + 1] + 1), v0[j] + cost); |
32 | } |
33 | |
34 | // copy v1 (current row) to v0 (previous row) for next iteration |
35 | /*for (int j = 0; j < v0.length; j++) |
36 | v0[j] = v1[j];*/ |
37 | |
38 | // swap arrays |
39 | int[] v = v1; v1 = v0; v0 = v; |
40 | } |
41 | |
42 | // for array copying: |
43 | // return v1[t.length()]; |
44 | // for array swapping: |
45 | return v0[t.length()]; |
46 | } |
Began life as a copy of #1000388
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: | #1000559 |
Snippet name: | Text diff function in JavaX (char-based, based on levenshtein distance, developing [maybe]) |
Eternal ID of this version: | #1000559/1 |
Text MD5: | 7574330524ed3d71c7eaec0d1353156a |
Author: | stefan |
Category: | javax |
Type: | JavaX source code |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2015-08-14 14:10:36 |
Source code size: | 1500 bytes / 46 lines |
Pitched / IR pitched: | No / Yes |
Views / Downloads: | 583 / 547 |
Referenced in: | [show references] |