Hemtal 6

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. OBS. Denna version fungerar alltså inte precis som den på föreläsningen.

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 för att print lzw(t) ska ge ovanstående som utskrift? Ge också en tabell med strängar och index som motsvarar tabellen i koden!

Rättningsmall

Står namnet överst till höger?

Den som gjort uppgiften ska skriva sitt namn och personnummer överst till höger på alla papper. Den som rättar ska skriva sitt namn och personnummer, samt "G" eller "IG" överst till vänster på första pappret.

Är det tydligt skrivet?

Går det att begripa? Är något otydligt? Kan man läsa allt?

Är det rätt svar?

Är det rätt svar? Rätt text t? Rätt tabell? Svaren gås igenom på övning.