Open RAR File

LZ78 and LZW

LZ78 is a compression algorithm developed by Abraham Lempel and Jacob Ziv in 1978 (hence the name LZ78). LZ78 is a dictionary coder algorithm which means that it maintains a dictionary of repeating occurrences of data. LZ78 processes the input data and converts it to an array of references to a dictionary and a character following the data entry occurrence. For each character of the input stream LZ78 checks if currently found longest prefix concatenated with a current character is available in the dictionary. If a match is found, then “last index found” is set to the dictionary match index and nothing is output. If not, then “last index found” is output together with current character as a pair and a new dictionary entry created from the current longest prefix concatenated with a current character. Dictionary should be pre-initialized with a record indexed as 0 which stores an empty string.

Below is a pseudo-code for LZ78 algorithm:
    list compressLZ78(string s):
    string buffer = "" // current prefix
    map dict = {} // dictionary
    list output = [] // resulting string
    for i = 0 .. s.length - 1:
        if dict.hasKey(buffer + s[i]): // check if we can increase the current prefix
            buffer += s[i]
        else:
            output.push({dict[buffer], s[i]}) // add pair of dictionary reference and next character to the output sequence
            dict[buffer + s[i]] = dict.length + 1 // add word to a dictionary
            buffer = "" // reset buffer
    return output


LZW is a modification of LZ78 compression algorithm designed by Abraham Lempel, Jacob Ziv and Terry Welch. The algorithm has several important improvements to LZ78. LZW uses a dictionary which is preinitialized with all ASCII characters (it could be pre-initialized with a different character set depending on implementation). Because of that there is no need to output the next character as in LZ78 and only the matching dictionary index is recorded. This on average makes LZW compression more efficient than LZ78.

LZW is used in GIF image compression and also Unix utilities “compress” and “decompress” (though it was removed from some of Unix distributions due to patent conflicts). As of now LZW patents are expired and algorithm could be used free of license concerns. But most new archiver implementations use more advanced versions of compression algorithms like PPM and LZMA.