In this assignment, you will learn about the famous Lempel-Ziv-Welch (LZW) compr
ID: 3534351 • Letter: I
Question
In this assignment, you will learn about the famous Lempel-Ziv-Welch (LZW) compression algorithm. Most compression algorithms including UNIX compress are based on the LZW algorithm. The LZW algorithm compresses a given text by figuring out patterns which appear very often in the text. The basic idea is to replace (perhaps very long) patterns which appear many times by a much shorter code. Read about this algorithm here .Your assignment is to implement the LZW algorithm. You can assume that the input text contains english characters (capital and small), space, and full stop. You need to write two programs - one for compressing an input text, and the other to uncompress the compressed text to the original text. To implement the dictionary of code and key, you will use a hash table. Use your own hash function, but you must use quadratic probing to resolve collisions. In this assignment, you will learn about the famous Lempel-Ziv-Welch (LZW) compression algorithm. Most compression algorithms including UNIX compress are based on the LZW algorithm. The LZW algorithm compresses a given text by figuring out patterns which appear very often in the text. The basic idea is to replace (perhaps very long) patterns which appear many times by a much shorter code. Read about this algorithm here .
Your assignment is to implement the LZW algorithm. You can assume that the input text contains english characters (capital and small), space, and full stop. You need to write two programs - one for compressing an input text, and the other to uncompress the compressed text to the original text. To implement the dictionary of code and key, you will use a hash table. Use your own hash function, but you must use quadratic probing to resolve collisions.
Explanation / Answer
package lzw;
/**
*time of start 01:47
* @author tarun
*/
import java.util.*;
import java.io.*;
class Dictionary
{
String dict[] = new String[10007];
public void push(String s)//tested ok
{
int hashvalue = Hash(s);
int c;
int i;
for( i = 0; i<10 ;i++)
{
c = hashvalue + i*i;
c = c007;
if(dict[c] == null)
{
dict[c]=s;
break;
}
}
if(i==10)
System.out.println("could not compress, please increase the size of array");
}
public static int Hash(String s)//tested ok
{
char c;
int cc, ans;
if(s.length()== 1)
{
ans = s.charAt(0);
return ans;
}
else
{
ans = 255;
for(int i = 0; i< s.length(); i++)
{
c = s.charAt(i);
cc = c;
ans = cc+ans;
}
ans = ans0007;
return ans;
}
}
public int Search(String s)//tested ok 1 means its present 0 means it isn't
{
int hashvalue,c, ans;
hashvalue = Hash(s);
for(int i=0;i<10;i++)
{
c =hashvalue + i*i;
if(dict[c] == null ? s == null : dict[c].equals(s))
{
ans = 1;
return ans;
}
}
ans = 0;
return ans;
}
public int getcode(String s) //tested ok 0 means not present
{
int hashvalue,c, ans;
hashvalue = Hash(s);
for(int i=0;i<10;i++)
{
c =hashvalue + i*i;
if(dict[c] == null ? s == null : dict[c].equals(s))
{
ans = c;
return ans;
}
}
ans = 0;
return ans;
}
public void singlestring(String s )//tested ok
{
int len = s.length();
char a ;
String aa ;
int searchresult;
for( int i=0; i<len; i++)
{
a = s.charAt(i);
aa = ""+a;
searchresult = Search(aa);
if(searchresult==0)
{
push(aa);
}
aa ="";
}
}
public void printdictionary ()//tested ok
{
for(int k = 0; k < 10007 ; k++)
{
if(dict[k]!=null)
{
System.out.println(dict[k]);
}
}
}
public String compression(String s)//tested ok
{
singlestring(s);
String w,code;
code = "";
w ="";
String q = "";
for(int i=0;i<s.length();i++)
{
w = w + s.charAt(i);
if(Search(w)== 1)
{
q = q + s.charAt(i);
}
else
{
push(w);
code = code + ","+getcode(q);
w =""+ s.charAt(i);
q = w;
}
if(i== s.length()-1)
code = code +","+getcode(q);
}
w = "";
code = code + ",";
return code;
}
public int check(int i)//tested ok
{
int ans = 1 ;
if (dict[i]== null)
return ans;
else
ans = 0;
return ans;
}
public String gete(String code,int j)//tested ok
{
String e="";
int k = 0;
int i;
for(i = 0; i<code.length(); i++)
{
if(code.charAt(i)==',')
{
k = k+1;
if(k==j+1)
{
for(j=i+1;j<code.length();j++)
{
if(code.charAt(j)== ',')
{
return e;
}
else
e = e + code.charAt(j);
}
}
}
}
return null;
}
public void deleteextra()
{
for(int i=256; i<10007; i++)
dict[i]=null;
}
public String decompress(String s)//troubleshooting
{
String tmp = "";
int len = s.length();
int a;
String phrase,ans="",tmp2;
for(int i = 0 ; i< len ; i++)
{
if(gete(s,i)!= null)
{
tmp2 = gete(s,i);
a = Integer.parseInt(tmp2);
if(dict[a] != null)
{
phrase = dict[a];
ans = ans+ phrase;
push(tmp + phrase.charAt(0));
}
else
{
phrase = tmp + tmp.charAt(0);
ans = ans + phrase;
push(phrase);
}
tmp =phrase;
}
}
return ans;
}
}
public class LZW {
public static String rds( int n, int len)
{
Random randomGenerator = new Random();
String s="";
for(int i=0; i < len; i++)
{
char a;
a = (char) (randomGenerator.nextInt(n) + 97);
s = s+a;
}
return s;
}
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Dictionary d = new Dictionary();
Dictionary d1 = new Dictionary();
System.out.println("do you want to enter a text to compress or compress a random text? press 0 for random text and press 1 for file input ");
int choice = Integer.parseInt(br.readLine());
if(choice==0)
{
System.out.println("enter the length of random text to be generated");
int length = Integer.parseInt(br.readLine());
System.out.println("enter the number of distinct alphabets required");
int alpha = Integer.parseInt(br.readLine());
String output = rds(alpha , length);
d.singlestring(output);
d1.singlestring(output);
System.out.println("the random text is:"+output);
String code = d.compression(output);
System.out.println("the compressed code is :" + code);
System.out.println("when you decompress the above code you get:");
String s = d1.decompress(code);
System.out.println(s);
}
if (choice ==1)
{
PrintWriter fout = new PrintWriter(new FileWriter("code.txt"));
Scanner fin = new Scanner(new FileReader("IN.txt"));
String sLine,k="";
while (fin.hasNext()) {
sLine = fin.next();
k = k+sLine;
}
String code = d.compression(k);
fout.println(code);
fout.close();
fin.close();
}
}
}