@Test public void testEncoding() { final String value = "abaabbabaacaacabb"; final List<LZ77Codeword> encoded = LZ77.encode(value.toCharArray(), 6, 5); assertEquals("(0,0,a)", encoded.get(0).toString()); assertEquals("(0,0,b)", encoded.get(1).toString()); assertEquals("(2,1,a)", encoded.get(2).toString()); assertEquals("(3,1,b)", encoded.get(3).toString()); assertEquals("(6,4,c)", encoded.get(4).toString()); assertEquals("(3,4,b)", encoded.get(5).toString()); assertEquals("(1,1,<eof>)", encoded.get(6).toString()); assertEquals(7, encoded.size()); }
public static List<LZ77Codeword> encode(final char[] input, final int backBufferSize, final int frontBufferSize) { final List<LZ77Codeword> result = new LinkedList<>(); int middle = 0; int start = middle - backBufferSize; int end = middle + frontBufferSize; while (middle < input.length) { log.debug("Window (start,middle,end): ({},{},{})", start, middle, end); final String backBuffer = safeSubString(input, start, middle); final String frontBuffer = safeSubString(input, middle, end); log.debug("Buffers: ({}|{})", backBuffer, frontBuffer); final int maxPrefixLength = frontBuffer.length(); final String buffer = safeSubString(input, start, end); int prefixIndex = 0; int prefixLength = 0; char prefixFollow = safeSubChar(input, middle); for (int i = 1; i <= maxPrefixLength; i++) { final String newPrefix = safeSubString(input, middle, middle + i); final int newPrefixIndex = buffer.indexOf(newPrefix); final boolean foundInWindow = newPrefixIndex != -1; final boolean foundInBackBuffer = newPrefixIndex < backBuffer.length(); if (foundInWindow && foundInBackBuffer) { prefixIndex = backBuffer.length() - newPrefixIndex; prefixLength = i; prefixFollow = safeSubChar(input, middle + i); } } final int skip = prefixLength + 1; start += skip; middle += skip; end += skip; log.debug("New codeword: ({},{},{}) skip +{}", prefixIndex, prefixLength, prefixFollow, skip); result.add(new LZ77Codeword(prefixIndex, prefixLength, prefixFollow)); } return result; }
LZ77 { public static List<LZ77Codeword> encode(final char[] input, final int backBufferSize, final int frontBufferSize) { final List<LZ77Codeword> result = new LinkedList<>(); int middle = 0; int start = middle - backBufferSize; int end = middle + frontBufferSize; while (middle < input.length) { log.debug("Window (start,middle,end): ({},{},{})", start, middle, end); final String backBuffer = safeSubString(input, start, middle); final String frontBuffer = safeSubString(input, middle, end); log.debug("Buffers: ({}|{})", backBuffer, frontBuffer); final int maxPrefixLength = frontBuffer.length(); final String buffer = safeSubString(input, start, end); int prefixIndex = 0; int prefixLength = 0; char prefixFollow = safeSubChar(input, middle); for (int i = 1; i <= maxPrefixLength; i++) { final String newPrefix = safeSubString(input, middle, middle + i); final int newPrefixIndex = buffer.indexOf(newPrefix); final boolean foundInWindow = newPrefixIndex != -1; final boolean foundInBackBuffer = newPrefixIndex < backBuffer.length(); if (foundInWindow && foundInBackBuffer) { prefixIndex = backBuffer.length() - newPrefixIndex; prefixLength = i; prefixFollow = safeSubChar(input, middle + i); } } final int skip = prefixLength + 1; start += skip; middle += skip; end += skip; log.debug("New codeword: ({},{},{}) skip +{}", prefixIndex, prefixLength, prefixFollow, skip); result.add(new LZ77Codeword(prefixIndex, prefixLength, prefixFollow)); } return result; } }
LZ77 { public static List<LZ77Codeword> encode(final char[] input, final int backBufferSize, final int frontBufferSize) { final List<LZ77Codeword> result = new LinkedList<>(); int middle = 0; int start = middle - backBufferSize; int end = middle + frontBufferSize; while (middle < input.length) { log.debug("Window (start,middle,end): ({},{},{})", start, middle, end); final String backBuffer = safeSubString(input, start, middle); final String frontBuffer = safeSubString(input, middle, end); log.debug("Buffers: ({}|{})", backBuffer, frontBuffer); final int maxPrefixLength = frontBuffer.length(); final String buffer = safeSubString(input, start, end); int prefixIndex = 0; int prefixLength = 0; char prefixFollow = safeSubChar(input, middle); for (int i = 1; i <= maxPrefixLength; i++) { final String newPrefix = safeSubString(input, middle, middle + i); final int newPrefixIndex = buffer.indexOf(newPrefix); final boolean foundInWindow = newPrefixIndex != -1; final boolean foundInBackBuffer = newPrefixIndex < backBuffer.length(); if (foundInWindow && foundInBackBuffer) { prefixIndex = backBuffer.length() - newPrefixIndex; prefixLength = i; prefixFollow = safeSubChar(input, middle + i); } } final int skip = prefixLength + 1; start += skip; middle += skip; end += skip; log.debug("New codeword: ({},{},{}) skip +{}", prefixIndex, prefixLength, prefixFollow, skip); result.add(new LZ77Codeword(prefixIndex, prefixLength, prefixFollow)); } return result; } private  LZ77(); }
LZ77 { public static List<LZ77Codeword> encode(final char[] input, final int backBufferSize, final int frontBufferSize) { final List<LZ77Codeword> result = new LinkedList<>(); int middle = 0; int start = middle - backBufferSize; int end = middle + frontBufferSize; while (middle < input.length) { log.debug("Window (start,middle,end): ({},{},{})", start, middle, end); final String backBuffer = safeSubString(input, start, middle); final String frontBuffer = safeSubString(input, middle, end); log.debug("Buffers: ({}|{})", backBuffer, frontBuffer); final int maxPrefixLength = frontBuffer.length(); final String buffer = safeSubString(input, start, end); int prefixIndex = 0; int prefixLength = 0; char prefixFollow = safeSubChar(input, middle); for (int i = 1; i <= maxPrefixLength; i++) { final String newPrefix = safeSubString(input, middle, middle + i); final int newPrefixIndex = buffer.indexOf(newPrefix); final boolean foundInWindow = newPrefixIndex != -1; final boolean foundInBackBuffer = newPrefixIndex < backBuffer.length(); if (foundInWindow && foundInBackBuffer) { prefixIndex = backBuffer.length() - newPrefixIndex; prefixLength = i; prefixFollow = safeSubChar(input, middle + i); } } final int skip = prefixLength + 1; start += skip; middle += skip; end += skip; log.debug("New codeword: ({},{},{}) skip +{}", prefixIndex, prefixLength, prefixFollow, skip); result.add(new LZ77Codeword(prefixIndex, prefixLength, prefixFollow)); } return result; } private  LZ77(); static List<LZ77Codeword> encode(final char[] input, final int backBufferSize, final int frontBufferSize); static char[] decode(final List<LZ77Codeword> input); }
LZ77 { public static List<LZ77Codeword> encode(final char[] input, final int backBufferSize, final int frontBufferSize) { final List<LZ77Codeword> result = new LinkedList<>(); int middle = 0; int start = middle - backBufferSize; int end = middle + frontBufferSize; while (middle < input.length) { log.debug("Window (start,middle,end): ({},{},{})", start, middle, end); final String backBuffer = safeSubString(input, start, middle); final String frontBuffer = safeSubString(input, middle, end); log.debug("Buffers: ({}|{})", backBuffer, frontBuffer); final int maxPrefixLength = frontBuffer.length(); final String buffer = safeSubString(input, start, end); int prefixIndex = 0; int prefixLength = 0; char prefixFollow = safeSubChar(input, middle); for (int i = 1; i <= maxPrefixLength; i++) { final String newPrefix = safeSubString(input, middle, middle + i); final int newPrefixIndex = buffer.indexOf(newPrefix); final boolean foundInWindow = newPrefixIndex != -1; final boolean foundInBackBuffer = newPrefixIndex < backBuffer.length(); if (foundInWindow && foundInBackBuffer) { prefixIndex = backBuffer.length() - newPrefixIndex; prefixLength = i; prefixFollow = safeSubChar(input, middle + i); } } final int skip = prefixLength + 1; start += skip; middle += skip; end += skip; log.debug("New codeword: ({},{},{}) skip +{}", prefixIndex, prefixLength, prefixFollow, skip); result.add(new LZ77Codeword(prefixIndex, prefixLength, prefixFollow)); } return result; } private  LZ77(); static List<LZ77Codeword> encode(final char[] input, final int backBufferSize, final int frontBufferSize); static char[] decode(final List<LZ77Codeword> input);  }