Lossless compression algorithm with Example

LZW Algorithm

What is LZW Algorithm?

    LZW Algorithm is a universal Lossless 
    data compression algorithm created by Abraham Lempel , Jacob Ziv and Terry Welch.

    This Algorithm is simple to implement and has the potential for very high Throughput in hardware 

    LZW can be made really fast; it grabs a fixed number of bits from input stream, so bit parsing is
    very easy. Table lookup is automatic. 

    [LZW] is a data compression method that takes 
    advantage of this repetition. The original version of
    the method was created by Lempel and Ziv in 1978 (LZ78) and was further refined by Welch in 1984,
    hence the LZW acronym. Like any adaptive/dynamic compression method, the idea is to 
        (1) start with an initial model,
        (2) read data piece by piece,
        (3) and update the model and encode the data as you go along. 
    LZW is a "dictionary"-based compression algorithm. This means that instead of tabulating character counts 
    and building trees (as for Huffman encoding), LZW encodes data by referencing a dictionary. Thus, to encode
    a substring, only a single code number, corresponding to that substring's index in the dictionary, needs to
    be written to the output file. Although LZW is often explained in the context of compressing text files, it 
    can be used on any type of file. However, it generally performs best on files with repeated substrings, such as 
    text files.

##Here I am trying to demonstrate example of compression and decompression of string 'banana_bandana' using LZW algorithm Now trying to create dictionary with index of above individual strings.

Index Entry
0 a
1 b
2 d
3 n
4 _


Pseudo code

string s;
char ch;

s = empty string;
while (there is still data to be read)
    ch = read a character;
    if (dictionary contains s+ch)     
        s = s+ch;                     
        encode s to output file;
        add s+ch to dictionary;
        s = ch;
encode s to output file;


    # Building and initializing the dictionary.
    dictionary_size = 256                   
    dictionary = {chr(i): i for i in range(dictionary_size)}    
    string = ""             # String is null.
    compressed_data = []    # variable to store the compressed data.

    # iterating through the input symbols.
    # LZW Compression algorithm
    for symbol in data:                     
        string_plus_symbol = string + symbol # get input symbol.
        if string_plus_symbol in dictionary: 
            string = string_plus_symbol
            if(len(dictionary) <= maximum_table_size):
                dictionary[string_plus_symbol] = dictionary_size
                dictionary_size += 1
            string = symbol

    if string in dictionary:


Input Current String Encoded output New Dictionary Index
b b Nothing none none
ba ba 1 ba 5
ban an 1,0 an 6
bana na 1,0,3 na 7
banan an - - -
banana ana 1,0,3,6 ana 8
banana_ a_ 1,0,3,6,0 a_ 9
banana_b _b 1,0,3,6,0,4 _b 10
banana_ba ba - - -
banana_ban ban 1,0,3,6,0,4,5 ban 11
banana_band nd 1,0,3,6,0,4,5,3 nd 12
banana_banda da 1,0,3,6,0,4,5,3,2 da 13
banana_bandan an - - -
banana_bandana ana 1,0,3,6,0,4,5,3,2,8 - -



string entry;
char ch;
int prevcode, currcode;

prevcode = read in a code;
decode/output prevcode;
while (there is still data to read)
    currcode = read in a code;
    entry = translation of currcode from dictionary;
    output entry;
    ch = first char of entry;
    add ((translation of prevcode)+ch) to dictionary;
    prevcode = currcode;


    maximum_table_size = pow(2,int(n))
    file = open(input_file, "rb")
    compressed_data = []
    next_code = 256
    decompressed_data = ""
    string = ""

    # Reading the compressed file.
    while True:
        rec = file.read(2)
        if len(rec) != 2:
        (data, ) = unpack('>H', rec)

    # Building and initializing the dictionary.
    dictionary_size = 256
    dictionary = dict([(x, chr(x)) for x in range(dictionary_size)])

    # iterating through the codes.
    # LZW Decompression algorithm
    for code in compressed_data:
        if not (code in dictionary):
            dictionary[code] = string + (string[0])
        decompressed_data += dictionary[code]
        if not(len(string) == 0):
            dictionary[next_code] = string + (dictionary[code][0])
            next_code += 1
        string = dictionary[code]


Encoded input Dictionary Translation Decoded Input Current String New Dictionary Index
1 1=b b - none none
1,0 0=a ba b ba 5
1,0,3 3=n ban a an 6
1,0,3,6 6=an banan n na 7
1,0,3,6,0 0=a banana an ana 8
1,0,3,6,0,4 4=_ banana_ a a_ 8
1,0,3,6,0,4 5=ba banana_ba _ _b 10
1,0,3,6,0,4,5,3 3=n banana_ban ba ban 11
1,0,3,6,0,4,5,3 2=d banana_band n nd 12
1,0,3,6,0,4,5,3,2,8 8=ana banana_bandana d da 13

Ref 1 Ref 2 Source Code

Post a Comment