Comment implémenter l'algorithme de compression LZW en C#

Comment implémenter l'algorithme de compression LZW en C#

Introduction :
Avec la croissance continue des données, le stockage et la transmission des données sont devenus une tâche importante. L'algorithme de compression LZW (Lempel-Ziv-Welch) est un algorithme de compression sans perte couramment utilisé qui peut réduire efficacement la taille des données. Cet article explique comment implémenter l'algorithme de compression LZW en C# et donne des exemples de code spécifiques.

1. Principe de l'algorithme de compression LZW
   L'algorithme de compression LZW est un algorithme de compression de dictionnaire. Son principe de base est de mapper la séquence de caractères continue apparaissant dans le flux de données d'entrée dans un codage unique. Lors de la compression, la séquence de caractères est progressivement ajoutée au dictionnaire et l'encodage correspondant est généré ; lors de la décompression, la séquence de caractères correspondante dans le dictionnaire est trouvée par l'encodage et la sortie. Le cœur de l’algorithme consiste à mettre à jour en permanence le dictionnaire afin qu’il puisse correspondre au flux de données d’entrée.
2. Étapes de mise en œuvre de l'algorithme de compression LZW
   (1) Initialiser le dictionnaire : initialisez chaque caractère du flux de données d'entrée avec un encodage indépendant.
   (2) Lit le premier caractère du flux de données d'entrée comme caractère actuel.
   (3) Répétez les étapes suivantes jusqu'à la fin du flux de données :
   a. Lisez le caractère suivant et fusionnez le caractère actuel et le caractère suivant dans une nouvelle séquence de caractères.
   b. Si la séquence de caractères existe déjà dans le dictionnaire, mettez à jour le caractère actuel avec la nouvelle séquence de caractères et continuez à lire le caractère suivant.
   c. Si la séquence de caractères n'existe pas dans le dictionnaire, affichez le caractère actuel, ajoutez la nouvelle séquence de caractères au dictionnaire et mettez à jour le caractère actuel avec le caractère suivant.
   (4) Affichez les caractères actuels restants.
3. Exemple de code C#
   Ce qui suit est un exemple de code pour implémenter l'algorithme de compression LZW en 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();
    }
}

Ce qui suit est un exemple d'utilisation de l'algorithme de compression LZW :

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();
    }
}

Dans l'exemple de code ci-dessus, nous utilisons la méthode LZWCompression类进行了数据的压缩与解压缩，其中压缩使用了Compress方法，解压缩使用了Decompress.

Conclusion :
Cet article présente comment implémenter l'algorithme de compression LZW en C# et donne des exemples de code spécifiques. L'algorithme de compression LZW est un algorithme de compression sans perte couramment utilisé et efficace qui peut nous aider à réduire la taille des données et à améliorer l'efficacité du stockage et de la transmission des données.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!