How to implement the LZW compression algorithm in C#

How to implement the LZW compression algorithm in C

#Introduction:
With the continuous growth of data, data storage and transmission have become an important task. The LZW (Lempel-Ziv-Welch) compression algorithm is a commonly used lossless compression algorithm that can effectively reduce the size of data. This article will introduce how to implement the LZW compression algorithm in C# and give specific code examples.

1. Principle of LZW compression algorithm
   LZW compression algorithm is a dictionary compression algorithm. Its basic principle is to map the continuous character sequence appearing in the input data stream into a unique encoding. When compressing, the character sequence is gradually added to the dictionary and the corresponding encoding is output; when decompressing, the corresponding character sequence in the dictionary is found through encoding and output. The core of the algorithm is to continuously update the dictionary so that it can match the input data stream.
2. LZW compression algorithm implementation steps
   (1) Initialize dictionary: Initialize each character in the input data stream to an independent encoding.
   (2) Read the first character in the input data stream as the current character.
   (3) Repeat the following steps until the end of the data flow:
   a. Read the next character and splice the current character and the next character into a new character sequence.
   b. If the character sequence already exists in the dictionary, update the current character to the new character sequence and continue reading the next character.
   c. If the character sequence does not exist in the dictionary, output the current character, add the new character sequence to the dictionary, and update the current character to the next character.
   (4) Output the remaining current characters.
3. C# Code Example
   The following is a code example for implementing the LZW compression algorithm in C#:

using System;
using System.Collections.Generic;
using System.Text;

class LZWCompression
{
    public static List<int> Compress(string data)
    {
        Dictionary<string, int> dictionary = new Dictionary<string, int>();
        List<int> compressedData = new List<int>();

        int currentCode = 256;

        for (int i = 0; i < 256; i++)
        {
            dictionary.Add(((char)i).ToString(), i);
        }

        string currentString = "";

        foreach (char c in data)
        {
            string newString = currentString + c;

            if (dictionary.ContainsKey(newString))
            {
                currentString = newString;
            }
            else
            {
                compressedData.Add(dictionary[currentString]);
                dictionary.Add(newString, currentCode);
                currentCode++;
                currentString = c.ToString();
            }
        }

        if (currentString != "")
        {
            compressedData.Add(dictionary[currentString]);
        }

        return compressedData;
    }

    public static string Decompress(List<int> compressedData)
    {
        Dictionary<int, string> dictionary = new Dictionary<int, string>();
        StringBuilder decompressedData = new StringBuilder();

        int currentCode = 256;

        for (int i = 0; i < 256; i++)
        {
            dictionary.Add(i, ((char)i).ToString());
        }

        int previousCode = compressedData[0].Value.ToString();

        decompressedData.Append(dictionary[previousCode]);

        for (int i = 1; i < compressedData.Count; i++)
        {
            int currentCode = compressedData[i];

            if (dictionary.ContainsKey(currentCode))
            {
                decompressedData.Append(dictionary[currentCode]);
                string newEntry = dictionary[previousCode] + dictionary[currentCode][0];
                dictionary.Add(currentCode, newEntry);
                previousCode = currentCode;
            }
            else
            {
                string newEntry = dictionary[previousCode] + dictionary[previousCode][0];
                decompressedData.Append(newEntry);
                dictionary.Add(currentCode, newEntry);
                previousCode = currentCode;
            }
        }

        return decompressedData.ToString();
    }
}

The following is an example of the use of the LZW compression algorithm:

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        string originalData = "AAAAABBBBCCCCCDDDDDEE";
        
        Console.WriteLine("原始数据： " + originalData);
        
        List<int> compressedData = LZWCompression.Compress(originalData);
        
        Console.WriteLine("压缩后的数据： " + string.Join(",", compressedData));

        string decompressedData = LZWCompression.Decompress(compressedData);

        Console.WriteLine("解压缩后的数据： " + decompressedData);

        Console.ReadLine();
    }
}

In the above code example, we use the LZWCompression class to compress and decompress data. The compression uses the Compress method, and the decompression uses the Decompressmethod.

Conclusion:
This article introduces how to implement the LZW compression algorithm in C# and gives specific code examples. The LZW compression algorithm is a commonly used and effective lossless compression algorithm that can help us reduce the size of data and improve data storage and transmission efficiency.

The above is the detailed content of How to implement the LZW compression algorithm in C#. For more information, please follow other related articles on the PHP Chinese website!