2011. május 5., csütörtök

LZW String tömörítés

Ma lyukasórában (elkészítetlen házifeladat és beadandó híján :D) 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 :D), 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ő.

Algoritmus & implementáció

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)

  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, különben megnézzük, hogy sx benne van-e a szótárban. Ha benne van, akkor s:=sx, különben kiírjuk s kódját, betesszük a szótárba sx-et, s:=x és ugrunk a 2. pontra.
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 abc 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)

  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), a * helyére beírjuk x első karakterét, kiírjuk x-et, s:=x és ugrunk a 2. pontra.
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! :-)