Created
September 21, 2022 15:35
-
-
Save pepyta/da59acd64b0dd1c0f3badc1a77e9933e to your computer and use it in GitHub Desktop.
LZW Encoding and decoding algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.Set; | |
| import java.util.HashSet; | |
| import java.util.List; | |
| import java.io.Console; | |
| import java.util.ArrayList; | |
| import java.util.EmptyStackException; | |
| public class Lzw { | |
| public static void main(String[] args) { | |
| if(args.length == 0) throw new Error("Pass the message as a paramter!"); | |
| String str = args[0]; | |
| EncodedMessage encoded = EncodedMessage.encode(str); | |
| encoded.printDictionary(); | |
| System.out.println("Result: " + encoded.toString()); | |
| System.out.println("Decoded: " + encoded.decode()); | |
| } | |
| } | |
| class EncodedMessage { | |
| private List<String> dictionary; | |
| private List<Integer> message; | |
| private EncodedMessage(List<String> dictionary, List<Integer> message) { | |
| this.dictionary = dictionary; | |
| this.message = message; | |
| } | |
| public static EncodedMessage encode(String input) { | |
| Set<Character> set = new HashSet<Character>(); | |
| for(char c: input.toCharArray()) { | |
| set.add(c); | |
| } | |
| List<String> dictionary = new ArrayList<String>(); | |
| for(char c: set) { | |
| dictionary.add(c + ""); | |
| } | |
| String curr = input.charAt(0) + ""; | |
| List<Integer> result = new ArrayList<Integer>(); | |
| int index = dictionary.indexOf(curr); | |
| for(int i = 1; i < input.length(); i++) { | |
| curr += input.charAt(i); | |
| int newIndex = dictionary.indexOf(curr); | |
| if(newIndex == -1) { | |
| dictionary.add(curr); | |
| curr = curr.charAt(curr.length() - 1) + ""; | |
| result.add(index + 1); | |
| index = dictionary.indexOf(curr); | |
| } else { | |
| index = newIndex; | |
| } | |
| } | |
| result.add(index + 1); | |
| return new EncodedMessage(dictionary, result); | |
| } | |
| public String decode() { | |
| String result = ""; | |
| for(int key: this.message) { | |
| result += this.dictionary.get(key - 1); | |
| } | |
| return result; | |
| } | |
| @Override | |
| public String toString() { | |
| String result = ""; | |
| for(int key: this.message) { | |
| result += key + " "; | |
| } | |
| return result; | |
| } | |
| public void printDictionary() { | |
| for(int i = 0; i < this.dictionary.size(); i++) { | |
| System.out.println(this.dictionary.get(i) + "\t" + (i + 1)); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment