LZW String tömörítés

Bevezetés

Ma lyukasórában (elkészítetlen házifeladat és beadandó híján 😀) sikerült implementálnom az LZW tömörítő algoritmust, kedvenc nyelvemen: Java-ban. Egyelőre a cél az volt, hogy működjön String-ekre (és ugyanazt az eredményt adja, mint az Algoritmusok és adatszerkezetek füzetemben 😀), a következő lépcső az lesz, hogy fájltömörítővé fejlesztem - ami már picit bonyolultabb lesz, hiszen ott már bitekre is kell boncolgatni a dolgokat.

Tök egyszerű algoritmus, az egész program nincs 60 sor, egy pici bonyolultsággal csak a Java típuskonverziói fűszerezték a kódot.

Az LZW tömörítés két nagy előnye, hogy nem kell előzetes számításokat végezni a bemeneten, illetve a szótárat nem kell belekódolni a tömörített fájlba - ugyanis a kódtábla az előzőekben feldolgozott adatokból épül fel, és a kitömörítő eljárás is ugyanúgy építi fel, mint ahogy a tömörítő.

Előfeltétel a kódoláshoz és a dekódoláshoz is egyaránt: egy egységes alapszótár.

Kódolás (tömörítés)

Algoritmus:

  1. Beolvassuk az első karaktert (s)
  2. Beolvassuk a következő karaktert (x)
  3. Ha x a szöveg vége jel, akkor kiírjuk s kódját és kilépünk
  4. Különben:
    • Ha sx benne van a szótárban, akkor s:=sx
    • Különben:
      • Kiírjuk s kódját
      • Betesszük a szótárba sx-et
      • s:=x
      • Ugrunk a 2. pontra

Java implementáció:

public List<Integer> compress(String input) {
    List<Integer> output = new ArrayList<Integer>();
    List<String> ct = new ArrayList<String>(baseDict);
    String s = Character.toString(input.charAt(0));
    String x;
    for (int i = 1; i < input.length(); i++) {
        x = Character.toString(input.charAt(i));
        if (ct.contains(s + x)) {
            s = s + x;
        } else {
            ct.add(s + x);
            output.add(ct.indexOf(s));
            s = x;
        }
    }
    output.add(ct.indexOf(s));
    return output;
}

Megjegyzés: a baseDict szintén egy ArrayList<String>, amibe előzőleg be kell tölteni az alapszótárat. Én az angol ábécé betűit pakoltam bele, mert ezzel dolgoztunk órán:

List<String> baseDict = new ArrayList<String>();
for (char c = 'a'; c <= 'z'; c++) {
    baseDict.add(Character.toString(c));
}

Dekódolás (kitömörítés)

Algoritmus:

  1. Dekódoljuk és kiírjuk az első kódot (s)
  2. s*-ot beírjuk a szótárba
  3. Dekódoljuk a következő kódot (x)
  4. A * helyére beírjuk x első karakterét
  5. Kiírjuk x-et
  6. s:=x
  7. Ugrunk a 2. pontra

Java implementáció:

public String decompress(List<Integer> input) {
    List<String> ct = new ArrayList<String>(baseDict);
    String s = ct.get(input.get(0));
    String output = s;
    String x;
    for (int i = 1; i < input.size(); i++) {
        ct.add(s); // s*
        x = ct.get(input.get(i));
        ct.set(ct.size() - 1, s
                + Character.toString(x.charAt(0)));
        x = ct.get(input.get(i));
        output += x;
        s = x;
    }
    return output;
}

Megjegyzés: az output-hoz hozzáadás előtt még egyszer dekódolok. Ezt azért csinálom, mert ha jön egy olyan kód, amihez még csak egy s*-os elem tartozik, akkor a csillag értékét csak a kövektező sorban levő felülírás után tudom használni.

További megjegyzés: ellenőrzésképpen kiírathatók a függvények belsejében generálódó szótárak is, ugyanazt a kódtáblát építik fel.

Érdekes algoritmus! 🙂

Zsolt vagyok, full-stack fejlesztő.
Crawlereket, webalkalmazásokat, statikus honlapokat és interaktív vizualizációkat készítek.
Copyright © 2019 Zsolt Jurányi | All rights reserved.