@Test public void testEncoding() { final String value = "abbcbcababcaabcaab"; final List<LZ78Codeword> encoded = LZ78.encode(value.toCharArray()); assertEquals(7, encoded.size()); assertEquals("(0,a)", encoded.get(0).toString()); assertEquals("(0,b)", encoded.get(1).toString()); assertEquals("(2,c)", encoded.get(2).toString()); assertEquals("(3,a)", encoded.get(3).toString()); assertEquals("(2,a)", encoded.get(4).toString()); assertEquals("(4,a)", encoded.get(5).toString()); assertEquals("(6,b)", encoded.get(6).toString()); }
public static List<LZ78Codeword> encode(final char[] input) { final List<LZ78Codeword> result = new LinkedList<>(); int position = 0; final Tree tree = new Tree(); while (position <= input.length - 1) { log.debug("Encoding from position: {}", position); Node bestLeafSoFar = tree.root; int longestPrefixSoFar = 0; for (int prefixEnd = position + 1; prefixEnd <= input.length; prefixEnd++) { final String prefix = safeSubString(input, position, prefixEnd); assert prefix.length() >= 1; log.debug("Trying to find prefix in dictionary: {} (length = {})", prefix, prefix.length()); final char prefixChar = prefix.charAt(longestPrefixSoFar); if (bestLeafSoFar.hasChild(prefixChar)) { bestLeafSoFar = bestLeafSoFar.getChild(prefixChar); longestPrefixSoFar = prefix.length(); } else { break; } } final char firstTerminalAfterPrefix = safeSubChar(input, position + longestPrefixSoFar); log.debug("Longest prefix found: (length = {}, start = {})", longestPrefixSoFar, bestLeafSoFar.id); log.debug("Extending node {} with {}.", bestLeafSoFar.id, firstTerminalAfterPrefix); tree.extend(bestLeafSoFar, firstTerminalAfterPrefix); final LZ78Codeword newCodeword = new LZ78Codeword(bestLeafSoFar.id, firstTerminalAfterPrefix); log.debug("Adding codeword: {}", newCodeword); result.add(newCodeword); position += longestPrefixSoFar + 1; } return result; }
LZ78 { public static List<LZ78Codeword> encode(final char[] input) { final List<LZ78Codeword> result = new LinkedList<>(); int position = 0; final Tree tree = new Tree(); while (position <= input.length - 1) { log.debug("Encoding from position: {}", position); Node bestLeafSoFar = tree.root; int longestPrefixSoFar = 0; for (int prefixEnd = position + 1; prefixEnd <= input.length; prefixEnd++) { final String prefix = safeSubString(input, position, prefixEnd); assert prefix.length() >= 1; log.debug("Trying to find prefix in dictionary: {} (length = {})", prefix, prefix.length()); final char prefixChar = prefix.charAt(longestPrefixSoFar); if (bestLeafSoFar.hasChild(prefixChar)) { bestLeafSoFar = bestLeafSoFar.getChild(prefixChar); longestPrefixSoFar = prefix.length(); } else { break; } } final char firstTerminalAfterPrefix = safeSubChar(input, position + longestPrefixSoFar); log.debug("Longest prefix found: (length = {}, start = {})", longestPrefixSoFar, bestLeafSoFar.id); log.debug("Extending node {} with {}.", bestLeafSoFar.id, firstTerminalAfterPrefix); tree.extend(bestLeafSoFar, firstTerminalAfterPrefix); final LZ78Codeword newCodeword = new LZ78Codeword(bestLeafSoFar.id, firstTerminalAfterPrefix); log.debug("Adding codeword: {}", newCodeword); result.add(newCodeword); position += longestPrefixSoFar + 1; } return result; } }
LZ78 { public static List<LZ78Codeword> encode(final char[] input) { final List<LZ78Codeword> result = new LinkedList<>(); int position = 0; final Tree tree = new Tree(); while (position <= input.length - 1) { log.debug("Encoding from position: {}", position); Node bestLeafSoFar = tree.root; int longestPrefixSoFar = 0; for (int prefixEnd = position + 1; prefixEnd <= input.length; prefixEnd++) { final String prefix = safeSubString(input, position, prefixEnd); assert prefix.length() >= 1; log.debug("Trying to find prefix in dictionary: {} (length = {})", prefix, prefix.length()); final char prefixChar = prefix.charAt(longestPrefixSoFar); if (bestLeafSoFar.hasChild(prefixChar)) { bestLeafSoFar = bestLeafSoFar.getChild(prefixChar); longestPrefixSoFar = prefix.length(); } else { break; } } final char firstTerminalAfterPrefix = safeSubChar(input, position + longestPrefixSoFar); log.debug("Longest prefix found: (length = {}, start = {})", longestPrefixSoFar, bestLeafSoFar.id); log.debug("Extending node {} with {}.", bestLeafSoFar.id, firstTerminalAfterPrefix); tree.extend(bestLeafSoFar, firstTerminalAfterPrefix); final LZ78Codeword newCodeword = new LZ78Codeword(bestLeafSoFar.id, firstTerminalAfterPrefix); log.debug("Adding codeword: {}", newCodeword); result.add(newCodeword); position += longestPrefixSoFar + 1; } return result; } private  LZ78(); }
LZ78 { public static List<LZ78Codeword> encode(final char[] input) { final List<LZ78Codeword> result = new LinkedList<>(); int position = 0; final Tree tree = new Tree(); while (position <= input.length - 1) { log.debug("Encoding from position: {}", position); Node bestLeafSoFar = tree.root; int longestPrefixSoFar = 0; for (int prefixEnd = position + 1; prefixEnd <= input.length; prefixEnd++) { final String prefix = safeSubString(input, position, prefixEnd); assert prefix.length() >= 1; log.debug("Trying to find prefix in dictionary: {} (length = {})", prefix, prefix.length()); final char prefixChar = prefix.charAt(longestPrefixSoFar); if (bestLeafSoFar.hasChild(prefixChar)) { bestLeafSoFar = bestLeafSoFar.getChild(prefixChar); longestPrefixSoFar = prefix.length(); } else { break; } } final char firstTerminalAfterPrefix = safeSubChar(input, position + longestPrefixSoFar); log.debug("Longest prefix found: (length = {}, start = {})", longestPrefixSoFar, bestLeafSoFar.id); log.debug("Extending node {} with {}.", bestLeafSoFar.id, firstTerminalAfterPrefix); tree.extend(bestLeafSoFar, firstTerminalAfterPrefix); final LZ78Codeword newCodeword = new LZ78Codeword(bestLeafSoFar.id, firstTerminalAfterPrefix); log.debug("Adding codeword: {}", newCodeword); result.add(newCodeword); position += longestPrefixSoFar + 1; } return result; } private  LZ78(); static List<LZ78Codeword> encode(final char[] input); static char[] decode(final List<LZ78Codeword> input); }
LZ78 { public static List<LZ78Codeword> encode(final char[] input) { final List<LZ78Codeword> result = new LinkedList<>(); int position = 0; final Tree tree = new Tree(); while (position <= input.length - 1) { log.debug("Encoding from position: {}", position); Node bestLeafSoFar = tree.root; int longestPrefixSoFar = 0; for (int prefixEnd = position + 1; prefixEnd <= input.length; prefixEnd++) { final String prefix = safeSubString(input, position, prefixEnd); assert prefix.length() >= 1; log.debug("Trying to find prefix in dictionary: {} (length = {})", prefix, prefix.length()); final char prefixChar = prefix.charAt(longestPrefixSoFar); if (bestLeafSoFar.hasChild(prefixChar)) { bestLeafSoFar = bestLeafSoFar.getChild(prefixChar); longestPrefixSoFar = prefix.length(); } else { break; } } final char firstTerminalAfterPrefix = safeSubChar(input, position + longestPrefixSoFar); log.debug("Longest prefix found: (length = {}, start = {})", longestPrefixSoFar, bestLeafSoFar.id); log.debug("Extending node {} with {}.", bestLeafSoFar.id, firstTerminalAfterPrefix); tree.extend(bestLeafSoFar, firstTerminalAfterPrefix); final LZ78Codeword newCodeword = new LZ78Codeword(bestLeafSoFar.id, firstTerminalAfterPrefix); log.debug("Adding codeword: {}", newCodeword); result.add(newCodeword); position += longestPrefixSoFar + 1; } return result; } private  LZ78(); static List<LZ78Codeword> encode(final char[] input); static char[] decode(final List<LZ78Codeword> input);  }