Libraryless. Click here for Pure Java version (374L/3K/10K).
!752 p { S s = "Hello world world world"; print("Original:\n " + s); S transformed = bwt(s, '|'); print("BWT Transformed:\n " + transformed); S x = inverseBWT(transformed, '|'); print("Transformed back:\n " + x); print(eq(s, x) ? "Yo!" : "No..."); print(); // Transform it again S doublyTransformed = bwt(transformed, '^'); print("Doubly Transformed (not very useful):\n " + doublyTransformed); } static S bwt(S input, char endMarker) { input += endMarker; int n = l(input); S[] tbl = new S[n]; for i to n: tbl[i] = rotateString(input, i); sort(tbl); new StringBuilder buf; for i to n: buf.append(last(tbl[i])); ret str(buf); } static S rotateString(S s, int n) { if (n == 0) ret s; ret substring(s, l(s)-n) + substring(s, 0, l(s)-n); } static S inverseBWT(S s, char endMarker) { int n = l(s); S[] tbl = new S[n]; for i to n: tbl[i] = ""; for i to n: { // insert for j to n: tbl[j] = s.charAt(j) + tbl[j]; // sort sort(tbl); } for i to n: if (last(tbl[i]) == endMarker) ret dropLast(tbl[i]); fail("NEVER FAIL in a perfect world!"); }
download show line numbers debug dex old transpilations
Travelled to 14 computer(s): aoiabmzegqzx, bhatertpkbcr, cbybwowwnfue, cfunsshuasjs, ddnzoavkxhuk, gwrvuhgaqvyk, ishqpsrjomds, lpdgvwnxivlt, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tslmcundralx, tvejysmllsmz, vouqrxazstgt
No comments. add comment
Snippet ID: | #1004868 |
Snippet name: | Naive Burrows Wheeler Transform (+ Inverse Transform) |
Eternal ID of this version: | #1004868/1 |
Text MD5: | 56e26874ed3a5d5ce3b44fbcf66dc6e9 |
Transpilation MD5: | a760bac83d2b8c4798a259d590c5d368 |
Author: | stefan |
Category: | javax / fun |
Type: | JavaX source code |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2016-09-08 17:47:21 |
Source code size: | 1203 bytes / 54 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 524 / 618 |
Referenced in: | [show references] |