Kompresní algoritmus LZW (autoři Lempel, Ziv, Welch, 1984) je slovníková kompresní metoda. Jedná se o vylepšení algoritmu LZ78. Hlavním rozdílem je kratší kódové slovo, které se skládá pouze z jednoho čísla - indexu slova ve slovníku. Algoritmus LZW je poměrně jednoduchý na implementaci, ale je nutné řešit velkou paměťovou náročnost slovníku. Tento nedostatek lze řeší různě, například "zmražením" slovníku při určité velikosti, jeho vymazáním, odstraněním dlouho nepoužitých frází (NRU) a podobně.

V každé iteraci algoritmu se hledá nejdelší fráze ve slovníku, která odpovídá dosud nezpracované části vstupního řetězce. Na výstup je poté vloženo kódové slovo, které se skládá z indexu fráze ve slovníku. Fráze ve slovníku je pak o tento znak rozšířena a označena nejmenším možným číslem.

Kompresní metoda LZW je slovníková, jednoprůchodová, adaptivní a symetrická.

Příklad

Komprese řetězce ABRABABRA

Inicializace

Do slovníku se před kompresí vloží všechny symboly vstupního řetězce a spojí se s kořenem. Tyto symboly je vedle kódových slov také nutné přenést k příjemci.

diagram
Krok 1

Načítáme symboly ze vstupu tak dlouho, dokud se jejich zřetězení nachází ve slovníku. Nejdelší nalezený řetězec je A s indexem 1. Na výstup vložíme tento index a slovník rozšíříme o první nenalezené slovo AB. Vytvoříme tedy nový uzel, spojíme jej s u uzlem 1 hranou označenou symbolem B a přiřadíme mu nejnižší volný index 4. Ve vstupním řetězci se posuneme o jeden znak.

  • Výstup: 1
diagram
Krok 2

Načítáme symboly ze vstupu tak dlouho, dokud se jejich zřetězení nachází ve slovníku. Nejdelší nalezený řetězec je B s indexem 2. Na výstup vložíme tento index a slovník rozšíříme o první nenalezené slovo BR. Vytvoříme tedy nový uzel, spojíme jej s u uzlem 2 hranou označenou symbolem R a přiřadíme mu nejnižší volný index 5. Ve vstupním řetězci se posuneme o jeden znak.

  • Výstup: 1, 2
diagram
Krok 3

Načítáme symboly ze vstupu tak dlouho, dokud se jejich zřetězení nachází ve slovníku. Nejdelší nalezený řetězec je R s indexem 3. Na výstup vložíme tento index a slovník rozšíříme o první nenalezené slovo RA. Vytvoříme tedy nový uzel, spojíme jej s u uzlem 3 hranou označenou symbolem A a přiřadíme mu nejnižší volný index 6. Ve vstupním řetězci se posuneme o jeden znak.

  • Výstup: 1, 2, 3
diagram
Krok 4

Načítáme symboly ze vstupu tak dlouho, dokud se jejich zřetězení nachází ve slovníku. Nejdelší nalezený řetězec je AB s indexem 4. Na výstup vložíme tento index a slovník rozšíříme o první nenalezené slovo ABA. Vytvoříme tedy nový uzel, spojíme jej s u uzlem 4 hranou označenou symbolem A a přiřadíme mu nejnižší volný index 7. Ve vstupním řetězci se posuneme o dva znaky.

  • Výstup: 1, 2, 3, 4
diagram
Krok 5

Načítáme symboly ze vstupu tak dlouho, dokud se jejich zřetězení nachází ve slovníku. Nejdelší nalezený řetězec je AB s indexem 4. Na výstup vložíme tento index a slovník rozšíříme o první nenalezené slovo ABR. Vytvoříme tedy nový uzel, spojíme jej s u uzlem 4 hranou označenou symbolem R a přiřadíme mu nejnižší volný index 8. Ve vstupním řetězci se posuneme o dva znaky.

  • Výstup: 1, 2, 3, 4, 4
diagram
Krok 6

Načítáme symboly ze vstupu tak dlouho, dokud se jejich zřetězení nachází ve slovníku. Nejdelší nalezený řetězec je RA s indexem 6. Na výstup vložíme tento index a slovník rozšířovat nemusíme, protože jsme dosáhli konce vstupního řetězce.

  • Výstup 1, 2, 3, 4, 4, 6
diagram

Zpětná dekomprese

Zpětnou dekompresi lze provádět pomocí tabulky řetězců. Příjemce nejprve obdrží symboly, které se ve vstupním řetězci vyskytovaly, a vloží je do tabulky.

Inicializace

Do tabulky se vloží přijaté symboly.

ŘádekKonstrukce slovaSlovo
1přijatoA
2přijatoB
3přijatoR
Krok 1

Je načteno kódové slovo 1. Na výstup se vypíše slovo z řádku 1. Následující kódové slovo je 2, slovník se rozšíří o nové slovo tvořené celým řádkem 1 a prvním symbolem z řádku 2.

  • Výstup: A
ŘádekKonstrukce slovaSlovo
1přijatoA
2přijatoB
3přijatoR
4řádek 1 + první symbol řádku 2AB
Krok 2

Je načteno kódové slovo 2. Na výstup se vypíše slovo z řádku 2. Následující kódové slovo je 3, slovník se rozšíří o nové slovo tvořené celým řádkem 2 a prvním symbolem z řádku 3.

  • Výstup: AB
ŘádekKonstrukce slovaSlovo
1přijatoA
2přijatoB
3přijatoR
4řádek 1 + první symbol řádku 2AB
5řádek 2 + první symbol řádku 3BR
Krok 3

Je načteno kódové slovo 3. Na výstup se vypíše slovo z řádku 3. Následující kódové slovo je 4, slovník se rozšíří o nové slovo tvořené celým řádkem 3 a prvním symbolem z řádku 4.

  • Výstup: ABR
ŘádekKonstrukce slovaSlovo
1přijatoA
2přijatoB
3přijatoR
4řádek 1 + první symbol řádku 2AB
5řádek 2 + první symbol řádku 3BR
6řádek 3 + první symbol řádku 4RA
Krok 4

Je načteno kódové slovo 4. Na výstup se vypíše slovo z řádku 4. Následující kódové slovo je 4, slovník se rozšíří o nové slovo tvořené celým řádkem 4 a prvním symbolem z řádku 4.

  • Výstup: ABRAB
ŘádekKonstrukce slovaSlovo
1přijatoA
2přijatoB
3přijatoR
4řádek 1 + první symbol řádku 2AB
5řádek 2 + první symbol řádku 3BR
6řádek 3 + první symbol řádku 4RA
7řádek 4 + první symbol řádku 4ABA
Krok 5

Je načteno kódové slovo 4. Na výstup se opět vypíše slovo z řádku 4. Následující kódové slovo je 6, slovník se rozšíří o nové slovo tvořené celým řádkem 4 a prvním symbolem z řádku 6.

  • Výstup: ABRABAB
ŘádekKonstrukce slovaSlovo
1přijatoA
2přijatoB
3přijatoR
4řádek 1 + první symbol řádku 2AB
5řádek 2 + první symbol řádku 3BR
6řádek 3 + první symbol řádku 4RA
7řádek 4 + první symbol řádku 4ABA
8řádek 4 + první symbol řádku 6ABR
Krok 5

Je načteno kódové slovo 6. Na výstup se vypíše slovo z řádku 6. Na vstupu již nejsou žádná další kódová slova, proto algoritmus skončí.

  • Výstup: ABRABABRA
ŘádekKonstrukce slovaSlovo
1přijatoA
2přijatoB
3přijatoR
4řádek 1 + první symbol řádku 2AB
5řádek 2 + první symbol řádku 3BR
6řádek 3 + první symbol řádku 4RA
7řádek 4 + první symbol řádku 4ABA
8řádek 4 + první symbol řádku 6ABR

Implementace (Java)

Kódové slovo

/**
 * Kódové slovo kompresního algoritmu LZW.
 *
 * @author Vojtěch Hordějčuk
 */
public class LZWCodeword {
    private final int index;

    /**
     * Vytvoří nové kódové slovo.
     *
     * @param index index uzlu
     */
    public LZWCodeword(final int index) {
        assert (index > 0);

        this.index = index;
    }

    /**
     * Vrátí index uzlu.
     *
     * @return index uzlu
     */
    public int getIndex() {
        return this.index;
    }

    @Override
    public String toString() {
        return String.format("%d", this.index);
    }
}

Zdrojový kód Pokrytí testy

Komprese a dekomprese

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * Kompresní algoritmus LZW.
 *
 * @author Vojtěch Hordějčuk
 */
public final class LZW {
    private static final Logger log = LoggerFactory.getLogger(LZW.class);

    /**
     * Získá abecedu (seznam symbolů) ze vstupního řetězce.
     *
     * @param input vstupní řetězec
     * @return abeceda vstupního řetězce
     */
    public static List<String> getAlphabet(final String input) {
        final List<String> alphabet = new LinkedList<>();

        for (int i = 0; i < input.length(); i++) {
            final String temp = input.substring(i, i + 1);

            if (!alphabet.contains(temp)) {
                alphabet.add(temp);
            }
        }

        return alphabet;
    }

    /**
     * Zakomprimuje vstupní řetězec algoritmem LZW.
     *
     * @param alphabet abeceda vstupních symbolů
     * @param input    vstupní řetězec
     * @return výstupní posloupnost kódových slov
     */
    public static List<LZWCodeword> compress(final List<String> alphabet, final String input) {
        int nodeCounter = 0;

        // kořen slovníku

        final Node root = new Node(nodeCounter++);

        // rozšířit slovník o symboly abecedy

        for (final String temp : alphabet) {
            root.extend(temp, nodeCounter++);
        }

        // výstupní posloupnost kódových slov

        final List<LZWCodeword> output = new LinkedList<>();

        // pozice ve vstupním řetězci

        int position = 0;

        // komprimuj, dokud nedojdeš na konec vstupu

        while (position < input.length()) {
            // aktuální uzel pro nejdelší nalezené slovo

            Node best_node = null;

            // délka nejdelšího nalezeného slova

            int best_skip = 0;

            // délka slova, které se nyní zkouší nalézt ve slovníku

            int try_length = 0;

            // vyhledáváné slovo

            String search = null;

            // poslední symbol nejkratšího nenalezeného slova

            String fresh = null;

            do {
                // zkus najít slovo o jeden symbol delší

                try_length++;

                search = input.substring(position, position + try_length);

                fresh = LZW.getSafeChar(input, position + try_length - 1);

                final Node temp = root.find(search);

                if (temp == null) {
                    // slovo již nebylo nalezeno

                    break;
                } else {
                    // uložit si uzel pro toto slovo a jeho délku

                    best_node = temp;
                    best_skip = try_length;
                }
            }
            while ((position + try_length < input.length()));

            // vložit nové kódové slovo na výstup

            output.add(new LZWCodeword(best_node.getIndex()));

            // rozšířir slovník

            if (fresh != null) {
                best_node.extend(fresh, nodeCounter++);
            }

            // posunout ukazatel o délku nejdelšího nalezeného slova

            position += best_skip;
        }

        return output;
    }

    /**
     * Dekomprimuje posloupnost kódových slov algoritmu LZW.
     *
     * @param alphabet  abeceda vstupních symbolů
     * @param codewords vstupní posloupnost kódových slov
     * @return dekomprimovaný řetězec
     */
    public static String decompress(final List<String> alphabet, final List<LZWCodeword> codewords) {
        // tabulka slov

        final List<String> table = new LinkedList<>();

        for (final String temp : alphabet) {
            table.add(temp);
        }

        // výstupní řetězec

        final StringBuilder output = new StringBuilder();

        for (int i = 0; i < codewords.size(); i++) {
            // aktuální kódové slovo

            final LZWCodeword current = codewords.get(i);

            // na výstup vložit řetězec

            final String word = table.get(current.getIndex() - 1);
            output.append(word);

            // aktualizovat slovník (pokud ještě bude nějaké slovo následovat)

            if (i + 1 < codewords.size()) {
                final LZWCodeword next = codewords.get(i + 1);
                final String nextWord = table.get(next.getIndex() - 1);
                table.add(word + nextWord.charAt(0));
            }
        }

        return output.toString();
    }

    /**
     * Vrátí znak na zadané pozici.
     * Pokud je pozice mimo rozsah, vrátí prázdný řetězec ("").
     *
     * @param input vstupní řetězec
     * @param index pozice (index)
     * @return znak na zadané pozici vstupního řetězce, nebo prázdný řetězec
     */
    private static String getSafeChar(final String input, final int index) {
        if ((index < 0) || (index >= input.length())) {
            return "";
        } else {
            return input.substring(index, index + 1);
        }
    }

    /**
     * Uzel slovníku, představující jedno slovo.
     *
     * @author Vojtěch Hordějčuk
     */
    private static class Node {
        /**
         * unikátní index uzlu
         */
        private final int index;
        /**
         * hrany k potomkům
         */
        private final Map<String, Node> edges;

        /**
         * Vytvoří nový uzel.
         */
        public Node(final int counter) {
            this.index = counter;
            this.edges = new HashMap<>();
        }

        /**
         * Vrátí uzel ve kterém končí daný prefix, nebo NULL.
         *
         * @param prefix hledaný prefix
         * @return uzel ve kterém končí daný prefix, nebo NULL
         */
        public Node find(final String prefix) {
            if (prefix.length() < 1) {
                // PREFIX končí zde

                return this;
            } else {
                final Node next = this.edges.get(prefix.substring(0, 1));

                if (next == null) {
                    // PREFIX není ve slovníku kompletní

                    return null;
                } else {
                    // vyhledat zbytek PREFIXu

                    return next.find(prefix.substring(1));
                }
            }
        }

        /**
         * Rozšíří uzel slovníku o nového potomka a spojí jej zadanou hranou.
         *
         * @param terminal symbol pro danou hranu
         * @param counter  node counter value
         */
        public void extend(final String terminal, final int counter) {
            this.edges.put(terminal, new Node(counter));
        }

        /**
         * Vrátí unikátní index daného uzlu.
         *
         * @return ID uzlu
         */
        public int getIndex() {
            return this.index;
        }

        @Override
        public String toString() {
            return String.format("(%d, edges to %s)", this.index, this.edges.toString());
        }
    }
}

Zdrojový kód Pokrytí testy

Reference

  • předmět X36KOD na FEL ČVUT