Lempel Ziv Welch

Explanation of the Lempel Ziv Welch Algorithm

1. Initiate the dictionary by loading it with standard substrings.
2. Establish a wK pattern where w is the longest sequence of input that is in the dictionary, and K represents the next character after w in the input.
3. Encode w as an output and then add wK to the dictionary.
4. Reset w to K and move onto the next character.

Detailed Lempel Ziv Welch Algorithm Example

def compress(uncompressed):
    # Build the dictionary.
    dict_size = 256
    dictionary = {chr(i): i for i in range(dict_size)}
    
    w = ""
    result = []
    for c in uncompressed:
        wc = w + c
        if wc in dictionary:
            w = wc
        else:
            result.append(dictionary[w])
            # Add wc to the dictionary.
            dictionary[wc] = dict_size
            dict_size += 1
            w = c
 
    # Output the code for w.
    if w:
        result.append(dictionary[w])
    return result

The Role of Lempel Ziv Welch in Data Compression

The role of Lempel Ziv Welch (LZW) in data compression is immensely significant. It is a universal lossless data compression algorithm that excels in diverse instances. You can come across LZW in formats like GIF for image compression. LZW operates by building up a dictionary of strings, substituting repeating occurrence of strings with a corresponding code. This makes it quite advantageous for files where certain phrases repeat often.

Understanding Lempel Ziv Welch Compression Method

1. The dictionary is initialised with individual characters.
2. A sequence of input characters (P) is read and the next character (C) is added to it.
3. If the combination (P+C) exists in the dictionary, the combination becomes the new P and the algorithm continues from step 2.
4. If the combination (P+C) doesn't exist in the dictionary, it is added. The code for P is added to the output, and C becomes the new P.
5. The process repeats from step 2 until there is no more input.

Importance and Advantages of Lempel Ziv Welch Data Compression

• Wide application: Thanks to its nature, LZW is utilised in a variety of applications like Unix’s ‘compress’ command, GIF images, and even in hardware data compression like disk drives.
• Speed: LZW is faster than many other types of compression, which makes it a favoured choice, especially where speed is a critical factor.
• No prior knowledge required: Unlike some compression algorithms, LZW doesn't need a priori knowledge of the data distribution and can compress all the data types to some extent.
• Lossless compression: LZW is a lossless algorithm. That is, the original data can be perfectly reconstructed from the compressed data. This attribute is essential when exact replicas of data are needed.

Deciphering Lempel Ziv Welch Coding

Steps Involved in Lempel Ziv Welch Coding Mechanism

1. Initialisation of the dictionary with elementary substrings.
2. Gradual appending of the dictionary with new found patterns while traversing the data.
3. Replacement of recurrent substrings with respective codes from the dictionary.

The LZW algorithm begins by initialising the dictionary with basic individual character strings. So, if your data is English text, the dictionary starts with 256 entries, one for each 8-bit ASCII character. Each character is assigned a unique code. From there, the algorithm starts processing the data, continually expanding the dictionary with a new entry for each new string encountered. A “new string” here refers to a string not found in the dictionary, but formed by adding a character to an existing string in the dictionary. It keeps track of the incoming character sequences and assigns them incremental codes. When it comes across a repeating string, it simply outputs the code for that string. The beauty of LZW lies in how it recognises patterns and builds a dictionary, thus, making it great for data where certain sets of characters frequently occur together. An important aspect of LZW is dictionary management. Dictionary size is dependent on the number of bits chosen for output codes. An 8-bit code yields a dictionary with 256 entries, while a 12-bit code offers 4,096 entries. Once the dictionary is full, one of two actions is needed: either stop adding strings and only emit codes for those in the dictionary (static dictionary), or make space for new codes by removing older ones (dynamic dictionary). The choice of strategy has a direct impact on the algorithm's efficiency and must hence be selected judiciously.

Lempel Ziv Welch Coding in Practical Use

Let’s say you have a string "GOOGOLGOOGLE". 
First, initialise a dictionary with individual characters as substrings.

def compress(uncompressed):
    dict_size = 256 
    dictionary = dict((chr(i), chr(i)) for i in range(dict_size))
   
    w = "" 
    result = []
    
    for c in uncompressed:
        wc = w + c
        if wc in dictionary:
            w = wc
        else:
            result.append(dictionary[w])
            dictionary[wc] = dict_size
            dict_size += 1
            w = c

    if w:
        result.append(dictionary[w])
    return result

Huffman Coding Versus Lempel Ziv Welch in Data Representation

Key Differences between Huffman Coding and Lempel-Ziv-Welch

• Methodology: Huffman Coding is a statistical compression method that deals with individual characters in data. In contrast, LZW is a dictionary-based method that operates on strings or sequences of data.
• Compression Type: Huffman Coding is entropy encoding used for lossless data compression, and LZW is also lossless but with the added benefit of not requiring prior knowledge about source statistics.
• Complexity: LZW's approach with strings rather than characters, as in Huffman Coding, often leads to better compression ratios but at the expense of higher computational complexity.
• Usage: Huffman code is used widely in JPEG image compression, while LZW shines in GIF and TIFF image formats and Unix file compression.

When to Choose Lempel Ziv Welch over Huffman Coding

• Repeating Sequences: LZW shines when the data contains longer repeating sequences. If you’re dealing with data where some sets of characters frequently appear together, LZW can offer better compression.
• No Prior Data Distribution Knowledge: Unlike Huffman Coding, LZW doesn't need pre-existing knowledge about the data's statistical distribution. This makes LZW more flexible for diverse data types and sources.
• Processing Time: In some cases, LZW can work faster than Huffman coding, especially with repeated sequences, making it suitable for real-time data compression needs.
• Long Data Streams: LZW does a commendable job when dealing with long strings of data. Huffman, since it operates on a character-level, might not provide efficient compression with large data streams.

How Lempel Ziv Welch Shapes Modern Computer Science

Lempel Ziv Welch's Impact on Current Encoding Standards

def compress(uncompressed):
    dict_size = 256 
    dictionary = dict((chr(i), i) for i in range(dict_size))
    w = ""
    result = []
    
    for c in uncompressed:
        wc = w + c
        if wc in dictionary:
            w = wc
        else:
            result.append(dictionary[w])
            dictionary[wc] = dict_size
            dict_size += 1
            w = c

    if w:
        result.append(dictionary[w])
        
    return result

Future Implications of Applying Lempel Ziv Welch in Data Representation