En av de mest brukte komprimerings- og dekomprimeringsalgoritmene kalles LZW-metoden - etter forskerne A.Lempel, J.Ziv og T.Welch. F.eks. er det den algoritmen som ligger under GIF-formatet for grafikk på internett.

Ziv og Lempel publiserte i 1978 en metode som i dag går under navnet LZ78-metoden. Idéen gikk ut på å bygge opp en «ordbok» mens filen leses. Hvert nytt «ord» på filen legges inn i «ordboken» og får samtidig tilordnet en tallkode. Hvis et «ord» (eller egentlig en tegnsekvens) blir funnet i «ordboken» blir «ordet» isteden representert ved hjelp av tallkoden. Hvis tallkodene i gjennomsnitt blir kortere enn ordene, så får vi en komprimering. Problemet var at ideen ikke lot seg implementere på en enkel og effektiv måte. Men ved hjelp av en smart idé som T.Welch fikk i 1984, fikk metoden sitt store gjennombrudd.

Komprimering

Anta at vi har en sekvens med ascii-tegn (f.eks. en String, en fil eller lign.) I starten har vi egentlig ingen ord i ordboken. De 256 «ordene» som kun består av ett tegn har jo i utgangspunktet fått tilordnet en tallkode - tegnets ascii-verdi. Derfor er det ikke nødvendig å legge disse «ordene» inn i ordboken.

Komprimering med LZW kan beskrives slik:

1. Vi har en «melding» i form av en tegnsekvens.
1. La tegnet c være første tegn i meldingen.
2. La tegnstrengen s være lik c.
3. La heltallet kode være acsii-verdien til c.
4. La heltallet nestekode være lik 256.
2. Er det flere tegn i sekvensen?
1. Hvis nei, skriv ut kode og avslutt!
2. Hvis ja, c = neste tegn i sekvensen.
3. Ligger tegnstrengen s + c i ordboken?
1. Hvis nei,
1. Skriv ut kode
2. legg s + c i ordboken sammen med verdien til nestekode som tallkode
3. nestekode++
4. s = c
5. kode = ascii(c)
2. Hvis ja,
1. kode = tallkoden til s + c og s = s + c
4. Gå tilbake til 2.

Eksempel:   Gitt tegnsekvensen   ABBABABAC   Algoritmen vil da etter 6 «runder» ha produsert flg. ordbok og utskrift av tallkoder:

Dekomprimering

Ved dekomprimering har vi en sekvens med tallkoder der første < 256. Nå skal vi bruke tallkodene til å bygge opp den samme ordboken som vi bygget opp under komprimeringen.

Dekomprimering med LZW kan beskrives slik:

1. Vi har en sekvens med tallkoder der første tallkode < 256.
1. Heltallet kode er første kode i sekvensen.
2. Heltallet nestekode settes til 256.
3. Tegnstrengen denne = char(kode).
4. I tillegg har vi tegnstrengen denne og tegnet c.
5. skriv ut denn
2. Er det flere tallkoder igjen i sekvensen?
1. Hvis nei, avslutt.
2. Hvis ja,
1. kode = neste tallkode fra sekvensen
2. forrige settes lik denne.
3. Er kode registrert i ordboken (dvs. kode < nestekode)?
1. Hvis ja,
1. denne settes lik ordet som hører til kode
2. c = første tegn i denne
2. Hvis nei,
1. c = første tegn i forrige
2. denne = forrige + c.
4.  
1. skriv ut denne
2. Legg forrige + c i ordboken med nestekode som nøkkel
3. nestekode++
4. gå tilbake til 2

Java-kode

  public static void komprimerTilKonsoll(String melding)
  {
    char c = melding.charAt(0);
    String s = "" + c;
    int kode = c;
    int nestekode = 256;

    Map<String,Integer> ordbok = new TreeMap<String,Integer>();

    for (int i = 1; i < melding.length(); i++)
    {
      c = melding.charAt(i);

      Integer ordkode = ordbok.get(s + c);
      if (ordkode == null)
      {
        System.out.println(kode + " " + Integer.toBinaryString(kode));
        ordbok.put(s + c, nestekode);
        nestekode++;
        s = "" + c;
        kode = c;
      }
      else
      {
        kode = ordkode;
        s = s + c;
      }
    }
    System.out.println(kode);

  }  // komprimerTilKonsoll

  public static void dekomprimerFraTabell(int[] a)
  {
    int kode = a[0]; // første tallkode - er < 256
    int nestekode = 256;

    String denne  = "" + (char)kode; // første tegn
    String forrige = null;
    char c;

    System.out.print(denne); // denne skrives ut

    Map<Integer,String> ordbok = new TreeMap<Integer,String>();

    for (int i = 1; i < a.length; i++)
    {
      kode = a[i];
      forrige = denne;

      if (kode < nestekode)
      {
        denne = kode < 256 ? "" + (char)kode : ordbok.get(kode);
        c = denne.charAt(0);
      }
      else
      {
        c = forrige.charAt(0);
        denne = forrige + c;
      }

      System.out.print(denne);
      ordbok.put(nestekode,forrige + c);
      nestekode++;
    }
  }  // dekomprimerFraTabell

Copyright © Ulf Uttersrud, 2011. All rights reserved.