package bitio;
import java.util.*;
import java.io.*;
import java.net.URL;
public class LZW
{
private static final int LZW_GRENSE = 16;
private static final int MAKS = (1 << LZW_GRENSE) - 1;
private static final int NYTT_BITFORMAT = 256;
private static final int FØRSTE_KODE = 257;
public static List<Integer> komprimer(String melding)
{
char c = melding.charAt(0);
String s = String.valueOf(c);
int kode = c;
int nestekode = 256;
Map<String,Integer> ordbok = new HashMap<>();
List<Integer> resultat = new ArrayList<>();
for (int i = 1; i < melding.length(); i++)
{
c = melding.charAt(i);
Integer ordkode = ordbok.get(s + c);
if (ordkode == null)
{
ordbok.put(s + c, nestekode++);
s = String.valueOf(c);
resultat.add(kode);
kode = c;
}
else
{
kode = ordkode;
s = s + c;
}
}
resultat.add(kode);
return resultat;
}
public static String dekomprimer(List<Integer> koder)
{
int kode = koder.get(0);
String t;
String s = String.valueOf((char)kode);
char c;
StringBuilder resultat = new StringBuilder(s);
int nestekode = 256;
Map<Integer,String> ordbok = new TreeMap<>();
for (int i = 1; i < koder.size(); i++)
{
kode = koder.get(i);
t = s;
if (kode < nestekode)
{
s = kode < 256 ? String.valueOf((char)kode)
: ordbok.get(kode);
c = s.charAt(0);
}
else
{
c = t.charAt(0);
s = t + c;
}
resultat.append(s);
ordbok.put(nestekode, t + c);
nestekode++;
}
return resultat.toString();
}
public static int komprimer0(InputStream inn, BitOutputStream ut)
throws IOException
{
int bitformat = 9, bitGrense = 512;
int c = inn.read();
if (c == -1) return;
int antallInnlesteTegn = 1;
Map<String,Integer> ordbok = new HashMap<>();
String s = String.valueOf((char)c);
int kode = c;
int nesteKode = FØRSTE_KODE;
while ((c = inn.read()) != -1)
{
antallInnlesteTegn++;
Integer ordkode = ordbok.get(s + (char)c);
if (ordkode == null)
{
while (kode >= bitGrense)
{
ut.writeBits(NYTT_BITFORMAT,bitformat);
bitformat++;
bitGrense <<= 1;
}
ut.writeBits(kode, bitformat);
if (nesteKode < MAKS)
{
ordbok.put(s + (char)c, nesteKode);
nesteKode++;
}
s = String.valueOf((char)c);
kode = c;
}
else
{
kode = ordkode;
s += (char)c;
}
}
while (kode >= bitGrense)
{
ut.writeBits(NYTT_BITFORMAT,bitformat);
bitformat++;
bitGrense <<= 1;
}
ut.writeBits(kode,bitformat);
return antallInnlesteTegn;
}
public static void dekomprimer0(BitInputStream inn, OutputStream ut)
throws IOException
{
int bitformat = 9;
int kode = inn.readBits(bitformat);
if (kode == -1) return;
Map<Integer,String> ordbok = new HashMap<>();
int nesteKode = FØRSTE_KODE;
String s = String.valueOf((char)kode);
String t;
char c;
ut.write(kode);
while ((kode = inn.readBits(bitformat)) != -1)
{
while (kode == NYTT_BITFORMAT)
{
bitformat++;
kode = inn.readBits(bitformat);
}
t = s;
if (kode < nesteKode)
{
s = kode < 256 ? String.valueOf((char)kode) : ordbok.get(kode);
c = s.charAt(0);
}
else
{
c = t.charAt(0);
s = t + c;
}
ut.write(s.getBytes());
ordbok.put(nesteKode++, t + c);
}
}
public static int komprimer(InputStream inn, BitOutputStream ut)
throws IOException
{
int bitformat = 9, bitGrense = 512;
int c = inn.read();
if (c == -1) return 0;
int antallInnlesteTegn = 1;
record Node(byte tegn, int forelder) {}
Map<Node,Integer> ordbok = new HashMap<>();
int kode = c;
int nesteKode = FØRSTE_KODE;
while ((c = inn.read()) != -1)
{
antallInnlesteTegn++;
Node node = new Node((byte)c,kode);
Integer ordkode = ordbok.get(node);
if (ordkode == null)
{
if (kode >= bitGrense)
{
ut.writeBits(NYTT_BITFORMAT,bitformat);
bitformat++;
bitGrense *= 2;
}
ut.writeBits(kode,bitformat);
if (nesteKode < MAKS)
{
ordbok.put(node,nesteKode);
nesteKode++;
}
kode = c;
}
else
{
kode = ordkode;
}
}
if (kode >= bitGrense)
{
ut.writeBits(NYTT_BITFORMAT,bitformat);
bitformat++;
}
ut.writeBits(kode,bitformat);
return antallInnlesteTegn;
}
public static int komprimer(String fraUrl, String tilFil) throws IOException
{
InputStream fra = new BufferedInputStream((new URL(fraUrl)).openStream());
BitOutputStream til = new BitOutputStream(new FileOutputStream(tilFil));
int antallInnlesteTegn = LZW.komprimer(fra, til);
fra.close(); til.close();
return antallInnlesteTegn;
}
public static void dekomprimer(BitInputStream inn, OutputStream ut)
throws IOException
{
int bitformat = 9;
int kode = inn.readBits(bitformat);
if (kode == -1) return;
record Node(byte tegn, int forelder) {}
List<Node> ordbok = new ArrayList<>();
for ( i = 0; i < FØRSTE_KODE; i++) ordbok.add(new Node((byte)i,-1));
Deque<Integer> stakk = new ArrayDeque<>();
int forelder = 0, forrige = kode;
int c = kode;
ut.write(c);
while ((kode = inn.readBits(bitformat)) != -1)
{
while (kode == NYTT_BITFORMAT)
{
bitformat++;
kode = inn.readBits(bitformat);
}
if (kode < ordbok.size()) forelder = kode;
else
{
forelder = forrige;
stakk.push(c);
}
while (forelder != -1)
{
Node node = ordbok.get(forelder);
stakk.push((int)node.tegn);
forelder = node.forelder;
}
c = stakk.peek();
while (!stakk.isEmpty()) ut.write(stakk.pop());
ordbok.add(new Node((byte)c,forrige));
forrige = kode;
}
}
public static void dekomprimer(String fraUrl, String tilFil) throws IOException
{
BitInputStream fra = new BitInputStream((new URL(fraUrl)).openStream());
OutputStream til = new BufferedOutputStream(new FileOutputStream(tilFil));
dekomprimer(fra, til);
fra.close(); til.close();
}
}