Plan Filkomprimering Principper Huffmans algoritme
Generering af krydsreferencer
Simulering
Hændelsesbaseret simulering Procesbaseret simulering
Filkomprimering Komprimering reducerer størrelsen af en fil
for at spare plads ved lagring
for at spare tid ved transmission Mange filer har et lavt informationsindhold. Komprimering benyttes til
tekst: nogle bogstaver er hyppigere end andre
grafik: store ensartede områder
lyd: gentagne mønstre
Run-length encoding Komprimering ved tælling af gentagelser. Komprimering af tekst:
Strengen AAAABBBAABBBBBCCCCCCCDABCBAAABBBBCCCD
omkodes til 4A3BAA5B8CDABCB3A4B3CD Med escape-tegn (her ’\’): \4A\3BAA\5B\8CDABCB\3A\4B\3CD Run-length encoding er normalt ikke særlig effektiv for tekstfiler.
Fixed-length encoding Strengen ABRACADABRA (11 tegn)
fylder
11 * 8 bit = 88 bit i byte-kode
11 * 5 bit = 55 bit i 5-bit-kode
11 * 3 bit = 33 bit i 3-bit-kode
(kun 5 forskellige bogstaver) D forekommer kun 1 gang, mens A forekommer 5 gange.
Vi kan forsøge at benytte korte koder for bogstaver, der forekommer hyppigt.
Variable-length encoding Hvis A = 0, B = 1, R = 01, C = 10 og D = 11, kan
ABRACADABRA
kodes som
0 1 01 0 10 0 11 0 1 01 0 (kun 15 bit) Problemet skyldes, at nogle koder er præfiks for andre. For eksempel er A præfiks for R. Men denne kode kan kun afkodes (dekomprimeres), hvis der anvendes skilletegn (f.eks. et blanktegn).
Præfikskoder En præfikskode for tegnene A, B, C, D og R: A = 11, B = 00, C = 010, D = 10 og R = 011.
Strengen ABRACADABRA kodes som 1100011110101110110001111 (25 bit) En kode, hvor ingen tegnkode er præfiks for nogen anden tegnkode, kaldes en præfikskode. Strengen kan kun afkodes på én måde. Men den valgte præfikskode er ikke den optimale.
Denne kan bestemmes ved hjælp af Huffmans algoritme.
Tries Koden repræsenteres ved et træ, et såkaldt trie (udtales traj). A B R C D 0 1 0 1 1 1 0 0 Tegnene er placeret i træets blade.
En venstre gren svarer til 0.
En højre gren svarer til 1. Kode: A = 0, B = 100, C = 110, D = 111 og R = 101.
Strengen ABRACADABRA kodes som 01001010110011101001010 (23 bit)
Huffmans algoritme
(D. A. Huffman, 1952) Beregn frekvenserne for de tegn, der indgår i meddelelsen
(eller benyt en foruddefineret frekvenstabel). Tegn Frekvens
A 5
B 2
C 1
D 1
R 2 Byg et trie ved successivt af kombinere de to mindste frekvenser.
Huffmans algoritme A 5 B 2 R 2 C 1 D 1 2 4 6 11 Start med et træ for hvert tegn.
Sålænge der er mere end ét træ:
sammensæt de 2 “billigste” træer til 1 træ
ved at tilføje en ny knude som rod. Træet er optimalt (minimerer ∑dybdei*frevensi) - men ikke unikt
Implementering af Huffmans algoritme class HuffmanTree {
HuffmanTree(Node root) {
this.root = root;
}
Node root;
}
class Node {...}
class Character extends Node {...} Repræsentation af træ:
class Node implements Comparable {
Node(int w) { weight = w; }
Node(int w, Node l, Node r) {
weight = w; left = l; right = r;
}
public int compareTo(Object rhs) {
Node n = (Node) rhs;
return weight < n.weight ? -1 :
weight == n.weight ? 0 : -1;
}
int weight;
Node left, right;
} weight angiver summen af bladenes frekvenser i det træ,
der har knuden som rod.
class Character extends Node {
Character(char c, int w) {
super(w);
character = c;
}
char character;
} Character-objekter udgør træets blade
Problemer for Huffmans algoritme Kodetræet skal medsendes (typisk 255 bytes)
Beregningsmæssigt dyr
To gennemløb af filen (frekvensbestemmelse + kodning)
Typisk 25% pladsreduktion, men ikke optimal
LZW-komprimering
(Lempel, Ziv og Welch, 1977) Opbyg successivt en ordbog i form af et trie. Eksempel: ABRACADABRA 0 A 1 B 2 R 3 C 4 D 5 B 6 A 7 Fixed-length encoding Kodning: ABR1C1D63A
Generering af krydsreferencer Udvikling af et program, der indlæser et Java-program og udskriver alle programmets navne i sorteret orden sammen med de linjenumre, hvori de forekommer.
Navne, der kun forekommer i kommentarer, tekststrenge og tegnkonstanter, skal ikke medtages.
Eksempel /* Trivial application that displays a string */
public class TrivialApplication {
public static void main(String[] args) {
System.out.println("Hello World!");
}
} input: output: String: 3
System: 4
TrivialApplication: 2
args: 3
class: 2
main: 3
out: 4
println: 4
public: 2, 3
static: 3
void: 3 1
2
3
4
5
6
Datastrukturer og algoritme Opbyg et binært søgetræ indeholdende de fundne navne.
Hver knude indholder et navn og en kø af de linjenumre, hvori navnet forekommer. Udskriv til slut søgetræets indhold i sorteret orden. TreeMap theIdentifiers; ArrayList lines;
Comments