package bitio;
import java.io.*;
import java.net.URL;
import hjelpeklasser.*;
public class Huffman
{
public static String[] ascii =
{"NUL","SOH","STX","ETX","EOT","ENQ","ACK","BEL","BS","HT","LF",
"VT","FF","CR","SO","SI","DLE","DC1","DC2","DC3","DC4","NAK",
"SYN","ETB","CAN","EM","SUB","ESC","FS","GS","RS","US"};
private static class Node
{
private int frekvens;
private Node venstre;
private Node høyre;
private Node() {}
private Node(int frekvens, Node v, Node h)
{
this.frekvens = frekvens;
venstre = v;
høyre = h;
}
}
private static class BladNode extends Node
{
private final char tegn;
private BladNode(char tegn, int frekvens)
{
super(frekvens, null, null);
this.tegn = tegn;
}
}
private static Node byggHuffmanTre(int[] frekvens)
{
PrioritetsKø<Node> kø =
new HeapPrioritetsKø<>((p,q) -> p.frekvens - q.frekvens);
for (int i = 0; i < frekvens.length; i++)
if (frekvens[i] > 0)
kø.leggInn(new BladNode((char)i, frekvens[i]));
if (kø.antall() < 2)
throw new IllegalArgumentException("Det er for få tegn!");
while (kø.antall() > 1)
{
Node v = kø.taUt();
Node h = kø.taUt();
int sum = v.frekvens + h.frekvens;
kø.leggInn(new Node(sum, v, h));
}
return kø.taUt();
}
private static void finnBitkoder(Node p, String kode, String[] koder)
{
if (p instanceof BladNode) koder[((BladNode)p).tegn] = kode;
else
{
finnBitkoder(p.venstre, kode + '0', koder);
finnBitkoder(p.høyre, kode + '1', koder);
}
}
public static String[] stringBitkoder(int[] frekvens)
{
Node rot = byggHuffmanTre(frekvens);
String[] bitkoder = new String[frekvens.length];
finnBitkoder(rot,"",bitkoder);
return bitkoder;
}
public static int[] stringFrekvens(String tekst)
{
int[] frekvens = new int[256];
for (int i = 0; i < tekst.length(); i++)
frekvens[tekst.charAt(i)]++;
return frekvens;
}
public static int[] streamFrekvens(InputStream inn) throws IOException
{
int[] frekvens = new int[256];
int tegn;
while ((tegn = inn.read()) != -1) frekvens[tegn]++;
inn.close();
return frekvens;
}
private static void finnLengder(Node p, int lengde, int[] lengder)
{
if (p.venstre == null)
{
lengder[((BladNode)p).tegn] = lengde;
}
else
{
finnLengder(p.venstre, lengde + 1, lengder);
finnLengder(p.høyre, lengde + 1, lengder);
}
}
public static int[] finnBitkoder(int[] lengder)
{
int[] blader = new int[32];
for (int lengde : lengder)
if (lengde < 32) blader[lengde]++;
else throw new IllegalStateException("Bitkodelengde > 31!");
int[] pos = new int[32];
for (int k = 31; k > 0; k--) pos[k - 1] = (pos[k] + blader[k])/2;
int[] bitkoder = new int[lengder.length];
for (int i = 0; i < bitkoder.length; i++)
if (lengder[i] > 0) bitkoder[i] = pos[lengder[i]]++;
return bitkoder;
}
public static int antBinSiffer(int k)
{
return k == 0 ? 0 : 32 - Integer.numberOfLeadingZeros(k);
}
public static void
komprimer(String fraUrl, String tilFil) throws IOException
{
InputStream inn = new BufferedInputStream
((new URL(fraUrl)).openStream());
int[] frekvens = streamFrekvens(inn);
Node rot = byggHuffmanTre(frekvens);
int[] lengder = new int[frekvens.length];
finnLengder(rot, 0, lengder);
int[] bitkoder = finnBitkoder(lengder);
int vaktpost = Tabell.maks(lengder);
int k = antBinSiffer(lengder[vaktpost]);
BitOutputStream ut =
new BitOutputStream(tilFil);
ut.writeBits(k, 3);
for (int lengde : lengder)
{
if (lengde == 0) ut.write0Bit();
else
ut.writeBits(lengde | 1 << k, k + 1);
}
int s = antBinSiffer(frekvens[vaktpost]);
ut.writeBits(s, 5);
ut.writeBits(frekvens[vaktpost], s);
inn = new BufferedInputStream
((new URL(fraUrl)).openStream());
int tegn;
while ((tegn = inn.read()) != -1)
{
ut.writeBits(bitkoder[tegn], lengder[tegn]);
}
ut.writeBits(bitkoder[vaktpost], lengder[vaktpost]);
inn.close();
ut.close();
}
private static Node byggKanoniskTre(int[] lengder)
{
int[] bitkoder = finnBitkoder(lengder);
Node rot = new Node();
for (int i = 0; i < lengder.length; i++)
{
if (lengder[i] > 0)
{
int n = bitkoder[i];
int k = (1 << lengder[i]) >> 1;
Node p = rot;
while (k > 1)
{
if ((k & n) == 0)
{
if (p.venstre == null) p.venstre = new Node();
p = p.venstre;
}
else
{
if (p.høyre == null) p.høyre = new Node();
p = p.høyre;
}
k >>= 1;
}
if ((n & 1) == 0) p.venstre = new BladNode((char)i,0);
else p.høyre = new BladNode((char)i,0);
}
}
return rot;
}
public static void
dekomprimer1(String fraUrl, OutputStream ut) throws IOException
{
BitInputStream inn =
new BitInputStream((new URL(fraUrl)).openStream());
int k = inn.readBits(3);
int[] lengder = new int[256];
for (int i = 0; i < lengder.length; i++)
{
if (inn.readBit() == 1)
{
lengder[i] = inn.readBits(k);
}
}
int vaktpost = Tabell.maks(lengder);
int s = inn.readBits(5);
int vaktpostfrekvens = inn.readBits(s) + 1;
Node rot = byggKanoniskTre(lengder);
int frekvens = 0;
for (Node p = rot; ; p = rot)
{
while (p.venstre != null)
p = inn.readBit() == 0 ? p.venstre : p.høyre;
if (((BladNode)p).tegn == vaktpost)
{
if (++frekvens == vaktpostfrekvens) break;
}
ut.write(((BladNode)p).tegn);
}
ut.close();
inn.close();
}
public static void
dekomprimer1(String fraUrl, String tilFil) throws IOException
{
dekomprimer1(fraUrl, new BitOutputStream(tilFil));
}
public static byte[] lagTegntabell(int[] lengder, int[] tilbake, int n)
{
int[] bitkoder = finnBitkoder(lengder);
byte[] tegntabell = new byte[1 << n];
for (int i = 0; i < lengder.length; i++)
if (lengder[i] > 0)
{
int d = n - lengder[i];
tilbake[i] = d;
int fra = bitkoder[i] << d;
int til = fra + (1 << d);
for (int j = fra; j < til; j++)
tegntabell[j] = (byte)i;
}
return tegntabell;
}
public static void
dekomprimer2(String fraUrl, OutputStream ut) throws IOException
{
BitInputStream inn =
new BitInputStream((new URL(fraUrl)).openStream());
int k = inn.readBits(3);
int[] lengder = new int[256];
for (int i = 0; i < lengder.length; i++)
{
if (inn.readBit() == 1)
{
lengder[i] = inn.readBits(k);
}
}
int vaktpost = Tabell.maks(lengder);
int s = inn.readBits(5);
int vaktpostfrekvens = inn.readBits(s) + 1;
int n = lengder[vaktpost];
int[] tilbake = new int[lengder.length];
byte[] tegntabell = lagTegntabell(lengder, tilbake, n);
int frekvens = 0;
for(;;)
{
int tegn = tegntabell[inn.readBits(n)] & 255;
if (tegn == vaktpost)
{
if (++frekvens == vaktpostfrekvens) break;
}
ut.write(tegn);
inn.unreadBits(tilbake[tegn]);
}
ut.close();
inn.close();
}
public static void
dekomprimer2(String fraUrl, String tilFil) throws IOException
{
dekomprimer2(fraUrl, new BitOutputStream(tilFil));
}
public static int[] treHøyde(int[] blader, int nivå)
{
int n = blader.length;
int[] noder = new int[n];
noder[n-1] = blader[n-1];
for (int k = n - 1; k > nivå; k--)
noder[k - 1] = noder[k]/2 + blader[k-1];
int maks = noder[Tabell.maks(noder)];
int[] høyder = new int[maks];
for (int i = n - 2; i >= nivå; i--)
{
int k = noder[i] - blader[i];
for (int j = 0; j < k; j++)
{
høyder[j] = Math.max(høyder[2*j],høyder[2*j+1]) + 1;
}
for (int j = k; j < noder[i+1]; j++) høyder[j] = 0;
}
int[] h = new int[noder[nivå] - blader[nivå]];
System.arraycopy(høyder,0,h,0,h.length);
return h;
}
public static void
dekomprimer3(String fraUrl, OutputStream ut) throws IOException
{
BitInputStream inn =
new BitInputStream((new URL(fraUrl)).openStream());
int k = inn.readBits(3);
int[] lengder = new int[256];
for (int i = 0; i < lengder.length; i++)
{
if (inn.readBit() == 1)
{
lengder[i] = inn.readBits(k);
}
}
int vaktpost = Tabell.maks(lengder);
int s = inn.readBits(5);
int vaktpostfrekvens = inn.readBits(s) + 1;
int n = lengder[vaktpost];
int[] blader = new int[n + 1];
for (int lengde : lengder)
if (lengde > 0) blader[lengde]++;
int[] bitkoder = finnBitkoder(lengder);
int m = (n + 1)/2;
byte[] tegntabell = new byte[1 << m];
int[] høyder = treHøyde(blader, m);
int grense = høyder.length;
for (int i = 0; i < grense; i++)
{
tegntabell[i] = (byte)høyder[i];
}
int[] tilbake = new int[lengder.length];
byte[][] tegntabeller = new byte[grense][];
for (int i = 0; i < grense; i++)
{
tegntabeller[i] = new byte[1 << høyder[i]];
}
for (int i = 0; i < lengder.length; i++)
{
int lengde = lengder[i];
if (lengde > 0)
{
if (lengde <= m)
{
int d = m - lengde;
tilbake[i] = d;
int fra = bitkoder[i] << d;
int til = fra + (1 << d);
for (int j = fra; j < til; j++)
tegntabell[j] = (byte)i;
}
else
{
int kode = bitkoder[i];
int d1 = lengde - m;
int kode1 = kode >> d1;
int kode2 = kode & ((1 << d1) - 1);
byte[] b = tegntabeller[kode1];
int d2 = tegntabell[kode1] - d1;
tilbake[i] = d2;
int fra = kode2 << d2;
int til = fra + (1 << d2);
for (int j = fra; j < til; j++) b[j] = (byte)i;
}
}
}
int frekvens = 0;
for(;;)
{
int lest = inn.readBits(m);
int tall = tegntabell[lest] & 255;
if (lest < grense)
{
byte[] b = tegntabeller[lest];
lest = inn.readBits(tall);
tall = b[lest] & 255;
}
if (tall == vaktpost)
{
if (++frekvens == vaktpostfrekvens) break;
}
ut.write(tall);
inn.unreadBits(tilbake[tall]);
}
ut.close();
inn.close();
}
public static void
dekomprimer3(String fraUrl, String tilFil) throws IOException
{
dekomprimer3(fraUrl, new BitOutputStream(tilFil));
}
}