Kompresní algoritmus LZ78 (autoři Abraham Lempel, Jacob Ziv, rok 1978) patří mezi slovníkové kompresní metody. Jedná se o poměrně jednoduchou metodu, ale náročnou na paměť. Tento nedostatek se řeší různě, například "zmražením" slovníku při určité velikosti, jeho občasným vyprázdněním, odstraněním dlouho nepoužitých frází (NRU), a podobně.

Algoritmus pracuje v krocích. Slovník je tvořen stromem, ve kterém každá cesta od kořene k listu představuje jednu frázi ze vstupního řetězce. Tento stroj je inicializován kořenovým uzlem (prázdnou frází) s indexem 0.

V každém kroku se ve slovníku se vyhledá nejdelší fráze, která odpovídá dosud nezpracované části vstupního řetězce (tj. cesta od kořene k listu). Na výstup je poté vloženo kódové slovo €(i,x)€, kde €i€ je index fráze ve slovníku a €x€ je první znak ze vstupu, který se v nalezené frázi nenachází. Nakonec je fráze ve slovníku o tento znak rozšířena a označena nejmenším možným nepoužitým číslem.

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

Příklady

Komprese řetězce ABRAKADAKABRA

Inicializace

Slovník je zpočátku prázdný a obsahuje pouze jeden kořenový uzel s indexem 0.

diagram
Krok 1

Načítáme symboly ze vstupu tak dlouho, dokud se jejich zřetězení nachází ve slovníku. Už první symbol A se ale ve slovníku nenachází, takže jej zakódujeme jako dvojici (0,A) a pak slovník rozšíříme. Vytvoříme nový uzel, spojíme jej s kořenem hranou označenou symbolem A a přiřadíme mu nejnižší volný index 1.

  • Výstup: (0, A)
diagram
Krok 2

Načítáme symboly ze vstupu tak dlouho, dokud se jejich zřetězení nachází ve slovníku. Už první symbol B se ale ve slovníku nenachází, takže jej zakódujeme jako dvojici (0,B) a pak slovník rozšíříme. Vytvoříme nový uzel, spojíme jej s kořenem hranou označenou symbolem B a přiřadíme mu nejnižší volný index 2.

  • Výstup: (0, A), (0, B)
diagram
Krok 3

Načítáme symboly ze vstupu tak dlouho, dokud se jejich zřetězení nachází ve slovníku. Už první symbol R se ale ve slovníku nenachází, takže jej zakódujeme jako dvojici (0,R) a pak slovník rozšíříme. Vytvoříme nový uzel, spojíme jej s kořenem hranou označenou symbolem R a přiřadíme mu nejnižší volný index 3.

  • Výstup: (0, A), (0, B), (0, R)
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 A, který začíná na indexu 1. Po něm následuje symbol K. Na výstup vypíšeme dvojici (1,K) a rozšíříme slovník. Vytvoříme nový uzel, spojíme jej s uzlem 1 hranou označenou symbolem K a přiřadíme mu nejnižší volný index 4.

  • Výstup: (0, A), (0, B), (0, R), (1, K)
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 A, který začíná na indexu 1. Po něm následuje symbol D. Na výstup vypíšeme dvojici (1,D) a rozšíříme slovník. Vytvoříme nový uzel, spojíme jej s uzlem 1 hranou označenou symbolem D a přiřadíme mu nejnižší volný index 5.

  • Výstup: (0, A), (0, B), (0, R), (1, K), (1, D)
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 AK, který začíná na indexu 4. Po něm následuje symbol A. Na výstup vypíšeme dvojici (4,A) a rozšíříme slovník. Vytvoříme nový uzel, spojíme jej s uzlem 4 hranou označenou symbolem A a přiřadíme mu nejnižší volný index 6.

  • Výstup: (0, A), (0, B), (0, R), (1, K), (1, D), (4, A)
diagram
Krok 7

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, který začíná na indexu 2. Po něm následuje symbol R. Na výstup vypíšeme dvojici (2,R) a rozšíříme slovník. Vytvoříme nový uzel, spojíme jej s uzlem 2 hranou označenou symbolem R a přiřadíme mu nejnižší volný index 7.

  • Výstup: (0, A), (0, B), (0, R), (1, K), (1, D), (4, A), (2, R)
diagram
Krok 8

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, který začíná na indexu 1. Za ním ve vstupním řetězci nenásleduje nic. Na výstup vypíšeme dvojici (1,konec), slovník již rozšiřovat nemusíme.

  • Výstup: (0, A), (0, B), (0, R), (1, K), (1, D), (4, A), (2, R), (1, konec)
diagram

Zpětná dekomprese

Zpětnou dekompresi lze provádět pomocí tabulky řetězců, která zpočátku obsahuje pouze řádek s indexem 0, na kterém je uložen prázdný řetězec.

Krok 1

Je načteno kódové slovo (0,A). Na výstup se vypíše slovo na řádku 0 zřetězené se symbolem A. Tabulka se o tento řetězec rozšíří.

ŘádekKonstrukce slovaSlovo
0prázdný řetězec
1řádek 0 + AA
  • Výstup: A
Krok 2

Je načteno kódové slovo (0,B). Na výstup se vypíše slovo na řádku 0 zřetězené se symbolem B. Tabulka se o tento řetězec rozšíří.

ŘádekKonstrukce slovaSlovo
0prázdný řetězec
1řádek 0 + AA
2řádek 0 + BB
  • Výstup: AB
Krok 3

Je načteno kódové slovo (0,R). Na výstup se vypíše slovo na řádku 0 zřetězené se symbolem R. Tabulka se o tento řetězec rozšíří.

ŘádekKonstrukce slovaSlovo
0prázdný řetězec
1řádek 0 + AA
2řádek 0 + BB
3řádek 0 + RR
  • Výstup: ABR
Krok 4

Je načteno kódové slovo (1,K). Na výstup se vypíše slovo na řádku 1 zřetězené se symbolem K. Tabulka se o tento řetězec rozšíří.

ŘádekKonstrukce slovaSlovo
0prázdný řetězec
1řádek 0 + AA
2řádek 0 + BB
3řádek 0 + RR
4řádek 1 + KAK
  • Výstup: ABRAK
Krok 5

Je načteno kódové slovo (1,D). Na výstup se vypíše slovo na řádku 1 zřetězené se symbolem D. Tabulka se o tento řetězec rozšíří.

ŘádekKonstrukce slovaSlovo
0prázdný řetězec
1řádek 0 + AA
2řádek 0 + BB
3řádek 0 + RR
4řádek 1 + KAK
5řádek 1 + DAD
  • Výstup: ABRAKAD
Krok 6

Je načteno kódové slovo (4,A). Na výstup se vypíše slovo na řádku 4 zřetězené se symbolem A. Tabulka se o tento řetězec rozšíří.

ŘádekKonstrukce slovaSlovo
0prázdný řetězec
1řádek 0 + AA
2řádek 0 + BB
3řádek 0 + RR
4řádek 1 + KAK
5řádek 1 + DAD
6řádek 4 + AAKA
  • Výstup: ABRAKADAKA
Krok 7

Je načteno kódové slovo (2,R). Na výstup se vypíše slovo na řádku 2 zřetězené se symbolem R. Tabulka se o tento řetězec rozšíří.

ŘádekKonstrukce slovaSlovo
0prázdný řetězec
1řádek 0 + AA
2řádek 0 + BB
3řádek 0 + RR
4řádek 1 + KAK
5řádek 1 + DAD
6řádek 4 + AAKA
7řádek 2 + RBR
  • Výstup: ABRAKADAKABR
Krok 8

Je načteno kódové slovo (1,konec). Na výstup se vypíše slovo na řádku 1 a dekódování skončí.

ŘádekKonstrukce slovaSlovo
0prázdný řetězec
1řádek 0 + AA
2řádek 0 + BB
3řádek 0 + RR
4řádek 1 + KAK
5řádek 1 + DAD
6řádek 4 + AAKA
7řádek 2 + RBR
  • Výstup: ABRAKADAKABRA

Implementace (Java)

Kódové slovo

/**
 * Single LZ-77 codeword.
 * Immutable class.
 */
public class LZ78Codeword {
    private final int i;
    private final char x;

    public LZ78Codeword(final int i, final char x) {
        this.i = i;
        this.x = x;
    }

    public int getI() {
        return i;
    }

    public char getX() {
        return x;
    }

    @Override
    public String toString() {
        return String.format("(%d,%s)", i, x == 0 ? "<eof>" : x);
    }
}

Zdrojový kód Pokrytí testy

Komprese a dekomprese

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

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

/**
 * Utility class for encoding and decoding with LZ77 algorithm.
 */
public final class LZ78 {
    private static final Logger log = LoggerFactory.getLogger(LZ78.class);

    private LZ78() {
        // utility class
    }

    // ENCODING
    // ========

    public static List<LZ78Codeword> encode(final char[] input) {
        final List<LZ78Codeword> result = new LinkedList<>();
        int position = 0;
        final Tree tree = new Tree();

        while (position <= input.length - 1) {
            log.debug("Encoding from position: {}", position);
            Node bestLeafSoFar = tree.root;
            int longestPrefixSoFar = 0;

            // try to find prefixes with increasing length
            for (int prefixEnd = position + 1; prefixEnd <= input.length; prefixEnd++) {
                final String prefix = safeSubString(input, position, prefixEnd);
                assert prefix.length() >= 1;
                log.debug("Trying to find prefix in dictionary: {} (length = {})", prefix, prefix.length());
                final char prefixChar = prefix.charAt(longestPrefixSoFar);

                if (bestLeafSoFar.hasChild(prefixChar)) {
                    bestLeafSoFar = bestLeafSoFar.getChild(prefixChar);
                    longestPrefixSoFar = prefix.length();
                } else {
                    break;
                }
            }

            // we have the longest prefix
            final char firstTerminalAfterPrefix = safeSubChar(input, position + longestPrefixSoFar);
            log.debug("Longest prefix found: (length = {}, start = {})", longestPrefixSoFar, bestLeafSoFar.id);
            log.debug("Extending node {} with {}.", bestLeafSoFar.id, firstTerminalAfterPrefix);
            tree.extend(bestLeafSoFar, firstTerminalAfterPrefix);
            final LZ78Codeword newCodeword = new LZ78Codeword(bestLeafSoFar.id, firstTerminalAfterPrefix);
            log.debug("Adding codeword: {}", newCodeword);
            result.add(newCodeword);
            position += longestPrefixSoFar + 1;
        }

        return result;
    }

    // DECODING
    // ========

    public static char[] decode(final List<LZ78Codeword> input) {
        // table of words
        final List<String> table = new LinkedList<>();
        // output string buffer
        final StringBuilder buffer = new StringBuilder();

        for (final LZ78Codeword codeword : input) {
            final String wordToAdd;

            if (codeword.getI() == 0) {
                // non-existing word (new symbol)
                log.debug("Appending non-existing word: {}", codeword.getX());
                wordToAdd = String.valueOf(codeword.getX());
            } else {
                final String wordFromTable = table.get(codeword.getI() - 1);

                if (codeword.getX() != 0) {
                    // existing word + terminal
                    log.debug("Appending existing word: {} + terminal `{}`", wordFromTable, codeword.getX());
                    wordToAdd = wordFromTable + codeword.getX();
                } else {
                    // existing word only
                    log.debug("Appending existing word: {}", wordFromTable);
                    wordToAdd = wordFromTable;
                }
            }

            // append the word to output
            buffer.append(wordToAdd);
            // extend the table of words
            table.add(wordToAdd);
            log.debug("Table of words extended: {}", wordToAdd);
        }

        return buffer.toString().toCharArray();
    }

    // UTILITY
    // =======

    private static class Tree {
        int counter = 0;
        final Node root = new Node(counter++);

        void extend(final Node parent, final char terminal) {
            parent.addChild(counter++, terminal);
        }
    }

    private static class Node {
        final int id;
        final Map<Character, Node> children;

        Node(final int id) {
            this.id = id;
            this.children = new LinkedHashMap<>();
        }

        void addChild(final int newId, final char newTerminal) {
            assert !children.containsKey(newTerminal);
            children.put(newTerminal, new Node(newId));
        }

        Node getChild(final char terminal) {
            return children.get(terminal);
        }

        boolean hasChild(final char terminal) {
            return children.containsKey(terminal);
        }
    }

    private static char safeSubChar(final char[] input, final int index) {
        if (index >= 0 && index <= input.length - 1) {
            return input[index];
        }

        return 0;
    }

    private static String safeSubString(final char[] input, final int start, final int end) {
        final StringBuilder buffer = new StringBuilder();

        for (int i = start; i < end; i++) {
            if (i >= 0 && i <= input.length - 1) {
                buffer.append(input[i]);
            }
        }

        return buffer.toString();
    }
}

Zdrojový kód Pokrytí testy

Reference