FÖRBÄTTRINGSARBETE PÅGÅR!
TILDA, ÖVNING 6
Komprimering, kryptering, dokumentering & testning
______________________________________________________________________
**********************************************************************
1. Smittskydd (Tildatenta 030828)
Du har fått ett mail som innehåller tips mot spridning av virus.
Informationen är komprimerad med ett Huffmanträd där nollor motsvarar
vänster och ettor motsvarar höger (se figur, T kodas t.ex. som 11)
Vad står det i meddelandet 010101011000110011001111 ?
o
/ \
/ \
/ \
/ \
o \
/ \ o
/ \ / \
o o o T
/ \ / \ / \
D V H N Ä A
______________________________________________________________________
**********************************************************************
2. "man är mans gamman" kan man läsa i Havamal. Konstruera en
huffmankod för tecknen i detta uttryck (rita trädet) och skriv
sedan upp det i kodad form.
______________________________________________________________________
**********************************************************************
3. Enkel kryptering
Kryptera lösenordet SIMSALABIM med
a) rot13
b) Transpositionschiffer
______________________________________________________________________
**********************************************************************
4. Testning
I labb 6 ska ni göra ett program som kontrollerar syntaxen
för en molekylformel. Skriv upp en samling indata att testa
programmet med!
______________________________________________________________________
**********************************************************************
5. RSA-kryptering (ur kursboken, uppg 2 s. 125)
Du vill hålla ditt turnummer (18) hemligt, och har därför
bestämt dig för att kryptera det med RSA. Välj två primtal
större än 500 och använd dom för att kryptera turnumret.
______________________________________________________________________
**********************************************************************
6. Lempel-Ziv
I denna uppgift ska du avkoda ett meddelande som
komprimerats med Lempel-Zivs metod. Komprimeringen
går till så att komprimeraren lagrar en lista med
strängar som från början enbart innehåller tomma strängen.
Komprimeraren läser tecken för tecken från intexten
den längsta sträng som ligger i strängtabellen.
Sedan skrivs index för denna sträng i tabellen ut,
följt av nästa tecken i intexten.
Strängtabellen utökas med strängen plus nästa tecken.
Därefter läses åter tecken för tecken från intexten.
Så fort en sträng inte finns i strängtabellen läggs den alltså
till.
Metoden kan i (icke-optimerad) kod beskrivas så här:
def lzw(text):
table = Table()
q=Queue()
for c in text: # spara texten tecken för tecken i en kö
q.put(c)
s=""
table.add(s)
kodtext="" # här sparas den kodade texten
while not q.isempty():
c=q.get()
if table.exists(s+c):
s=s+c
else:
kodtext+=str(table.code(s))+c
table.add(s+c)
s=""
if not s=="":
kodtext+=str(table.code(s))
return kodtext
Klassen Table stöder inläggning av strängar, kontroll av
om en sträng finns i tabellen och möjlighet att ta reda
på index hos en speciell sträng.
Index bestäms av ordningen strängarna lades in i, där
den första strängen har index 1.
Uppgiften är att avkoda följande text, där alfabetet
består av versaler och mellanslag kodat som "_".
1S1T1O1R2T4C1K1H4L1M2_6O1L3A1_9O14M1A5
Det vill säga: vad är t om
print lzw(t)
ger ovanstående som utskrift?
Ge också en tabell med strängar och index som motsvarar tabellen i koden!
LÖSNINGAR
______________________________________________________________________
======================================================================
1. Smittskydd
HANDTVÄTT
______________________________________________________________________
======================================================================
2. "man är mans gamman"
Totalt är det 18 tecken. Andelen av respektive tecken:
Tecken | antal | andel
----------------------
m | 4 | 2/9
a | 4 | 2/9
n | 3 | 3/18
" " | 3 | 3/18
ä | 1 | 1/18
r | 1 | 1/18
s | 1 | 1/18
g | 1 | 1/18
Detta ger efter trädskapande till exempel följande huffmankoder:
Tecken | Huffmankod
-------------------
m | 10
a | 11
n | 010
" " | 011
ä | 0000
r | 0001
s | 0010
g | 0011
Vilket ger följande kodning av texten:
10 11 010 011 0000 0001 011 10 11 010 0010 011 0011 11 10 10 11 010
______________________________________________________________________
======================================================================
3. Enkel kryptering
a) FVZFNYNOVZ
b) SSAMIABMLI (andra varianter är också möjliga)
______________________________________________________________________
======================================================================
4. Testning
Tänk på att du ska testa både med giltiga och ogiltiga molekylformler!
______________________________________________________________________
======================================================================
5. RSA-kryptering
p = 503
q = 601
n = p*q = 302303
f = (p-1)*(q-1) = 301200
Välj e så att gcd(e, f) = 1
301200 = 2*5*2*5*2*2*3*251
Faktorn 7 finns inte med, välj e = 7
Krypteringen:
18 upphöjt till 7 modulo 302303
______________________________________________________________________
======================================================================
6. Lempel-Ziv
Index | sträng
--------------------
1 | ""
2 | "S"
3 | "T"
4 | "O"
5 | "R"
6 | "ST"
7 | "OC"
8 | "K"
9 | "H"
10 | "OL"
11 | "M"
12 | "S_"
13 | "STO"
14 | "L"
15 | "TA"
16 | "_"
17 | "HO"
18 | "LM"
19 | "A"